Defining finite unions of intervals with algebraic endpoints on the reals

Question

I'm currently working a bit on Enderton's logic textbook (2nd ed), and, on the second chapter, he marks the following exercise on definability with an asterisk.

Let $(\mathbb{R}; +, \cdot)$ be the reals with the usual operations. Consider the usual first-order language plus symbols for multiplication and addition. Enderton asks us to show that any finite union of intervals with algebraic endpoints is definable in that structure. By this, I suppose he means that we must give a formula with free variables whose satisfaction set will be precisely the unions in question. I'm a bit at loss about how to proceed, though. It seems that one should first produce a formula which express the notion of order (but that is not too difficult), which would allow one to define the notion of an interval. Then one would need to define finite union of intervals (but that is also not difficult, I suppose; just take the disjunction of the formulas for intervals). Finally, one would also need to define algebraic numbers (but I'm not sure about how to do this). Is this right? If so, how can I define the algebraic numbers?

In addition, aside from Tarski's paper on definable sets of reals, are there any references that give a step by step proof of this theorem and its converse (that those are the only definable sets of reals)? I'm specially interested in textbooks.

Answer 1

First, order can be defined by defining "nonnegative" to mean having a square root, and $x \leq y$ to mean that $\exists z (x + z = y \text{and $z$ is nonnegative})$.

Next, you'll want to establish that every integer is definable. Start with $1$.

You don't need to define a statement "$x$ is algebraic." Given a particular algebraic number $\alpha$, you merely want to define the statement "$x > \alpha$." If you let $f(x)$ be a nonzero polynomial with integer coefficients of minimal degree with $\alpha$ as a root, then $\alpha$ is a simple root of $f(x)$. (There's some algebra involved here.) So $f$ crosses the $x$-axis at $\alpha$.

Say, for instance, that $f$ is increasing near $\alpha$. (Otherwise, use $-f$.) Then take two rational numbers $p$ and $q$ such that $f$ is positive on $(\alpha,q]$ and negative on $(p,\alpha]$. The statement $x > \alpha$ can be defined by the condition "($f(x) > 0$ and $x > p$) or $x > q$".

A statement such as $x > p = a/b$, where $a$ and $b$ are integers, can itself be defined by saying that $bx > a$.

You probably need to show that $x = \alpha$ is also definable, and this can be done analogously.

The kind of statement you were talking about is then a finite combination (using connectives) of statements of the type $x > \alpha_i$ and $x = \alpha_i$, where $\alpha_1, \alpha_2, \dots, \alpha_r$ are a fixed list of algebraic numbers.

I'm sorry, but I don't know where this theorem might be proved.

Answer 2

I claim that every interval with algebraic endpoints is definable. Taking disjunctions, it follows that also any finite union of intervals is definable.

As you noticed, the order relation is definable, then we may freely use the symbol $<$.

In a linearly ordered structure every algebraic element is definable. In fact, $a$ is algebraic if it is the solution of a formula $\varphi(x)$ with finitely many solution. So we may define $a$ saying that it is the $n$-th solution (when these are ordered by $<$) of $\varphi(x)$.

Cleary, intervals with definable endpoints are definable sets.QED

N.B. Note that you are not "defining" the set of algebraic numbers (you cannot). The answer is (has to be) non uniform.

Answer 3

In order to define an arbitrary natural number $n$, we can deploy the formula $\phi_n$:

$\phi_n := \exists x \forall y ((y \cdot x = y) \wedge n =(x + \dots + x))$

Where the expression "$x + \dots + x$"' contains $n$ iterations of $x$. We can also define $0$ directly by using:

$\phi_0 := \forall t ((s + t) = s)$.

Using the above formulas, we can now define any particular integer. If $n$ is a positive integer, just use $\phi_n$. Otherwise, use the formula:

$\phi_{-n} := \exists n (\phi_n \wedge \exists s (\phi_0 \wedge (w + n) = s))$.

Now we can use these formulas to define any particular rational number. Let $n, m \in \mathbb{N}$. We define the rational $\frac{n}{m} \in \mathbb{Q}$ by the formula $\phi_q$:

