Completions of countable non-standard models of ℚ

Peter Laubenheimer Thomas Schick Uni Göttingen Germany

Ulrich Stuhler^{∗}

Last compiled May 1, 2006; last edited April 20, 2006 or later

Abstract

In this note, we study non-standard models of the rational numbers with countably many elements.

These are ordered fields, and so it makes sense to complete them, using non-standard Cauchy sequences. The main part of this note shows that these completions are real closed, i.e. each positive number is a square, and each polynomial of odd degree has a root. This way, we give a direct proof of a consequence of a theorem of Hauschild. In a previous version of this note, not being aware of these results, we missed to mention this reference. We thank Matthias Aschenbrenner for pointing out this and related work.

We also give some information about the set of real parts of the finite elements of such completions —about the more interesting results along this we have been informed by Matthias Aschenbrenner and Martin Goldstern.

The main idea of our proof relies on a way to describe real zeros of a polynomial in terms of first order logic. This is achieved by carefully using the sign changes of such a polynomial.

1 About the ”’size”’ of ^{∗}ℚ

Let^{∗}ℚ be a countable field which is elementary equivalent, but not isomorphic to ℚ. Recall that “elementary equivalent” means that an (arithmetic) expression of first order is true in ^{∗}ℚ if and only if it is true in ℚ.

We have a canonical embedding of ℚ into ^{∗}ℚ. We continue to denote the image with ℚ. Recall that any non-standard model of ℚ contains an element e such that e > q for each q ∈ ℚ.

The shortest way to construct a model for ^{∗}ℚ uses model theory. We simply take as axioms all axioms of ℚ and additionally the following countable number of axioms: the existence of an element e with e > 1, e > 2, ….

Each finite subset of this axioms is satisfied by the standard ℚ. By the compactness theorem in first order model theory, there exists a model which also satisfies the given infinite set of axioms. By the theorem of Löwenheim-Skolem, we can choose such models of countable cardinality.

∗email: schick@uni-math.gwdg.de, stuhler@uni-math.gwdg.de www http://www.uni-math.gwdg.de/schick, http://www.uni-math.gwdg.de/stuhler Fax: ++49 -551/39 2985

Each non-standard model^{∗}ℚ contains the (externally defined) subset^{∗}ℚ_{fin} := {x ∈ ^{∗}ℚ | ∃n ∈ ℚ : −n ≤ x ≤ n}.

Every element x ∈ ^{∗}ℚ_{fin} defines a Dedekind cut: ℚ = {q ∈ ℚ | q ≤ x}∪{q ∈ ℚ | q > x}. We therefore get a order preserving map

fp: ^{∗}ℚ_{fin} → ℝ  (1.1)

which restricts to the standard inclusion of the standard rationals and which respects addition and multiplication. An element of^{∗}ℚ_{fin} is called infinitesimal, if it is mapped to 0 under the map fp.

We first address the question what is the possible range of fp.

1.2 Proposition. Choose an arbitrary subset M ⊂ ℝ. Then there is a model ∗ℚ^{M} such that fp(^{∗}ℚ_{fin}^{M}) ⊃ M. Moreover, the cardinality of ^{∗}ℚ^{M} can be chosen to coincide with M, if M is infinite.

Proof. Choose M ⊂ ℝ. For each m ∈ M choose q_{1}^{m} < q_{2}^{m} < ⋯ < p_{2}^{m} < p_{1}^{m} with lim q_{k}^{m} = lim p_{k}^{m} = m.

We add to the axioms of ℚ the following axioms: ∀m ∈ M∃e_{m} such that q_{k}^{m} < e_{m} < p_{k}^{m} for all k ∈ ℕ.

Again, the standard ℚ is a model for each finite subset of these axioms, so that the compactness theorem implies the existence of ^{∗}ℚ^{M} as required, where the cardinality of ^{∗}ℚ^{M} can be chosen to be the cardinality of the set of axioms, i.e. of M, if M is infinite. Note that by construction fp(e_{m}) = m for all m ∈ M.

1.3 Remark. It follows in particular that for each countable subset of ℝ we can find a countable model of ^{∗}ℚ such that the image of fp contains this subset. Note, on the other hand, that the image will only be countable, so that the different models will have very different ranges.

