## 2.2. Uncountable Infinity

### Theorem 2.2.5: Cardinality of Power Sets

**P(S)**is always bigger than the cardinality of

**S**for an set

**S**.

### Proof:

The proof will be similar to proof about the uncountablility of the open interval (0,1): we will attempt to list all sets of**P(S)**next to all elements of

**S**, and then exhibit a set that can not be in that list. However, we will do this in a more abstract fashion this time.

Let us denote the elements of the set **S** by small letters
*a, b, c, ...,* and the elements of **P(S)** by capital letters
**A**, **B**, **C**, .... Note that each member of
**P(S)** is again a set in itself. Suppose there was a function *f*
between **S **and **P(S)**. That means, that we may have the
following correspondence:

*a*corresponds to**A**, i.e.**A**=*f(a)**b*corresponds to**B**, i.e.**B**=*f(b)**c*corresponds to**C**, i.e.**C**=*f(c)*

**X**as follows:

or, in other words:X= { sS: {s} f(s) = 0 }

ifHence,T=f(t), thentis inXif and only iftis not contained inT

**X**contains all those elements that are not contained in their associated sets under the above function

*f*. This is easy to understand by means of a concrete example:

Let **S** = {1, 2, 3}. Then
**P**(**S**) = { **0, **{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }.
An arbitrary function from **S** to **P**(**S**) might associate
the elements of **S** as follows:

- 1 is associated with {3}
- 2 is associated with {1,2,3}
- 3 is associated with {1,2}.

**X**defined above consist of the following elements:

- f(1) = {3}, and 1 is not in {3}. Thus, {1} is in
**X**. - f(2) = {1,2,3}, and 2 is in {1,2,3}. Thus, {2} is not in
**X**. - f(3) = {1, 2}, and 3 is not in {1,2}. Thus, {3} is in
**X**.

**X**= {1, 3}.

Incidentally, there is no element from **S** that is mapped to the
set **X**.

Now let us return to the proof. Since **X** consists of elements of **S**,
**X** is a subset of **S**, and hence **X** is an element of
**P**(**S**). If the above map *f* was an onto map, then there must
be an element *x* from S with *f(x) = ***X**. Where is that
element *x* ?:
Suppose *x* is contained in **X**:

SinceSupposeXcontains those elements that are not in its associated set, we have thatxis not contained inf(x) =X.

*x*is not contained in

**X**:

SinceThis is clearly not possible, showing that our assumption thatXcontains exactly those elements that are not in its associated set, andxis assumed to be not inX= f(x), thenxmust be contained inX.

*f*is onto is false. Hence, whatever map between

**S**and

**P**(

**S**) exists, it can not be onto. But from a previous example we already know that the cardinality of

**P**(

**S**) is at least as large as the cardinality of

**S**, i.e. there is a one-to-one map from

**S**to

**P**(

**S**). Since this map can not also be onto, we have proved that

*card(*.

**P**(**S**)) > card(**S**)