Content deleted Content added
→Ordering of cardinals: Make the formulation even more strict |
|||
Line 100:
==Consequences==
===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>. In the
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.
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>.
====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> and <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
| |||