Mathematics / Review Essay

Vol. 2, NO. 3 / September 2016

Cantor’s Diagonalization Method

Alexander Kharazishvili

Letters to the Editors

In response to “Cantor’s Diagonalization Method”

Among various philosophical categories, the finite and the infinite are of pivotal importance. The relationship between them is so close, sophisticated, and profound that neither can be perceived and studied without appealing to the other. Both notions are the subject of extensive mathematical research. Modern set theory is entirely devoted to the study of the most general properties of finite and infinite families of objects. 

A set of objects is finite if there exists a one-to-one correspondence, or bijection, between the set and some natural number n. It is assumed that n is identified with the set of all strictly smaller natural numbers. It follows that 0 is identical to the empty set ∅, and 1 coincides with the one-element set {∅}, while 2 is equal to {∅,{∅}}, and so on. If a set of objects is not finite, it is infinite. For example, it is a straightforward to demonstrate that the set N of all natural numbers is infinite.

Galileo offered some useful remarks about the paradoxical nature of infinite sets in the seventeenth century.1 There is a one-to-one correspondence between the natural numbers and their squares. N is equinumerous with a proper part of itself. This is impossible for a finite set of objects.

Bernard Bolzano suggested defining infinite sets as those sets that are equinumerous with their proper subsets.2 This is the definition adopted by Richard Dedekind.3 All sets satisfying this definition are now known as infinite in the Dedekind sense: D-infinite sets.4 All sets which are not D-infinite are now known as finite in the Dedekind sense: D-finite sets. D-finite sets are not quite identical to finite sets. Every finite set is D-finite, but the axiom of choice is needed to establish the converse.5 Even weak versions of the axiom of choice, it should be noted, are extremely non-constructive.6

The introduction of more or less rigorous concepts of infinity was deeply connected with the development of real mathematical analysis in the second part of the nineteenth century by Georg Cantor, Dedekind, Charles Méray, and Karl Weierstrass. Their definitions of the real numbers turned out to be equivalent. The classical theory of Dedekind cuts is now embedded in the theory of Galois connections.7 Cantor’s construction of the real numbers is now recognized as a prototype of completion procedures in arbitrary metric spaces.8 Naïve set theory emerged in the second part of the nineteenth century almost entirely as the result of work by Cantor.

No one, David Hilbert affirmed, can expel us from the paradise that Cantor created.9

Hilbert’s assertion was optimistic. Delicate and difficult moments followed the axiomatization of naïve set theory by Ernst Zermelo and Abraham Fraenkel.10 The role of axiomatic Zermelo–Fraenkel (ZF) set theory as a basis for all of mathematics was itself subject to debate. Today, category theorists argue for the replacement of set theory by category theory.11

The Diagonal Argument

Cantor’s great achievement was his ingenious classification of infinite sets by means of their cardinalities. He defined ordinal numbers as order types of well-ordered sets, generalized the principle of mathematical induction, and extended it to the principle of transfinite induction.

Cantor also created the diagonal argument, which he applied with extraordinary success. Consider any two families of sets {Xi : i ∈ I} and {Yi : i ∈ I}, both indexed by some set of indices, and suppose that Xi ≠ Xj whenever i ≠ j. In the family of all pairs of the form (Xi,Yj), consider the diagonal consisting of all pairs (Xi,Yi), where i ranges over I, and define a subset Z of {Xi : i ∈ I} by stipulating:

Xi ∈ Z if and only if Xi ∉ Yi.

It immediately follows that Z cannot be identical with any Yi, since the relations Xi ∈ Yi and Xi ∉ Yi are in conflict.

Some straightforward consequences follow.

First, Cantor’s celebrated theorem (1891) demonstrates that there is no surjection from any set X onto the family of its subsets, the power set P(X). The proof is straight forward. Take I = X, and consider the two families {xx : x ∈ X} and {Yx : x ∈ X}, where each Yx is a subset of X. The subset Z of X produced by diagonalization for these two families differs from all sets Yx(x ∈ X), so the equality {Yx : x ∈ X} = P(X) is impossible.

If there is no surjection from a set A onto a nonempty set B, then there is no injection from B into A. It follows that there is no injection from P(X) into X. Since there is an embedding f of X into P(X), given by the formula f(x) = {x} for each x ∈ X, X is equinumerous with a certain part of P(X). The reverse is not true. Whence Cantor’s remarkable inequality card(X) < card(P(X)), where card(X) is the cardinality of X, and card(P(X)) is the cardinality of P(X). This inequality implies an infinite series of inequalities:

card(X) < card(P(X)) < card(P(P(X))) < card(P(P(P(X)))) < …

