Power Sets

This page is http://www.math.uic.edu/~lewis/las100/power.html

Main Questions:

  1. What is a cardinal number?
  2. What is the power set of a set?
  3. How many elements are there in the power set of a finite set?

Cardinal Numbers

We group all the sets which are equivalent to each other into an "equivalence class" called a cardinal number. Then we often label the cardinal numbers as usual numbers 0 (the equivalence class of all sets with 0 elements), 1, 2, 3 (the equivalence class of all sets with 3 elements), 4, ... . This works fine until we get into infinite sets. The countable sets are set to have a cardinality of "aleph-0", and them things get more complicated.

Bigger Sets (or Bigger Cardinal Numbers)

Among infinite sets there are counatable sets and sets which are not countable. Not surprisingly, there is no "biggest" cardinal number, i.e., given any set (or cardinal number), there is a way to construct a biiger set or bigger cardinal number. The method is to construct the power set of a set -- the set of all subsets of a set X. The power set is often denopted by 2^X or 2X. (We allow the empty subset of X (the subset with 0 elements).

Examples

The set X = {1,2}.
The subsets are
empty, {1}, {2}, {1,2}
so that 2X has cardinality 4 = 22.
The set X = {1,2,3}.
The subsets are
empty, {1}, {2}, {3}, {1,2}, {2,3}, {3,1}, {1,2,3}
so that 2X has cardinality 8 = 23.
The set X = {1,2,3, 4}.
The subsets are
empty, {1}, {2}, {3}, {4}, {1,2}, {2,3}, {3,4} {4,1}, {1,2,3}, {2,3,4}, ...
(find all subsets!) so that 2X has cardinality 16 = 24.
The set X = {1,2,3,..N}.
The subsets are
empty, {1}, {2}, {3}, ...{N}, {1,2}, {2,3}, {3,4} ... {N-1,N}, {1,2,3}, {2,3,4}, ...
(This gets complicated) and one can show that 2X has cardinality 2N.

The result we can show is: Theorem: The set X is not equivalent to 2X.

This is another example of proof by contradiction.

Suppose the statement is false. Then X is equivalent to 2X. Thus there is a bijection

f: X <---> 2X
which is one to one and onto.

Now define A = { x in X such that x is not in f(X)}. By our assumption, we know there is a unique b in X such that f(b) = A.

Let's look at this fixed element b. If b is in A, then b is not in f(b) = A!. On the other hand, if b is not in A = f(b), then b is in A!. The element must be in A and not be in A. This is a contradiction, since each element of X is either in or out of A, but not both.

Thus we have reached a contradiction and must conclude that there is no equivalence function f: X <---> 2X.

Back to Prof. Lewis's LAS 100 home page