Content deleted Content added
→Ordering of cardinals: Make the formulation even more strict |
|||
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>.
Assuming the [[law of excluded middle]] implies <math>|2^S|=|{\mathcal P}(S)|</math>, and then the set <math>2^{\mathbb N}</math> is not enumerable and 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.
Line 107:
====In the absence of excluded middle====
Also in [[Constructivism (mathematics)|constructive mathematics]], there is no surjection from the full ___domain <math>{\mathbb N}</math> onto the space of functions <math>{\mathbb N}^{\mathbb N}</math> or onto the collection of subsets <math>{\mathcal P}({\mathbb N})</math>, which is to say these two collections are uncountable. Using the notation for injection existence as above, <math>{\mathbb N}<2^{\mathbb N}</math>
It is however harder or impossible to order ordinals and also cardinals, constructively. For example, the Schröder–Bernstein theorem requires the law of excluded middle.<ref>{{Cite arXiv|eprint=1904.09193|title=Cantor-Bernstein implies Excluded Middle|class=math.LO|last1=Pradic|first1=Pierre|last2=Brown|first2=Chad E.|year=2019}}</ref> In fact, the standard ordering on the reals, extending the ordering of the rational numbers, is not necessarily decidable either. Neither are most properties of interesting classes of functions decidable, by [[Rice's theorem]], i.e. the set of counting numbers for the subcountable sets may not be [[Recursive set|recursive]] and can thus fail to be countable. In an otherwise constructive context (in which the law of excluded middle not taken as axiom), it is consistent to adopt non-classical axioms that contradict consequences of the law of excluded middle. Uncountable sets such as <math>2^{\mathbb N}</math> or <math>{\mathbb N}^{\mathbb N}</math> may be asserted to be [[subcountability|subcountable]], a notion of size orthogonal to theorems about the existence of injections that is redundant in the classical context.<ref>{{citation
| |||