Cantor's diagonal argument: Difference between revisions

Revision as of 22:56, 28 May 2024

Revision as of 12:56, 25 July 2024

Line 101:

With equality defined as the existence of a bijection between their underlying sets, Cantor also defines binary predicate of cardinalities <math>|S|</math> and <math>|T|</math> in terms of the [[Cardinality#Comparing_sets|existence of injections]] between <math>S</math> and <math>T</math>. It has the properties of a [[preorder]] and is here written "<math>\le</math>". One can embed the naturals into the binary sequences, thus proving various ''injection existence'' statements explicitly, so that in this sense <math>|{\mathbb N}|\le|2^{\mathbb N}|</math>, where <math>2^{\mathbb N}</math> denotes the function space <math>{\mathbb N}\to\{0,1\}</math>. But following from the argument in the previous sections, there is ''no surjection'' and so also no bijection, i.e. the set is uncountable. For this one may write <math>|{\mathbb N}|<|2^{\mathbb N}|</math>, where "<math><</math>" is understood to mean the existence of an injection together with the proven absence of a bijection (as opposed to alternatives such as the negation of Cantor's preorder, or a definition in terms of [[Von Neumann cardinal assignment|assigned]] [[ordinal numbers|ordinals]]). Also <math>|S|<|{\mathcal P}(S)|</math> in this sense, as has been shown, and at the same time it is the case that <math>\neg(|{\mathcal P}(S)|\le|S|)</math>, for all sets <math>S</math>.

Assuming the [[law of excluded middle]], [[characteristic functions]] surject onto powersets, and then <math>|2^S|=|{\mathcal P}(S)|</math>. So the uncountable <math>2^{\mathbb N}</math> is also not enumerable and it can also be mapped onto <math>{\mathbb N}</math>. [[classical mathematics|Classically]], the [[Schröder–Bernstein theorem]] is valid and says that any two sets which are in the injective image of one another are in bijection as well. Here, every unbounded subset of <math>{\mathbb N}</math> is then in bijection with <math>{\mathbb N}</math> itself, and every [[subcountable]] set (a property in terms of surjections) is then already countable, i.e. in the surjective image of <math>{\mathbb N}</math>. In this context the possibilities are then exhausted, making "<math>\le</math>" a [[partial order|non-strict partial order]], or even a [[total order]] when assuming [[axiom of choice|choice]]. The diagonal argument thus establishes that, although both sets under consideration are infinite, there are actually ''more'' infinite sequences of ones and zeros than there are natural numbers.

Cantor's result then also implies that the notion of the [[set of all sets]] is inconsistent: If <math>S</math> were the set of all sets, then <math>{\mathcal P}(S)</math> would at the same time be bigger than <math>S</math> and a subset of <math>S</math>.