# Thread: Equivalence relation

1. ## Equivalence relation

Let S be a finite set and denote by 2^S = {A|A ⊆ S} the set of all subsets of S. Define
a relation ∼ on 2^S by A ∼ B if and only if A and B have the same number of elements.
(a) Show that ∼ is an equivalence relation on 2^S.
(b) Let S = {1, 2, 3, 4}. List the (sixteen) elements of 2^S and explicitly list the
elements in each equivalence class determined by ∼.

I understand how to do (a), but not b.
For (b), I have 2^1=2,2^2=4,2^3=8,2^4=16
I have 2 elements of 2^S because 8 and 16 aren't in S.

2. By 2^S it's not meant to raise 2 to a power (although there's a reason that notation is used), but rather to take all possible subsets of S. Then you partition 2^S (the set of all subsets) into equivalence classes based on their cardinality. So the class of subsets with zero elements is {{}}, the class of one-element subsets is {{1},{2},{3},{4}}, and so forth.

How many subsets have four elements?

3. That makes a lot more sense now.
Only one subset has 4 elements, the subset being S itself.
If 2^S is not meant to raise 2 to a power why is this notation used?

4. Originally Posted by kathrynmath
If 2^S is not meant to raise 2 to a power why is this notation used?
If each of $\displaystyle A~\&~B$ is a set the notation $\displaystyle B^A$ is the set of all functions $\displaystyle f:A\to B$.
It is common to have $\displaystyle 2^A=\{f:A\to \{0,1\}\}$ which corresponds to all the subsets of $\displaystyle A$.