Cantor's diagonal argument

:Note: in order to fully understand this article you may want to refer to the set theory portion of the table of mathematical symbols.

General sets

A generalized form of the diagonal argument was used by Cantor to prove Cantor's theorem: for every set S the power set of S, i.e., the set of all subsets of S (here written as P(S)), is larger than S itself. This proof proceeds as follows:

Related Topics:
Cantor's theorem - Set - Power set - Subset

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Let f be any one-to-one function from S to P(S). It suffices to prove f cannot be surjective. That means that some member of P(S), i.e., some subset of S, is not in the image of f. That set is

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:T={,sin S: s otin f(s),}.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

If T is in the range of f, then for some t in S we have T = f(t). Either t is in T or not.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

If t is in T, then t is in f(t), but, by definition of T, that implies t is not in T. On the other hand, if t is not in T, then t is not in f(t), and by definition of T, that implies t is in T. Either way, we have a contradiction.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Note the similarity between the construction of T and the set in Russell's paradox. Its result can be used to show that the notion of the set of all sets is an inconsistent notion in normal set theory; if S would be the set of all sets then P(S) would at the same time be bigger than S and a subset of S.

Related Topics:
Russell's paradox - Set of all sets - Set theory

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The above proof fails for W. V. Quine's "New Foundations" set theory, which has a different version of the axiom of separation in which {,sin S: s otin f(s),} cannot be expressed.

Related Topics:
W. V. Quine - Axiom of separation

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

For a more concrete account of this proof that is possibly easier to understand see Cantor's theorem.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Analogues of the diagonal argument are widely used in mathematics to prove the existence or nonexistence of certain objects. For example, the conventional proof of the unsolvability of the halting problem is essentially a diagonal argument.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The diagonal argument shows that the set of real numbers is "bigger" than the set of integers. Therefore, we can ask if there is a set whose cardinality is "between" that of the integers and that of the reals. This question leads to the famous continuum hypothesis. Similarly, the question of whether there exists a set whose cardinality is between s and P(s) for some s, leads to the generalized continuum hypothesis.

Related Topics:
Cardinality - Continuum hypothesis - Generalized continuum hypothesis

~ ~ ~ ~ ~ ~ ~ ~ ~ ~