A set or class is "larger" than another set or class if the first set is of "higher power" than the second set, that is, if there exists a one-to-one correspondence between the entire second set and a subset of the first, but no such correspondence between the entire first set and a subset of the second.

What follows is a representation of Georg Cantor's proof, as filtered through the axiom system of Paul Bernays. Please notice that the entire proof derives from more mundane axioms of set theory without requiring more controversial ones like the Axiom of Choice.

If you don't understand the notation follow this link.

Given a set a, consider a one-to-one correspondence F between a and a class C of subsets of a. We must prove there is a subset of a which cannot belong to C, meaning there is no possible one-to-one correspondence (or even a merely surjective mapping) between a and the class of all subsets of a (which we'll call Π(a)).

This subset, call it t, is a ∩ {x|x ∉ F(x)}.

  • t ⊆ a. The intersection of a with anything is always a subset of a.
  • By our definition of t, c ∈ t <-> c ∈ a & c ∉ F(c)
  • which means (c ∈ a & t = F(c)) -> (c ∈ t <-> c ∉ t)
  • so, c ∈ t -> t != F(c) This is what we wanted to prove. t is not in C = Δ2F because it cannot be the image in F for any subset of a!

Because of you can never have a one-to-one correspondence between a and Π(a), you can always construct a class of subsets of a which has higher power than a.

When you accept the potency axiom, the class Π(a) is represented by the set π(a), and so you must conclude that there exist sets (such as π(a)) which are of higher power than a.

The famous diagonal argument of Cantor demonstrates a special (perhaps "clearer"?) case of the proof, one which specifically denies the existence of a one-to-one corespondence between the integers and the reals. t is the generalization of the number created by taking a "diagonal" through the digit representations of the real numbers in the attempted one-to-one correspondence.

Another rendition of Georg Cantor's proof with more modern notations.

Theorem

For any set A, the power set P(A) is larger than A. This holds since there exists an obvious injection from A to P(A), and not so obvious, there does not exist a surjection from A to P(A).

Proof by contradiction

Suppose there exists surjective f: A → P(A).
Let B = {a ∈ A : a !∈ f(a)}. ("!∈" meaning "not in," for browsers that don't support ∉)
Since B ∈ P(A) and f surjective, ∃ b ∈ A : f(b) = B.
But b exists neither in B nor not in B! Contradiction. ∴ Surjective f cannot exist.

Russell was one of the people who asked about the case where A contained everything. This line of thought lead to the celebrated Russell's Paradox. To resolve this paradox, modern axiomatic set theory was developed. (see: ZF, Axiom of Choice)

Log in or registerto write something here or to contact authors.