We prove in Section 2 that fp(^{∗}ℚ) contains for any countable model ^{∗}ℚ every real algebraic number. It remains an open problem to determine precisely the possible image sets.

Matthias Aschenbrenner kindly explained us, that the set of computable real numbers always is contained in the image. Here, a real number r ∈ ℝ is computable if the set of pairs {(m, n) ∈ ℕ | n ≠ 0, m/n < |r|} is computable. Moreover, he also explained that the image is itself a real closed subfield of ℝ. As explained by Martin Goldstern, the first result can be strengthened to the fact that every definable real number is contained in the image. A real number r is definable if the set of pairs {(m, n) ∈ ℕ^{2} | n ≠ 0, m/n < |r|} is definable by a formula A(x, y) of first order logic over the rationals.

2 Cauchy completions

2.1 Definition. A Cauchy-Sequence in ^{∗}ℚ is a sequence (a_{k})_{k∈ℕ} such that for every ϵ ∈ ^{∗}ℚ, ϵ > 0 there is an n_{ϵ} ∈ ℕ such that |a_{m} − a_{n}| < ϵ for each m, n > n_{ϵ}.

We define the completion \overline{^{∗}ℚ} in the usual way as equivalence classes of Cauchy sequences.

2.2 Remark. This is a standard construction and works for all ordered fields. The result is again a field, extending the original field. Note that, in our case, each point in \overline{^{∗}ℚ} is infinitesimally close to a point in ^{∗}ℚ, since there is an 0 < ϵ ∈ ^{∗}ℚ which is smaller than every positive rational number.

In many non-standard models of ℚ, there are no sequences tending to zero which are not eventually zero. This is not the case if ^{∗}ℚ is countable, so that \overline{^{∗}ℚ} is potentially different from ^{∗}ℚ (and we will actually see that it is different from ^{∗}ℚ as a consequence of Theorem 2.6.

2.3 Lemma. Assume that ^{∗}ℚ is countable. Let {q_{1}, q_{2}, … } = ^{∗}ℚ_{>0} be a enumeration of the positive elements of ^{∗}ℚ.

Define the sequence c_{k} inductively as follows: c_{1} := q_{1}, c_{k} is the next element in the list after c_{k−1} which is smaller than c_{k−1}. We end up with a decreasing sequence which eventually is smaller than each positive element of ^{∗}ℚ, i.e. tends to zero.

2.4 Remark. Every element of ^{∗}ℚ which is algebraic over ℚ already belongs to ℚ.

This follows since for a given (irreducible) polynomial p ∈ ℚ[x] the statement: “there is no a ∈ ℚ with p(a) = 0” is of first order and therefore remains true in ^{∗}ℚ.

2.5 Lemma. For every model ^{∗}ℚ, fp: ^{∗}ℚ_{fin} → ℝ extends to fp: \overline{^{∗}ℚ}_{fin} → ℝ, but the image is unchanged.

Proof. Every x ∈ \overline{^{∗}ℚ} is the limit of a sequence of elements in ^{∗}ℚ, i.e. is inienitesimally close to elements in ^{∗}ℚ. Consequently, the finite part is the limit of elements of ^{∗}ℚ, and the map fp extends by continuity. Since the image of an infinitesimal element under fp is 0 ∈ ℝ, for each x ∈ \overline{^{∗}ℚ}_{fin} there is an x′ ∈ ^{∗}ℚ_{fin} with fp(x) = fp(x′) = 0 (since x − x′ is infinitesimal).

Nevertheless, the passage from ^{∗}ℚ to \overline{^{∗}ℚ} adds many roots of polynomials:

2.6 Theorem. Assume that ^{∗}ℚ is a non-standard model of the rationals which has countably many elements. Then the field \overline{^{∗}ℚ} is real closed, i.e.

(1) If c ∈ \overline{^{∗}ℚ} satisfies c > 0 then there is \sqrt{c} ∈ \overline{^{∗}ℚ} with \sqrt{c} > 0 and \sqrt{c}^{2} = c.

(2) If p ∈ \overline{^{∗}ℚ}[x] is a polynomial of odd degree, then there is a ∈ \overline{^{∗}ℚ} with p(a) = 0.

This is a direct consequence of the following theorem 2.8, because every polynomial of odd degree, as well as the polynomial x^{2} − a for a positive has a sign change. However, it can also be regarded as a special case of the following theorem of Hauschild (compare [2]).

2.7 Theorem. The completion (defined using Cauchy sequences indexed by ordinals) of an ordered field K is real closed if and only if for every polynomial f ∈ K[x] and all a, b, ϵ ∈ K with a < b and every ϵ > 0 there is c ∈ K with a < c < b and |f(c)| < ϵ.

Since the condition is valid in ℚ and is “a” statement of logic of first order, the condition is valid for any non-standard model ^{∗}ℚ, as well, and it follows that the completion is real closed.

This result was kindly pointed out to us by Matthias Aschenbrenner, and therefore makes the following arguments superfluous. Nonetheless, it might be a nice illustration of this kind of argument to follow the argument, which is neither particularly new nor particularly general.

2.8 Theorem. Suppose, f(x) ∈ ^{∗}ℚ̄[x], a polynomial of degree m, a, b ∈ ^{∗}ℚ̄ such that f(a)f(b) < 0, that is, f is changing sign between a and b, then there exists x ∈ [a, b], f(x) = 0.

2.9 Remark. Let fp: ^{∗}ℚ → ℝ be the finite part map of (1.1). We denote the elements of f^{−1}(r) for r ∈ ℝ infinitesimally close to r.

Note that by Lemma 2.5 the map fp extends to \overline{^{∗}ℚ}, but its image is unchanged. Theorem 2.6 therefore implies in particular that for each polynomial of odd degree over ^{∗}ℚ we can find points which are “infinitesimally close” to a root.

Proof of Theorem 2.8. I) In a first step we show the theorem under the additional assumption, that f(x) ∈ ^{∗}ℚ[x]. Proof of this: By choosing a′, b′ sufficiently close to a, b, such that [a′, b′] ⊂ (a, b), we can assume additionally, that a, b ∈ ^{∗}ℚ as well. We consider the following statement: Given ^{∗}n ∈ ^{∗}ℕ, a, b ∈ ^{∗}ℚ, such that f(a)f(b) < 0, there exist a_{1}, b_{1} ∈ ^{∗}ℚ, [a_{1}, b_{1}] ⊂ [a, b], |a_{1} − b_{1}| ≤ \frac{1}{^{∗}n}, such that f(a_{1})f(b_{1}) < 0.

