Cantor's diagonal argument: Difference between revisions
imported>Nick Johnson m (added a missing right parenthesis) |
mNo edit summary |
||
| (8 intermediate revisions by 5 users not shown) | |||
| Line 1: | Line 1: | ||
{{subpages}} | |||
'''Cantor's diagonal argument''' provides a convenient proof that the set <math>2^{\mathbb{N}}</math> of subsets of the [[natural number]]s (also known as its [[power set]]) is not [[countable set|countable]]. More generally, it is a recurring theme in [[computability]] theory, where perhaps its most well known application is the negative solution to the [[halting problem]]. | '''Cantor's diagonal argument''' provides a convenient proof that the set <math>2^{\mathbb{N}}</math> of subsets of the [[natural number]]s (also known as its [[power set]]) is not [[countable set|countable]]. More generally, it is a recurring theme in [[computability]] theory, where perhaps its most well known application is the negative solution to the [[halting problem]]. | ||
| Line 6: | Line 7: | ||
:1, '''1''', 1, 1, 0, ... | :1, '''1''', 1, 1, 0, ... | ||
:1, 0, '''1''', 0, 0, ... | :1, 0, '''1''', 0, 0, ... | ||
Now, we construct a sequence ''s=(s<sub>1</sub>,s<sub>2</sub>,s<sub>3</sub>,....) | Now, we construct a sequence ''s'' = (''s''<sub>1</sub>, ''s''<sub>2</sub>, ''s''<sub>3</sub>, ....), which is ''not'' on the list while still, <math>s_i\in\{0,1\}</math> for all ''i''. This is done as follows. Take <math>s_1</math> to be ''different'' from the first digit of the first member on the list. In our example the digit is 0 (in boldface) and so <math>s_1</math> is defined to be 1. Take <math>s_2</math> to be ''different'' from the second digit of the second member on the list (in our example <math>s_2=0</math>). Generally, define <math>s_n</math> as different from the n-th digit of the n-th entry on the list. In other words, the sequence ''s'' = (''s''<sub>1</sub>, ''s''<sub>2</sub>, ''s''<sub>3</sub>, ....) contains "the complement in <math>\{0,1\}</math>" of the diagonal of our table. It follows that the sequence ''s'' itself is not on the list, since it is different from every member by the definition. The list was supposed to contain ''all'' the 0-1 sequences. The contradiction shows that such sequences can not be enumerated (or they are not countable). | ||
The role of the diagonal clearly explains the name of the argument. | The role of the diagonal clearly explains the name of the argument. | ||
==Formal argument== | ==Formal argument== | ||
To prove that the family of all subsets of <math>\mathbb{N}</math> is not countable, we associate to any set <math>S \subset \mathbb{N}</math> | To prove that the family of all subsets of <math>\mathbb{N}</math> is not countable, we associate to any set <math>S \subset \mathbb{N}</math> its [[characteristic function]] <math>\phi : \mathbb{N} \rightarrow \{0, 1\}</math> by setting <math>\phi(n) = 1</math> if <math>n \in S</math> and <math>\phi(n) = 0</math>, otherwise. Conversely, every such function defines a subset. Observe also that every such function corresponds to a 0-1 sequence and vice-versa. | ||
If power set is countable, there is a bijective map <math>F : \mathbb{N} \rightarrow 2^{\mathbb{N}}</math>, that allows us to assign an index <math>i = F^{-1} (S)</math> to every subset S. In other words, all the functions <math> \phi: \mathbb{N} \rightarrow \{0, 1\}</math> can be enumerated as <math>\{\phi_1, \phi_2, \phi_3, \ldots \}</math>. Assuming this has been done, we proceed to construct a function <math>\psi : \mathbb{N} \rightarrow \{ 0, 1\}</math> that is not in this list. Consequently, the corresponding set, <math>T</math> cannot be in the range of <math>F</math>. | If power set is countable, there is a bijective map <math>F : \mathbb{N} \rightarrow 2^{\mathbb{N}}</math>, that allows us to assign an index <math>i = F^{-1} (S)</math> to every subset S. In other words, all the functions <math> \phi: \mathbb{N} \rightarrow \{0, 1\}</math> can be enumerated as <math>\{\phi_1, \phi_2, \phi_3, \ldots \}</math>. Assuming this has been done, we proceed to construct a function <math>\psi : \mathbb{N} \rightarrow \{ 0, 1\}</math> that is not in this list. Consequently, the corresponding set, <math>T</math> cannot be in the range of <math>F</math>. | ||
| Line 19: | Line 20: | ||
It follows that <math>\psi \not= \phi_i </math> for any <math>i</math>, and it must therefore correspond to a set not in the range of <math>F</math>. This contradiction shows that <math>2^{\mathbb{N}}</math> cannot be countable. | It follows that <math>\psi \not= \phi_i </math> for any <math>i</math>, and it must therefore correspond to a set not in the range of <math>F</math>. This contradiction shows that <math>2^{\mathbb{N}}</math> cannot be countable. | ||
[[ | ==Application to general sets== | ||
[[Category: | More generally, the argument shows that a [[set]] cannot be put into [[one-to-one correspondence]] with its [[power set]]: equivalently, the [[cardinality]] of a set is strictly less than that of its power set. The argument proceeds by showing that there cannot be a [[surjection]] from a set ''X'' to the set ''PX'' of subsets of ''X''. Suppose if possible that there were such a surjection ''f''. Form the set | ||
:<math> C = \{ x \in X : x \not\in f(x) \} . \, </math> | |||
Since ''C'' is a subset of ''X'' then from the assumption that ''f'' is surjective there is an element ''c'' of ''X'' such that ''f''(''c'') = ''C''. We now ask whether ''c'' is in ''C''. We find that | |||
:<math> c \in C \Leftrightarrow c \in \{ x \in X : x \not\in f(x) \} \Leftrightarrow c \not\in f(c) \Leftrightarrow c \not\in C , \,</math> | |||
which is a contradiction. Hence the supposition that ''f'' is a surjection is untenable. In particular, then, ''f'' cannot be a [[bijection]].[[Category:Suggestion Bot Tag]] | |||
Latest revision as of 16:00, 24 July 2024
Cantor's diagonal argument provides a convenient proof that the set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{\mathbb{N}}} of subsets of the natural numbers (also known as its power set) is not countable. More generally, it is a recurring theme in computability theory, where perhaps its most well known application is the negative solution to the halting problem.
Informal description
The original Cantor's idea was to show that the family of 0-1 infinite sequences is not countable. This is done by contradiction. If this family is countable then its members can be enumerated or enlisted. Such a list gives a table of digits, like in the following arbitrarily chosen example:
- 0, 1, 0, 1, 0, ...
- 1, 1, 1, 1, 0, ...
- 1, 0, 1, 0, 0, ...
Now, we construct a sequence s = (s1, s2, s3, ....), which is not on the list while still, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_i\in\{0,1\}} for all i. This is done as follows. Take Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_1} to be different from the first digit of the first member on the list. In our example the digit is 0 (in boldface) and so Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_1} is defined to be 1. Take Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_2} to be different from the second digit of the second member on the list (in our example Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_2=0} ). Generally, define Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_n} as different from the n-th digit of the n-th entry on the list. In other words, the sequence s = (s1, s2, s3, ....) contains "the complement in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{0,1\}} " of the diagonal of our table. It follows that the sequence s itself is not on the list, since it is different from every member by the definition. The list was supposed to contain all the 0-1 sequences. The contradiction shows that such sequences can not be enumerated (or they are not countable).
The role of the diagonal clearly explains the name of the argument.
Formal argument
To prove that the family of all subsets of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{N}} is not countable, we associate to any set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S \subset \mathbb{N}} its characteristic function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi : \mathbb{N} \rightarrow \{0, 1\}} by setting Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi(n) = 1} if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \in S} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi(n) = 0} , otherwise. Conversely, every such function defines a subset. Observe also that every such function corresponds to a 0-1 sequence and vice-versa.
If power set is countable, there is a bijective map Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F : \mathbb{N} \rightarrow 2^{\mathbb{N}}} , that allows us to assign an index Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i = F^{-1} (S)} to every subset S. In other words, all the functions Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi: \mathbb{N} \rightarrow \{0, 1\}} can be enumerated as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{\phi_1, \phi_2, \phi_3, \ldots \}} . Assuming this has been done, we proceed to construct a function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \psi : \mathbb{N} \rightarrow \{ 0, 1\}} that is not in this list. Consequently, the corresponding set, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} cannot be in the range of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} .
For each Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} , either Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_i(i) = 0} or Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi_i(i) = 1} , and so we define Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \psi(i)=1-\phi_i(i)} . Clearly, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \psi(i)\in \{0,1\}} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \psi(i) \not= \phi_i(i)} .
It follows that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \psi \not= \phi_i } for any Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} , and it must therefore correspond to a set not in the range of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} . This contradiction shows that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{\mathbb{N}}} cannot be countable.
Application to general sets
More generally, the argument shows that a set cannot be put into one-to-one correspondence with its power set: equivalently, the cardinality of a set is strictly less than that of its power set. The argument proceeds by showing that there cannot be a surjection from a set X to the set PX of subsets of X. Suppose if possible that there were such a surjection f. Form the set
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C = \{ x \in X : x \not\in f(x) \} . \, }
Since C is a subset of X then from the assumption that f is surjective there is an element c of X such that f(c) = C. We now ask whether c is in C. We find that
- Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c \in C \Leftrightarrow c \in \{ x \in X : x \not\in f(x) \} \Leftrightarrow c \not\in f(c) \Leftrightarrow c \not\in C , \,}
which is a contradiction. Hence the supposition that f is a surjection is untenable. In particular, then, f cannot be a bijection.