Fact-checked by Grok 2 weeks ago

Cantor's diagonal argument

Cantor's diagonal argument is a proof by contradiction formulated by German mathematician Georg Cantor in 1891 to show that the set of real numbers is uncountable, meaning it has a greater cardinality than the set of natural numbers and cannot be listed exhaustively in a sequence.^[1] The argument assumes an enumeration of all real numbers in the unit interval (0,1) via their infinite decimal expansions and constructs a new real number that differs from the nth number in the list at the nth decimal place, ensuring it is not in the list and thus contradicting the assumption of completeness.^[2] This proof, originally published in Cantor's paper "Über eine elementare Frage der Mannigfaltigkeitslehre" in the Jahresbericht der Deutschen Mathematiker-Vereinigung, marked a pivotal advancement in set theory, building on Cantor's earlier 1874 demonstration of the reals' uncountability using nested intervals but offering a more direct and generalizable method.^[1] Despite initial controversy from figures like Leopold Kronecker, who rejected infinite sets, the diagonal argument established the existence of transfinite cardinalities, revealing that infinities come in different sizes, with the continuum's cardinality denoted as \mathfrak{c} or $2^{\aleph_0}.^[1] Beyond its application to the reals, the argument generalizes to Cantor's theorem, which states that for any set S, the power set \mathcal{P}(S) (the set of all subsets of S) has strictly greater cardinality than S, proven by a similar diagonal construction on binary sequences representing subsets. This theorem underpins the hierarchy of infinite cardinals and has profound implications in mathematics, including the unresolved continuum hypothesis, which posits that no set has cardinality strictly between that of the naturals and the reals.^[3] The diagonal method's influence extends to logic and computability theory, where variants appear in Gödel's incompleteness theorems (1931), which use self-referential diagonalization to show limitations of formal systems, and in Turing's proof of the undecidability of the halting problem (1936), demonstrating that no algorithm can solve all instances of program termination.^[4] These applications highlight the argument's enduring role in revealing inherent limitations and unresolvability in mathematical and computational structures.^[5]

Background Concepts

Countable Sets and Enumerations

A countable set is defined as one that can be placed in a one-to-one correspondence, or bijection, with the set of natural numbers \mathbb{N} = \{1, 2, 3, \dots\}.^[6] This bijection allows every element of the set to be associated uniquely with a natural number, enabling the set to be listed or enumerated without omission or repetition. The concept was introduced by Georg Cantor in his foundational work on infinite sets during the 1870s. Countable sets encompass both finite sets and countably infinite sets. A finite set is countable by mapping its elements to the first n natural numbers for some n \in \mathbb{N}. Countably infinite sets, however, match the cardinality of \mathbb{N} exactly, meaning they are infinite but can still be exhaustively listed in a sequence. Examples include the set of integers \mathbb{Z} = \{\dots, -2, -1, 0, 1, 2, \dots\}, which can be enumerated by alternating positive and negative numbers (e.g., 0, 1, -1, 2, -2, ...), and the set of rational numbers \mathbb{Q}.^[6] An enumeration of a countable set is a sequence a_1, a_2, a_3, \dots where each a_n \in \mathbb{N} indexes a unique element of the set, covering all elements precisely once. This listing process formalizes the bijection and is central to distinguishing countable infinities from larger infinities. Cantor's development of these ideas arose from his investigations into the uniqueness of trigonometric series representations in the early 1870s.^[6] In 1873, he proved that the rational numbers are countable, a result building on his prior work.^[6] To illustrate the countability of the positive rationals \mathbb{Q}^+, consider arranging them in an infinite grid where rows represent numerators and columns denominators, both starting from 1: the entry at row m and column n is the fraction m/n. Traversing this grid along diagonals—first $1/1, then $1/2 and $2/1, then $3/1, $2/2, $1/3, and so on—yields a sequence that includes all positive rationals, with duplicates (like $2/2 = 1/1) skipped to ensure a bijection. This diagonal enumeration method, introduced by Cantor, demonstrates how \mathbb{Q}^+ bijects with \mathbb{N}, and extending it to all \mathbb{Q} by including negatives and zero preserves countability.^[6]

Cardinality and Power Sets