The hierarchy of infinite sets can be continued. Starting with the set N of all natural numbers, one gets

X0 = N,   X1 = P(N),   X2 = P(P(N)),   X3 = P(P(P(N))), … .

Taking the union of the family {Xn : n ∈ N} yields the set X = ∪{Xn : n ∈ N}, whose cardinality is strictly greater than the cardinality of any set Xn(n ∈ N). Starting with the set X instead of N, and successively iterating the operations one then arrives at sets with larger and larger cardinalities. Why not a set whose cardinality exceeds the cardinality of all sets obtained in this way? The question leads unavoidably to the concept of a strongly inaccessible cardinal whose existence is not provable within the framework of  formal set theory. Why not, for that matter, infinities of an even higher order? Gefragt, getan. The result is the theory of large cardinals.12

Second, there is no universal set U satisfying the relation X ∈ U for every set X. This is known as Cantor’s paradox. This follows from a direct diagonalization argument. Suppose that such a U does exist. Take

I = U, {Xi : i ∈ I} = {xx : x ∈ U},{Yi : i ∈ I} = {yy : y ∈ U},

and apply the diagonalization method to {Xi : i ∈ I} and {Yi : i ∈ I}. The set Z that is produced contradicts the universality of U. 

U comprises a very big class of sets, so big, in fact, that it is a proper class of sets. The notion of a class is substantially more general than the notion of a set. Classes are more or less irrelevant for traditional fields of mathematics, which are restricted to local sets. Assuming the existence of a strongly inaccessible cardinal number, one may get an analogue of a universal set. This is sometimes useful for certain types of arguments, especially in abstract set theory, category theory, universal algebra, and general and algebraic topology.13

Third, there is no set R whose elements are precisely those sets X which satisfy X ∉ X. Suppose to the contrary that such a set R does exist and take

I = R,   {Xi : i ∈ I} = {xx : x ∈ R},   {Yi : i ∈ I} = {yy : y ∈ R}.

Applying the diagonalization method to {Xi : i ∈ I} and {Yi : i ∈ I} yields a subset Z of {Xi : i ∈ I} differing from all sets Yi(i ∈ I). On the other hand, the relation Z ∈ Z implies that Z = Xi for some index i ∈ I. Consequently, Z ∉ Z, is a contradiction.

This is a paradox. It was first noticed by Bertrand Russell in 1901. It shows that if a general property S(X) of various sets X is given, one cannot always assert that there exists a set {X : S(X)} consisting of exactly those sets X which satisfy S(X). Every unary relation S(X) of a variable set X, it is worth noting, determines a unique class CS = {X : S(X)}, whose elements are precisely all those sets X for which S(X) holds true. Russell’s collection R is a proper class of sets.

An appreciation of these philosophically interesting results requires virtually no mathematics. Nikolai Luzin characterizes the diagonalization method as an extremely powerful tool for obtaining substantially new mathematical objects.14

Transcendental Numbers

Consider the unit segment [0,1] on the real line R. The points of [0,1] can be identified with the corresponding characteristic functions of subsets of N. The special case of Cantor’s inequality

card(N) < card(P(N))

leads directly to the uncountability of [0,1] and, therefore, to the uncountability of R. Another way to obtain the same result is to construct an infinite sequence of nested line segments so that the n-th segment does not contain the n-th member of a given infinite sequence of points of R. This is an argument first used by Cantor in 1873. The completeness of R yields a point distinct from all members of the sequence.

A remarkable corollary is the existence of many transcendental real numbers. A real number is algebraic if it is a root of some non-zero polynomial with rational coefficients; it is transcendental if it is not a root of any nonzero rational polynomial. The family of all such polynomials is countable, and the total number of distinct roots of each such polynomial does not exceed the degree of the polynomial. The family of all algebraic numbers is thus equinumerous with N, while the family of all transcendental numbers is equinumerous with R.

There are many more transcendental than algebraic numbers.

Concrete examples of transcendental numbers had been found prior to the work of Cantor. In 1844, Joseph Liouville established that ∑{(1/10)n! : n ∈ N} is a transcendental number. A weakness of Cantor’s method is that it will not determine an individual representative of the transcendental numbers. But, slightly revised and modified, it does allow for an explicit example. For this purpose, let us constructively enumerate all nonzero polynomials with integer coefficients, and denote the resulting sequence as {pn : n ∈ N}. Let k(n) stand for the degree of the polynomial pn. Start with p0 and divide [0,1] into 2k(0) + 1 pairwise congruent sub-segments. At least one of those smaller sub-segments will not contain any root of p0.

