Editing Cantor's diagonal argument (section)

=== 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'''.
|}