In set theory, the cardinality of a set denotes its size, formally defined such that two sets A and B have equal cardinality, written |A| = |B|, if there exists a bijection—a one-to-one correspondence—between their elements.^[7] To compare sizes when equality does not hold, one says |A| \leq |B| if there is an injection from A to B, meaning every element of A maps uniquely into B without necessarily covering all of B; conversely, |A| \geq |B| if there is a surjection from A to B, meaning every element of B is hit by at least one element of A.^[7] The Schröder–Bernstein theorem guarantees that if both |A| \leq |B| and |B| \leq |A| hold, then a bijection exists, so |A| = |B|.^[8] For infinite sets, cardinalities are represented by transfinite numbers called alephs, with \aleph_0 (aleph-null) denoting the smallest infinite cardinal, which is the cardinality of the natural numbers \mathbb{N} or any countable set.^[7] Larger infinite cardinals follow, such as \aleph_1, \aleph_2, and so on, forming a hierarchy where each exceeds the previous in size.^[7] The power set \mathcal{P}(S) of a set S, also denoted $2^S, is the collection of all subsets of S.^[9] For a finite set S with n elements, the cardinality is |\mathcal{P}(S)| = 2^n, as each element can either be included or excluded from a subset, yielding $2 choices per element.^[9] This exponential growth intuitively extends to infinite sets, suggesting that power sets are strictly larger. Cantor's theorem asserts that for any set S, |\mathcal{P}(S)| > |S|, meaning no bijection exists between S and its power set.^[7] To see why no surjection can map S onto \mathcal{P}(S), represent each subset T \subseteq S by its characteristic function \chi_T: S \to \{0,1\}, where \chi_T(s) = 1 if s \in T and $0 otherwise.^[7] Suppose a function f: S \to \mathcal{P}(S) purportedly covers all subsets; then the "diagonal" subset D = \{s \in S \mid s \notin f(s)\}—defined to differ from f(s) at the element s—cannot equal any f(t), yielding a contradiction.^[7] This result, originally proved by Georg Cantor in 1891, establishes the existence of larger infinities and underpins the hierarchy of cardinals.

The Diagonal Argument for Real Numbers

Binary Representations of Reals

Real numbers in the open interval (0,1) can be represented using infinite binary expansions of the form x = 0.b_1 b_2 b_3 \dots, where each b_i \in \{0,1\} and x = \sum_{i=1}^\infty \frac{b_i}{2^i}.^[10] This representation is not unique for certain values, specifically the dyadic rationals (numbers of the form k/2^m for integers k, m), which admit two expansions: one terminating in infinite 0s and another in infinite 1s. For example, \frac{1}{2} = 0.1000\dots_2 = 0.0111\dots_2. To facilitate the diagonal argument without complications from dual representations, a convention is adopted to select only the expansion ending in infinite 0s for such numbers.^[10] Such binary expansions establish a surjective mapping from the set of all infinite binary sequences to the reals in (0,1), allowing these reals to be identified with sequences of 0s and 1s—or, more formally, with functions from the natural numbers \mathbb{N} to the set {0,1}.^[10] In Georg Cantor's original 1891 presentation of the diagonal argument to the German Mathematical Society, the focus was on the uncountability of infinite sequences over {0,1}, which directly corresponds to binary representations and underpins the analysis of real numbers.^[11] Modern expositions often emphasize binary expansions for their simplicity over decimal ones, as the two-element alphabet avoids additional issues with digit choices.^[10] To assume the reals in (0,1) are countable, one supposes an enumeration of all such binary sequences as rows in an infinite table, where the n-th row represents the n-th real via its binary digits b_{n1}, b_{n2}, b_{n3}, \dots.^[10]

Construction of the Diagonal Element