How then to find the first of these sub-segments? The Sturm algorithm solves the problem of finding the total number of real roots of p0 which lie on any segment of R with rational end-points.15 Denote the required sub-segment of [0,1] by ∆0, then divide ∆0 into 2k(1) + 1 pairwise congruent sub-segments and apply again the Sturm algorithm for finding a sub-segment ∆1 of ∆0 which is free from all roots of p1, and so on. Continuing this process leads to the infinite sequence ∆0, ∆1, … , ∆n, … of nested line segments. It becomes clear that the unique point belonging to all of these segments presents a concrete transcendental number.

A generalized version of Sturm’s algorithm leads to a remarkable theorem formulated by Alfred Tarski. Elementary algebra is decidable. There is an algorithm that determines whether any given statement of the theory is a theorem.16

Cantor’s diagonalization argument establishes that there exists a definable mapping H from the set RN into R, such that, for any real sequence {tn : n ∈ N}, the value H({tn : n ∈ N}) differs from all tn(n ∈ N). But, the existence of an analogous definable mapping G from the family of all countable subsets of R into R, cannot be established within Zermelo-Fraenkel theory. The existence of G implies the existence of a subset of R having cardinality ω1, where ω1 denotes the least uncountable ordinal number. But in ZF theory it is impossible to establish the relation ω1 ≤ card(R).

The existence of a subset of R of cardinality ω1 implies the existence of a Lebesgue nonmeasurable subset of R. This is a result established by Saharon Shelah and Jean Raisonnier.17 Cantor’s famous continuum hypothesis asserts that card(R) = ω1.18 The continuum hypothesis cannot be proved or disproved within the formal ZFC theory. This we know as a result of work by Kurt Gödel and Paul Cohen.

The Growth of Functions

If f is a function acting from N into N, it is not difficult to describe another function g from N into N whose values are greater than the corresponding values of f. We can easily choose g so that the inequality f(n) < g(n) would be satisfied for every natural number n. In that case, g strictly majorizes f. Ditto for any finite family {f0, f1, … , fk} of functions acting from N into N. We always can find a function g which strictly majorizes all f0, f1, … , fk. There is no guarantee that there exists a single function g strictly majorizing all fk(k ∈ N).

If one follows Paul du Bois-Reymond and compares the functions according to their growth, then an appropriate version of the diagonalization method leads to a far-reaching theory.19

For any two functions f and g, each of which acts from N into N, let us say that g is of higher growth than f if lim(g(n)/f(n)) = +∞ as n tends to infinity. The growth of g strictly majorizes the growth of f.

Suppose that we are given an arbitrary countable family {f0, f1, … , fk, …} of functions acting from N into N subject to the constraint that there is a function g : N → N that tends to +∞ much faster than any function fk(k ∈ N). It suffices that

g(n) = (n + 1)max{fk(i) + 1 : k < n + 1, i <n + 1} (n ∈ N).

A straightforward verification shows that the growth of such a g strongly majorizes the growth of each given function fk(k ∈ N).

These considerations can be extended to an arbitrary sequence of functions f0,  f1, … , fk, … acting from the positive half-line [0,+∞] into itself. Then

g(x) = (n + 1)max{fk(x) + 1 : k < n + 1},

whenever a real x satisfies n ≤ x < n + 1. From the definition of g, one readily gets, for any k ∈ N, that lim(g(x)/fk(x)) = +∞ as a variable x ∈ [0,+∞] tends to +∞.

The growth of g is higher than the growth of any function fk(k ∈ N).

In some sense, du Bois-Reymond may be regarded as one of the creators of the diagonalization method.

Together, of course, with Cantor. 

Descriptive Set Theory

In contrast to general set theory, descriptive set theory is concerned with those sets of real numbers, or those families of real-valued functions, that are definable in ZF by concrete properties, or are obtained by using constructive processes.20 Whatever exists in descriptive set theory must be exhibited.

René-Louis Baire took the first steps in this direction.21 Starting with the family B0 of all continuous functions on the unit segment [0,1] with values in the same segment [0,1], and using some transfinite process up to ω1, Baire defined a class of functions as follows. Considering a non-zero ordinal α < ω1 and assuming that the classes Bβ of functions are determined for all ordinals β < α, he took Bα as the class of all pointwise limits of sequences of functions belonging to ∪{Bβ : β < α}. He then put B = ∪{Bα : α < ω1}. The functions belonging to B are, in fact, Borel functions, named after Émile Borel, that act from [0,1] into [0,1]. If α < ω1, then any function from the difference Bα \ (∪{Bβ : β < α}) is a function of order α.