This is a first order statement, which obviously is true in ℚ itself. Therefore it is true in ^{∗}ℚ. Now we choose a sequence of nonstandard numbers (^{∗}n_{i} | i = 1, 2, …) in ^{∗}ℕ, such that lim_{i→∞} ^{∗}n_{i} = ∞ resp. lim_{i→∞} \frac{1}{^{∗}n_{i}} = 0. We can choose a

sequence of nested intervalls [a, b] ⊃ [a_{1}, b_{1}] ⊃ …, such that |a_{i} − b_{i}| ≤ \frac{1}{^{∗}n_{i}} and f(a_{i})f(b_{i}) < 0 for all i = 1, 2, . . .. Then (a_{i} | i = 1, 2, …), and (b_{i} | i = 1, 2, …) are Cauchy convergent sequences in ^{∗}ℚ, which have a common limit lim_{i→∞} a_{i} =

lim_{i→∞} b_{i} = x ∈ [a, b]. By renaming the a_{i}, b_{i} we can additionally assume, that

f(a_{i}) < 0 for all i ≥ 1, f(b_{i}) > 0 for all i ≥ 1. (It is not necessary, that a_{i} < b_{i}!) Then

f(x) = f( lim_{i→∞} a_{i}) = lim_{i→∞} f(a_{i}) ≤ 0 ,

but also

f(x) = f( lim_{i→∞} b_{i}) = lim_{i→∞} f(b_{i}) ≥ 0 .

Therefore f(x) = 0 and I) is proved.

II) Now we show the theorem in full generality. We do this by induction with respect to m = deg f(x).

i) m = 1 is trivial.

ii) Induction step. We assume the theorem to hold for all polynomials of degree ≤ (m − 1). We will show, that it holds for f(x), deg f(x) = m. We consider the derivative f′(x) on the intervall [a, b]. Suppose {y_{i} | 0 = 1, …, r} is the set of zeros of f′ on [a, b] in ^{∗}ℚ̄, so r ≤ (m − 1). We obtain a partition of the intervall [a, b]