Assume, for the sake of contradiction, that the real numbers in the open interval (0,1) form a countable set. Then there exists an enumeration r_1, r_2, r_3, \dots, where each r_k is expressed in its binary expansion as r_k = 0.b_{k1} b_{k2} b_{k3} \dots_2, with each digit b_{ki} \in \{0,1\}.^[11]^[12] Construct a new real number d = 0.d_1 d_2 d_3 \dots_2 in (0,1) by taking the diagonal of this enumeration and flipping each entry, so that d_i = 1 - b_{ii} for every positive integer i. This diagonal element d differs from each r_n in the enumeration because its n-th binary digit is d_n = 1 - b_{nn} \neq b_{nn}, the n-th digit of r_n.^[11]^[12]^[13] The difference between d and any r_n is bounded below by the position of their first disagreement: since they differ at the n-th binary place (and possibly agree before), it follows that |d - r_n| \geq 2^{-n}. This quantitative separation confirms that d cannot equal r_n, as their binary expansions are distinct.^[13]^[12] Binary expansions are not always unique, as certain dyadic rationals in (0,1) admit two representations: one ending in infinite 0s and the other in infinite 1s. However, the choice of flipping the diagonal digit ensures the constructed d differs from the specific representation listed for each r_n, and thus from r_n itself, regardless of alternative representations. To further avoid potential equality issues, one may stipulate that all expansions in the enumeration terminate with infinite 0s when dual representations exist; the diagonal construction then yields a d that also adheres to this convention or differs sufficiently to remain distinct.^[12]^[13] The argument applies directly to (0,1), but extends to the closed interval [0,1] since adding the countable set {0,1} to an uncountable set preserves uncountability.^[11]

Generalization to Arbitrary Sets

Proof for Power Sets

Cantor's theorem states that for any set S, the cardinality of the power set \mathcal{P}(S), which consists of all subsets of S, is strictly greater than the cardinality of S itself.^[14] To prove this, assume for contradiction that there exists a surjective function f: S \to \mathcal{P}(S), meaning every subset of S is f(s) for some s \in S, where each f(s) \subseteq S.^[14] The power set \mathcal{P}(S) can be identified with the set of all functions from S to \{0,1\}, via characteristic functions: for any subset A \subseteq S, the characteristic function \chi_A: S \to \{0,1\} is defined by \chi_A(x) = 1 if x \in A and $0 otherwise.^[14] Under this identification, the assumed surjection f assigns to each element s \in S a binary-valued function f(s): S \to \{0,1\}, purportedly covering all possible such functions. Construct the diagonal set D = \{ x \in S \mid x \notin f(x) \}. This set D differs from every f(x) along the "diagonal": for any particular x \in S, the membership of x in D is the opposite of its membership in f(x), flipping the value at the position corresponding to x.^[14] To see the contradiction, suppose D = f(y) for some y \in S. Then y \in D if and only if y \notin f(y), which is y \notin D, yielding y \in D if and only if y \notin D. This impossibility shows that D cannot be in the image of f, contradicting the surjectivity assumption.^[14] Thus, no such surjection exists, so |S| < |\mathcal{P}(S)|. The argument is a proof by contradiction in classical logic, relying on the law of excluded middle to establish the membership dichotomy for each x.^[14] This general diagonal construction applies to arbitrary sets S, extending the technique originally used to show that the real numbers are uncountable when S = \mathbb{N} and subsets model binary representations of reals.^[14]

Implications for Set Cardinalities

Cantor's diagonal argument establishes that for any set S, the cardinality of its power set |P(S)| is strictly greater than the cardinality of S itself, denoted |P(S)| > |S|. This result, known as Cantor's theorem, follows from the existence of an injection from S to P(S) via the mapping that sends each element x \in S to the singleton set \{x\}, while the no-surjection result implies no injection from P(S) to S. Furthermore, the cardinality of the power set satisfies |P(S)| \geq 2^{|S|}, achieved by injecting the set of functions from S to \{0,1\}—which has cardinality $2^{|S|}—into P(S) by associating each function f: S \to \{0,1\} with the subset \{x \in S \mid f(x) = 1\}. Combined with the strict inequality |P(S)| > |S|, this yields |P(S)| \geq 2^{|S|} > |S|. For the countable set S = \mathbb{N}, where |\mathbb{N}| = \aleph_0, the power set P(\mathbb{N}) has cardinality $2^{\aleph_0}, which equals the cardinality of the continuum \mathfrak{c} = |\mathbb{R}|, establishing that the real numbers are uncountable. Under the continuum hypothesis, $2^{\aleph_0} = \aleph_1, though this remains independent of standard set axioms.^[15] In infinite cardinal arithmetic, Cantor's result generalizes to show that for any infinite cardinal \kappa, \kappa < 2^\kappa. This implies an unending hierarchy of infinite cardinals: \aleph_0 < 2^{\aleph_0} \leq 2^{2^{\aleph_0}} < 2^{2^{2^{\aleph_0}}} < \cdots. Cantor introduced this framework in his 1895 work on transfinite numbers, defining the alephs \aleph_0, \aleph_1, \aleph_2, \dots as the well-ordered infinite cardinals and establishing their strict ordering through power set iterations. These alephs form a transfinite sequence without maximum, reflecting the exponential growth of cardinalities beyond any given infinite size.^[15]