Are there functions of order α for any α < ω1? By using a clever diagonalization argument, Henri Lebesgue was able to give a positive answer.22 Lebesgue also enriched the diagonalization method by introducing the new and fruitful idea of a universal function for a given class of functions. He first proved that, for every ordinal α < ω1, there exists a mapping Fα : [0,1]2 → [0,1] satisfying:

  1. Fα is a Borel function of two variables.
  2. For each function f ∈ Bα, there is a point t from [0,1] such that f = Fα(·, t).

To obtain this preliminary result, Lebesgue utilizes the method of transfinite induction and defines Fα by a certain transfinite process. For each α < ω1, Lebesgue presents a parameterization of all functions from the family Bα. Supposing that there are no functions of order Bα, Lebesgue introduces the Borel mapping Gα : [0,1] × [0,1] → [0,1] by the formula:

Gα(x, t) = limn→∞(nFα(x, t))/(1 + nFα(x, t))   (x ∈ [0,1], t ∈ [0,1]).

Verification that:

  1. ran(Gα) = {0,1},
  2. for any Borel function g : [0,1] → {0,1}, there exists a point t ∈ [0,1] such that g = Gα(·, t),

is easy enough.

Now, apply a diagonalization argument and put h(x) = 1 - Gα(x, x) for each x ∈ [0,1]. The function h is Borel and ran(h) = {0,1}. Keeping 2. in mind, pick a point t from [0,1] for which h = Gα(·, t). Then the equalities

h(t) = 1 - Gα(t, t) = Gα(t, t), Gα(t, t) = 1/2

follow, contradicting 1. Voilà, the existence of Baire functions of any order α < ω1 and, consequently, the existence of Borel sets in [0,1] of the same order α.

A further extension of the Borel subsets of R are the so-called analytic sets in R which are also definable within ZF theory. A subset of R is analytic, Mikhail Suslin argued, if it is either empty or is a continuous image of the set I of all irrational numbers. Developing Lebesgue’s idea, Luzin then proved that there exists an analytic set A in the plane R2, such that the vertical sections of A constitute the family of all analytic subsets of R. A may be regarded as a universal analytic set in the plane. A simple diagonal argument shows that A itself is a non-Borel subset of the plane, and that there is also a non-Borel analytic set in R.23

Lebesgue was the first to discover a non-Borel analytic subset of R,24 but he remained unaware of its significance. Some years later, it was shown that a certain component of Lebesgue’s partition of R is a proper analytic set.25 There are many interesting concrete sets of functions that are analytic but not Borel. The set of all continuous real-valued functions, defined on [0,1], and differentiable at some point of [0,1], is a non-Borel analytic subset of the Banach space of all continuous real-valued functions on [0,1].26 Many other such sets can be constructed in the theory of trigonometric series.27

The diagonalization method is also effective when dealing with the projective subsets of R. Their structure is substantially more complicated than the structure of analytic sets.28 An obvious diagonal argument leads to the conclusion that there is no projective subset of the plane that is universal for the family of all projective subsets of R. Although the projective sets are definable without using the axiom of choice, their Lebesgue measurability cannot be demonstrated within ZFC.29

Totally Discontinuous Functions

Every Lebesgue measurable function possesses the property that its restriction to a certain subset of R of the cardinality of the continuum is necessarily continuous. By well-ordering of the continuum, Wacław Sierpinski and Antoni Zygmund were able to use a diagonal argument to the existence of an utterly discontinuous function. There is a function f : R→ R  such that for each subset X of R having the power of the continuum, the function f|X, the restriction of f to X, is not continuous on X.30

The family of Sierpinski–Zygmund functions is large within the family of all functions from R into R. Any function h : R → R admits a representation in the form h = f1 + f2, where both f1 and f2 are injective Sierpinski–Zygmund functions.31 Consequently, the family of all injective Sierpinski–Zygmund functions is equinumerous with the family of all functions acting from R into itself.32

A similar argument shows that there is a function g : R → R satisfying a much stronger condition: for each subset X of R having the cardinality of the continuum, g|X is not Borel on X. For every partial Borel function, φ : R → R defined on an uncountable Borel subset of R, the set {x ∈ R : φ(x) = g(x)} has cardinality strictly less than the cardinality of the continuum.33

Does there exist a function f : R → R such that, for any uncountable subset Y of R, f|Y is not continuous? Good question. Given the continuum hypothesis, any Sierpinski–Zygmund function yields a positive answer. Nevertheless, the question cannot be resolved within ZFC. Mike Shinoda demonstrated that Martin’s axiom, together with the negation of the continuum hypothesis, implies that if h : R → R, then, for each uncountable set Y in R, there exists an uncountable set Z ⊂ Y such that h|Z is continuous.34

Enumerable and Recursive Sets

