# WikiJournal Preprints/Can each number be specified by a finite text?

Open access • Publication charge free • Public peer review

<meta name='citation_doi' value=>

## Article information

Author: Boris Tsirelson[a]

Tsirelson, B.

## Abstract

Contrary to popular misconception, the question in the title is far from simple. It involves sets of numbers on the first level, sets of sets of numbers on the second level, and so on, endlessly. The infinite hierarchy of the levels involved distinguishes the concept of "definable number" from such notions as "natural number", "rational number", "algebraic number", "computable number" etc.

## Introduction

The question in the title may seem simple, but is able to cause controversy and trip up professional mathematicians. Here is a quote from a talk "Must there be numbers we cannot describe or define?" [1] by J.D. Hamkins.

The math tea argument
Heard at a good math tea anywhere:
“There must be real numbers we cannot describe or define, because there are uncountably many real numbers, but only countably many definitions.”
Does this argument withstand scrutiny?

See also "Maybe there's no such thing as a random sequence" [2] by P.G. Doyle (in particular, on pages 6,7 note two excerpts from A. Tarski [42]). And on Wikipedia one can also find the flawed "math tea" argument on talk pages and obsolete versions of articles.[1] [2] And elsewhere on the Internet.[3] I, the author, was myself a witness and accomplice. I shared and voiced the flawed argument in informal discussions (but not articles or lectures). Despite some awareness (but not professionalism) in mathematical logic,[4] I was a small part of the problem, and now I try to become a small part of the solution, spreading the truth.

Careless handling of the concept "number specified by a finite text" leads to paradoxes; in particular, Richard's paradox.

The paradox begins with the observation that certain expressions of natural language define real numbers unambiguously, while other expressions of natural language do not. For example, "The real number the integer part of which is 17 and the ${\displaystyle n}$th decimal place of which is 0 if ${\displaystyle n}$ is even and 1 if ${\displaystyle n}$ is odd" defines the real number 17.1010101... = 1693/99, while the phrase "the capital of England" does not define a real number.

Thus there is an infinite list of English phrases (such that each phrase is of finite length, but lengths vary in the list) that define real numbers unambiguously. We first arrange this list of phrases by increasing length, then order all phrases of equal length lexicographically (in dictionary order), so that the ordering is canonical. This yields an infinite list of the corresponding real numbers: ${\displaystyle r_{1},r_{2},\dots }$ Now define a new real number ${\displaystyle r}$ as follows. The integer part of ${\displaystyle r}$ is 0, the ${\displaystyle n}$th decimal place of ${\displaystyle r}$ is 1 if the ${\displaystyle n}$th decimal place of ${\displaystyle r_{n}}$ is not 1, and the ${\displaystyle n}$th decimal place of ${\displaystyle r}$ is 2 if the ${\displaystyle n}$th decimal place of ${\displaystyle r_{n}}$ is 1.

The preceding two paragraphs are an expression in English that unambiguously defines a real number ${\displaystyle r.}$ Thus ${\displaystyle r}$ must be one of the numbers ${\displaystyle r_{n}.}$ However, ${\displaystyle r}$ was constructed so that it cannot equal any of the ${\displaystyle r_{n}.}$ This is the paradoxical contradiction.

(Quoted from Wikipedia.)

In order to ask (and hopefully solve) a well-posed question we have to formalize the concept "number specified by a finite text" via a well-defined mathematical notion "definable number". What exactly is meant by "text"? And what exactly is meant by "number specified by text"? Does "specified" mean "defined"? Can we define such notions as "definition" and "definable"? Striving to understand definitions in general, let us start with some examples.

136 notable constants are collected, defined and discussed in the book "Mathematical constants" by Steven Finch [3]. The first member of this collection is "Pythagoras’ Constant, ${\displaystyle {\sqrt {2}}}$"; the second is "The Golden Mean, ${\displaystyle \varphi }$"; the third "The Natural Logarithmic Base, e"; the fourth "Archimedes’ Constant, ${\displaystyle \pi }$"; and the last (eleventh) in Chapter 1 "Well-Known Constants" is "Chaitin’s Constant".

Each constant has several equivalent definitions. Below we take for each constant the first (main) definition from the mentioned book.