Consequences in Set Theory

Hierarchy of Infinite Cardinals

The hierarchy of infinite cardinals emerges directly from the implications of Cantor's diagonal argument, which establishes that for any set of cardinality \kappa, its power set has strictly greater cardinality $2^\kappa > \kappa. This strict inequality implies an unending ascent in cardinal sizes, with no largest infinite cardinal possible, as repeated applications of the power set operation generate ever-larger transfinite sizes. Cantor formalized this structure using the aleph numbers, denoted \aleph_\alpha, where \aleph_0 represents the cardinality of the natural numbers, the smallest infinite cardinal. Subsequent alephs, such as \aleph_1, \aleph_2, and so on, index the infinite cardinals in order of increasing magnitude, with each \aleph_{\alpha+1} being the smallest cardinal strictly larger than \aleph_\alpha.^[16] Cantor conjectured that there is no cardinal strictly between \aleph_0 and $2^{\aleph_0}, the cardinality of the continuum, suggesting that the power set of the naturals yields the next aleph in the sequence. Under this conjecture—later termed the continuum hypothesis (CH)—\aleph_1 = 2^{\aleph_0}, positioning \aleph_1 immediately after \aleph_0 and establishing a tight progression where each successive power set aligns with the next aleph. Without assuming CH, the hierarchy still orders the alephs transfinitely, but potential gaps may exist between \aleph_0 and $2^{\aleph_0}, though the diagonal argument guarantees that $2^{\aleph_0} exceeds \aleph_0 and fits somewhere in the aleph sequence beyond it. Historically, Cantor's exploration of this hierarchy culminated in 1897, when he grappled with the paradox arising from assuming a largest cardinal, such as the cardinality of the "set of all sets," whose power set would contradict the maximality by being larger. This paradox, articulated in his correspondence, highlighted foundational tensions in naive set theory, as the diagonal argument precluded any ultimate cardinal while suggesting an absolute infinity. The issue was resolved through the influence of Russell's paradox in 1901, which exposed inconsistencies in unrestricted set formation, prompting Ernst Zermelo to axiomatize set theory in 1908 with ZFC principles that separate proper classes from sets, thereby accommodating the infinite cardinal hierarchy without contradiction.^[17]^[18] Well-ordering ties ordinals to this cardinal ordering, as Cantor defined infinite cardinals as initial ordinals—well-ordered sets whose order type cannot be bijected with any smaller ordinal—ensuring every cardinal is well-orderable under the axiom of choice. This connection allows ordinals to index the alephs (\aleph_\alpha corresponds to the \alpha-th initial ordinal), providing a linear, well-ordered backbone to the transfinite hierarchy derived from diagonalization.^[16]

Role in the Continuum Hypothesis