Say that f is a function acting from a subset of N into N. f is partial recursive, or computable, if there is an algorithm determining f(x) for any element x ∈ dom(f). If, dom(f) = N, f is a total recursive function. Partial recursive functions from Nk → Nr can be defined in the same way. A set X ⊂ Nk is recursively enumerable if X coincides with the range of some partial recursive function.

Every recursively enumerable set can be described by a formula of formal arithmetic. If X ⊂ N is a recursively enumerable set, then there always exists an arithmetical formula S(x) of one free variable x, such that ∀x(x ∈ X ⇔ S(x)). Yuri Matiyasevich demonstrated that recursively enumerable sets are identical with the diophantine sets, whose nature is purely number-theoretical.35

This is a remarkable result.

A set Y ⊂ N is recursive, or recursively decidable, if there is an algorithm that for every y ∈ N determines whether y belongs to Y. By the same token, Y ⊂ N is recursive if, and only if, its characteristic function fY is a total recursive function. It is not difficult to verify that:36

  1. The composition of any two partial recursive functions is again a partial recursive function.
  2. If f : N → N and g : N → N are any two partial recursive functions, then their product function

(n, m) → (f(n), g(m))(n ∈ dom(f), m ∈ dom(g)),

is also a partial recursive function.

  1. Under a partial recursive function, the image of a recursively enumerable set is again a recursively enumerable set.
  2. A partial function is a partial recursive function if, and only if, its graph is a recursively enumerable set.
  3. Every recursive set is recursively enumerable.
  4. A recursively enumerable set X ⊂ N is recursive if, and only if, its complement N\X is recursively enumerable.

That there exists a universal partial recursive function, h : N × N → N, for the class of all partial recursive functions is a very deep result. Applying the diagonal argument to h, i.e., defining g by

g(n) = h(n, n) + 1      ((n, n) ∈ dom(h)),

one easily infers that the obtained partial recursive function g does not admit an extension to a total recursive function. In addition, the set dom(g) turns out to be recursively enumerable, but not recursive. This is closely connected with Gödel’s first incompleteness theorem. By means of an astonishingly ingenious diagonal argument, Gödel established that in any recursive formal system rich enough to generate arithmetic, there must exist a sentence such that neither the sentence, nor its negation, can be derived from the axioms. The set of arithmetic truths is neither recursive, nor recursively enumerable.

There is a vivid analogy between classical descriptive set theory and recursion theory. Borel sets are similar to recursive sets, and Suslin sets, to recursively enumerable sets. Consider these striking analogies:

(a) The family of all Borel sets in R forms a σ-algebra of subsets of R.

(a’) The family of all recursive sets in N forms an algebra of subsets of N.

(b) Every uncountable analytic set contains an uncountable Borel set and, in fact, contains a set homeomorphic to Cantor’s discontinuum.

(b’) Every infinite recursively enumerable set contains an infinite recursive set.

(c) There is an analytic set in R whose complement is not analytic; or, equivalently, there is a non-Borel analytic set in R.

(c’) There is a recursively enumerable set in N whose complement is not recursively enumerable, or, equivalently, a non-recursive enumerable set in N.

(d) A set X ⊂ R is analytic if, and only if, X is the projection of some Borel subset of R × R.

(d’) A set Y ⊂ N is recursively enumerable if, and only if, Y is the projection of some recursive subset of N × N.

Tarski and Gödel

Consider again formal arithmetic. Let k be a natural number and Z a subset of Nk. Z is arithmetically definable if there is a formula S(x1, x2, …, xk), with free variables x1, x2, …, xk, such that

(n1, n2 , …, nk) ∈ Z ⇔ S(n1, n2, …, nk)

for all natural numbers n1, n2, …, nk. If k and r are natural numbers and f is a partial function acting from Nk into Nr, then f is a partial arithmetic function if the graph of f is an arithmetically definable subset of Nk+r. The family of all arithmetically definable sets satisfies a number of obvious relations.37 Arithmetically definable sets are crucial for Tarski’s undefinability theorem.38

A mathematical theory T has both a syntactic structure and a semantic interpretation. Syntax describes the provable sentences of T; semantics describes its possible models. The standard model of formal arithmetic is the set N of all natural numbers with its canonical structure. There are many nonstandard models of the same formal system.39

The alphabet of formal arithmetic is countable; there is an algorithm that decides, for any finite sequence of formulas of formal arithmetic, whether the sequence is a proof in formal arithmetic. In a triumph of ingenuity, Gödel showed how the elements and sequences of elements in any countable formal system could be canonically mapped to the natural numbers, a scheme that is now called Gödel’s numbering. All formulas and proofs of formal arithmetic admit appropriate enumerations.40

