Content deleted Content added
Tags: Mobile edit Mobile web edit |
→In the absence of excluded middle: State stricter statement Tags: Mobile edit Mobile web edit |
||
Line 106:
====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, also <math>{\mathbb N}
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
| |||