The continuum hypothesis (CH), first formulated by Georg Cantor, states that there is no infinite cardinal strictly between the cardinality of the countable set of natural numbers, denoted \aleph_0, and the cardinality of the continuum, the power set of the natural numbers with cardinality $2^{\aleph_0}; equivalently, $2^{\aleph_0} = \aleph_1.^[19] Cantor's diagonal argument provides the foundational proof that $2^{\aleph_0} > \aleph_0, demonstrating the uncountability of the real numbers and establishing a strict inequality that motivates CH but leaves its equality unresolved.^[3] Cantor devoted significant efforts in the 1880s and 1890s to proving CH, developing concepts like transfinite ordinals and perfect sets in pursuit of a resolution, but these attempts ultimately failed and are believed to have exacerbated his psychological difficulties.^[6] The problem remained open until 1938, when Kurt Gödel introduced the constructible universe L and proved that CH is consistent with Zermelo–Fraenkel set theory including the axiom of choice (ZFC), as L satisfies both ZFC and CH. In 1963, Paul Cohen invented the forcing technique and demonstrated that the negation of CH is also consistent with ZFC, thereby proving CH's full independence from these axioms.^[20] This independence implies the existence of ZFC models where CH holds (such as Gödel's L) and others where it fails, including scenarios where $2^{\aleph_0} = \aleph_2 or even larger cardinals.^[19]

Broader Applications of Diagonalization

In Computability and Turing Machines

Cantor's diagonal argument, originally used to establish the uncountability of the real numbers, profoundly influenced computability theory by inspiring diagonalization techniques to demonstrate limitations of algorithmic computation, most notably in the proof of the halting problem's undecidability.^[21] In his 1936 paper "On Computable Numbers, with an Application to the Entscheidungsproblem," Alan Turing formalized the notion of computation via Turing machines and applied a diagonalization argument to show that not all real numbers are computable, implying inherent limits on what algorithms can achieve.^[22] Turing assumed an effective enumeration of all Turing machines M_1, M_2, \dots , where each M_i computes a partial function f_i: \mathbb{N} \to \mathbb{N} (undefined on inputs where it does not halt).^[22] He then constructed a diagonal function g defined by

g(n) = \begin{cases} f_n(n) + 1 & \text{if } f_n(n) \text{ is defined}, \\ 0 & \text{otherwise}. \end{cases}

This g differs from every f_i at input i, since g(i) \neq f_i(i) by construction, showing that g cannot be computed by any Turing machine in the enumeration (i.e., g is not partial recursive), which contradicts the assumption that all such functions are covered.^[22] The self-referential input e for machine M_e—where e indexes M_e itself—lies at the heart of this diagonal construction, enabling the contradiction.^[22] Turing extended this idea to prove the undecidability of the halting problem, which asks whether a given Turing machine M_e halts on input e.^[22] Assume for contradiction that a Turing machine H decides the halting problem: on input (e, e), H outputs 1 if M_e halts on e and 0 otherwise.^[22] Construct a new machine D that, on input e, simulates H on (e, e); if H outputs 1, D loops forever, and if 0, D halts.^[22] Now run D on its own index d (the self-referential case): if H says D halts on d, then D loops, and if H says it loops, then D halts—a direct contradiction via diagonalization.^[22] Thus, no such H exists, establishing the halting problem as undecidable.^[22] Building on Turing's work, Rice's theorem (1953) generalizes these undecidability results to properties of Turing machine languages.^[23] It states that any non-trivial property of the languages recognized by Turing machines—meaning a property that holds for some but not all recursively enumerable languages—is undecidable.^[23] The proof employs a diagonal reduction: to decide if a machine M_e has a language satisfying property P, reduce to the halting problem by constructing a machine that simulates M_e on inputs and appends behaviors ensuring the property holds or not based on halting, leading to a contradiction if P were decidable.^[23] This leverages the self-referential diagonal input to show that semantic properties of computations cannot be algorithmically determined in general.^[23]

In Logic and Foundational Systems

Cantor's diagonal argument has profound implications in mathematical logic, particularly in demonstrating the limitations of formal systems through self-referential constructions. In 1931, Kurt Gödel employed a diagonalization technique, now known as the diagonal lemma, to prove his first incompleteness theorem for sufficiently powerful formal systems of arithmetic, such as Peano arithmetic. The diagonal lemma states that for any formula B(x) with one free variable in the language of arithmetic, there exists a sentence G such that the system proves G \leftrightarrow B(\ulcorner G \urcorner), where \ulcorner G \urcorner is the Gödel number of G. This enables the construction of self-referential sentences that reveal inherent incompleteness. The construction relies on Gödel numbering, which assigns unique natural numbers to formulas and proofs in the system, allowing syntactic objects to be treated arithmetically. Gödel constructs a sentence G asserting its own unprovability: G \equiv \neg \operatorname{Prov}(\ulcorner G \urcorner), where \operatorname{Prov}(y) is a predicate representing the provability relation formalized via diagonalization. If G is provable, then \operatorname{Prov}(\ulcorner G \urcorner) holds, contradicting G; if unprovable, then G is true but undecidable, proving incompleteness. This diagonal self-reference exploits the system's ability to encode its own syntax, leading to sentences neither provable nor refutable. Building on similar ideas, Alfred Tarski in 1933 used diagonalization to prove the undefinability of truth within a formal language. Tarski showed that no consistent theory containing arithmetic can define a truth predicate T(x) for its own sentences such that \phi \leftrightarrow T(\ulcorner \phi \urcorner) holds for all \phi, as this would lead to a contradiction via the liar sentence L \equiv \neg T(\ulcorner L \urcorner). The proof employs a diagonal argument on the satisfaction relation between sequences and formulas, demonstrating that any attempt to internalize truth generates paradoxes, necessitating a stronger metalanguage. This result underscores the hierarchical nature of languages required to discuss truth. The connection to the liar paradox—"This sentence is false"—illustrates an informal precursor to these formal diagonal arguments. The paradox arises from self-reference, yielding a contradiction in classical bivalent logic: assuming the sentence true implies it false, and vice versa. Tarski formalized this issue, showing how diagonalization captures the semantic antinomies inherent in self-applicable truth predicates. While these diagonal techniques robustly establish incompleteness and undefinability in classical formal systems, their application encounters limitations in non-classical logics. In intuitionistic logic, which rejects the law of excluded middle, the full force of the paradoxes may fail or require reinterpretation, as self-referential constructions do not necessarily yield contradictions without classical assumptions about truth values.^[24]

Variants and Limitations

Intuitionistic Versions

In the classical formulation of Cantor's diagonal argument, the construction of the diagonal element relies on the decidability of membership for each entry b_{ii} in the purported enumeration, allowing a straightforward "flip" to define a distinct element (e.g., setting the i-th component to $1 - b_{ii} if binary).^[25] In intuitionistic logic, where the law of excluded middle does not hold, such decidability cannot be assumed for arbitrary sets, complicating the direct flipping mechanism since membership x \in f(x) may remain undecided, preventing the uniform construction of a single diagonal element that differs from all enumerated ones.^[26] L.E.J. Brouwer, in developing intuitionism during the 1920s, rejected non-constructive proofs of existence and critiqued aspects of classical set theory, arguing that infinite sets like the continuum should be viewed as potential rather than actual infinities.^[26] While Brouwer accepted the conclusion of uncountability for the real numbers, he replaced Cantor's diagonal argument with a novel constructive proof based on the continuity principle, which shows that the universal spread (the set of all choice sequences of natural numbers) generates uncountably many elements by demonstrating that any purported enumeration fails due to the principle that functions on spreads are determined by finite initial segments. This approach avoids non-constructive existence claims, ensuring that uncountability is established through explicit constructions rather than hypothetical completions.^[26] Subsequent adaptations in intuitionistic frameworks modify the proof to construct a witness step-by-step for decidable cases, such as binary sequences. For instance, in Martin-Löf's intuitionistic type theory, an intuitionistic version proves there is no surjective function from the natural numbers \mathbb{N} to the function type \mathbb{N} \to \mathbb{N} by assuming such a surjection f and using a fixed-point construction via the successor function to derive a contradiction, yielding \neg \exists f : \mathbb{N} \to (\mathbb{N} \to \mathbb{N}) \, \forall y : \mathbb{N} \to \mathbb{N} \, \exists x : \mathbb{N} \, (f(x) = y), without invoking the excluded middle.^[27] For the real numbers, the proof proceeds by constructing a sequence that decides membership or digit values incrementally, but establishing full uncountability of the continuum in this manner often requires additional choice principles, as unrestricted surjections may not be constructively ruled out without them.^[25] In more abstract settings like topos theory or Heyting algebras, diagonalization preserves the strict inequality |P(S)| > |S| for decidable sets S, leveraging the internal intuitionistic logic of the topos where the subobject classifier acts as a Heyting algebra to define power objects constructively. Here, Lawvere's fixed-point theorem generalizes the diagonal argument to cartesian closed categories, showing that any surjection from S to Y^S implies every endomorphism on Y has a fixed point, which fails for Y = 2 (the two-element object), thus proving non-surjectivity without classical assumptions. The key difference from the classical case is the absence of a uniformly constructible diagonal element across all potential enumerations; instead, the argument establishes that no surjection exists from a countable set to the continuum, relying on constructive contradictions rather than exhaustive enumeration.^[25] Diaconescu's theorem highlights a limitation: in intuitionistic set theory (IZF), the full axiom of choice implies the law of excluded middle, meaning that proofs of cardinality results like Cantor's theorem, when extended to require choice for non-decidable sets, may inadvertently invoke classical principles. Thus, intuitionistic versions prioritize decidable or explicitly constructible cases to maintain full constructivity.

Adaptation to New Foundations

New Foundations (NF), proposed by Willard Van Orman Quine in 1937, is an axiomatic set theory that employs a stratified form of the comprehension axiom to circumvent paradoxes such as Russell's paradox. This stratification requires that formulas used in comprehension respect type levels, effectively imposing a simple type structure without explicit types in the language. As a result, NF admits a universal set V, the set of all sets, which serves as the universe of discourse. The classical Cantor's diagonal argument, which constructs a subset of S not in the image of any function f: S → P(S) via the diagonal set {y ∈ S | y ∉ f(y)}, cannot be directly carried out in NF. The defining formula y ∉ f(y) is unstratified: assigning type i to y requires f to have type i+1 for the membership relation ⟨y, f(y)⟩ ∈ f to make sense, but f(y) ⊆ S demands type i+2 for f(y), leading to a type mismatch. This prevents the comprehension of the diagonal set without adjustment.^[28] To adapt the argument, stratified comprehension is used to define a diagonal set at appropriate type levels. For a function f: X → P(X), the formula can be stratified by assigning type i to the variable y and type i+2 to f, allowing the comprehension {y | y ∉ f(y)} to proceed without violation. This yields a proof that no such f is surjective onto P(X), establishing |P(X)| > |X| for any set X in NF. However, the cardinal structure in NF differs markedly from ZFC: the axiom of choice fails, and the hierarchy of infinite cardinals lacks the well-behaved aleph-fixed points of ZFC.^[28] M. Randall Holmes advanced the understanding of NF in the 1990s through his development of tangled type theory (TTT), showing its equiconsistency with NF-style systems. In consistent models of NF derived from TTT, the adapted diagonalization confirms uncountability results, such as the power set of the naturals exceeding countable cardinality, but the universal set V itself may admit a bijection with ω (the set of natural numbers) in some models, challenging classical applications where the universe cannot be "small." This countability possibility arises because NF's stratification alters how injections and surjections interact with the universal set, permitting V to be Dedekind-infinite yet bijectable with ω.^[29] In June 2025, Holmes provided a complete proof of NF's consistency using tangled type theory, constructing explicit models that validate these cardinality results.^[29]

References

[1]
[PDF] Cantor's Other Proofs that R Is Uncountable
One of the best known proofs is Georg Cantor's diagonalization argument showing the uncountability of the real numbers R. Few people know, however, that this ...
[2]
[PDF] Cantor's Diagonal Argument - Jeremy Martin
In fact, there are infinitely many sizes of infinite sets. Georg Cantor proved this astonishing fact in 1895 by showing that the the set of real numbers is not.
[3]
The Continuum Hypothesis
Cantor's diagonal argument shows that the real numbers can not be enumerated. ... This prominence showed the importance of Cantor's ideas in Hilbert's view ...
[4]
Computability and Complexity
May 6, 2004 · The diagonal argument goes back to Georg Cantor who used it to show that the real numbers are uncountable. Gödel used a similar diagonal ...
[5]
Computability and Complexity - Stanford Encyclopedia of Philosophy
Jun 24, 2004 · The diagonal argument goes back to Georg Cantor who used it to show that the real numbers are uncountable. Gödel used a similar diagonal ...2. Turing Machines · 4. Computational Complexity... · 4.2 Significance Of...
[6]
Georg Cantor (1845 - 1918) - Biography - MacTutor
Cantor published a paper on trigonometric series in 1872 in which he defined irrational numbers in terms of convergent sequences of rational numbers.
[7]
Set Theory - Stanford Encyclopedia of Philosophy
Oct 8, 2014 · Given two cardinals $\kappa$ and $\lambda$, the sum $\kappa +\lambda$ is defined as the cardinality of the set consisting of the union of ...
[8]
Schröder-Bernstein Theorem -- from Wolfram MathWorld
The Schröder-Bernstein theorem for numbers states that if n<=m<=n, then m=n. For sets, the theorem states that if there are injections of the set A into the ...
[9]
Power Set -- from Wolfram MathWorld
- **Definition**: A power set of a set $ S $ is the set of all subsets of $ S $, denoted as $ 2^S $ or $ P(S) $.
[10]
https://math.libretexts.org/Bookshelves/Mathematical_Logic_and_Proof/Gentle_Introduction_to_the_Art_of_Mathematics_(Fields)/08%3A_Cardinality/8.03%3A_Cantors_Theorem
[11]
(PDF) A Translation of G. Cantor's “Ueber eine elementare Frage ...
Aug 23, 2019 · PDF | A Translation of G. Cantor's “Ueber eine elementare Frage der Mannigfaltigkeitslehre” which contains the diagonal argument.
[12]
8.3 Cantor's theorem - A Gentle Introduction to the Art of Mathematics
This argument that we've been edging towards is known as Cantor's diagonalization argument. The reason for this name is that our listing of binary ...
[13]
[PDF] Cantor's diagonal argument - City, University of London
(i) The above proof is known as the diagonal argument because we constructed our element b by considering the diagonal elements in the array (1). (ii) It is ...Missing: original paper
[14]
Contributions to the founding of the theory of transfinite numbers
Mar 10, 2009 · Translation of two memoirs which appeared in the Mathematische ... Beiträge zur begründung der transfiniten mengenlehre." cf. Pref
[15]
Cantors 1891 Diagonal Proof - English Translation - Logic
pp 75-78 (1891). This is the basis for the Diagonal proof and for the Power Set Theorem. The original German text of Cantor's proof is also included below. ...
[16]
English Translation of Cantor's Contributions to The Founding ...
This is a new (2024) English translation of Sections 1 to 6 of Cantor's 1895 paper “Beiträge zur Begründung der transfiniten Mengenlehre”.
[17]
Beiträge zur Begründung der transfiniten Mengenlehre - EuDML
Beiträge zur Begründung der transfiniten Mengenlehre. Georg Cantor · Mathematische Annalen (1895). Volume: 46, page 481-512; ISSN: 0025-5831; 1432-1807/e ...Missing: translation | Show results with:translation
[18]
English translation of Cantor's Grundlagen - Logic
An online English translation of Cantor's Grundlagen (Foundations of a theory of sets): Part 5 of Über unendliche lineare Punktmannig-faltigkeiten.
[19]
[PDF] Cantor's Letter to Dedekind
in the first part of his letter, Cantor deals with the same contradiction as Burali-Forti about the multiplicity of all ordinals.
[20]
Untersuchungen über die Grundlagen der Mengenlehre. I - EuDML
Zermelo, E.. "Untersuchungen über die Grundlagen der Mengenlehre. I." Mathematische Annalen 65 (1908): 261-281. <http://eudml.org/doc/158344>.Missing: pdf | Show results with:pdf
[21]
[PDF] The Continuum Hypothesis and Set-Theoretic Forcing
May 21, 2019 · Cantor famously discovered that the set of real numbers (the continuum) has a strictly greater cardinality than the set of natural numbers. ...
[22]
THE INDEPENDENCE OF THE CONTINUUM HYPOTHESIS - PNAS
The independence of the Continuum Hypothesis means it cannot be derived from other set theory axioms, including the Axiom of Choice.
[23]
(PDF) The Diagonal Argument - a study of cases - ResearchGate
Aug 6, 2025 · PDF | We investigate the role (and the history) of the diagonal argument in set theory, computability theory and logic.
[24]
[PDF] ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ...
The "computable" numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means.
[25]
CLASSES OF RECURSIVELY ENUMERABLE SETS AND THEIR ...
H. G. RICE. 1. Introduction. In this paper we consider classes whose elements are re- cursively enumerable sets of non-negative integers.
[26]
[1004.2239] Intuitionism and the liar paradox - arXiv
Apr 13, 2010 · Abstract:The concept of informal mathematical proof considered in intuitionism is apparently vulnerable to a version of the liar paradox.
[27]
On a proof of Cantor's theorem - Mathematics and Computation
Apr 8, 2007 · A first observation is that this is a constructively valid proof, hence Cantor's theorem holds in intuitionistic set theory just as well.
[28]
[PDF] Intuitionistic Mathematics and Logic - CS@Cornell
When Brouwer proved that the universal spread generates uncountably many elements, he replaced Cantor's diagonal argument by a new argument of exceptional ...
[29]
[PDF] An intuitionistic version of Cantor's theorem - Unipd
Sep 24, 1996 · An intuitionistic version of Cantor's theorem, which shows that there is no surjective function from the type of the natural numbers N into the ...Missing: logic | Show results with:logic
[30]
[PDF] Scrapbook on Set Theory with a Universal Set - DPMMS
Sep 21, 2020 · Page 1. Scrapbook on Set Theory with a Universal Set. Thomas Forster ... NF then Mπ is also a model of NF. Now we have some examples of ...
[31]
https://arxiv.org/abs/1503.01406