• The first constant ${\displaystyle {\sqrt {2}}}$ is defined as the positive real number whose product by itself is equal to 2. That is, the real number ${\displaystyle x}$ satisfying ${\displaystyle x>0}$ and ${\displaystyle x^{2}=2.}$
• The second constant ${\displaystyle \varphi }$ is defined as the real number satisfying ${\displaystyle \varphi >0}$ and ${\displaystyle \textstyle 1+{\frac {1}{\varphi }}=\varphi .}$
• The third constant ${\displaystyle e}$ is defined as the limit of ${\displaystyle \textstyle (1+x)^{1/x}}$ as ${\displaystyle x\to 0.}$ That is, the real number satisfying the following condition:
for every ${\displaystyle \varepsilon >0}$ there exists ${\displaystyle \delta >0}$ such that for every ${\displaystyle x}$ satisfying ${\displaystyle -\delta and ${\displaystyle x\neq 0}$ holds ${\displaystyle \textstyle -\varepsilon <(1+x)^{1/x}-e<\varepsilon .}$
The same condition in symbols:
${\displaystyle \textstyle \forall \varepsilon >0\,\,\exists \delta >0\,\,\forall x\;{\big (}\,(-\delta
logical notation

${\displaystyle \land }$ "and"      ${\displaystyle \lor }$ "or"      ${\displaystyle \Longrightarrow }$ "implies"      ${\displaystyle \neg }$ "not"      ${\displaystyle \forall }$ "for every"      ${\displaystyle \exists }$ "there exists (at least one)"      ${\displaystyle \exists !}$ "there exists one and only one"          (a longer list).

We note that these three definitions are of the form "the real number ${\displaystyle x}$ satisfying ${\displaystyle P(x)}$" where ${\displaystyle P(x)}$ is a statement that may be true or false depending on the value of its variable ${\displaystyle x}$; in other words, not a statement when ${\displaystyle x}$ is just a variable, but a statement whenever a real number is substituted for the variable. Such ${\displaystyle P(x)}$ is called a property of ${\displaystyle x}$, or a predicate (on real numbers).

Not all predicates may be used this way. For example, we cannot say "the real number ${\displaystyle x}$ satisfying ${\displaystyle x^{2}=2}$" (why "the"? two numbers satisfy, one positive, one negative), nor "the real number ${\displaystyle x}$ satisfying ${\displaystyle x^{2}=-2}$" (no such numbers). In order to say "the real number ${\displaystyle x}$ satisfying ${\displaystyle P(x)}$" we have to prove existence and uniqueness:

existence: ${\displaystyle \exists x\;P(x)}$ (in words: there exists ${\displaystyle x}$ such that ${\displaystyle P(x)}$);
uniqueness: ${\displaystyle \forall x,y\;{\big (}\,(P(x)\land P(y))\Longrightarrow (x=y)\,{\big )}}$ (in words: whenever ${\displaystyle x}$ and ${\displaystyle y}$ satisfy ${\displaystyle P}$ they are equal).

The road to definable numbers passes through definable predicates. We postpone this matter to the next section and return to examples.

• The fourth constant ${\displaystyle \pi }$ is defined as the area enclosed by a circle of radius 1.

This definition involves geometry. True, a lot of equivalent definitions in terms of numbers are well-known; in particular, according to the mentioned book, this area is equal to ${\displaystyle \textstyle \,4\int _{0}^{1}{\sqrt {1-x^{2}}}\,dx=\lim _{n\to \infty }{\frac {4}{n^{2}}}\sum _{k=0}^{n}{\sqrt {n^{2}-k^{2}}}\,.}$ However, in general, every branch of mathematics may be involved in a definition of a number; existence of an equivalent definition in terms of (only) numbers is not guaranteed.

The last example is Chaitin's constant. In contrast to the four constants (mentioned above) of evident theoretical and practical importance, Chaitin's constant is rather of theoretical interest. Its definition is intricate. Here is a simplified version, sufficient for our purpose.[5]

• The last constant ${\displaystyle \Omega }$ is defined as the sum of the series ${\displaystyle \textstyle \Omega =\sum _{N=1}^{\infty }2^{-N}A_{N}}$ where ${\displaystyle A_{N}}$ is equal to 1 if there exist natural numbers ${\displaystyle x_{1},x_{2},x_{3},x_{4},x_{5},x_{6},x_{7},x_{8},x_{9}}$ such that ${\displaystyle f(N,x_{1},x_{2},x_{3},x_{4},x_{5},x_{6},x_{7},x_{8},x_{9})=0,}$ otherwise ${\displaystyle A_{N}=0;}$ and ${\displaystyle f}$ is a polynomial in 10 variables, with integer coefficients, such that the sequence ${\displaystyle A_{1},A_{2},\dots }$ is uncomputable.

Hilbert’s tenth problem asked for a general algorithm that could ascertain whether the Diophantine equation ${\displaystyle f(x_{0},\dots ,x_{k})=0}$ has positive integer solutions ${\displaystyle (x_{0},\dots ,x_{k}),}$ given arbitrary polynomial ${\displaystyle f}$ with integer coefficients. It appears that no such algorithm can exist even for a single ${\displaystyle f}$ and arbitrary ${\displaystyle x_{0},}$ when ${\displaystyle f}$ is complicated enough. See Wikipedia: computability theory, Matiyasevich's theorem; and Scholarpedia:Matiyasevich theorem.

The five numbers ${\displaystyle {\sqrt {2}},\varphi ,e,\pi ,\Omega }$ are defined, thus, should be definable according to any reasonable approach to definability. The first four numbers ${\displaystyle {\sqrt {2}},\varphi ,e,\pi }$ are computable (both theoretically and practically; in fact, trillions, that is, millions of millions, of decimal digits of ${\displaystyle \pi }$ are already computed), but the last number ${\displaystyle \Omega }$ is uncomputable. How so? Striving to better understand this strange situation we may introduce approximations ${\displaystyle A_{M,N}}$ to the numbers ${\displaystyle A_{N}}$ as follows: ${\displaystyle A_{M,N}}$ is equal to 1 if there exist natural numbers ${\displaystyle x_{1},x_{2},x_{3},x_{4},x_{5},x_{6},x_{7},x_{8},x_{9}}$ less than ${\displaystyle M}$ such that ${\displaystyle f(N,x_{1},x_{2},x_{3},x_{4},x_{5},x_{6},x_{7},x_{8},x_{9})=0,}$ otherwise ${\displaystyle A_{N}=0;}$ here ${\displaystyle M}$ is arbitrary. For each ${\displaystyle N}$ we have ${\displaystyle A_{M,N}\uparrow A_{N}}$ as ${\displaystyle M\to \infty ;}$ that is, the sequence ${\displaystyle A_{1,N},A_{2,N},\dots }$ is increasing, and converges to ${\displaystyle A_{N}.}$ Also, this sequence ${\displaystyle A_{1,N},A_{2,N},\dots }$ is computable (given ${\displaystyle M,}$ just check all the ${\displaystyle (M-1)^{9}}$ points ${\displaystyle (N,x_{1},x_{2},x_{3},x_{4},x_{5},x_{6},x_{7},x_{8},x_{9}),}$ ${\displaystyle 0). Now we introduce approximations ${\displaystyle \omega _{M}}$ to the number ${\displaystyle \Omega }$ as follows: ${\displaystyle \textstyle \omega _{M}=\sum _{N=1}^{M}2^{-N}A_{M,N}.}$ We have ${\displaystyle \omega _{M}\uparrow \Omega }$ (as ${\displaystyle M\to \infty }$), and the sequence ${\displaystyle \omega _{1},\omega _{2},\dots }$ is computable. A wonder: a computable increasing sequence of rational numbers converges to a uncomputable number!

For every ${\displaystyle N}$ there exists ${\displaystyle M}$ such that ${\displaystyle A_{M,N}=A_{N};}$ such ${\displaystyle M}$ depending on ${\displaystyle N,}$ denote it ${\displaystyle M_{N}}$ and get ${\displaystyle \textstyle \sum _{N=1}^{\infty }2^{-N}A_{M_{N},N}=\Omega ;}$ moreover, ${\displaystyle \textstyle \Omega -\sum _{N=1}^{K}2^{-N}A_{M_{N},N}\leq 2^{-K}}$ for all ${\displaystyle K.}$ In order to compute ${\displaystyle \Omega }$ up to ${\displaystyle 2^{-K}}$ it suffices to compute ${\displaystyle \textstyle \sum _{N=1}^{K}2^{-N}A_{M_{N},N}.}$ Doesn't it mean that ${\displaystyle \Omega }$ is computable? No, it does not, unless the sequence ${\displaystyle M_{1},M_{2},\dots }$ is computable. Well, these numbers need not be optimal, just large enough. Isn't ${\displaystyle \textstyle M_{N}=10^{1000N}}$ large enough? Amazingly, no, this is not large enough. Moreover, ${\displaystyle \textstyle M_{N}=10^{10^{1000N}}}$ is not enough. And even the "power tower"${\displaystyle M_{N}=\underbrace {10^{10^{\cdot ^{\cdot ^{10}}}}} _{1000N}}$ is still not enough!

Here is the first paragraph from a prize-winning article by Bjorn Poonen [4]:

Does the equation ${\displaystyle \textstyle x^{3}+y^{3}+z^{3}=29}$ have a solution in integers? Yes: (3, 1, 1), for instance. How about ${\displaystyle \textstyle x^{3}+y^{3}+z^{3}=30\,?}$ Again yes, although this was not known until 1999: the smallest solution is (−283059965, −2218888517, 2220422932). And how about ${\displaystyle \textstyle x^{3}+y^{3}+z^{3}=33\,?}$ This is an unsolved problem.

Given that the simple Diophantine equation ${\displaystyle \textstyle N+x^{3}+y^{3}-z^{3}=0}$ has solutions for ${\displaystyle N=30}$ but only beyond ${\displaystyle 10^{9}}$ we may guess that the "worst case" Diophantine equation ${\displaystyle f(N,x_{1},x_{2},x_{3},x_{4},x_{5},x_{6},x_{7},x_{8},x_{9})=0}$ needs very large ${\displaystyle M_{N}.}$ In fact, the sequence ${\displaystyle M_{1},M_{2},\dots }$ has to be uncomputable (otherwise ${\displaystyle \Omega }$ would be computable, but it is not). Some computable sequences grow fantastically fast. See Wikipedia: "Ackermann function", "Fast-growing hierarchy". And nevertheless, no one of them bounds from above the sequence ${\displaystyle M_{1},M_{2},\dots \,}$ Reality beyond imagination!

Every computable number is definable, but a definable number need not be computable. Computability being another story, we return to definability.

## From predicates to relations

Recall the five definitions mentioned in the introduction. They should be special cases of a general notion "definition". In order to formalize this idea we have to be more pedantic than in the introduction. "Nothing but the hard technical story is any real good" (Littlewood, A Mathematician's Miscellany, page 70); exercises are waiting for you.

All mathematical objects (real numbers, limits, sets etc.) are treated in the framework of the mainstream mathematics, unless stated otherwise. Alternative approaches are sometimes mentioned in Sections 9, 10. Naive set theory suffices for Sections 27; axiomatic set theory is used in Sections 810.

A definition is a text in a language. A straightforward formalization of such notions as "definition" and "definable" uses "formal language" (a formalization of "language") and other notions of model theory. Surprisingly, there is a shorter way. Operations on sets are used instead of logical symbols, and relations instead of predicates.

"However, predicates have many different uses and interpretations in mathematics and logic, and their precise definition, meaning and use will vary from theory to theory." (Quoted from Wikipedia.) Here we use predicates for informal explanations only; on the formal level they will be avoided (replaced with relations).

The number ${\displaystyle {\sqrt {2}}}$ was defined as the real number ${\displaystyle x}$ such that ${\displaystyle P(x),}$ where ${\displaystyle P(x)}$ is the predicate "${\displaystyle x>0}$ and ${\displaystyle x^{2}=2}$". This predicate is the conjunction ${\displaystyle P_{1}(x)\land P_{2}(x)}$ of two predicates ${\displaystyle P_{1}(x)}$ and ${\displaystyle P_{2}(x),}$ the first being "${\displaystyle x>0}$", the second "${\displaystyle x^{2}=2}$". The single-element set ${\displaystyle A=\{x\in \mathbb {R} \mid P(x)\}=\{{\sqrt {2}}\}}$ corresponding to the predicate ${\displaystyle P(x)}$ is the intersection ${\displaystyle A=A_{1}\cap A_{2}}$ of the sets ${\displaystyle A_{1}=\{x\in \mathbb {R} \mid P_{1}(x)\}=(0,\infty )}$ and ${\displaystyle A_{2}=\{x\in \mathbb {R} \mid P_{2}(x)\}=\{-{\sqrt {2}},{\sqrt {2}}\}.}$ (Here and everywhere, ${\displaystyle \mathbb {R} }$ is the set of all real numbers.)

set notation

${\displaystyle A=\{x\mid P(x)\}}$   "${\displaystyle A}$ is the set of all ${\displaystyle x}$ such that ${\displaystyle P(x)}$"      ${\displaystyle x\in A}$   "${\displaystyle x}$ belongs to ${\displaystyle A}$"      ${\displaystyle A\cup B}$   union      ${\displaystyle A\cap B}$   intersection      ${\displaystyle A\setminus B}$ set difference      ${\displaystyle A\times B}$   Cartesian product      ${\displaystyle \mathbb {R} }$   real line      ${\displaystyle \mathbb {R} ^{2}}$   Cartesian plane          and more, more, more.

This is instructive. In order to formalize a definition of a number via its defining property, we have to deal with sets of numbers, and more generally, relations between numbers.

Also, ${\displaystyle x^{2}}$ is the product ${\displaystyle x\cdot x,}$ and ${\displaystyle 2}$ is the sum ${\displaystyle 1+1.}$ But what is "product", "sum", "${\displaystyle 1}$" and "${\displaystyle 0}$"? The answer is given by the axiomatic approach to real numbers: they are a complete totally ordered field. It means that addition, multiplication and order are defined and have the appropriate properties. Thus, 0 is defined as the real number ${\displaystyle x}$ satisfying the condition ${\displaystyle \forall y\;(x+y=y).}$ Similarly, ${\displaystyle 1}$ is defined as the real number ${\displaystyle x}$ satisfying the condition ${\displaystyle \forall y\;(x\cdot y=y).}$

Now we need predicates with two and more variables. The order is a binary (that is, with two variables) predicate "${\displaystyle x\leq y}$". Addition is a ternary (that is, with three variables) predicate "${\displaystyle x+y=z}$". Similarly, multiplication is a ternary predicate "${\displaystyle xy=z}$" (denoted also "${\displaystyle x\cdot y=z}$" or "${\displaystyle x\times y=z}$").

Each unary (that is, with one variable) predicate ${\displaystyle P(x)}$ on real numbers leads to a set ${\displaystyle \{x\in \mathbb {R} \mid P(x)\}}$ of real numbers, a subset of the real line ${\displaystyle \mathbb {R} .}$ Likewise, each binary predicate ${\displaystyle P(x,y)}$ on reals leads to a set ${\displaystyle \{(x,y)\in \mathbb {R} ^{2}\mid P(x,y)\}}$ of pairs of real numbers, a subset of the Cartesian plane ${\displaystyle \mathbb {R} ^{2}=\mathbb {R} \times \mathbb {R} ,}$ the latter being the Cartesian product of the real line by itself. On the other hand, a binary relation on ${\displaystyle \mathbb {R} }$ is defined as an arbitrary subset of ${\displaystyle \mathbb {R} ^{2}.}$

Thus, each binary predicate on reals leads to a binary relation on reals. If we swap the variables, that is, turn to another predicate ${\displaystyle Q(x,y)}$ that is ${\displaystyle P(y,x),}$ then we get another relation ${\displaystyle \{(x,y)\mid Q(x,y)\}=\{(x,y)\mid P(y,x)\}=\{(y,x)\mid P(x,y)\},}$ inverse (in other words, converse, or opposite) to the former relation (generally different, but sometimes the same).

Similarly, each ternary predicate on reals leads to a ternary relation on reals; and, changing the order of variables, we get ${\displaystyle 3!=6}$ ternary relations (generally, different) corresponding to 6 permutations of 3 variables. And generally, each n-ary predicate on reals leads to a n-ary relation on reals (a subset of ${\displaystyle \mathbb {R} ^{n}}$); and, changing the order of variables, we get ${\displaystyle n!}$ such relations. The case ${\displaystyle n=1}$ is included (for unification); a unary relation on reals (called also property of reals) is a subset of ${\displaystyle \mathbb {R} .}$

Thus, on reals, the order is the binary relation ${\displaystyle \{(x,y)\mid x\leq y\},}$ the addition is the ternary relation${\displaystyle \{(x,y,z)\mid x+y=z\},}$ and the multiplication is the ternary relation${\displaystyle \{(x,y,z)\mid xy=z\}.}$ Still, we cannot forget predicates until we understand how to construct new relations out of these basic relations. For example, how to construct the binary relation ${\displaystyle \{(x,y)\mid x+y=y\}}$ and the unary relation ${\displaystyle \{x\mid \forall y\;(x+y=y)\}\,?}$ We know that if a predicate ${\displaystyle P(x)}$ is the conjunction ${\displaystyle P_{1}(x)\land P_{2}(x)}$ of two predicates, then it leads to the intersection ${\displaystyle A=A_{1}\cap A_{2}}$ of the corresponding sets. Similarly, the disjunction ${\displaystyle P_{1}(x)\lor P_{2}(x)}$ leads to the union ${\displaystyle A=A_{1}\cup A_{2}}$, and the negation ${\displaystyle \neg P_{1}(x)}$ leads to the complement ${\displaystyle A=\mathbb {R} \setminus A_{1}.}$ Also, the implication ${\displaystyle P_{1}(x)\Longrightarrow P_{2}(x)}$ leads to ${\displaystyle A=(\mathbb {R} \setminus A_{1})\cup A_{2},}$ and the equivalence ${\displaystyle P_{1}(x)\Longleftrightarrow P_{2}(x)}$ leads to ${\displaystyle A={\big (}(\mathbb {R} \setminus A_{1})\cap (\mathbb {R} \setminus A_{2}){\big )}\cup (A_{1}\cap A_{2}).}$ The same holds for n-ary predicates; the disjunction ${\displaystyle P_{1}(x,y)\lor P_{2}(x,y)}$ still corresponds to the union ${\displaystyle A=A_{1}\cup A_{2},}$ the negation ${\displaystyle \neg P_{1}(x,y,z)}$ to the complement ${\displaystyle A=\mathbb {R} ^{3}\setminus A_{1},}$ etc. But what to do when ${\displaystyle P(x,y)}$ is ${\displaystyle P_{1}(x,y,y),\,}$ or ${\displaystyle P(x)}$ is ${\displaystyle \forall y\;P_{1}(x,y),\,}$ or ${\displaystyle P(x,y,z)}$ is ${\displaystyle P_{1}(y,x)\land P_{2}(y,z),\,}$ etc?

This question was answered, in context of axiomatic set theory, in the first half of the 20th century.[6] A somewhat different answer, in the context of definability, was given by van den Dries in 1998 [5], [6] and slightly modified by Auke Bart Booij in 2013 [7]; see also Macintyre 2016 [8, "Defining First-Order Definability"]. Here is the answer (slightly modified).

First, in addition to the Boolean operations (union and complement; intersection is superfluous, since it is complement of the union of complements) on subsets of ${\displaystyle \mathbb {R} ^{n},}$ we introduce permutation of coordinates; for example (${\displaystyle n=3}$), ${\displaystyle A=\{(x,y,z)\in \mathbb {R} ^{3}\mid (z,x,y)\in A_{1}\};}$ and in general,

${\displaystyle A=\{(x_{1},\dots ,x_{n})\in \mathbb {R} ^{n}\mid (x_{i_{1}},\dots ,x_{i_{n}})\in A_{1}\}}$

where ${\displaystyle (i_{1},\dots ,i_{n})}$ is an arbitrary permutation of ${\displaystyle (1,\dots ,n).}$

In particular, permutation of coordinates in a binary relation gives the inverse relation. For example, the inverse to ${\displaystyle \{(x,y)\mid x\leq y\}}$ is ${\displaystyle \{(x,y)\mid y\leq x\}=\{(x,y)\mid x\geq y\}.}$ And, by the way, the intersection of these two is the relation ${\displaystyle \{(x,y)\mid x=y\}}$ (corresponding to the predicate "${\displaystyle x=y}$").

Second, set multiplication, in other words, Cartesian product by ${\displaystyle \mathbb {R} }$: ${\displaystyle A=A_{1}\times \mathbb {R} ,}$ that is,

${\displaystyle A=\{(x_{1},\dots ,x_{n+1})\in \mathbb {R} ^{n+1}\mid (x_{1},\dots ,x_{n})\in A_{1}\},}$

turns a ${\displaystyle n}$-ary relation to a relation that is formally ${\displaystyle (n+1)}$-ary, but the last variable is unrelated to others.

Now, returning to a predicate ${\displaystyle P(x,y,z)}$ of the form ${\displaystyle P_{1}(y,x)\land P_{2}(y,z),}$ we treat the corresponding ternary relation ${\displaystyle A=\{(x,y,z)\in \mathbb {R} ^{3}\mid P(x,y,z)\}}$ as the intersection of two ternary relations ${\displaystyle A_{1}=\{(x,y,z)\in \mathbb {R} ^{3}\mid P_{1}(y,x)\}}$ and ${\displaystyle A_{2}=\{(x,y,z)\in \mathbb {R} ^{3}\mid P_{2}(y,z)\};}$ and ${\displaystyle A_{1}}$ as the Cartesian product of the binary relation ${\displaystyle B_{1}=\{(x,y)\in \mathbb {R} ^{2}\mid P_{1}(y,x)\}}$ by ${\displaystyle \mathbb {R} ,}$ ${\displaystyle B_{1}}$ being inverse to the relation ${\displaystyle B_{2}=\{(x,y)\in \mathbb {R} ^{2}\mid P_{1}(x,y)\}}$ (corresponding to the given predicate ${\displaystyle P_{1}(x,y)}$); and ${\displaystyle A_{2}}$ as obtained (by permutation of coordinates) from the Cartesian product ${\displaystyle \{(y,z,x)\in \mathbb {R} ^{3}\mid P_{2}(y,z)\}=\{(y,z)\in \mathbb {R} ^{2}\mid P_{2}(y,z)\}\times \mathbb {R} }$ (by ${\displaystyle \mathbb {R} }$) of the relation corresponding to the given predicate ${\displaystyle P_{2}(y,z).}$

Third, the projection; for example (${\displaystyle n=1}$), ${\displaystyle A=\{x\mid \exists y\in \mathbb {R} \;{\big (}(x,y)\in A_{1}{\big )}\};}$ and in general,

${\displaystyle A=\{(x_{1},\dots ,x_{n})\mid \exists x_{n+1}\in \mathbb {R} \;{\big (}(x_{1},\dots ,x_{n+1})\in A_{1}{\big )}\};}$

it turns a ${\displaystyle (n+1)}$-ary relation to a ${\displaystyle n}$-ary relation. For ${\displaystyle n=1}$ the set ${\displaystyle A}$ is also called the domain of the binary relation ${\displaystyle A_{1}.}$

Now, returning to a predicate ${\displaystyle P(x,y)}$ of the form ${\displaystyle P_{1}(x,y,y),\,}$ we rewrite it as "${\displaystyle \exists z\;{\big (}P_{1}(x,y,z)\land y=z{\big )}}$" and treat the corresponding binary relation as the projection of the ternary relation ${\displaystyle \{(x,y,z)\mid P_{1}(x,y,z)\}\cap \{(x,y,z)\mid y=z\},}$ and ${\displaystyle \{(x,y,z)\mid y=z\}}$ as a permutation of the Cartesian product ${\displaystyle \{(y,z)\mid y=z\}\times \mathbb {R} .}$

What if ${\displaystyle P(x)}$ is "${\displaystyle \forall y\;P_{1}(x,y)}$"? Then we rewrite it as "${\displaystyle \neg \exists y\;\neg P_{1}(x,y)}$" and get the complement of the projection of the complement of the relation corresponding to ${\displaystyle P_{1}(x,y).}$

So, we accept the 3 given relations (order, addition, multiplication) as "definable", and we accept the 5 operations (complement, union, permutation, set multiplication, projection) for producing definable relations out of other definable relations. Thus we get infinitely many definable relations (unary, binary, ternary and so on).

More formally, these relations are called "first-order definable (without parameters) over ${\displaystyle (\mathbb {R} ;\leq ,+,\times )}$"; but, less formally, "definable over" is often replaced with "definable in" (and sometimes "definable from"); "without parameters" is omitted throughout this essay; also "first order" and "over ${\displaystyle (\mathbb {R} ;\dots )}$" are often omitted in this section. See Wikipedia: Definable set: Definition; The field of real numbers.

Generally, starting from a set (not necessarily the real line) and some chosen relations on this set (including the equality relation if needed), and applying the 5 operations (complement, union, permutation, set multiplication, projection) repeatedly (in all possible combinations), one obtains an infinite collection of relations (unary, binary, ternary and so on) on the given set. Every such collection of relations is called a structure (Booij [7]), or a VDD-structure (Brian Tyrrell [9]) on the given set. According to Tyrrell [9, page 3], "The advantage of this definition is that no model theory is then needed to develop the theory". The technical term "VDD structure" (rather than just "structure" used by van den Dries and Booij) is chosen by Tyrrell "to prevent a notation clash" (Tyrrell [9, page 2]), since many other structures of different kinds are widely used in mathematics. "VDD" apparently refers to van den Dries who pioneered this approach. But let us take a shorter term "D-structure", where "D" refers to "definable" and "Dries" as well. The D-structure obtained (by the 5 operations) from the chosen relations, in other words, generated by these relations, is the smallest D-structure containing these relations.

Generality aside, we return to the special case, the D-structure of definable relations on the real line defined above (generated by order, addition and multiplication; though, the order appears to be superfluous).

• Exercise 2.1. Prove that a relation is definable in ${\displaystyle (\mathbb {R} ;\leq ,+,\times )}$ if and only if it is definable in ${\displaystyle (\mathbb {R} ;+,\times ).}$  Hint: ${\displaystyle x\leq y}$ if and only if ${\displaystyle \exists z\in \mathbb {R} \;(x+z^{2}=y).}$

We say that a number ${\displaystyle x}$ is definable, if the single-element set ${\displaystyle \{x\}}$ is a definable unary relation.

• Exercise 2.2. Prove that the numbers 0 and 1 are definable.  Hint: recall "${\displaystyle \forall y\;(x+y=y)}$" and "${\displaystyle \forall y\;(x\cdot y=y)}$".
• Exercise 2.3. Prove that the sum of two definable numbers is definable.  Hint: ${\displaystyle \exists y\in \mathbb {R} \;\exists z\in \mathbb {R} \;\,{\big (}(y\in A_{1})\land (z\in A_{2})\land (y+z=x){\big )}.}$
• Exercise 2.4. Prove that the number ${\displaystyle {\frac {355}{113}}}$ is definable.  Hint: ${\displaystyle \exists y\in \mathbb {R} \;\exists z\in \mathbb {R} \;\,(y=113\land z=355\land xy=z).}$
• Exercise 2.5. Prove that the number ${\displaystyle {\sqrt {2}}}$ is definable.  Hint: ${\displaystyle (x>0)\land (x\cdot x=2).}$
• Exercise 2.6. Prove that the golden ratio ${\displaystyle \varphi }$ is definable.
• Exercise 2.7. Prove that the binary relation "${\displaystyle y=|x|}$" is definable.  Hint: ${\displaystyle (x^{2}=y^{2}\land y\geq 0).}$

In contrast, the ternary relation "${\displaystyle x^{y}=z}$" is not definable. Moreover, the binary relation ${\displaystyle \{(x,y)\mid y=2^{x}\land 0\leq x\leq 1\}}$ is not definable. The problem is that all relations definable in ${\displaystyle (\mathbb {R} ;+,\times )}$ are semialgebraic sets over (the subring of) integers.

Proofs

Theorem. All relations definable in ${\displaystyle (\mathbb {R} ;+,\times )}$ are semialgebraic sets over integers.

Proof. The two relations "${\displaystyle +}$", "${\displaystyle \times }$" are semialgebraic (evidently). Two operations, permutation and set multiplication, applied to semialgebraic relations, give semialgebraic relations (evidently). The third, projection operation, applied to a semialgebraic relation, gives a semialgebraic relation by the Tarski–Seidenberg theorem [10, Theorem 2.76].

Theorem. If ${\displaystyle a>1}$ and ${\displaystyle -\infty then the binary relation ${\displaystyle \{(x,y)\mid (y=a^{x})\land (b\leq x\leq c)\}}$ is not semialgebraic.

Proof. Assume the contrary. Then the function ${\displaystyle x\mapsto a^{x}}$ on ${\displaystyle [b,c],}$ being semialgebraic, must be algebraic [10, Prop. 2.86], [11, Corollary 3.5]). It means existence of a polynomial ${\displaystyle p(\cdot ,\cdot )}$ (not identically 0) such that ${\displaystyle p(x,a^{x})=0}$ for all ${\displaystyle x\in [b,c].}$ It follows that ${\displaystyle p(z,e^{z\log a})=0}$ for all complex numbers ${\displaystyle z.}$ Taking ${\displaystyle z={\tfrac {2n\pi i}{\log a}}}$ we get ${\displaystyle p{\big (}{\tfrac {2n\pi i}{\log a}},1{\big )}=0}$ for all integer ${\displaystyle n.}$ Therefore ${\displaystyle p(z,1)=0}$ for all complex ${\displaystyle z}$ (otherwise the polynomial ${\displaystyle z\mapsto p(z,1)}$ cannot have infinitely many roots). Similarly, taking ${\displaystyle z={\tfrac {\log u+2n\pi i}{\log a}}}$ we get ${\displaystyle p(z,u)=0}$ for all complex ${\displaystyle z}$ and all ${\displaystyle u>0,}$ therefore everywhere; a contradiction.

Thus, we cannot define the number ${\displaystyle e}$ via ${\displaystyle (1+x)^{1/x}}$ in this framework. Also, only algebraic numbers are definable in this framework.

Each natural number is definable, which does not mean that the set ${\displaystyle \mathbb {N} }$ of all natural numbers is definable (in ${\displaystyle (\mathbb {R} ;+,\times )}$). In fact, it is not!

Proof

Follows immediately from the lemma below.

Lemma. For every semialgebraic subset ${\displaystyle A}$ of ${\displaystyle \mathbb {R} }$ there exists ${\displaystyle a\in \mathbb {R} }$ such that either ${\displaystyle (a,\infty )\subset A}$ or ${\displaystyle (a,\infty )\cap A=\emptyset .}$

Proof. First, the claim holds for every set of the form ${\displaystyle A=\{x\in \mathbb {R} \mid p(x)>0\}}$ where ${\displaystyle p(\cdot )}$ is a polynomial, since either ${\displaystyle p(x)\to +\infty }$ as ${\displaystyle x\to +\infty ,}$ or ${\displaystyle p(x)\to -\infty }$ as ${\displaystyle x\to +\infty ,}$ or ${\displaystyle p(x)}$ is constant. Second, a Boolean operation (union, complement), applied to sets that satisfy the claim, gives a set that satisfies the claim (evidently).

We could accept the set ${\displaystyle \mathbb {N} }$ of natural numbers as definable, that is, turn to definability in ${\displaystyle (\mathbb {R} ;+,\times ,\mathbb {N} ),}$ but does it help to define the number ${\displaystyle e}$? Surprisingly, it does! "[...] then the situation changes drastically" (van den Dries [5, Example 1.3]). See also Booij [7, page 17]: "[...] if we add the seemingly innocent set Z to the tame structure of semialgebraic sets, we get a wild structure [...]"

## Beyond the algebraic

In this section, "definable" means "first order definable in ${\displaystyle (\mathbb {R} ;+,\times ,\mathbb {N} )}$". In other words, the real line is endowed with the D-structure generated by addition, multiplication, and the set of natural numbers. Good news: we'll see that the five numbers ${\displaystyle {\sqrt {2}},\varphi ,e,\pi ,\Omega ,}$ discussed in Introduction, are definable. Bad news: in addition to their usual definitions we'll use Diophantine equations, computability and Matiyasevich's theorem (mentioned in Introduction in relation to Chaitin's constant). The reader not acquainted with computability theory should rely on intuitive idea of computation (instead of formal proofs of computability), and consult the linked Wikipedia article for computability-related notions ("recursively enumerable", "computable sequence"). Alternatively, the reader may skip to Section 5; there, usual definitions will apply, no computability needed.

Every Diophantine set

${\displaystyle \{(a_{1},\dots ,a_{n})\in \mathbb {N} ^{n}\mid \exists x_{1},\dots ,x_{m}\in \mathbb {N} \;\;p(a_{1},\dots ,a_{n},\,x_{1},\dots ,x_{m})=0\}}$

(where ${\displaystyle p(\dots )}$ is a polynomial with integer coefficients), treated as a subset of ${\displaystyle \mathbb {R} ^{n},}$ is a definable n-ary relation. And every recursively enumerable set is Diophantine.

For every computable sequence ${\displaystyle (k_{1},k_{2},\dots )}$ of natural numbers, the binary relation ${\displaystyle \{(n,k)\in \mathbb {N} ^{2}\mid k=k_{n}\}=\{(1,k_{1}),(2,k_{2}),\dots \}}$ is recursively enumerable, therefore definable.

In particular, the binary relation "${\displaystyle x\in \mathbb {N} }$ and ${\displaystyle y=x^{x}}$" is definable, as well as "${\displaystyle x\in \mathbb {N} }$ and ${\displaystyle y=(x+1)^{x}}$". Now (at last!) the number ${\displaystyle e}$ is definable, via ${\displaystyle \lim _{n\to \infty }(1+{\tfrac {1}{n}})^{n}=\lim _{n\to \infty }{\tfrac {(n+1)^{n}}{n^{n}}};}$ more formally, ${\displaystyle e}$ is the real number satisfying the condition

${\displaystyle \forall \varepsilon >0\;\exists n\in \mathbb {N} \;\forall m\in \mathbb {N} \;\;{\big (}m\geq n\Longrightarrow -\varepsilon m^{m}<(m+1)^{m}-em^{m}<\varepsilon m^{m}{\big )}.}$

This is not quite the definition mentioned in Introduction, but equivalent to it.

Similarly, for every convergent computable sequence of rational numbers, its limit is a definable number. In other words, every limit computable real number is definable.

Every computable real number is limit computable, therefore definable. In particular, the number ${\displaystyle \pi }$ is computable, therefore definable.

Chaitin's constant is not computable, but still, limit computable (recall Introduction: it is the limit of a computable increasing sequence of rational numbers), therefore definable. So, all the five constants discussed in Introduction (taken from the book "Mathematical constants") are definable. Moreover, all the constants discussed in that book are definable.

On the other hand, if we choose a number between 0 and 1 at random, according to the uniform distribution, we almost surely get an undefinable number, because the definable numbers are a countable set.

Of course, such a randomly chosen undefinable number is not an explicit example of undefinable number. It may seem that "explicit example of undefinable number" is a patent nonsense, just as "defined undefinable number". But no, not quite nonsense, see Section 4.

An infinite sequence ${\displaystyle (x_{1},x_{2},\dots )=(x_{n})_{n}}$ of real numbers is nothing but the binary relation ${\displaystyle \{(n,x)\mid n\in \mathbb {N} \land x=x_{n}\}=}$ ${\displaystyle \{(1,x_{1}),(2,x_{2}),\dots \};}$ if this binary relation is definable, we say that the sequence is definable. If a sequence is definable, then all its members are definable numbers. However, a sequence of definable numbers is generally not definable.

• Exercise 3.1. If a definable sequence converges, then its limit is a definable number. Prove it.

A function ${\displaystyle f:\mathbb {R} \to \mathbb {R} }$ is nothing but the binary relation "${\displaystyle f(x)=y}$", that is, ${\displaystyle A=\{(x,y)\mid f(x)=y\};}$ if this binary relation is definable, we say that the function is definable. An arbitrary binary relation ${\displaystyle A}$ is a function if and only if for every ${\displaystyle x}$ there exists one and only one ${\displaystyle y}$ such that ${\displaystyle (x,y)\in A.}$

• Exercise 3.2. If ${\displaystyle f}$ is a definable function and ${\displaystyle x}$ is a definable number, then ${\displaystyle f(x)}$ is a definable number. Prove it.

However, a function that has definable values at all definable arguments is generally not definable.

• Exercise 3.3. If a definable function is differentiable, then its derivative is a definable function. Prove it.  Hint: the derivative is the limit of...
• Exercise 3.4. If a definable function ${\displaystyle f}$ is continuous, then its antiderivative ${\displaystyle F}$ is definable if and only if ${\displaystyle F(0)}$ is a definable number. Prove it.  Hint: ${\displaystyle \textstyle F(x)=F(0)+\lim _{n\to \infty }{\frac {x}{n}}\sum _{k=1}^{n}f({\frac {k}{n}}x).}$

Similarly to the number ${\displaystyle e}$ we can treat the exponential function ${\displaystyle x\mapsto e^{x}.}$ First, the relation ${\displaystyle \textstyle {\big \{}(n,p,q,u)\mid n\in \mathbb {N} \land p\in \mathbb {N} \land q\in \mathbb {N} \land u={\big (}1+{\frac {p}{q}}\cdot {\frac {1}{n}}{\big )}^{n}{\big \}}}$ is definable (since ${\displaystyle \textstyle {\big (}1+{\frac {p}{q}}\cdot {\frac {1}{n}}{\big )}^{n}}$ is a computable function of ${\displaystyle n,p,q}$). Second, the relation ${\displaystyle \{(x,y)\mid y=e^{x}\}}$ is definable, since ${\displaystyle e^{x}}$ is the limit of ${\displaystyle \textstyle {\big (}1+{\frac {p}{q}}\cdot {\frac {1}{n}}{\big )}^{n}}$ as ${\displaystyle n}$ tends to infinity and ${\displaystyle {\tfrac {p}{q}}}$ tends to ${\displaystyle x;}$ more formally (but still not completely formally...), ${\displaystyle y=e^{x}}$ if and only if

${\displaystyle \forall \varepsilon >0\;\exists \delta >0\;\forall n\in \mathbb {N} \,\forall p\in \mathbb {Z} \,\forall q\in \mathbb {N} \,\forall u\;\;{\bigg (}{\Big (}n\geq {\frac {1}{\delta }}{\Big )}\land {\Big (}-\delta

here ${\displaystyle \mathbb {Z} }$ is the set of integers (evidently definable).

The cosine function may be treated via complex numbers and Euler's formula ${\displaystyle e^{ix}=\cos x+i\sin x.}$ First, the real part of the complex number ${\displaystyle \textstyle {\big (}1+i{\frac {p}{q}}\cdot {\frac {1}{n}}{\big )}^{n}}$ is a computable function of ${\displaystyle n,p,q.}$ Second, its limit as ${\displaystyle n}$ tends to infinity and ${\displaystyle {\tfrac {p}{q}}}$ tends to ${\displaystyle x}$ is equal to the real part ${\displaystyle \cos x}$ of the complex number ${\displaystyle e^{ix}.}$

Note that the exponential integral ${\displaystyle \operatorname {Ei} (x)}$ and the sine integral ${\displaystyle \operatorname {Si} (x)}$ are definable nonelementary functions.

Definable functions can be pathological and disrespect dimension. In particular, there is a definable one-to-one correspondence between the (two-dimensional) square ${\displaystyle (0,1)\times (0,1)}$ and a subset of the (one-dimensional) interval ${\displaystyle (0,1),}$ which will be used in Section 6. Here is a way to this fact.

Given two numbers ${\displaystyle x,y\in (0,1),}$ we consider their decimal digits: ${\displaystyle \textstyle x=(0.\alpha _{1}\alpha _{2}\dots )_{10}=\sum _{n=1}^{\infty }10^{-n}\alpha _{n}}$ where ${\displaystyle \alpha _{n}\in \{0,1,2,3,4,5,6,7,8,9\}}$ for each ${\displaystyle n,}$ and the set ${\displaystyle \{n:\alpha _{n}\neq 9\}}$ is infinite (since we represent, say, ${\displaystyle {\tfrac {1}{2}}}$ as ${\displaystyle (0.5000\dots )_{10}}$ rather than ${\displaystyle (0.4999\dots )_{10}}$); and similarly ${\displaystyle y=(0.\beta _{1}\beta _{2}\dots )_{10}.}$ We interweave their digits, getting a third number ${\displaystyle z=(0.\alpha _{1}\beta _{1}\alpha _{2}\beta _{2}\dots )_{10}\in (0,1).}$ The ternary relation between such ${\displaystyle x,y,z}$ is a function ${\displaystyle W_{2}:(0,1)\times (0,1)\to (0,1).}$ Not all numbers of ${\displaystyle (0,1)}$ are of the form ${\displaystyle W_{2}(x,y)}$ (for example, ${\displaystyle \textstyle {\frac {21}{1100}}=(0.01909090\dots )_{10}}$ is not), which does not matter. It does matter that ${\displaystyle x,y}$ are uniquely determined by ${\displaystyle W_{2}(x,y),}$ that is, ${\displaystyle W_{2}(x_{1},y_{1})=W_{2}(x_{2},y_{2})}$ implies ${\displaystyle x_{1}=x_{2}\land y_{1}=y_{2}.}$ In other words, ${\displaystyle W_{2}}$ is an injection ${\displaystyle (0,1)\times (0,1)\to (0,1).}$

Denoting by ${\displaystyle D(n,x)}$ the ${\displaystyle n}$-th decimal digit ${\displaystyle \alpha _{n}}$ of ${\displaystyle x\in (0,1)}$ we have ${\displaystyle D(n,x)=\lfloor 10\cdot \operatorname {frac} (10^{n-1}x)\rfloor ;}$ here ${\displaystyle \lfloor a\rfloor }$ is the integer part of ${\displaystyle a,}$ and ${\displaystyle \operatorname {frac} (a)=a-\lfloor a\rfloor }$ is the fractional part of ${\displaystyle a.}$

• Exercise 3.5. The integer part function is definable. Prove it.  Hint: ${\displaystyle \{(x,\lfloor x\rfloor )\mid x>0\}=\{(x,n)\mid x>0\land n+1\in \mathbb {N} \land n\leq x
• Exercise 3.6. The function ${\displaystyle D:\mathbb {N} \times (0,1)\to \mathbb {R} }$ is definable. (See Booij [7, Lemma 3.4].) Prove it.  Hint: ${\displaystyle D(n,x)=d\Longleftrightarrow \exists k\in \mathbb {N} \;\;\exists y\in \mathbb {R} \;\;{\big (}k=10^{n-1}\land y=\operatorname {frac} (kx)\land d=\lfloor 10y\rfloor {\big )}.}$
• Exercise 3.7. The function ${\displaystyle W_{2}:(0,1)^{2}\to (0,1)}$ is definable. Prove it.  Hint: ${\displaystyle z=W_{2}(x,y)\Longleftrightarrow \forall n\in \mathbb {N} \;\;{\big (}D(2n,z)=D(n,y)\land D(2n-1,z)=D(n,x){\big )}.}$
• Exercise 3.8. Generalize the previous exercise to ${\displaystyle W_{3}:(0,1)^{3}\to (0,1).}$  Hint: consider ${\displaystyle D(3n-2,z),}$ ${\displaystyle D(3n-1,z),}$ ${\displaystyle D(3n,z).}$

## Explicit example of undefinable number

We construct such example in two steps. First, we enumerate all numbers definable in ${\displaystyle (\mathbb {R} ;+,\times ,\mathbb {N} )}$ ("first order" is meant but omitted, as before); that is, we construct a sequence ${\displaystyle (x_{1},x_{2},\dots )}$ of real numbers that contains all numbers definable in ${\displaystyle (\mathbb {R} ;+,\times ,\mathbb {N} )}$ (and only such numbers). Second, we construct a real number not contained in this sequence.

The second step is well-known and simple, so let us do it now, for an arbitrary sequence ${\displaystyle (x_{1},x_{2},\dots )}$ of real numbers. We construct a real number ${\displaystyle x}$ via its decimal digits, as ${\displaystyle \textstyle x=\sum _{n=1}^{\infty }{\frac {\alpha _{n}}{10^{n}}},}$ and we choose each ${\displaystyle \alpha _{n}}$ to be different from the n-th digit (after the decimal point) of the absolute value ${\displaystyle |x_{n}|}$ of ${\displaystyle x_{n}.}$ To be specific, let us take ${\displaystyle \alpha _{n}=3}$ if ${\displaystyle 10k+7\leq 10^{n}|x_{n}|<10k+8}$ for some integer ${\displaystyle k,}$ and ${\displaystyle \alpha _{n}=7}$ otherwise. Then ${\displaystyle x\neq x_{n}}$ since the integral part of ${\displaystyle 10^{n}|x|,}$ being of the form ${\displaystyle 10\ell +\alpha _{n}}$ for integer ${\displaystyle \ell ,}$ is different from the integral part of ${\displaystyle 10^{n}|x_{n}|,}$ the latter being of the form ${\displaystyle 10k+\beta _{n}}$ for integer ${\displaystyle k,}$ and ${\displaystyle \alpha _{n}\neq \beta _{n}}$ (either ${\displaystyle \beta _{n}=7,\alpha _{n}=3}$ or ${\displaystyle \beta _{n}\neq 7,\alpha _{n}=7}$). This is an instance of Cantor's diagonal argument.

Now we start constructing a sequence ${\displaystyle (x_{1},x_{2},\dots )}$ of real numbers that contains all numbers definable in ${\displaystyle (\mathbb {R} ;+,\times ,\mathbb {N} )}$ (and only such numbers). These numbers being elements of single-element subsets of ${\displaystyle \mathbb {R} }$ definable in ${\displaystyle (\mathbb {R} ;+,\times ,\mathbb {N} ),}$ and these subsets being unary relations, we enumerate all relations (unary, binary, ...) definable in ${\displaystyle (\mathbb {R} ;+,\times ,\mathbb {N} ).}$ These are obtained from the three given relations (addition, multiplication, "naturality") via the 5 operations (complement, union, permutation, set multiplication, projection) applied repeatedly. We may save on permutations by restricting ourselves to adjacent transpositions, that is, permutations that swap two adjacent numbers ${\displaystyle k,k+1}$ and leave intact other numbers of ${\displaystyle \{1,\dots ,n\};}$ this is sufficient, since every permutation is a product of some adjacent transpositions. We start with the three given relations

${\displaystyle A_{1}=\{(x,y,z)\mid x+y=z\},\quad }$ "addition"
${\displaystyle A_{2}=\{(x,y,z)\mid xy=z\},\quad }$ "multiplication"
${\displaystyle A_{3}=\mathbb {N} ,\quad }$ "naturality"

and apply to them the five operations (whenever possible). The first operation "complement" gives

${\displaystyle A_{4}=\{(x,y,z)\mid x+y\neq z\},}$
${\displaystyle A_{5}=\{(x,y,z)\mid xy\neq z\},}$
${\displaystyle A_{6}=\{x\mid x\notin \mathbb {N} \}.}$

The "union" operation gives

${\displaystyle A_{7}=\{(x,y,z)\mid (x+y=z)\lor (xy=z)\}.}$

The "permutation" operation (reduced to adjacent transpositions), applied to the ternary relation ${\displaystyle A_{1},}$ gives two relations ${\displaystyle A_{8},A_{9};}$ namely, ${\displaystyle A_{8}=\{(x,y,z)\mid y+x=z\}}$ (equal to ${\displaystyle A_{1}}$ due to commutativity, but we do not bother) and ${\displaystyle A_{9}=\{(x,y,z)\mid x+z=y\};}$ we apply the same to ${\displaystyle A_{2}}$ getting ${\displaystyle A_{10},A_{11}.}$ Further, "set multiplication" gives the 4-ary relation

${\displaystyle A_{12}=\{(x,y,z,w)\mid x+y=z\},}$

similarly ${\displaystyle A_{13},}$ and ${\displaystyle A_{14}=\{(x,y)\mid x\in \mathbb {N} \}}$. The most remarkable "projection" operation gives

${\displaystyle A_{15}=\{(x,y)\mid \exists z\;(x+y=z)\}\quad }$

(in fact, ${\displaystyle A_{15}=\mathbb {R} ^{2}}$), and similarly ${\displaystyle A_{16}.}$

The first 16 relations ${\displaystyle A_{1},\dots ,A_{16}}$ are thus constructed. On the next iteration we apply the 5 operations to these 16 relations (whenever possible; though, some are superfluous) and get a longer finite list. And so on, endlessly. A bit cumbersome, but really, a routine exercise in programming, isn't it? Well, it is, provided however that the "programming language" stipulates the data type "relation over ${\displaystyle \mathbb {R} }$" and the relevant operations on relations. By the way, equality test for relations is not needed (unless we want to skip repetitions); but test of existence and uniqueness (for unary relations), and extraction of the unique element, are needed for the next step.

Now we are in position to construct ${\displaystyle x_{n};}$ for each ${\displaystyle n}$ we check, whether the relation ${\displaystyle A_{n}}$ is of the form ${\displaystyle \{u\}}$ for ${\displaystyle u\in \mathbb {R} }$ or not; if it is, we take ${\displaystyle x_{n}=u,}$ otherwise ${\displaystyle x_{n}=0.}$ (Note that ${\displaystyle x_{n}=0}$ whenever the relation ${\displaystyle A_{n}}$ is not unary.)

Applying the diagonal argument (above) to this sequence ${\displaystyle (x_{1},x_{2},\dots )}$ we construct a real number ${\displaystyle x}$ not contained in the sequence, therefore, not definable in ${\displaystyle (\mathbb {R} ;+,\times ,\mathbb {N} ).}$

This number ${\displaystyle x}$ is defined, but not in ${\displaystyle (\mathbb {R} ;+,\times ,\mathbb {N} ).}$ Why not? Because the definition of ${\displaystyle x}$ involves a sequence of relations on ${\displaystyle \mathbb {R} .}$ Sequences of numbers are used in Section 3, but sequences of relations are something new, beyond the first order. (See Wikipedia: First-order logic, Second-order logic.)

Is there a better approach? Could we define in ${\displaystyle (\mathbb {R} ;+,\times ,\mathbb {N} )}$ the same sequence ${\displaystyle (x_{1},x_{2},\dots ),}$ or maybe another sequence containing all computable numbers, by a clever trick? No, this is impossible. For every sequence definable in ${\displaystyle (\mathbb {R} ;+,\times ,\mathbb {N} )}$ the diagonal argument gives a number definable in ${\displaystyle (\mathbb {R} ;+,\times ,\mathbb {N} )}$ and not contained in the given sequence.

## Second order

We introduce second-order definability in ${\displaystyle (\mathbb {R} ;+,\times ).}$ The set ${\displaystyle \mathbb {N} }$ of natural numbers is second-order definable in ${\displaystyle (\mathbb {R} ;+,\times ),}$ as we'll see soon. In contrast to the first order definability, usual definitions of mathematical constants will apply without recourse to computability and Diophantine sets.

A second-order predicate is a predicate that takes a first-order predicate as an argument. Likewise, a second-order relation is a relation between relations. For example, the binary relation ${\displaystyle f'=g}$ between a function ${\displaystyle f}$ and its derivative ${\displaystyle g}$ may be thought of as a relation between two binary relations: first, the relation ${\displaystyle f(x)=y}$ between real numbers ${\displaystyle x,y,}$ and second, the relation ${\displaystyle g(t)=v}$ between real numbers ${\displaystyle t,v.}$ First order definability of a real number involves definable first-order relations (between real numbers). Second order definability of a real number involves definable second-order relations (between first-order relations). Here is a possible formalization of this idea.

We introduce the set

${\displaystyle \mathbf {S} ={\big (}\mathbb {R} \cup \mathbb {R} ^{2}\cup \mathbb {R} ^{3}\cup \dots {\big )}\cup {\big (}\operatorname {P} (\mathbb {R} )\cup \operatorname {P} (\mathbb {R} ^{2})\cup \operatorname {P} (\mathbb {R} ^{3})\cup \dots {\big )}={\bigg (}\bigcup _{n=1}^{\infty }\mathbb {R} ^{n}{\bigg )}\cup {\bigg (}\bigcup _{n=1}^{\infty }\operatorname {P} (\mathbb {R} ^{n}){\bigg )}}$

that contains, on one hand, all tuples (finite sequences) ${\displaystyle (x_{1},\dots ,x_{n})\in \mathbb {R} ^{n}}$ of real numbers (for all ${\displaystyle n}$; here we do not distinguish 1-tuples from real numbers), and on the other hand, all ${\displaystyle n}$-ary relations ${\displaystyle A\subset \mathbb {R} ^{n}}$ on ${\displaystyle \mathbb {R} }$ (for all ${\displaystyle n}$). Here ${\displaystyle \operatorname {P} (\mathbb {R} )}$ is the set of all subsets (that is, the power set) of the real line ${\displaystyle \mathbb {R} ,}$ in other words, of unary relations on ${\displaystyle \mathbb {R} ;}$ ${\displaystyle \operatorname {P} (\mathbb {R} ^{2})}$ is the set of all subsets (that is, the power set) of the Cartesian plane ${\displaystyle \mathbb {R} ^{2},}$ in other words, of binary relations on ${\displaystyle \mathbb {R} ;}$ and so on. On this set ${\displaystyle \mathbf {S} }$ we introduce two relations:

• membership, the binary relation ${\displaystyle \cup _{n=1}^{\infty }\{{\big (}(x_{1},\dots ,x_{n}),A{\big )}\mid (x_{1},\dots ,x_{n})\in A\}\subset \mathbf {S} ^{2};}$ it says that the given ${\displaystyle n}$-tuple belongs to the given ${\displaystyle n}$-ary relation;
• "appendment", the ternary relation ${\displaystyle \cup _{n=1}^{\infty }\{{\big (}x,(x_{1},\dots ,x_{n}),(x_{1},\dots ,x_{n},x)\mid x_{1},\dots ,x_{n},x\in \mathbb {R} \}\subset \mathbf {S} ^{3};}$ it says that the latter tuple results from the former tuple by appending the given real number.

The two ternary relations on ${\displaystyle \mathbb {R} ,}$ addition and multiplication, may be thought of as ternary relations on ${\displaystyle \mathbf {S} }$ (since ${\displaystyle \mathbb {R} \subset \mathbf {S} }$):

• addition: ${\displaystyle \{(x,y,z)\mid x,y,z\in \mathbb {R} ,x+y=z\}\subset \mathbf {S} ^{3};}$
• multiplication: ${\displaystyle \{(x,y,z)\mid x,y,z\in \mathbb {R} ,xy=z\}\subset \mathbf {S} ^{3}.}$

We endow ${\displaystyle \mathbf {S} }$ with the D-structure generated by the four relations (membership, appendment, addition, multiplication). All relations on ${\displaystyle \mathbf {S} }$ that belong to this D-structure will be called second-order definable. In the rest of this section, "definable" means "second-order definable", unless stated otherwise.

• Exercise 5.1. The set ${\displaystyle \cup _{n=1}^{\infty }\mathbb {R} ^{n}}$ of all tuples and the set ${\displaystyle \cup _{n=1}^{\infty }\operatorname {P} (\mathbb {R} ^{n})}$ of all relations are definable subsets of ${\displaystyle \mathbf {S} .}$ Prove it.  Hint: first, the set of all tuples is ${\displaystyle \{s\in \mathbf {S} \mid \exists r,t\in \mathbf {S} \;\;(r,s,t)\in A\}}$ where ${\displaystyle A}$ is the appendment relation; second, take the complement.
• Exercise 5.2. The set ${\displaystyle \mathbb {R} }$ of all real numbers is a definable subset of ${\displaystyle \mathbf {S} .}$ Prove it.  Hint: ${\displaystyle \mathbb {R} =\{r\in \mathbf {S} \mid \exists s,t\in \mathbf {S} \;\;(r,s,t)\in A\}}$ where ${\displaystyle A}$ is the appendment relation.
• Exercise 5.3. Each ${\displaystyle \mathbb {R} ^{n}}$ is a definable subset of ${\displaystyle \mathbf {S} .}$ Prove it.  Hint: ${\displaystyle \mathbb {R} ^{n+1}=\{t\in \mathbf {S} \mid \exists r\in \mathbb {R} \;\exists s\in \mathbb {R} ^{n}\;\;(r,s,t)\in A\}}$ where ${\displaystyle A}$ is the appendment relation.
• Exercise 5.4. The set ${\displaystyle \operatorname {P} (\mathbb {R} )}$ of all sets of real numbers (that is, unary relations) is a definable subset of ${\displaystyle \mathbf {S} .}$ Prove it.  Hint: for ${\displaystyle A\in \cup _{n=1}^{\infty }\operatorname {P} (\mathbb {R} ^{n})}$ we have ${\displaystyle A\in \operatorname {P} (\mathbb {R} )\Longleftrightarrow A\subset \mathbb {R} \Longleftrightarrow (\forall a\in A\;\;a\in \mathbb {R} )\Longleftrightarrow \neg (\exists a\in A\;\;a\notin \mathbb {R} );}$ apply the projection to ${\displaystyle \{(A,a)\mid A\in \cup _{n=1}^{\infty }\operatorname {P} (\mathbb {R} ^{n})\land a\in A\land a\notin \mathbb {R} \}.}$
• Exercise 5.5. For each ${\displaystyle n}$ the set ${\displaystyle \operatorname {P} (\mathbb {R} ^{n})}$ of all ${\displaystyle n}$-ary relations is a definable subset of ${\displaystyle \mathbf {S} .}$ Prove it.  Hint: similar to the previous exercise.
• Exercise 5.6. If ${\displaystyle B\subset \operatorname {P} (\mathbb {R} )}$ is a definable set of subsets of ${\displaystyle \mathbb {R} }$, then the union ${\displaystyle \cup _{A\in B}A}$ of all these subsets is a definable set (of real numbers). Prove it.  Hint: for ${\displaystyle x\in \mathbb {R} }$ we have ${\displaystyle x\in \cup _{A\in B}A\Longleftrightarrow \exists A\;\;(A\in B\land x\in A);}$ take the projection of ${\displaystyle \{(x,A)\mid A\in B\land x\in A\}=(\mathbb {R} \times B)\cap \{(x,A)\mid x\in A\}.}$
• Exercise 5.7. Do the same for the intersection ${\displaystyle \cap _{A\in B}A.}$  Hint: ${\displaystyle \cap _{A\in B}A=\mathbb {R} \setminus \cup _{A\in B}(\mathbb {R} \setminus A);}$ consider ${\displaystyle \{(x,A)\mid A\in B\land x\in \mathbb {R} \setminus A\}=(\mathbb {R} \times B)\cap \{(x,A)\mid x\notin A\}.}$ (But what if ${\displaystyle B}$ is empty?)
• Exercise 5.8. Generalize the two exercises above to ${\displaystyle B\subset \operatorname {P} (\mathbb {R} ^{2}),}$ ${\displaystyle B\subset \operatorname {P} (\mathbb {R} ^{3})}$ and so on.  Hint: now ${\displaystyle x}$ is a tuple.

In particular, taking a single-element set ${\displaystyle B=\{A\}}$ we see that definability of ${\displaystyle \{A\}}$ implies definability of ${\displaystyle A.}$ The converse holds as well (see below).

• Exercise 5.9. If a set ${\displaystyle A\subset \mathbb {R} }$ (of real numbers) is definable, then the set ${\displaystyle \operatorname {P} (A)}$ (of all subsets of ${\displaystyle A}$) is definable. Prove it.  Hint: for ${\displaystyle A_{1}\in \operatorname {P} (\mathbb {R} )}$ we have ${\displaystyle A_{1}\in \operatorname {P} (A)\Longleftrightarrow A_{1}\subset A\Longleftrightarrow (\forall x\in A_{1}\;\;x\in A)\Longleftrightarrow \neg (\exists x\in A_{1}\;\;x\notin A);}$ consider ${\displaystyle \{(A_{1},x)\mid A_{1}\in \operatorname {P} (\mathbb {R} )\land x\in \mathbb {R} \land x\in A_{1}\land x\notin A\}={\big (}\operatorname {P} (\mathbb {R} )\times (\mathbb {R} \setminus A){\big )}\cap \{(A_{1},x)\mid x\in A_{1}\}.}$
• Exercise 5.10. Do the same for the set ${\displaystyle \{A_{1}\in \operatorname {P} (\mathbb {R} )\mid A_{1}\supset A\}}$ (of all supersets of ${\displaystyle A}$).  Hint: similarly to the previous exercise, consider ${\displaystyle {\big (}P(\mathbb {R} )\times A{\big )}\cap \{(A_{1},x)\mid x\notin A_{1}\}.}$
• Exercise 5.11. Generalize the two exercises above to ${\displaystyle A\subset \mathbb {R} ^{2},}$ ${\displaystyle A\subset \mathbb {R} ^{3}}$ and so on.

Remark.   These 11 exercises (above) do not use addition and multiplication, nor any properties of real numbers. They generalize readily to a more general situation. One may start with an arbitrary set ${\displaystyle R}$ (rather than the real line ${\displaystyle \mathbb {R} }$), consider the set ${\displaystyle S}$ constructed from ${\displaystyle R}$ as above (all tuples and all relations), endow ${\displaystyle S}$ by a D-structure such that the two relations on ${\displaystyle S}$, membership and appendment, are definable, and generalize the 11 exercises to this case.

Taking the intersection of the set of subsets and the set of supersets we see that definability of ${\displaystyle A}$ implies definability of the single-element set (called singleton) ${\displaystyle B=\{A\}.}$ So, ${\displaystyle A}$ is definable if and only if ${\displaystyle \{A\}}$ is definable. And still (by convention, as before) a real number ${\displaystyle x}$ is definable if and only if ${\displaystyle \{x\}}$ is definable.

Does it mean that, for example, numbers ${\displaystyle 0,}$ ${\displaystyle 1,}$ ${\displaystyle {\sqrt {2}}}$ are definable (as well as every rational number and every algebraic number)? We know that they are first-order definable in ${\displaystyle (\mathbb {R} ;+,\times );}$ does it follow that they are (second-order) definable in ${\displaystyle \mathbf {S} ?}$

The answer is affirmative, but needs a proof. Here we face another general question. Let ${\displaystyle S}$ be a set and ${\displaystyle R\subset S}$ its subset. Every ${\displaystyle n}$-ary relation on ${\displaystyle R}$ is also a ${\displaystyle n}$-ary relation on ${\displaystyle S}$ (since ${\displaystyle R\subset S\Longrightarrow R^{n}\subset S^{n}\Longrightarrow \operatorname {P} (R^{n})\subset \operatorname {P} (S^{n})}$). Thus, given some relations on ${\displaystyle R,}$ we get two D-structures; first, the D-structure on ${\displaystyle R}$ generated by the given relations, and second, the D-structure on ${\displaystyle S}$ generated by the same relations.

Lemma.   Assume that ${\displaystyle R}$ is a definable subset of ${\displaystyle S}$ (according to the second D-structure). Then every relation on ${\displaystyle R}$ definable according to the first D-structure is also definable according to the second D-structure.

Proof

Denote the first D-structure by ${\displaystyle D_{R}}$ and the second by ${\displaystyle D_{S}.}$ We know that ${\displaystyle R\in D_{S}.}$ It follows (via set multiplication) that ${\displaystyle R\times S\in D_{S},}$ ${\displaystyle R\times S\times S=R\times S^{2}\in D_{S},}$ and so on; by induction, ${\displaystyle R\times S^{n}\in D_{S}}$ for all ${\displaystyle n.}$ Thus (via permutation), ${\displaystyle S^{n}\times R\in D_{S}.}$

In order to prove that ${\displaystyle D_{R}\subset D_{S}}$ we compare the five operations on relations (complement, union, permutation, set multiplication, projection) over ${\displaystyle R}$ (call them ${\displaystyle R}$-operations) and over ${\displaystyle S}$ (${\displaystyle S}$-operations). We have to check that each ${\displaystyle R}$-operation applied to relations on ${\displaystyle R}$ that belong to ${\displaystyle D_{S}}$ gives again a relation (on ${\displaystyle R}$) that belongs to ${\displaystyle D_{S}.}$

For the union we have nothing to check, since the ${\displaystyle R}$-union of two relations is equal to their ${\displaystyle S}$-union. Similarly, we have nothing to check for permutation and projection. Only set multiplication and complement need some attention.

Set multiplication. The ${\displaystyle R}$-multiplication applied to ${\displaystyle A\in \operatorname {P} (R^{n})\cap D_{S}}$ gives ${\displaystyle A\times R.}$ We have ${\displaystyle A\times R=(A\times S)\cap (S^{n}\times R)\in D_{S}}$ since ${\displaystyle A\times S\in D_{S}}$ and ${\displaystyle S^{n}\times R\in D_{S}.}$

It follows (by induction) that ${\displaystyle R^{n}\in D_{S}}$ for all ${\displaystyle n.}$

Complement. The ${\displaystyle R}$-complement applied to ${\displaystyle A\in \operatorname {P} (R^{n})\cap D_{S}}$ gives ${\displaystyle R^{n}\setminus A.}$ We note that the ${\displaystyle S}$-complement ${\displaystyle S^{n}\setminus A}$ belongs to ${\displaystyle D_{S}}$ (since ${\displaystyle A\in D_{S}}$), thus ${\displaystyle R^{n}\setminus A=R^{n}\cap (S^{n}\setminus A)\in D_{S}}$ (since ${\displaystyle R^{n}\in D_{S}}$).

Now we are in position to prove definability of the set ${\displaystyle \mathbb {N} }$ of natural numbers. It is sufficient to prove definability of the set ${\displaystyle B\subset \operatorname {P} (\mathbb {R} )}$ of all sets ${\displaystyle A\subset \mathbb {R} }$ satisfying the two conditions ${\displaystyle 1\in A}$ and ${\displaystyle \forall x\in A\;(x+1\in A)}$ (since the intersection of all these ${\displaystyle A}$ is ${\displaystyle \mathbb {N} }$). The complement ${\displaystyle \operatorname {P} (\mathbb {R} )\setminus B=\{A\in \operatorname {P} (\mathbb {R} )\mid \exists x\in \mathbb {R} \;(x\in A\land x+1\notin A)\}}$ is the projection of the intersection of two sets, ${\displaystyle \{(A,x)\in \operatorname {P} (\mathbb {R} )\times \mathbb {R} \mid x\in A\}}$ and ${\displaystyle \{(A,x)\in \operatorname {P} (\mathbb {R} )\times \mathbb {R} \mid x+1\notin A\}.}$ The former results from the (permuted) membership relation; the latter is the projection of the projection of ${\displaystyle \{(A,x,y,z)\in \operatorname {P} (\mathbb {R} )\times \mathbb {R} ^{3}\mid y\in \{1\}\land x+y=z\land z\notin A\},}$ this set being the intersection of three sets: first, ${\displaystyle \operatorname {P} (\mathbb {R} )\times \mathbb {R} \times \{1\}\times \mathbb {R} ;}$ second, ${\displaystyle \operatorname {P} (\mathbb {R} )}$ times the addition relation; third, ${\displaystyle \operatorname {P} (\mathbb {R} )\times \mathbb {R} \times \mathbb {R} \times (\mathbb {R} \setminus A).}$ It follows that ${\displaystyle B}$ is definable, whence ${\displaystyle \textstyle \mathbb {N} =\cap _{A\in B}A}$ is definable.

This is instructive. In order to formalize a definition of a set via its defining property, we have to deal with sets of sets, and more generally, relations between sets.

Using again the lemma above we see that all real numbers first-order definable in ${\displaystyle (\mathbb {R} ;+,\times ,\mathbb {N} )}$ are second-order definable. Section 3 gives many examples, including the five numbers ${\displaystyle {\sqrt {2}},\varphi ,e,\pi ,\Omega ,}$ discussed in Introduction. But second-order proofs of their definability are much more easy and natural.

The binary relation "${\displaystyle x\in \mathbb {N} \land y=x!}$" is the sequence ${\displaystyle (n!)_{n\in \mathbb {N} }}$ of factorials, that is, the set ${\displaystyle \{(1,1),(2,2),(3,6),(4,24),(5,120),\dots \}.}$ It is definable, similarly to ${\displaystyle \mathbb {N} ,}$ since it is the least subset ${\displaystyle A}$ of ${\displaystyle \mathbb {R} ^{2}}$ such that ${\displaystyle (1,1)\in A}$ and ${\displaystyle (x,y)\in A\Longrightarrow {\big (}x+1,(x+1)y{\big )}\in A.}$ Alternatively, it is definable since it is the only subset ${\displaystyle A}$ of ${\displaystyle \mathbb {R} ^{2}}$ with the following three properties: :

${\displaystyle \forall (x,y)\in A\;\;x\in \mathbb {N} ,}$
${\displaystyle \forall x\in \mathbb {N} \;\;\exists !y\in \mathbb {R} \;\;(x,y)\in A,}$
${\displaystyle \forall (x,y)\in A\;\;{\big (}x+1,(x+1)y{\big )}\in A.}$

That is, the factorial is the only function ${\displaystyle \mathbb {N} \to \mathbb {R} }$ satisfying the recurrence relation ${\displaystyle (n+1)!=(n+1)n!}$ and the initial condition ${\displaystyle 1!=1.}$

• Exercise 5.12. Partial sums of the series ${\displaystyle \textstyle \sum _{n=0}^{\infty }{\frac {1}{n!}}}$ are a definable sequence. Prove it.
• Exercise 5.13. The number ${\displaystyle e}$ is definable. Deduce it from the previous exercise.

In the first-order framework it is possible to treat many functions (for instance, the exponential function ${\displaystyle x\mapsto e^{x},}$ the sine and cosine functions ${\displaystyle \sin ,\cos ,}$ the exponential integral ${\displaystyle \operatorname {Ei} }$ and the sine integral ${\displaystyle \operatorname {Si} }$) and many relations between functions (for instance, derivative and antiderivative); arguments and values of these functions are arbitrary real numbers (not necessarily definable), but the functions are definable. Such notions as arbitrary functions (not necessarily definable), continuous functions (and their antiderivatives), differentiable functions (and their derivatives) need the second-order framework.

As was noted there, a function ${\displaystyle f:\mathbb {R} \to \mathbb {R} }$ is nothing but the binary relation "${\displaystyle f(x)=y}$", that is, ${\displaystyle A=\{(x,y)\mid f(x)=y\}.}$ An arbitrary binary relation ${\displaystyle A}$ is such a function if and only if for every ${\displaystyle x}$ there exists one and only one ${\displaystyle y}$ such that ${\displaystyle (x,y)\in A}$ (existence and uniqueness). For functions defined on arbitrary subsets of the real line the condition is weaker: for every ${\displaystyle x}$ there exists at most one ${\displaystyle y}$ such that ${\displaystyle (x,y)\in A}$ (uniqueness).

• Exercise 5.14. (a) All ${\displaystyle A\in \operatorname {P} (\mathbb {R} ^{2})}$ satisfying the uniqueness condition are a definable subset of ${\displaystyle \operatorname {P} (\mathbb {R} ^{2});}$ (b) the same holds for the existence and uniqueness condition. Prove it.
• Exercise 5.15. All continuous functions ${\displaystyle \mathbb {R} \to \mathbb {R} }$ are a definable subset of ${\displaystyle \operatorname {P} (\mathbb {R} ^{2}).}$ Prove it.
• Exercise 5.16. All differentiable functions ${\displaystyle \mathbb {R} \to \mathbb {R} }$ are a definable subset of ${\displaystyle \operatorname {P} (\mathbb {R} ^{2}).}$ Prove it.
• Exercise 5.17. The binary relation "${\displaystyle f'=g}$" is definable. That is, the set of all pairs ${\displaystyle (f,g)}$ of functions ${\displaystyle \mathbb {R} \to \mathbb {R} }$ such that ${\displaystyle \forall x\in \mathbb {R} \;{\big (}f'(x)=g(x){\big )}}$ is a definable subset of ${\displaystyle \operatorname {P} (\mathbb {R} ^{2})\times \operatorname {P} (\mathbb {R} ^{2})}$ (in other words, definable binary relation on ${\displaystyle \operatorname {P} (\mathbb {R} ^{2})}$). Prove it.

Antiderivative can now be treated in full generality. In contrast, in the first-order framework it was treated via Riemann integral ${\displaystyle \textstyle F(x)=F(0)+\lim _{n\to \infty }{\frac {x}{n}}\sum _{k=1}^{n}f({\frac {k}{n}}x)}$ for continuous definable ${\displaystyle f}$ only. In particular, now the exponential function ${\displaystyle x\mapsto e^{x}}$ may be treated via ${\displaystyle f(e^{x})-f(1)=x}$ where ${\displaystyle f'(x)={\tfrac {1}{x}}}$ for ${\displaystyle x>0;}$ accordingly, the constant ${\displaystyle e}$ may be treated via ${\displaystyle f(e)-f(1)=1.}$ Alternatively, the exponential function may be treated via the differential equation ${\displaystyle f'=f}$ (and initial condition ${\displaystyle f(0)=1}$). Trigonometric functions ${\displaystyle \sin ,\cos }$ may be treated via the differential equation ${\displaystyle f''=-f;}$ accordingly, the constant ${\displaystyle \pi }$ may be treated as the least positive number such that ${\displaystyle (f''=-f)\Longrightarrow {\big (}f(\pi )=-f(0){\big )}.}$ Or, alternatively, as ${\displaystyle \textstyle \pi =4\int _{0}^{1}{\sqrt {1-x^{2}}}\,dx}$ (via antiderivative).

This is instructive. In the second-order framework we may define functions (and infinite sequences) via their properties, irrespective of computability, Diophantine equations and other tricks of the first-order framework.

Nice; but what about second-order definable real numbers? Are they all first-order definable, or not? Even if obtained from complicated differential equations, they are computable, therefore, first-order definable in ${\displaystyle (\mathbb {R} ;+,\times ,\mathbb {N} )}$. Probably, our only chance to find a second-order definable but first-order undefinable number is, to prove that the explicit example of (first-order) undefinable number, given in Section 4, is second-order definable; and our only chance to prove this conjecture is, to formalize that section within the second-order framework.

## First-order undefinable but second-order definable

Recall the infinite sequence of relations ${\displaystyle (A_{k})_{k=1}^{\infty }}$ treated in Section 4. Is it second-order definable? Each ${\displaystyle A_{k}}$ belongs to the set ${\displaystyle \mathbf {S} }$ (from Section 5); their infinite sequence is a binary relation between ${\displaystyle k}$ and ${\displaystyle A_{k}}$ (namely, the set of pairs ${\displaystyle \{(1,A_{1}),(2,A_{2}),\dots \}}$), thus, a special case of a binary relation on ${\displaystyle \mathbf {S} ;}$ the question is, whether this relation is definable, or not. Like the sequence of factorials, it is defined by recursion. But factorials, being numbers, are first-order objects, which is why their sequence is second-order definable via its properties. In contrast, relations ${\displaystyle A_{k}}$ are second-order objects! Does it mean that third order is needed for defining their sequence by recursion?

True, the sequence of factorials is first-order definable (in ${\displaystyle (\mathbb {R} ;+,\times ,\mathbb {N} )}$) due to its computability, via Matiyasevich's theorem. Could something like that be invented for second-order objects? Probably not.

Yet, these obstacles are surmountable. The sequence of relations may be replaced with a single relation by a kind of currying (or rather, uncurrying); the disjoint union ${\displaystyle \{1\}\times A_{1}\cup \{2\}\times A_{2}\cup \dots }$ may be used instead of the set of pairs ${\displaystyle \{(1,A_{1}),(2,A_{2}),\dots \}.}$ Further, relations ${\displaystyle A_{k}}$ of different arities may be replaced with unary relations (subsets of the real line), since two real numbers may be encoded into a single real number via an appropriate definable injection ${\displaystyle \mathbb {R} ^{2}\to \mathbb {R} ,}$ and the same applies to three and more numbers (moreover, to infinitely many numbers, see Booij [7, Section 3.2]). In addition, tuples ${\displaystyle (x_{1},\dots ,x_{n})}$ may be replaced (whenever needed) by finite sequences ${\displaystyle (x_{k})_{k=1}^{n}=\{(1,x_{1}),\dots ,(n,x_{n})\},}$ which provides a richer assortment of definable relations.

The distinction between tuples and finite sequences is a technical subtlety that may be ignored in many contexts, but sometimes requires attention. It is tempting to say that an ordered pair ${\displaystyle (a,b),}$ a 2-tuple (that is, tuple of length 2), and a 2-sequence (that is, finite sequence of length 2) are just all the same. However, the 2-sequence is, by definition, a function on ${\displaystyle \{1,2\},}$ thus, the set of two ordered pairs ${\displaystyle \{(1,a),(2,b)\}.}$ Surely we cannot define an ordered pair to be a set of two other ordered pairs! If sequences are defined via functions, and functions are defined via pairs, then pairs must be defined before sequences, and cannot be the same as 2-sequences. See Wikipedia: sequence (formal definition), tuples (as nested ordered pairs), and ordered pair: Kuratowski's definition. For convenience we'll denote a finite sequence ${\displaystyle (x_{k})_{k=1}^{n}=\{(1,x_{1}),\dots ,(n,x_{n})\}}$ by ${\displaystyle [x_{1},\dots ,x_{n}];}$ it is similar to, but different from, the tuple ${\displaystyle (x_{1},\dots ,x_{n}).}$

We'll construct again, this time in the second-order framework, the sequence ${\displaystyle (x_{1},x_{2},\dots )}$ of real numbers that contains all numbers first-order definable in ${\displaystyle (\mathbb {R} ;+,\times ,\mathbb {N} ),}$ exactly the same sequence as in Section 4. To this end we'll construct first the disjoint union ${\displaystyle \{1\}\times B_{1}\cup \{2\}\times B_{2}\cup \dots }$ of unary relations ${\displaystyle B_{k}}$ on ${\displaystyle \mathbb {R} }$ similar to, but different from, relations ${\displaystyle A_{1},A_{2},\dots }$ (unary, binary, ...) constructed there (that exhaust all relations first-order definable in ${\displaystyle (\mathbb {R} ;+,\times ,\mathbb {N} )}$).

Before the unary relations ${\displaystyle B_{k}}$ we construct 4-tuples ${\displaystyle b_{k}}$ of integers (call them "instructions") imitating a program for a machine that computes ${\displaystyle B_{k}.}$ Similarly to a machine language instruction, each ${\displaystyle b_{k}}$ contains an operation code, address of the first operand, a parameter or address of the second operand (if applicable, otherwise 0), and in addition, the arity of ${\displaystyle A_{k}.}$

Recall Section 4. Three relations ${\displaystyle A_{1},A_{2},A_{3}}$ of arities 3,3,1 are given, and lead to the next 13 relations ${\displaystyle A_{4},\dots ,A_{16}.}$ In particular, ${\displaystyle A_{4}}$ is the complement of ${\displaystyle A_{1}.}$ Accordingly, we let ${\displaystyle b_{4}=(1,1,0,3);}$ here, operation code 1 means "complement...", operand address 1 means "...of ${\displaystyle A_{1}}$", the third number 0 is dummy, and the last number 3 means that the relation ${\displaystyle A_{4}}$ is ternary. Similarly, ${\displaystyle b_{5}=(1,2,0,3)}$ and ${\displaystyle b_{6}=(1,3,0,1).}$

Further, ${\displaystyle A_{7}}$ being the union of ${\displaystyle A_{1}}$ and ${\displaystyle A_{2},}$ we let ${\displaystyle b_{7}=(2,1,2,3);}$ operation code 2 means "union...", first operand address 1 means "...of ${\displaystyle A_{1}}$", second operand address 2 means "...and ${\displaystyle A_{2}}$", and again, 3 is the arity of ${\displaystyle A_{7}.}$

Further, ${\displaystyle A_{8}}$ being a permutation of ${\displaystyle A_{1},}$ we let ${\displaystyle b_{8}=(3,1,1,3);}$ operation code 3 means "permutation...", operand address 1 means "...of ${\displaystyle A_{1}}$", the parameter 1 means "swap 1 and 2", and 3 is the arity of ${\displaystyle A_{8}.}$ Similarly, ${\displaystyle b_{9}=(3,1,2,3)}$ (in ${\displaystyle A_{1}}$ swap 2 and 3), ${\displaystyle b_{10}=(3,2,1,3)}$ (in ${\displaystyle A_{2}}$ swap 1 and 2), ${\displaystyle b_{11}=(3,2,2,3)}$ (in ${\displaystyle A_{2}}$ swap 2 and 3).

Further, ${\displaystyle A_{12}}$ being ${\displaystyle A_{1}\times \mathbb {R} ,}$ we let ${\displaystyle b_{12}=(4,1,0,4);}$ operation code 4 means "set multiplication", 1 refers to the operand ${\displaystyle A_{1},}$ and 4 is the arity of ${\displaystyle A_{12}.}$ Similarly, ${\displaystyle b_{13}=(4,2,0,4)}$ and ${\displaystyle b_{14}=(4,3,0,2).}$

Further, ${\displaystyle A_{15}}$ being the projection of ${\displaystyle A_{1},}$ we let ${\displaystyle b_{15}=(5,1,0,2);}$ operation code 5 means "projection...", 1 means "...of ${\displaystyle A_{1}}$", and 2 means "...is binary". Similarly, ${\displaystyle b_{16}=(5,2,0,2).}$

This way, the finite sequence ${\displaystyle [3,3,1]}$ of natural numbers (interpreted as arities) leads to the finite sequence ${\displaystyle [b_{4},\dots ,b_{16}]}$ of 4-tuples (interpreted as instructions). Similarly, every finite sequence of natural numbers leads to the corresponding finite sequence of 4-tuples. The relation between these two finite sequences is definable; the proof is rather cumbersome, like a routine exercise in programming, but doable. Having this relation, we define an infinite sequence of 4-tuples ${\displaystyle b_{k}}$ (interpreted as the infinite "program") together with an infinite sequence ${\displaystyle (k_{n})_{n=1}^{\infty }}$ by the following defining properties:

• ${\displaystyle k_{1}=3;\;\;\;\forall n\in \mathbb {N} \;\;k_{n}
• ${\displaystyle b_{1}=b_{2}=(0,0,0,3);\;b_{3}=(0,0,0,1);}$
• for every ${\displaystyle n=1,2,\dots }$ the finite sequence ${\displaystyle [b_{k_{n}+1},\dots ,b_{k_{n+1}}]}$ of 4-tuples corresponds (according to the definable relation treated above) to the finite sequence of the natural numbers that are the last (fourth) elements of the 4-tuples ${\displaystyle b_{1},\dots ,b_{k_{n}}.}$

In particular, ${\displaystyle k_{1}=3,}$ ${\displaystyle k_{2}=16;}$ the third property for ${\displaystyle n=1}$ states that ${\displaystyle [b_{4},\dots ,b_{16}]}$ corresponds to ${\displaystyle [3,3,1].}$ And for ${\displaystyle n=2}$ it states that ${\displaystyle [b_{17},\dots ,b_{k_{3}}]}$ corresponds to ${\displaystyle [3,3,1,3,3,1,3,3,3,3,3,4,4,2,2,2].}$ And so on.

The infinite program is ready. It could compute all relations ${\displaystyle A_{k}}$ if executed by a machine able to process relations of all arities. Is such machine available in our framework? The disjoint union ${\displaystyle \{1\}\times A_{1}\cup \{2\}\times A_{2}\cup \dots }$ could be used instead of the set of pairs ${\displaystyle \{(1,A_{1}),(2,A_{2}),\dots \},}$ but is not contained in (say) ${\displaystyle \mathbb {R} ^{100}.}$ True, in practice 100-ary relations do not occur in definitions; but we investigate definability in principle (rather than in practice). We encode all relation into unary relations as follows.

We recall the definable injective functions ${\displaystyle W_{2}:(0,1)^{2}\to (0,1)}$ and ${\displaystyle W_{3}:(0,1)^{3}\to (0,1)}$ treated in the end of Section 3. The same works for any ${\displaystyle (0,1)^{m}.}$ But we need to serve all dimensions ${\displaystyle m}$ by a single definable function. To this end we turn from sets ${\displaystyle \mathbb {R} ^{m}}$ of ${\displaystyle m}$-tuples ${\displaystyle (x_{1},\dots ,x_{m})}$ to sets, denote them ${\displaystyle \mathbb {R} ^{[m]},}$ of ${\displaystyle m}$-sequences ${\displaystyle [x_{1},\dots ,x_{m}].}$

• Exercise 6.1. The set of all finite sequences of real numbers, ${\displaystyle \{[x_{1},\dots ,x_{m}]\mid m\in \mathbb {N} ,\,x_{1},\dots ,x_{m}\in \mathbb {R} \}=\cup _{m=1}^{\infty }\mathbb {R} ^{[m]}\subset \operatorname {P} (\mathbb {R} ^{2}),}$ is definable, and the binary relation "length", ${\displaystyle \{([x_{1},\dots ,x_{m}],m)\mid m\in \mathbb {N} ,\,x_{1},\dots ,x_{m}\in \mathbb {R} \}=\cup _{m=1}^{\infty }{\big (}\mathbb {R} ^{[m]}\times \{m\}{\big )}\subset \operatorname {P} (\mathbb {R} ^{2})\times \mathbb {R} ,}$ on ${\displaystyle \mathbf {S} }$ is a definable function on that set. Prove it.  Hint: start with the binary relation.
• Exercise 6.2. The function ${\displaystyle E:([x_{1},\dots ,x_{m}],k)\mapsto x_{k}}$ ("evaluation") is a definable real-valued function on the set ${\displaystyle \cup _{m=1}^{\infty }{\big (}\mathbb {R} ^{[m]}\times \{1,\dots ,m\}{\big )}.}$ Prove it.  Hint: for ${\displaystyle s=[x_{1},\dots ,x_{m}],}$ ${\displaystyle k\in \mathbb {N} }$ and ${\displaystyle x\in \mathbb {R} }$ we have ${\displaystyle E(s,k)=x\Longleftrightarrow (k,x)\in s\Longleftrightarrow \exists p{\big (}p\in s\land (k,x)=p{\big )};}$ use the two given relations on ${\displaystyle \mathbf {S} ,}$ membership and appendment (consider ${\displaystyle n=1}$ in the definition of appendment).

We choose a definable bijection ${\displaystyle h:\mathbb {R} \to (0,1),}$ for example, ${\displaystyle \textstyle h(x)={\frac {1}{2}}(1+{\frac {x}{1+|x|}}),}$ and define a function ${\displaystyle W:\cup _{m=1}^{\infty }\mathbb {R} ^{[m]}\to \mathbb {R} }$ by ${\displaystyle W([x_{1},\dots ,x_{m}])=W_{m}{\big (}h(x_{1}),\dots ,h(x_{m}){\big )}}$ for all ${\displaystyle m\in \mathbb {N} }$ and ${\displaystyle x_{1},\dots ,x_{m}\in \mathbb {R} .}$

• Exercise 6.3. The function ${\displaystyle W}$ is definable. Prove it.  Hint: for all ${\displaystyle m\in \mathbb {N} ,}$ ${\displaystyle x_{1},\dots ,x_{m}\in \mathbb {R} }$ and ${\displaystyle z\in \mathbb {R} }$ we have ${\displaystyle W([x_{1},\dots ,x_{m}])=z\Longleftrightarrow W_{m}{\big (}h(x_{1}),\dots ,h(x_{m}){\big )}=z\Longleftrightarrow \forall k\in \{1,\dots ,m\}\;\;\forall n\in \mathbb {N} \;\;D(m(n-1)+k,z)=D(n,h(x_{k}));}$ that is, for all ${\displaystyle m\in \mathbb {N} ,}$ ${\displaystyle s\in \mathbb {R} ^{[m]}}$ and ${\displaystyle z\in \mathbb {R} }$ holds