# Thread: equivalence class help :(

1. ## 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?

2. First you need to establish what a relation on a set $\displaystyle S$ is.

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

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

An equivalence relation is a relation which is:

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

b) Symmetric: $\displaystyle 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: $\displaystyle x R y, y R z \implies x R z$.

Examples:

$\displaystyle =$ is an equivalence relation trivially.

$\displaystyle <$ is not an equivalence because $\displaystyle a < a$ is always false and $\displaystyle a < b$ means it is not the case that $\displaystyle 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.

3. 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?
$\displaystyle [\emptyset] ,[\{1\}],[\{1,2\}],[\{1,2,3\}],[\{1,2,3,4\}],[\{1,2,3,4,5\}],[\{1,2,3,4,5,6\}]$