Editing Cantor's diagonal argument (section)

==Consequences==
===Ordering of cardinals===
With equality defined as the existence of a bijection between their underlying sets, Cantor also defines binary predicate 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>. It has the properties of a [[preorder]] and is 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, i.e. the set is uncountable. For this one may write <math>|{\mathbb N}|<|2^{\mathbb N}|</math>, where "<math><</math>" is understood to mean the existence of an injection together with the proven absence of a bijection (as opposed to alternatives such as the negation of Cantor's preorder, or a definition in terms of [[Von Neumann cardinal assignment|assigned]] [[ordinal numbers|ordinals]]). Also <math>|S|<|{\mathcal P}(S)|</math> in this sense, as has been shown, and at the same time it is the case that <math>\neg(|{\mathcal P}(S)|\le|S|)</math>, for all sets <math>S</math>.

Assuming the [[law of excluded middle]], [[characteristic functions]] surject onto powersets, and then <math>|2^S|=|{\mathcal P}(S)|</math>. So the uncountable <math>2^{\mathbb N}</math> is also not enumerable and it can also be mapped onto <math>{\mathbb N}</math>. 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. Again using "<math><</math>" for proven injection existence in conjunction with bijection absence, one has <math>{\mathbb N}<2^{\mathbb N}</math> and <math>S<{\mathcal P}(S)</math>. Further, <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=Cécilia|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
 | contribution = Russell's paradox and diagonalization in a constructive context
 | contribution-url = https://publish.uwo.ca/~jbell/russ.pdf
 | mr = 2104745
 | pages = 221–225
 | publisher = de Gruyter, Berlin
 | series = De Gruyter Series in Logic and its Applications
 | 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 is a notion of size that is redundant in the classical context, but otherwise need not imply countability. 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]].

In a set theory, theories of mathematics are [[Model theory|modeled]]. Weaker logical axioms mean fewer 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 well-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>{{Cite arXiv|eprint=2404.01256|title=The Countable Reals|class=math.LO|last1=Bauer|last2=Hanson|year=2024}}</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.

===Diagonalization in broader context===
[[Russell's paradox]] has shown that set theory that includes an [[unrestricted comprehension]] scheme is contradictory.  Note that there is a similarity between the construction of ''T'' and the set in Russell's paradox. Therefore, depending on how we modify the axiom scheme of comprehension in order to avoid Russell's paradox, arguments such as the non-existence of a set of all sets may or may not remain valid.

Analogues of the diagonal argument are widely used in mathematics to prove the existence or nonexistence of certain objects. For example, the conventional proof of the unsolvability of the [[halting problem]] is essentially a diagonal argument.  Also, diagonalization was originally used to show the existence of arbitrarily hard [[complexity classes]] and played a key role in early attempts to prove [[P versus NP|P does not equal NP]].