Cantor's diagonal argument: Difference between revisions

Revision as of 18:48, 3 April 2025

Revision as of 02:16, 12 April 2025

Line 32:

| ...

|}

Next, a sequence ''s'' is constructed by choosing the 1st digit as [[Ones' complement|complementary]] to the 1st digit of ''s''_''1'' (swapping '''0'''s for '''1'''s and vice versa), the 2nd digit as complementary to the 2nd digit of ''s''_''2'', the 3rd digit as complementary to the 3rd digit of ''s''_''3'', and generally for every ''n'', the ''n''^-th digit as complementary to the ''n''^-th digit of ''s''_''n''. For the example above, this yields

:{|

|-

Line 55:

| ''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''_''n'', since their ''n''^-th digits differ (highlighted in the example).

Hence, ''s'' cannot occur in the enumeration.

Line 67:

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..._''b''. This leads to the family of functions: {{nowrap|''f''_''b''{{space|hair}}(''t'') {{=}} 0.''t''_''b''}}. The functions {{nowrap|''f''{{space|hair}}_''b''(''t'')}} are injections, except for {{nowrap|''f''{{space|hair}}₂(''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 "''φ_ν'' denote any sequence of rationals in [0,&nbsp;1]." Cantor lets ''φ_ν'' 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>

Line 90 ⟶ 89:

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]]. ThatThis 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 \not\innotin 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''); cf.see picture.

:<math>T = \{ s \in S : s \not\in 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''); cf. picture.

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