a := y_{0} ≤ y_{1} < y_{2} < … < y_{r} ≤ b =: y_{r+1} .

By the induction hypothesis, f′(x) does not change sign on any of the open intervalls (y_{i}, y_{i+1}). However, there must be a change of sign of f in at least one of the intervalls [y_{i}, y_{i+1}].

Therefore, by replacing, if necessary, [a, b] by one of the intervalls [y_{i}, y_{i+1}], we can assume from the beginning, that f on [a, b] satisfies the following conditions:

(1) f(a) < 0, f(b) > 0

(2) Either f′(x) > 0 for all x ∈ (a, b) or f′(x) < 0 for all x ∈ (a, b).

Replacing, if necessary, f by (−f), we can assume also a < b. Additionally, we can assume: a, b ∈ ^{∗}ℚ.

Of course, additionally we can exclude the second possibility in 2) as follows: choose ε ∈ ^{∗}ℚ, such that ε(b − a) < \frac{f(b)−f(a)}{2} and approximate f(x) by g(x) ∈ ∗ℚ[x], deg(g) = m, coefficientwise so sharp, such that |f′(x) − g′(x)| < ε holds on [a, b]. This implies in particular, that g′(x) < ε for x ∈ [a, b]. Then as this is again a first order statement, which does hold for ℚ, we have

g(b) − g(a) < ε(b − a) ,

so

g(b) − g(a) < \frac{f(b) − f(a)}{2} =: c .

If g is chosen, such that additionally |g(b) − f(b)| < \frac{c}{4}, |g(a) − f(a)| < \frac{c}{4} hold, we obtain a contradition. Therefore we can even assume

1)  f(a) < 0 f(b) > 0 ,

2)  f′(x) > 0 for all x ∈ (a, b) .

Using the same kind of argument, we obtain additionally

3)  f(x) is monoton increasing on [a, b] .

We can still improve the situation by finding m, M ∈ ^{∗}ℚ, 0 < m < M such that m < f′(x) < M holds for all x ∈ [a, b], (again it may be necessary to replace [a, b] by a subintervall).

This can be seen as follows: Consider the second derivative f′′(x) on [a, b]. By induction hypothesis there is a finite set {z_{1}, …, z_{s}} of zeros of f′′(x) on [a, b], s ≤ m − 2. Using the considerations above, it follows, that f′(x) is monoton on each of the intervalls [z_{i}, z_{i+1}], i = 0, …, s, where z_{0} := a, z_{s+1} := b. Therefore we can choose

m := inf{f′(z_{i}) | i = 0, …, s + 1}

and

M := sup{f′(z_{i}) | i = 0, …, s + 1}

and the claim above is shown.

Now, finally the situation is sufficiently under control to proof the theorem: As earlier, we choose a sequence of nonstandard numbers (^{∗}n_{i} | i = 1, 2, …), ∗n_{i} ∈ ^{∗}ℕ satisfying lim_{i→∞} \frac{1}{^{∗}n_{i}} = 0.

We choose polynomials g_{i}(x) ∈ ^{∗}ℚ[x] (i ≥ 1) satisfying

1)  |f(x) − g_{i}(x)| ≤ \frac{1}{^{∗}n_{i}}

2)  |f′(x) − g′_{i}(x)| ≤ \frac{1}{^{∗}n_{i}}

for x ∈ [a, b].

Additionally, we can assume

3) g_{i}(a) < 0, g_{i}(b) > 0 for i ∈ ℕ

4) g_{i}(x) is monoton increasing on [a, b] and one has

m < g′_{i}(x) < M for x ∈ [a, b]

i ∈ ℕ arbitrary.

(4) is satisfied by replacing m, M for example by \frac{m}{2}, 2M) and throwing away finitely many g_{i} if necessary.)

By I) above, we can conclude, that there exist x_{i} ∈ ^{∗}ℚ̄, x_{i} ∈ [a, b], uniquely determined, such that g_{i}(x_{i}) = 0, i = 1, 2, …, .

We show next that (x_{i} | i ∈ ℕ) is a Cauchy sequence in ^{∗}ℚ̄. We conclude as follows: Consider x_{i}, x_{j} ∈ [a, b]. Assume first, that g_{j}(x_{i}) < 0 which implies x_{i} < x_{j}. We have

