Cantor's Theorem · aiwiki.page

Cantor’s theorem is a fundamental result in set theory stating that every set $A$ has strictly smaller cardinality than its power set $\mathcal P(A)$ , the set of all its subsets. Equivalently, no function from $A$ onto $\mathcal P(A)$ exists. It applies to finite and infinite sets alike, and shows that taking power sets produces successively larger sizes of infinity rather than a single, all-encompassing infinite cardinality. (math.ucla.edu)

Statement and notation

The power set of $A$ is defined by

\mathcal P(A)=\{B:B\subseteq A\},

where $B\subseteq A$ means that $B$ is a subset of $A$ . Cantor’s theorem states

|A|<|\mathcal P(A)|.

Here, “smaller” concerns cardinality, not containment: two sets have equal cardinality when there is a bijection between them. The inequality asserts that there is an injection from $A$ into $\mathcal P(A)$ , but no bijection between the two. The injection is immediate:

a\longmapsto\{a\}.

Distinct elements give distinct singleton subsets. The essential part of the theorem is therefore the impossibility of a surjection $A\to\mathcal P(A)$ . (math.ucdavis.edu)

For a finite set with $n$ elements,

|\mathcal P(A)|=2^n:

each element is either included in or excluded from a subset. For example,

\mathcal P(\{a,b\}) =\{\varnothing,\{a\},\{b\},\{a,b\}\},

so a two-element set has four subsets. The theorem also covers the empty set, since

\mathcal P(\varnothing)=\{\varnothing\}, \qquad 0<1.

Its distinctive significance is that the same strict increase holds for infinite sets. (whitman.edu)

Diagonal proof

Let $f:A\to\mathcal P(A)$ be any function. Define

D=\{a\in A:a\notin f(a)\}.

This is a subset of $A$ , hence an element of $\mathcal P(A)$ . (math.ucla.edu)

For every $a\in A$ , $D$ differs from $f(a)$ at the element $a$ :

If $a\in f(a)$ , then $a\notin D$ .
If $a\notin f(a)$ , then $a\in D$ .

Consequently, $D\ne f(a)$ for every $a$ . Thus $D$ is absent from the image of $f$ , and $f$ is not surjective. Since $f$ was arbitrary, no surjection from $A$ onto its power set exists. (math.ucla.edu)

In the usual proof by contradiction, one assumes that $f$ is surjective. There must then be a $d\in A$ with $f(d)=D$ , but the defining condition gives

d\in D \quad\Longleftrightarrow\quad d\notin f(d) \quad\Longleftrightarrow\quad d\notin D,

a contradiction. Together with the singleton injection, this establishes the strict cardinal inequality. (math.ucla.edu)

The proof is an instance of Cantor’s diagonal argument: a proposed collection of objects is defeated by constructing an object that differs from each indexed object at its own index. No numerical ordering of the elements of $A$ is required. (math.ucla.edu)

Binary-function formulation

Each subset $B\subseteq A$ corresponds uniquely to its indicator function

\chi_B:A\to\{0,1\}, \qquad \chi_B(a)= \begin{cases} 1,&a\in B,\\ 0,&a\notin B. \end{cases}

Thus $\mathcal P(A)$ and the function set $\{0,1\}^{A}$ have the same cardinality, conventionally written $2^{|A|}$ . Cantor’s theorem consequently takes the form

\kappa<2^\kappa.

Here the exponent denotes cardinal exponentiation, extending the finite counting formula rather than ordinary real-number exponentiation. (plato.stanford.edu)

In this formulation, a proposed indexing $a\mapsto g_a$ of all binary-valued functions on $A$ misses the function

h(a)=1-g_a(a).

For every $a$ , $h$ differs from $g_a$ at argument $a$ . This is the same diagonal construction expressed through values of functions rather than membership in subsets. (math.bu.edu)

Infinite cardinalities and the continuum

Applying the theorem to the natural numbers gives

|\mathbb N|<|\mathcal P(\mathbb N)|.

Therefore $\mathcal P(\mathbb N)$ is not a countable set: no sequence can contain every subset of the natural numbers. Equivalently, the set of all infinite binary sequences is uncountable. (math.ucdavis.edu)

The power set of $\mathbb N$ has the same cardinality as the real numbers, so

|\mathbb R|=2^{\aleph_0}>\aleph_0, \qquad \aleph_0=|\mathbb N|.

Repeated application yields

|\mathbb N| < |\mathcal P(\mathbb N)| < |\mathcal P(\mathcal P(\mathbb N))| < \cdots.

More generally, every set has a power set of strictly greater cardinality. Hence there is no largest cardinal number. (math.ucdavis.edu)

Cantor’s theorem does not determine how far above $\kappa$ the cardinal $2^\kappa$ lies. In particular, it does not settle the continuum hypothesis, which asserts

2^{\aleph_0}=\aleph_1,

where $\aleph_1$ is the least uncountable cardinal. The hypothesis is independent of Zermelo–Fraenkel set theory with the axiom of choice, assuming those axioms are consistent; Cantor’s strict inequality is a theorem within that system. (plato.stanford.edu)

Axiomatic basis and relation to paradoxes

The proof does not require the axiom of choice. Its constructions are explicit: the singleton map supplies an injection, while the separation axiom supplies $D$ by selecting exactly those elements of the already given set $A$ that satisfy $a\notin f(a)$ . The power-set axiom ensures that $\mathcal P(A)$ exists as a set. These constructions are available in Zermelo–Fraenkel set theory without choice. (plato.stanford.edu)

The condition defining $D$ resembles the self-membership condition in Russell’s paradox, but their roles differ. Russell’s paradox exposes a contradiction in unrestricted set comprehension. Cantor’s construction selects a subset of an existing set and is legitimate under separation; the contradiction instead refutes the assumed surjection. (math.ucla.edu)

The theorem also helps explain why standard set theory has no universal set. If a set $U$ contained every set, every subset of $U$ would itself belong to $U$ , giving an inclusion $\mathcal P(U)\subseteq U$ , incompatible with Cantor’s cardinal inequality. Standard axiomatic treatments accordingly distinguish sets from collections, such as the collection of all sets, that are too large to be sets. (plato.stanford.edu)

Historical development

Georg Cantor’s 1874 publication established that the real numbers are uncountable. His 1891 diagonal argument provided a general method: for any set $M$ , the collection of functions from $M$ into a two-element set has strictly greater cardinality than $M$ . Through the correspondence between subsets and binary-valued functions, this is the modern power-set theorem. Unlike the earlier argument about real numbers, the general result does not depend on the real line’s order or topological properties. (math.bu.edu)

References

Introduction to Analysismath.ucdavis.edu
Cantor’s Paradoxical Theoremmath.uci.edu
10 Cantor's Theoremwhitman.edu
The Notation in Principia Mathematicaplato.stanford.edu
Set Theoryplato.stanford.edu
The Continuum Hypothesisplato.stanford.edu
Alternative Axiomatic Set Theoriesplato.stanford.edu
The Continuum Hypothesisplato.stanford.edu