# equivalence class help :(

• Sep 24th 2009, 09:30 PM
glopez09
equivalence class help :(
i just can't comprehend what an equivalence class is. i can't even get started on this problem. maybe someone can help me atleast get started?

here's the problem

let A = {1,2,3,4,5,6} and S = power set of A

a) for a,b is an element of S, define a~b if a and b have the same number of elements. prove that ~ defines an equivalence relation on S.

b)how many equivalence class are there? list one element from each equivalence class.

i understand what an equivalence relation is. my professor gave me some hints but i can't draw anything from them.

{1,2} ~ {2,3}
{1,2,3} ~ {4,5,6}

i understand that part, but then how would i do part b?
• Sep 24th 2009, 10:43 PM
Matt Westwood
First you need to establish what a relation on a set $S$ is.

Given the set of all ordered pairs taken from $S \times S$, a relation is any subset $R$ of this set.

If $(x, y) \in R$ we can write $x R y$ and say "x is related to y by R".

An equivalence relation is a relation which is:

a) Reflexive: $\forall a \in S: (a, a) \in R$. All elements are related to themselves.

b) Symmetric: $x R y \implies y R x$. If one element is related by R to another one, then the other one is likewise related to the first.

c) Transitive: $x R y, y R z \implies x R z$.

Examples:

$=$ is an equivalence relation trivially.

$<$ is not an equivalence because $a < a$ is always false and $a < b$ means it is not the case that $b < a$.

Recommend you revise your work on relations, then you should be able to get a better handle on how an equivalence relation works.
• Sep 25th 2009, 07:24 AM
Plato
Quote:

Originally Posted by glopez09
let a = {1,2,3,4,5,6} and s = power set of a

a) for a,b is an element of s, define a~b if a and b have the same number of elements. Prove that ~ defines an equivalence relation on s.

B)how many equivalence class are there? List one element from each equivalence class.
But then how would i do part b?

$[\emptyset] ,[\{1\}],[\{1,2\}],[\{1,2,3\}],[\{1,2,3,4\}],[\{1,2,3,4,5\}],[\{1,2,3,4,5,6\}]$