Is ∼ an Equivalence Relation on the Power Set of a Finite Set?

[kathrynag]

Homework Statement

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 ∼.

Homework Equations

The Attempt at a Solution

I started by determining what an equivalence relation is:
i. (a,a) is in ~
ii. For all (a,b) in S, if (a,b) is in ~, then (b,a) is in ~
iii. For all a,b,c in S, if (a,b) is in ~ and (b,c) is in ~, then (a,c) is in ~.
I have trouble using the definitions.
I tried doing something like 2^{a}=2^{a}

 

[gerben]

Just follow the definitions, the relation defined was: "have the same number of elements"

So in order to check this: (a,a) is in ~
you just need to check: do 'a' and 'a' have the same number of elements

etc.(also, you meant: ii. For all a and b in 2^{S}, if (a,b) is in ~, then (b,a) is in ~... as the relation was defined on 2^{S}, not on S)

 

[kathrynag]

a and a have the same number of elements since a has the same number of elements as itself.
If a and b have the same number of elements, b and a have the same number of elements.
If a and b have the same number of elements and a and c have the same number of elements, then since a has the same number of element of b and c, b must have the same number of elements as c.

Ok for part b)
elements are 2, 4, 8, 16, but only 2, 4 are in S. I don't see how to get 16 elements.

 

[HallsofIvy]

No, for a set, S, the notation "2^S" means "the collection of all subsets of S". That notation is used because if set S contains n elements then it has 2^4 subsets. {1, 2, 3, 4} has 4 members so it has 2^4= 16 subsets.

The only subset that has 0 members is the empty set.

Their are 4 subsets that contain 1 member: {1}, {2}, {3}, {4}.

There are 6 subsets that contain 2 members, 4 that contain 3 members, and 1 that contains 4 members.

In general, if a set contains n members, there are the binomial coefficient,
\begin{pmatrix}n \\ m\end{pmatrix}
subsets that contain m members.