Cantor's diagonal argument: Difference between revisions

Revision as of 13:33, 22 April 2023

Revision as of 15:01, 22 April 2023

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 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

| last = Bell | first = John L. | author-link = John Lane Bell

| editor-last = Link | editor-first = Godehard

Line 119:

| title = One hundred years of Russell's paradox

| volume = 6

| year = 2004}}</ref><ref>Rathjen, M. "[http://www1.maths.leeds.ac.uk/~rathjen/acend.pdf Choice principles in constructive and classical set theories]", Proceedings of the Logic Colloquium, 2002</ref>
This Theis elaboratea collectionnotion of subsetssize oforthogonal ato settheorems isabout constructivelythe notexistence exchangeableof withinjections theand collection ofwhich itsis characteristicredundant functionsin andthe alsoclassical thecontext. The existence of injections from the uncountable <math>2^{\mathbb N}</math> or <math>{\mathbb N}^{\mathbb N}</math> into <math>{\mathbb N}</math> is here possible as well.<ref>Bauer, A. "[http://math.andrej.com/wp-content/uploads/2011/06/injection.pdf An injection from N^N to N]", 2011</ref> So the cardinal relation fails to be [[Antisymmetric relation|antisymmetric]]. Consequently, also in the presence of function space sets that are even classically uncountable, [[intuitionist]]s do not accept this relation to constitute a hierarchy of transfinite sizes.<ref>{{cite book |title=Mathematics and Logic in History and in Contemporary Thought |author=Ettore Carruccio |publisher=Transaction Publishers |year=2006 |page=354 |isbn=978-0-202-30850-0}}</ref>

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]].