Let us denote by Tr the set of all natural numbers that correspond to those sentences true in the standard model of formal arithmetic. Tarski’s celebrated theorem states that Tr is not an arithmetical set. It suffices to check that the set F of all natural numbers corresponding to sentences that are false in formal arithmetic is not arithmetical. The proof proceeds by contradiction. Suppose that F is, in fact, arithmetical. Now consider a recursive enumeration An(x)(n ∈ N) of all formulas with exactly one free variable x. Consider next the set {(n, m) : An(m) is false}. By the properties of arithmetical sets it follows that this set is arithmetical. But the set {n : An(n) is false} is obviously arithmetical as well. Consequently, there is a natural number k such that

Ak(n) ⇔ An(n) is false

is true for any natural number n. Finally, taking n = k,

Ak(k) ⇔ Ak(k) is false,

which is a contradiction and yields Tarski’s undefinability theorem. The last formula expresses the liar’s paradox, because the sentence Ak(k) asserts that Ak(k) is false.

Tarski’s theorem leads to Gödel’s first incompleteness theorem. Let Pr denote the set of natural numbers corresponding to the provable sentences in formal arithmetic. Pr is recursively enumerable. Since any recursively enumerable set of integers is arithmetical, Pr cannot coincide with Tr. It can only be a proper subset of Tr. Truth and provability are not the same. That this discovery was revolutionary hardly does justice to its significance. Thus, there is a sentence S that is true, but not provable, in the standard model of formal arithmetic. Neither S, nor its negation, ¬S, is provable and formal arithmetic is incomplete. A similar argument is applicable to any recursive mathematical theory that is stronger than formal arithmetic (e.g., ZFC set theory).

In some sense, it is mathematics itself that is incomplete.41

