Content deleted Content added
→In the absence of excluded middle: Missing word 'is' |
|||
Line 108:
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>, <math>S<{\mathcal P}(S)</math> and <math>\neg({\mathcal P}(S)\le S)</math>, as previously noted. Likewise, <math>2^{\mathbb N}\le{\mathbb N}^{\mathbb N}</math>, <math>2^S\le{\mathcal P}(S)</math> and of course <math>S\le S</math>, also in [[constructive set theory]].
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
| last = Bell | first = John L. | author-link = John Lane Bell
| editor-last = Link | editor-first = Godehard
Line 123:
When the [[axiom of powerset]] is not adopted, in a constructive framework even the subcountability of all sets is then consistent. That all said, in common set theories, the non-existence of a set of all sets also already follows from [[Axiom schema of predicative separation|Predicative Separation]].
In a set theory, theories of mathematics are [[Model theory|modeled]]. Weaker logical axioms mean less constraints and so allow for a richer class of models. A set may be identified as a [[Construction of the real numbers|model of the field of real numbers]] when it fulfills some [[Tarski's axiomatization of the reals|axioms of real numbers]] or a [[Constructive analysis|constructive rephrasing]] thereof. Various models have been studied, such as the [[Construction_of_the_real_numbers#Construction_from_Cauchy_sequences|Cauchy reals]] or the [[Dedekind cut|Dedekind reals]], among others. The former relate to quotients of sequences while the later are good behaved cuts taken from a powerset, if they exist. In the presence of excluded middle, those are all isomorphic and uncountable. Otherwise, [[Effective_topos#Realizability_topoi|variants]] of the Dedekind reals can be countable<ref>Bauer, A., Hanson, J. A. "The countable reals", 2022</ref> or inject into the naturals, but not jointly. When assuming [[countable choice]], constructive Cauchy reals even without an explicit [[modulus of convergence]] are then [[Cauchy_sequence#Completeness|Cauchy-complete]]<ref>Robert S. Lubarsky, [https://arxiv.org/pdf/1510.00639.pdf ''On the Cauchy Completeness of the Constructive Cauchy Reals''], July 2015</ref> and Dedekind reals simplify so as to become isomorphic to them. Indeed, here choice also aids diagonal constructions and when assuming it, Cauchy-complete models of the reals are uncountable.
===Open questions===
| |||