Editing Cantor's diagonal argument (section)

== Uncountable set ==
Cantor considered the set ''T'' of all infinite [[sequences]] of [[binary digits]] (i.e. each digit is zero or one).<ref group=note>Cantor used "''m'' and "''w''" instead of "0" and "1", "''M''" instead of "''T''", and "''E''<sub>''i''</sub>" instead of "''s''<sub>''i''</sub>".</ref>
He begins with a [[constructive proof]] of the following [[Lemma (mathematics)|lemma]]:
:If ''s''<sub>1</sub>, ''s''<sub>2</sub>, ... , ''s''<sub>''n''</sub>, ... is any enumeration of elements from ''T'',<ref group=note>Cantor does not assume that every element of ''T'' is in this enumeration.</ref> then an element ''s'' of ''T'' can be constructed that doesn't correspond to any ''s''<sub>''n''</sub> in the enumeration.
The proof starts with an enumeration of elements from ''T'', for example
:{|
|-
| ''s''<sub>1</sub> = || (0, || 0, || 0, || 0, || 0, || 0, || 0, || ...)
|-
| ''s''<sub>2</sub> = || (1, || 1, || 1, || 1, || 1, || 1, || 1, || ...)
|-
| ''s''<sub>3</sub> = || (0, || 1, || 0, || 1, || 0, || 1, || 0, || ...)
|-
| ''s''<sub>4</sub> = || (1, || 0, || 1, || 0, || 1, || 0, || 1, || ...)
|-
| ''s''<sub>5</sub> = || (1, || 1, || 0, || 1, || 0, || 1, || 1, || ...)
|-
| ''s''<sub>6</sub> = || (0, || 0, || 1, || 1, || 0, || 1, || 1, || ...)
|-
| ''s''<sub>7</sub> = || (1, || 0, || 0, || 0, || 1, || 0, || 0, || ...)
|-
| ...
|}
Next, a sequence ''s'' is constructed by choosing the 1st digit as [[Ones' complement|complementary]] to the 1st digit of ''s''<sub>''1''</sub> (swapping '''0'''s for '''1'''s and vice versa), the 2nd digit as complementary to the 2nd digit of ''s''<sub>''2''</sub>, the 3rd digit as complementary to the 3rd digit of ''s''<sub>''3''</sub>, and generally for every ''n'', the ''n''-th digit as complementary to the ''n''-th digit of ''s''<sub>''n''</sub>. For the example above, this yields
:{|
|-
| ''s''<sub>1</sub> || = || (<u>'''0'''</u>, || 0, || 0, || 0, || 0, || 0, || 0, || ...)
|-
| ''s''<sub>2</sub> || = || (1, || <u>'''1'''</u>, || 1, || 1, || 1, || 1, || 1, || ...)
|-
| ''s''<sub>3</sub> || = || (0, || 1, || <u>'''0'''</u>, || 1, || 0, || 1, || 0, || ...)
|-
| ''s''<sub>4</sub> || = || (1, || 0, || 1, || <u>'''0'''</u>, || 1, || 0, || 1, || ...)
|-
| ''s''<sub>5</sub> || = || (1, || 1, || 0, || 1, || <u>'''0'''</u>, || 1, || 1, || ...)
|-
| ''s''<sub>6</sub> || = || (0, || 0, || 1, || 1, || 0, || <u>'''1'''</u>, || 1, || ...)
|-
| ''s''<sub>7</sub> || = || (1, || 0, || 0, || 0, || 1, || 0, || <u>'''0'''</u>, || ...)
|-
| ...
|-
|
|-
| ''s'' || = || (<u>'''1'''</u>, || <u>'''0'''</u>, || <u>'''1'''</u>, || <u>'''1'''</u>, || <u>'''1'''</u>, || <u>'''0'''</u>, || <u>'''1'''</u>, || ...)
|}
By construction, ''s'' is a member of ''T'' that differs from each ''s''<sub>''n''</sub>, since their ''n''-th digits differ (highlighted in the example).
Hence, ''s'' cannot occur in the enumeration.

Based on this lemma, Cantor then uses a [[proof by contradiction]] to show that:
:The set ''T'' is uncountable.
The proof starts by assuming that ''T'' is [[countable set#Definition|countable]].
Then all its elements can be written in an enumeration ''s''<sub>1</sub>, ''s''<sub>2</sub>, ... , ''s''<sub>''n''</sub>, ... .
Applying the previous lemma to this enumeration produces a sequence ''s'' that is a member of ''T'', but is not in the enumeration. However, if ''T'' is enumerated, then every member of ''T'', including this ''s'', is in the enumeration. This contradiction implies that the original assumption is false. Therefore, ''T'' is uncountable.<ref name="Cantor.1891"/>

=== Real numbers ===
The uncountability of the [[real number]]s was already established by [[Cantor's first uncountability proof]], but it also follows from the above result. To prove this, an [[injective function|injection]] will be constructed from the set ''T'' of infinite binary strings to the set '''R''' of real numbers. Since ''T'' is uncountable, the [[Image (mathematics)|image]] of this function, which is a subset of '''R''', is uncountable. Therefore, '''R''' is uncountable. Also, by using a method of construction devised by Cantor, a [[bijection]] will be constructed between ''T'' and '''R'''. Therefore, ''T'' and '''R''' have the same cardinality, which is called the "[[cardinality of the continuum]]" and is usually denoted by <math>\mathfrak{c}</math> or <math>2^{\aleph_0}</math>.

An injection from ''T'' to '''R''' is given by mapping binary strings in ''T'' to [[decimal fractions]], such as mapping ''t''&nbsp;=&nbsp;0111... to the decimal 0.0111.... This function, defined by {{nowrap|''f''{{space|hair}}(''t'') {{=}} 0.''t''}}, is an injection because it maps different strings to different numbers.<ref group=note>While 0.0111... and 0.1000... would be equal if interpreted as binary fractions (destroying injectivity), they are different when interpreted as decimal fractions, as is done by ''f''. On the other hand, since ''t'' is a binary string, the equality 0.0999... = 0.1000... of decimal fractions is not relevant here.</ref>

Constructing a bijection between ''T'' and '''R''' is slightly more complicated.
Instead of mapping 0111... to the decimal 0.0111..., it can be mapped to the [[radix|base]]-''b'' number: 0.0111...<sub>''b''</sub>. This leads to the family of functions: {{nowrap|''f''<sub>''b''</sub>{{space|hair}}(''t'') {{=}} 0.''t''<sub>''b''</sub>}}. The functions {{nowrap|''f''{{space|hair}}<sub>''b''</sub>(''t'')}} are injections, except for {{nowrap|''f''{{space|hair}}<sub>2</sub>(''t'')}}. This function will be modified to produce a bijection between ''T'' and '''R'''.

{| class="wikitable collapsible collapsed"
! Construction of a bijection between ''T'' and '''R'''
|- style="text-align: left; vertical-align: top"
| {{multiple image|total_width=200|image1=Linear transformation svg.svg|width1=106|height1=159|caption1=The function ''h'': (0,1) → (−π/2, π/2)|image2=Tangent one period.svg|width2=338|height2=580|caption2=The function tan: (−π/2, π/2) → '''R'''}}
This construction uses a method devised by Cantor that was published in 1878. He used it to construct a bijection between the [[closed interval]] [0, 1] and the [[irrational number|irrational]]s in the [[open interval]] (0,&nbsp;1). He first removed a [[countably infinite]] subset from each of these sets so that there is a bijection between the remaining uncountable sets. Since there is a bijection between the countably infinite subsets that have been removed, combining the two bijections produces a bijection between the original sets.<ref>See page 254 of {{Citation|author=Georg Cantor|title=Ein Beitrag zur Mannigfaltigkeitslehre|url=http://www.digizeitschriften.de/dms/img/?PID=GDZPPN002156806|volume=84|pages=242&ndash;258|journal=Journal für die Reine und Angewandte Mathematik|year=1878}}. This proof is discussed in {{Citation|author=Joseph Dauben|title=Georg Cantor: His Mathematics and Philosophy of the Infinite|publisher=Harvard University Press|year=1979|isbn=0-674-34871-0}}, pp. 61&ndash;62, 65. On page 65, Dauben proves a result that is stronger than Cantor's. He lets "''φ<sub>ν</sub>'' denote any sequence of rationals in [0,&nbsp;1]." Cantor lets ''φ<sub>ν</sub>'' denote a sequence [[Enumeration|enumerating]] the rationals in [0,&nbsp;1], which is the kind of sequence needed for his construction of a bijection between [0,&nbsp;1] and the irrationals in (0,&nbsp;1).</ref>

Cantor's method can be used to modify the function {{nowrap|''f''{{space|hair}}<sub>2</sub>(''t'') {{=}} 0.''t''<sub>2</sub>}} to produce a bijection from ''T'' to (0,&nbsp;1). Because some numbers have two binary expansions, {{nowrap|''f''{{space|hair}}<sub>2</sub>(''t'')}} is not even [[injective function|injective]]. For example, {{nowrap|''f''{{space|hair}}<sub>2</sub>(1000...) {{=}}}} 0.1000...<sub>2</sub>&nbsp;= 1/2 and {{nowrap|''f''{{space|hair}}<sub>2</sub>(0111...) {{=}}}} 0.0111...<sub>2</sub>&nbsp;= {{nowrap|[[Infinite series|1/4 + 1/8 + 1/16 + ...]] {{=}}}} 1/2, so both 1000... and 0111... map to the same number, 1/2.

To modify {{nowrap|''f''<sub>2</sub>{{space|hair}}(''t'')}}, observe that it is a bijection except for a countably infinite subset of (0,&nbsp;1) and a countably infinite subset of ''T''. It is not a bijection for the numbers in (0,&nbsp;1) that have two [[binary expansion]]s. These are called [[dyadic rational|dyadic]] numbers and have the form {{nowrap|''m''{{space|hair}}/{{space|hair}}2<sup>''n''</sup>}} where ''m'' is an odd integer and ''n'' is a natural number. Put these numbers in the sequence: ''r''&nbsp;= (1/2, 1/4, 3/4, 1/8, 3/8, 5/8, 7/8,&nbsp;...). Also, {{nowrap|''f''<sub>2</sub>{{space|hair}}(''t'')}} is not a bijection to (0,&nbsp;1) for the strings in ''T'' appearing after the [[binary point]] in the binary expansions of 0, 1, and the numbers in sequence ''r''. Put these eventually-constant strings in the sequence: ''s''&nbsp;= ({{color|#808080|000}}..., {{color|#808080|111}}..., 1{{color|#808080|000}}..., 0{{color|#808080|111}}..., 01{{color|#808080|000}}..., 00{{color|#808080|111}}..., 11{{color|#808080|000}}..., 10{{color|#808080|111}}...,&nbsp;...). Define the bijection ''g''(''t'') from ''T'' to (0,&nbsp;1): If ''t'' is the ''n''<sup>th</sup> string in sequence ''s'', let ''g''(''t'') be the ''n''<sup>th</sup> number in sequence ''r''{{space|hair}}; otherwise, ''g''(''t'')&nbsp;=&nbsp;0.''t''<sub>2</sub>.

To construct a bijection from ''T'' to '''R''', start with the [[trigonometric functions|tangent function]] tan(''x''), which is a bijection from (−π/2,&nbsp;π/2) to '''R''' (see the figure shown on the right). Next observe that the [[linear function]] ''h''(''x'')&nbsp;= {{nowrap|π''x'' – π/2}} is a bijection from (0,&nbsp;1) to (−π/2,&nbsp;π/2) (see the figure shown on the left). The [[function composition|composite function]] tan(''h''(''x''))&nbsp;= {{nowrap|tan(π''x'' – π/2)}} is a bijection from (0,&nbsp;1) to '''R'''. Composing this function with ''g''(''t'') produces the function tan(''h''(''g''(''t'')))&nbsp;= {{nowrap|tan(π''g''(''t'') – π/2)}}, which is a bijection from ''T'' to '''R'''.
|}

===General sets===
[[File:Diagonal argument powerset svg.svg|thumb|250px|Illustration of the generalized diagonal argument: The set <math>T = \{n \in \mathbb{N}: n \not\in f(n)\}</math> at the bottom cannot occur anywhere in the [[Range of a function|range]] of <math>f:\mathbb{N}\to\mathcal{P}(\mathbb{N})</math>. The example mapping ''f'' happens to correspond to the example enumeration ''s'' in the picture [[#Lead|above]].]]
A generalized form of the diagonal argument was used by Cantor to prove [[Cantor's theorem]]: for every [[Set (mathematics)|set]] ''S'', the [[power set]] of ''S''—that is, the set of all [[subset]]s of ''S'' (here written as '''''P'''''(''S''))—cannot be in [[bijection]] with ''S'' itself. This proof proceeds as follows:

Let ''f'' be any [[Function (mathematics)|function]] from ''S'' to '''''P'''''(''S''). It suffices to prove that ''f'' cannot be [[surjective]]. This means that some member ''T'' of '''''P'''''(''S''), i.e. some subset of ''S'', is not in the [[Image (mathematics)|image]] of ''f''. As a candidate consider the set
: <math>T = \{ s \in S : s \notin f(s) \}.</math>

For every ''s'' in ''S'', either ''s'' is in ''T'' or not. If ''s'' is in ''T'', then by definition of ''T'', ''s'' is not in ''f''(''s''), so ''T'' is not equal to ''f''(''s''). On the other hand, if ''s'' is not in ''T'', then by definition of ''T'', ''s'' is in ''f''(''s''), so again ''T'' is not equal to ''f''(''s''); see picture.

For a more complete account of this proof, see [[Cantor's theorem]].