Endmark
DOI: 10.37282/991819.16.27
  1. Galileo Galilei, Opere, Ristampa della Edizione Nationale, 1–20 t. (Firenze: Barbèra, 1929–1939), VIII, 78–80. ↩
  2. Bernard Bolzano, Paradoxien des Unendlichen, (Leipzig: C. H. Reclam. Sen, 1851). ↩
  3. Richard Dedekind, Was sind und was sollen die Zahlen (Braunschweig: F. Vieweg, 1888). ↩
  4. Horst Herrlich, Axiom of Choice (Berlin Heidelberg: Springer-Verlag, 2006). ↩
  5. See Horst Herrlich, Axiom of Choice (Berlin Heidelberg: Springer-Verlag, 2006); Thomas Jech, The Axiom of Choice (Amsterdam: North-Holland Publishing Co., 1973); Lorenz Halbeisen, Combinatorial Set Theory (Berlin: Springer-Verlag, 2011). ↩
  6. See Horst Herrlich, Axiom of Choice (Berlin Heidelberg: Springer-Verlag, 2006); Thomas Jech, The Axiom of Choice (Amsterdam: North-Holland Publishing Co., 1973); Lorenz Halbeisen, Combinatorial Set Theory (Berlin: Springer-Verlag, 2011); Wacław Sierpinski, Cardinal and Ordinal Numbers (Warsaw: PWN, 1958). ↩
  7. See Paul Cohn, Universal Algebra (London: Harper & Row, 1965); Saunders MacLane, Categories for the Working Mathematician (New York: Springer-Verlag, 1998). ↩
  8. Nicolas Bourbaki, Topologie générale  (Paris: Hermann, 1961). ↩
  9. David Hilbert, “Über das Unendliche (On the Infinite),” Mathematische Annalen 95 (1926). ↩
  10. See Abraham Fraenkel, Yehoshua Bar-Hillel, and Azriel Levy, Foundations of Set Theory (Amsterdam: North-Holland Publishing Co., 1973); Thomas Jech, Set Theory (London: Academic Press, 1978); Akihiro Kanamori, “Set Theory from Cantor to Cohen,” in Philosophy of Mathematics, Handbook of the Philosophy of Science (Burlington, MA: Elsevier, 2007), 1–65. ↩
  11. See Paul Cohn, Universal Algebra (London: Harper & Row, 1965); Saunders MacLane, Categories for the Working Mathematician (New York: Springer-Verlag, 1998). ↩
  12. See Lorenz Halbeisen, Combinatorial Set Theory (Berlin: Springer-Verlag, 2011); Thomas Jech, Set Theory (London: Academic Press, 1978); Akihiro Kanamori, “Set Theory from Cantor to Cohen,” in Philosophy of Mathematics, Handbook of the Philosophy of Science (Burlington, MA: Elsevier, 2007), 1–65; Akihiro Kanamori, The Higher Infinite (Berlin-Heidelberg: Springer-Verlag, 2003). ↩
  13. See, for example, Paul Cohn, Universal Algebra (London: Harper & Row, 1965); Thomas Jech, Set Theory (London: Academic Press, 1978); Akihiro Kanamori, “Set Theory from Cantor to Cohen,” in Philosophy of Mathematics, Handbook of the Philosophy of Science (Burlington, MA: Elsevier, 2007), 1–65. ↩
  14. Nikolai Luzin, Collected Works, v. II, (Moscow: Izd. Akad. Nauk SSSR, 1958). ↩
  15. Paul Cohn, Algebra, vol. 2, (New York: Wiley, 1977). ↩
  16. For a detailed explanation see Erwin Engeler, Metamathematik der Elementarmathematik (Berlin Heidelberg: Springer-Verlag, 1983). ↩
  17. See Saharon Shelah, “Can You Take Solovay’s Inaccessible Away?” Israel Journal of Mathematics 48, no. 1 (1984): 1-47; Jean Raisonnier, “A Mathematical Proof of S. Shelah’s Theorem on the Measure Problem and Related Results,” Israel Journal of Mathematics, 48, n. 1 (1984): 48–56. For other profound connections between ω1 and card(R), see also Horst Herrlich, Axiom of Choice (Berlin-Heidelberg: Springer-Verlag, 2006); Thomas Jech, The Axiom of Choice (Amsterdam: North-Holland Publishing Co., 1973); Lorenz Halbeisen, Combinatorial Set Theory (Berlin: Springer-Verlag, 2011); Wacław Sierpinski, Cardinal and Ordinal Numbers (Warsaw: PWN, 1958); Thomas Jech, Set Theory (London: Academic Press, 1978). ↩
  18. See Thomas Jech, Set Theory (London: Academic Press, 1978). ↩
  19. Paul du Bois-Reymond, “Über asymptotische Werte, infinitäre Approximationen und infinitäre Auflösungen von Gleichungen (On Asymptotic Values, Infinitary Approximations and Infinitary Solutions of Equations),” Mathematisch Annalen 8 (1875): 363–414. ↩
  20. See Nikolai Luzin, Collected Works, vol. II (Moscow: Izd. Akad. Nauk SSSR, 1958) (in Russian); Akihiro Kanamori, “The Emergence of Descriptive Set Theory,” Synthese 251 (1995): 241–262; Alexander Kechris, Classical Descriptive Set Theory (New York: Springer-Verlag, 1995). ↩
  21. René-Louis Baire, Leçons sur les Fonctions Discontinues (Paris: Gauthier-Villars, 1905). ↩
  22. Henri Lebesgue, “Sur les fonctions representables analytiquement,” Journal de Mathématiques Pures et Appliquées 1, Ser. 6 (1905): 139–216. ↩
  23. See Nikolai Luzin, Collected Works vol. II (Moscow: Izd. Akad. Nauk SSSR, 1958) (in Russian). ↩
  24. Henri Lebesgue, “Sur les fonctions representables analytiquement,” Journal de Mathématiques Pures et Appliquées 1 (1905): 139–216. ↩
  25. For a detailed analysis of Lebesgue’s partition of R with further far-reaching generalizations, see Nikolai Luzin, Collected Works, vol. II (Moscow: Izd. Akad. Nauk SSSR, 1958) (in Russian). ↩
  26. R. Daniel Mauldin, “The Set of Continuous Nowhere Differentiable Functions,” Pacific Journal of Mathematics 83, no. 1 (1979): 199–205; R. Daniel Mauldin, “The Set of Continuous Nowhere Differentiable Functions: A Correction,” Pacific Journal of Mathematics 121, no. 1 (1986): 119–20. ↩
  27. For more information, see Alexander Kechris, Classical Descriptive Set Theory (New York: Springer-Verlag, 1995). ↩
  28. See, for example, Nikolai Luzin, Collected Works vol. II (Moscow: Izd. Akad. Nauk SSSR, 1958) (in Russian); Alexander Kechris, Classical Descriptive Set Theory (New York: Springer-Verlag, 1995). ↩
  29. Thomas Jech, Set Theory (London: Academic Press, 1978). ↩
  30. Wacław Sierpinski and Antoni Zygmund, “Sur une fonction qui est discontinue sur tout ensemble de puissance du continu,” Fundamenta Mathematicae 4 (1923): 316–18. ↩
  31. See Alexander Kharazishvili, Set Theoretical Aspects of Real Analysis (New York: Chapman and Hall/CRC, 2015). ↩
  32. There are also many Sierpinski–Zygmund functions with interesting additional algebraic properties, e.g., some are additive. See Alexander Kharazishvili, Set Theoretical Aspects of Real Analysis (New York: Chapman and Hall/CRC, 2015). ↩
  33. See Alexander Kharazishvili, Set Theoretical Aspects of Real Analysis (New York: Chapman and Hall/CRC, 2015). ↩
  34. Juichi Shinoda, “Some Consequences of Martin’s Axiom and the Negation of the Continuum Hypothesis,” Nagoya Mathematical Journal 49 (1973): 117–25. ↩
  35. Yuri Matiasevich, “Diophantine Sets,” Uspekhi Matematicheskikh Nauk 22, no. 5 (1972): 185–222 (in Russian). ↩
  36. See Elliott Mendelson, Introduction to Mathematical Logic (New York: Chapman and Hall/CRC, 2015); Hartley Rogers, Jr., Theory of Recursive Functions and Effective Computability (New York: McGraw-Hill Book Co., 1967). ↩
  37. The relations are as follows:
    1. If X and Y are arithmetical subsets of Nk, then the sets X ∪ Y, X ∩ Y, and Nk \ X are also arithmetical subsets of Nk.
    2. If r and k are natural numbers, such that r ≤ k and Z is an arithmetical set in Nk, then the projection of Z on Nr is an arithmetical subset of Nr.
    3. If X is an arithmetical subset of Nk and Y is an arithmetical subset of Nr, then X × Y is an arithmetical subset of Nk+r.
    4. The graph of any partial recursive function is an arithmetical set, so any partial recursive function is a partial arithmetical function.
    5. The image (pre-image) of an arithmetical set under a partial arithmetical function is again an arithmetical set; consequently, the image (pre-image) of an arithmetical set under a partial recursive function is again an arithmetical set.
    Analogous relations hold true for the class of projective sets in Euclidean space. ↩
  38. See Alfred Tarski, “Der Wahrheitsbegriff in den formalisierten Sprachen,” Studia Philosophica 1 (1936): 261–405. ↩
  39. See Erwin Engeler, Metamathematik der Elementarmathematik (Berlin-Heidelberg: Springer-Verlag, 1983); Elliott Mendelson, Introduction to Mathematical Logic (New York: Chapman and Hall/CRC, 2015). ↩
  40. For details, see Elliott Mendelson, Introduction to Mathematical Logic (New York: Chapman and Hall/CRC, 2015); Raymond Smullyan, Gödel’s Incompleteness Theorems (Oxford: Oxford University Press, 1991); John Stillwell, Roads to Infinity: The Mathematics of Truth and Proof (Natick, MA: A.K. Peters, 2010). ↩
  41. The purely syntactic form of Gödel’s incompleteness theorem may be found in Elliott Mendelson, Introduction to Mathematical Logic (New York: Chapman and Hall/CRC, 2015); Raymond Smullyan, Gödel’s Incompleteness Theorems (Oxford: Oxford University Press, 1991); and John Stillwell, Roads to Infinity: The Mathematics of Truth and Proof (Natick, MA: A.K. Peters, 2010), where rich additional information on Tarski’s undefinability theorem and two Gödel’s incompleteness theorems is also presented. Post’s role in the discovery of the incompleteness phenomena is highlighted in John Stillwell, Roads to Infinity: The Mathematics of Truth and Proof (Natick, MA: A.K. Peters, 2010). ↩

