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.