0 = g_{j}(x_{j}) ≥ g_{j}(x_{i}) + (x_{j} − x_{i})m

This implies

0 < x_{j} − x_{i} < \frac{−g_{j}(x_{i})}{m}

However,

|g_{j}(x_{i})| = |g_{j}(x_{i}) − g_{i}(x_{i})|
≤ |g_{j}(x_{i}) − f(x_{i})| + |f(x_{i}) − g_{i}(x_{i})|
≤ \frac{2}{min\{^{∗}n_{i}, ^{∗}n_{j}\}}

Interchanging i, j we obtain the same estimate, if g_{j}(x_{i}) > 0. (Then x_{i} > x_{j}, so g_{i}(x_{j}) < g_{i}(x_{i}) = 0).

In any case we obtain |x_{j} −x_{i}| ≤ \frac{2}{m min\{^{∗}n_{i}, ^{∗}n_{j}\}}, which implies that (x_{i} | i = 1, 2, …) is a Cauchy sequence in [a, b]. So lim_{i→∞} x_{i} =: x ∈ [a, b] already exists.

We obtain f(x) = f( lim_{i→∞} x_{i}) = lim_{i→∞} f(x_{i}), but |f(x_{i})| ≤ g_{i}(x_{i}) + \frac{1}{^{∗}n_{i}} ≤ \frac{1}{^{∗}n_{i}}, so

f(x) = 0 follows. □

We now want to address the question, which is the image of the map fp: \overline{^{∗}ℚ}_{fin} → ℝ. Let K ⊂ \overline{^{∗}ℚ} be the set of all elements which are algebraic over ℚ. Recall that this implies that every element of \overline{^{∗}ℚ} which is algebraic over K already belongs to K. Since \overline{^{∗}ℚ} is a real closed ordered field, the subfield K is real closed ordered, as well.

Given p(x) = x^{n} + ∑_{k=0}^{n−1} a_{k}x^{n} ∈ ℚ[x], the statement

|p(t)| ≥ 1 ∀t ∈ ℚ with |t| ≥ n + ∑_{k=0}^{n} |a_{k}|

is true and therefore remains true for t ∈ ^{∗}ℚ. Since each element in K is the zero of a polynomial over ℚ, K ⊂ \overline{^{∗}ℚ}_{fin}.

Consequently, the restricted map fp: K → ℝ, being multiplicative and additive and now defined on all of K, is a field extension into the subfield K_{ℝ} of ℝ consisting of algebraic numbers over ℚ.

Since both K and K_{ℝ} are real closed, adjoining \sqrt{−1} produces the algebraic closure of ℚ and therefore the induced map K[\sqrt{−1}] → K_{ℝ}[\sqrt{−1}] is an isomorphism, so that fp: K → K_{ℝ} also is an isomorphism.

2.10 Corollary. If ^{∗}ℚ is countable, then the image of

fp: ^{∗}ℚ_{fin} → ℝ

contains every real number which is algebraic over ℚ.

Proof. This follows from the preceeding discussion because fp(\overline{^{∗}ℚ}_{fin}) = fp(^{∗}ℚ_{fin}).

2.11 Question. We have seen that for every countable subset Z of ℝ, we can find a countable model ^{∗}ℚ such that the countable set fp(^{∗}ℚ_{fin}) contains Z.

On the other hand, fp(^{∗}ℚ_{fin}) always contains the subfield K_{ℝ} ⊂ ℝ of algebraic numbers over ℚ. Even stronger, using the results explained to us by Matthias Aschenbrenner and Martin Goldstern, fp(^{∗}ℚ_{fin}) always contains all definable real numbers, and is real closed.

It would be interesting to find more precise information about the possible image sets.

In particular: can every subfield of ℝ with the above properties be obtained as image of fp? Does this perhaps depend on the model of set theory one uses?

References

[1] Richard Kaye. Models of Peano arithmetic, volume 15 of Oxford Logic Guides. The Clarendon Press Oxford University Press, New York, 1991. Oxford Science Publications.

[2] Sibylla Prieß-Crampe. Angeordnete Strukturen, volume 98 of Ergebnisse der Mathematik und ihrer Grenzgebiete. Springer-Verlag, Berlin, 1983.