Cantor's diagonal argument: Difference between revisions

Revision as of 12:47, 22 April 2023

Revision as of 13:20, 22 April 2023

Line 101:

===Ordering of cardinals===

With equality defined as the existence of a bijection between their underlying sets, Cantor also defines a [[preorder]] 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>, 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, and in this sense <math>|{\mathbb N}|<|2^{\mathbb N}|</math>, i.e. Asthe shownset is uncountable. Also <math>|S|<|{\mathcal P}(S)|</math>, 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]] implies <math>|2^S|=|{\mathcal P}(S)|</math>, and then the setso <math>2^{\mathbb N}</math> is also not enumerable. Here andit can 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>.