$\phi_q := \exists n \exists m(\phi_n \wedge \phi_m \wedge ((n \cdot q) = m))$

And the rational $-\frac{n}{m}$ can be defined by the formula $\phi_{-q}$:

$\phi_{-q} (q') := \exists q \phi_q \wedge (\exists s \phi_0 (s) \wedge (q' + q =s))$.

Using this, we can define the set of the algebraic roots $r$ of a polynomial using the following formula:

$\phi_r : = \exists q_1 \dots \exists q_k (\phi_{q_1} \wedge \dots \wedge \phi_{q_k} \wedge (\exists s (\phi_0 \wedge ((q_0 + (q_1 \cdot r) + \dots + (q_k \cdot r^k)) = s)))$

Given this, we can now use the following formula to characterize the less than relation:

$\phi_{a \leq b} : = \exists v (a+(v \cdot v) =b)$

and this one to characterize the strictly less than relation:

$\phi_{a<b} (a, b) := \phi_{a \leq b} \wedge a \not = b$

Now, the problem with the above $\phi_r$ is that it doesn't distinguish among the roots of the given polynomial. We can, however, order its roots, and thus capture the $i$-th root of a polynomial of degree $k$ using the following formulas (I'll use $\sum\limits_{j=0}^{n}r_j$ as an abbreviation for $\exists r_0 \dots \exists r_n$):

$\phi_{r_0} : = \phi_r (r_0) \wedge \forall r (\phi_r(r) \rightarrow\phi_{r_0 < r} (r_0, r))$;

$\phi_{r_1} := \phi_r (r_1) \wedge \exists r (\phi_r (r) \wedge \phi_{r < r_1}(r, r_1) \wedge \forall r' ((\phi_r (r') \wedge \phi_{r' < r_1}) \rightarrow r' = r))$;

$\phi_{r_i} : = \phi_r (r_i) \wedge \sum\limits_{j=0}^{i-1}r_j (\bigwedge\limits_{j=0}^{i-1} (\phi_r (r_j) \wedge \bigwedge\limits_{0 \leq f < g <i} (r_f \not = r_g) \wedge \phi_{r_j < r_i} (r_j, r_i)) \wedge \forall r' (\phi_r (r') \wedge \phi_{r' < r_i} (r', r_i) \rightarrow \bigvee\limits_{j=0}^{i-1} (r' = r_j)))$

Now, using those formulas, we can we can define, for algebraic numbers $r_i, u_j$ (which are the $i$-th and $j$-th root of a polynomial) the following intervals:

$[r_i, u_j]$, $(r_i, u_j]$, $(r_i, u_j)$, $[r_i, u_j)$

by using the following formulas:

$\phi_{(r_i,u_j)} := \exists r_i \exists u_j (\phi_{r_i} \wedge \phi_{u_j} \wedge (\phi_{r_i < b}(b)) \wedge (\phi_{b \leq u_j}(b)))$;

$\phi_{(r_i,u_j]} := \exists r_i \exists u_j (\phi_{r_i} \wedge \phi_{u_j} \wedge (\phi_{r_i < b} (b)) \wedge (\phi_{b \leq u_j}(b))))$;

$\phi_{[r_i,u_j)} := \exists r_i \exists u_j (\phi_{r_i} \wedge \phi_{u_j} \wedge (\phi_{r_i \leq b} (b)) \wedge (\phi_{b < u_j} (b)))$;

$\phi_{[r,u]} := \exists r_i \exists u_j (\phi_{r_i} \wedge \phi_{u_j} \wedge (\phi_{r_i \leq b} (b)) \wedge (\phi_{b < u_j}(b)))$.

Finally, we can use any finite union of intervals with algebraic endpoints by simply taking disjunctions of the above formulas, e.g. $[r_i, u_j] \cup [r'_l, u'_h]$:

$\phi_{[r_i, u_j] \cup [r'_l, u'_h]} := \phi_{[r_i, u_j]} \vee \phi_{[r'_l, u'_h]}$.

Since the above procedure is almost mechanical, it follows that any finite union of intervals with algebraic endpoints is definable.