Alexander Kharazishvili is Chief Researcher in the Department of Mathematical Analysis at the A. Razmadze Mathematical Institute.

More from this Contributor

Mathematics Big, Little, Nothing, Everything
Alexander Kharazishvili
No finite set is bigger than everything, and so every finite set is smaller than something. If one object is added to a small finite set, it gets bigger, but stays small. Could that be right?
Mathematics Strangely Convergent Sequences
Alexander Kharazishvili
Math can be considered an interplay between finite and infinite collections and between discrete and continuous structures. Alexander Kharazishvili looks at convergent and divergent sequences.
view Contributor

More on Mathematics

At Lunch with Freeman Dyson
William Press
The prisoner’s dilemma, played once, involves limited strategy. But consider the iterated prisoner’s dilemma. Using information from the previous plays, each player can try to outwit their accomplice.
A Crisis of Identification
David Michael Roberts
Almost a decade after claiming a proof of the abc conjecture, Shinichi Mochizuki’s work is stil debated. David Michael Roberts examines efforts by Peter Scholze and Jacob Stix to resolve the impasse.
Reflections on an Essay by Wigner
Sergiu Klainerman
In a new essay, Sergiu Klainerman retraces the development of modern mathematics, unexpected consequences in physics, and the perennial question of whether mathematics is itself a science.
view all articles
Endmark

Copyright © Inference 2024

ISSN #2576–4403