Cantor's diagonal argument: Difference between revisions

Revision as of 18:49, 2 May 2023

Revision as of 16:12, 14 June 2023

Line 100:

==Consequences==

===Ordering of cardinals===

With equality defined as the existence of a bijection between their underlying sets, Cantor also defines abinary [[preorder]]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, and in this sense <math>|{\mathbb N}|<|2^{\mathbb N}|</math>, i.e. the set 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]], [[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.