Content deleted Content added
→Ordering of cardinals: Link to Neumann assignment |
|||
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.
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. The elaborate collection of subsets of a set is constructively not exchangeable with the collection of its characteristic functions. In an otherwise constructive context (in which the law of excluded middle is 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]].<ref>{{citation
| |||