On embedding models of arithmetic of cardinality ℵ_{1} into reduced powers^{∗}

Juliette Kennedy^{†} Department of Mathematics University of Helsinki Helsinki, Finland

Saharon Shelah^{‡} Institute of Mathematics Hebrew University Jerusalem, Israel and Department of Mathematics Rutgers University

September 1, 2002

Abstract

In the early 1970’s S.Tennenbaum proved that all countable models of P A^{−} + ∀_{1} − T h(ℕ) are embeddable into the reduced product ℕ^{ω}/F, where F is the cofinite filter. In this paper we show that if M is a model of P A^{−} + ∀_{1} − T h(ℕ), and |M| = ℵ_{1}, then M is embeddable into ℕ^{ω}/D, where D is any regular filter on ω.

∗MSC 2000 classification 03C62, 03C20, 03C50 †Research partially supported by grant 40734 of the Academy of Finland.

‡Research partially supported by the United States-Israel Binational Science Foundation. Publication number [728].

1 Preliminaries

Let LA, the language of arithmetic, be the first order language with nonlogical symbols +, ·, 0, 1, ≤. ℕ denotes the standard LA structure. We shall be concerned with the following theories: The theory ∀_{1}-T h(ℕ), defined as the set of all universal formulas true in the standard LA structure ℕ. Henceforth we refer to theories satisfying ∀_{1}-T h(ℕ) as Diophantine correct. We will also refer to the theory P A^{−}, which consists of the following axioms (x < y abbreviates x ≤ y ∧ x ≠ y):

1.) ∀x, y, z((x + y) + z = x + (y + z)) 2.) ∀x, y(x + y = y + x) 3.) ∀x, y, z((x · y) · z = x · (y · z)) 4.) ∀x, y(x · y = y · x) 5.) ∀x, y, z(x · (y + z) = x · y + x · z) 6.) ∀x((x + 0 = x) ∧ (x · 0 = 0)) 7.) ∀x(x · 1 = x) 8.) ∀x, y, z((x < y ∧ y < z) → x < z) 9.) ∀x(x ≤ x) 10.) ∀x, y(x < y ∨ x = y ∨ y < x) 11.) ∀x, y, z(x < y → x + z < y + z) 12.) ∀x, y, z(0 < z ∧ x < y → x · z < y · z) 13.) ∀x, y(x < y → ∃z(x + z = y)) 14.) 0 < 1 ∧ ∀x(x > 0 → x ≥ 1) 15.) ∀x(x ≥ 0).

Thus the theory P A^{−} is the theory of nonnegative parts of discretely ordered rings. For interesting examples of these models see [2].

2 The Countable Case

We begin by presenting the two embedding theorems of Stanley Tennenbaum, which represent countable models of P A^{−} by means of sequences of real numbers. We note that Theorems 1 and 3 follow from the ℵ_{1}-saturation of the structures ℕ^{ω}/F and 𝔸^{ω}/F ([1]), however we present Tennenbaum’s construction as it constructs the embeddings directly:

We consider first the reduced power (of LA structures) ℕ^{ω}/F, where F is the cofinite filter in the boolean algebra of subsets of ℕ. Let 𝔸 be the standard LA structure with domain all nonnegative real algebraic numbers. We also consider the reduced power 𝔸^{ω}/F.

If f is a function from ℕ to ℕ, let [f] denote the equivalence class of f in ℕ^{ω}/F. We use a similar notation for 𝔸^{ω}/F. When no confusion is possible, we will use f and [f] interchangeably.

Theorem 1 (Tennenbaum) Let M be a countable Diophantine correct model of P A^{−}. Then M can be embedded in ℕ^{ω}/F.

Proof. Let m_{1}, m_{2}, … be the distinct elements of M. Let P_{1}, P_{2}, … be all polynomial equations over ℕ in the variables x_{1}, x_{2}, … such that M ⊧ P_{i}(x_{1}/m_{1}, x_{2}/m_{2}, …). Each system of equations P_{1} ∧⋯∧P_{n} has a solution in M. Thus, by Diophantine correctness, there is a sequence of natural numbers v_{1}(n), v_{2}(n), … for which

ℕ ⊧ (P_{1} ∧ ⋯ ∧ P_{n})(x_{1}/v_{1}(n), x_{2}/v_{2}(n), …).

Note that if the variable x_{i} does not appear in P_{1} ∧ ⋯ ∧ P_{n}, then the choice of v_{i}(n) is completely arbitrary. Our embedding h : M ⟶ ℕ^{ω}/F is given by:

m_{i} ⟼ [λn.v_{i}(n)].

In the figure below, the i-th row is the solution in integers to P_{1}∧⋯∧P_{n}, and the i-th column “is” h(m_{i}).

m_{1}  m_{2}  … m_{n}  …
P_{1} v_{1}(1) v_{2}(1) … v_{n}(1) …
P_{2} v_{1}(2) v_{2}(2) … v_{n}(2) …
⋮  ⋮  ⋮  ⋮
P_{n} v_{1}(n) v_{2}(n) … v_{n}(n) …
⋮  ⋮  ⋮  ⋮

Note that if m_{e} is the element 0^{M} of M, then the polynomial equation x_{e} = 0 appears as one of the P ’s. It follows that, for n sufficiently large, v_{e}(n) = 0. Thus h(0^{M}) is the equivalence class of the zero function. Similarly, h maps every standard integer of M to the class of the corresponding constant function.

We show that h is a homomorphism. Suppose M ⊧ m_{i}+m_{j} = m_{k}. Then the polynomial x_{i}+x_{j} = x_{k} must be one of the P ’s, say P_{r}. If n ≥ r, then by construction v_{i}(n)+v_{j}(n) = v_{k}(n). Hence ℕ^{ω}/F ⊧ h(m_{i})+h(m_{j}) = h(m_{k}), as required. A similar argument works for multiplication. Suppose M ⊧ m_{i} ≤ m_{j}. By an axiom of P A^{−}, for some k, M ⊧ m_{i} + m_{k} = m_{j}. Thus, as we have shown, h(m_{i}) + h(m_{k}) = h(m_{j}). It follows from the definition of the relation ≤ in N that h(m_{i}) ≤ h(m_{j}).

To see that h is one to one, suppose that m_{i} ≠ m_{j}. Since in models of P A^{−} the order relation is total, we may assume that m_{i} < m_{j}. Again by the axioms of P A^{−}, we can choose m_{k} such that m_{i} + m_{k} + 1 = m_{j}. As we have shown, ℕ^{ω}/F ⊧ h(m_{i}) + h(m_{k}) + h(1) = h(m_{j}). Since h(1) is the class of the constant function 1, it follows that h(m_{i}) ≠ h(m_{j}). □

Corollary 2 Let M be a countable model of the ∀_{1}-T h(ℕ). Then M can be embedded in ℕ^{ω}/F.

Proof. The models of the ∀_{1}-T h(ℕ) are precisely the substructures of models of T h(ℕ). Thus, M extends to a model of P A^{−}, which can be embedded in ℕ^{ω}/F as in Theorem 1. □

Before turning to the theorem for the non-Diophantine correct case, we observe first that the given embedding depends upon a particular choice of enumeration m_{1}, m_{2}, … of M, since different enumerations will in general produce different polynomials. We also note that different choices of solution yield different embeddings. Also, as we shall see below, we need not restrict ourselves to Diophantine formulas: we can carry out the construction for LA formulas of any complexity which hold in M.

We state the non-Diophantine correct case of the theorem:

Theorem 3 (Tennenbaum) Let M be a countable model of P A^{−}. Then M can be embedded in 𝔸^{ω}/F.

Proof. Given an enumeration m_{1}, m_{2}, … of M, we form conjunctions of polynomial equations P_{n} exactly as before. We wish to produce solutions of P_{1} ∧ ⋯ ∧ P_{n} in the nonnegative algebraic reals for each n. We proceed as follows: The model M can be embedded in a real closed field F by a standard construction. (Embed M in an ordered integral domain, then form the (ordered) quotient field, and then the real closure.) Choose k so large that x_{1}, …, x_{k} are all the variables that occur in the conjunction P_{1}∧⋯∧P_{n}. The sentence ∃x_{1} … x_{k}(P_{1} ∧ ⋯ ∧ P_{n} ∧ x_{1} ≥ 0 ∧ x_{2} ≥ 0 ⋯ ∧ x_{k} ≥ 0) is true in M, hence in F. It is a theorem of Tarski that the theory of real closed fields is complete. Thus, this same sentence must be true in the field of real algebraic numbers. This means we can choose nonnegative algebraic real numbers v_{1}(n), v_{2}(n) … satisfying the conjunction P_{1} ∧ ⋯ ∧ P_{n}. Let h : M ⟶ 𝔸^{ω}/F be given by

m_{i} ⟼ [λn.v_{i}(n)].

The proof that h is a homomorphism, and furthermore an embedding, proceeds exactly as before, once we note that the equivalence classes all consist of nonnegative sequences of real algebraic numbers. □

Remark 4 Under any of the embeddings given above, if M ⊧ P A^{−} then nonstandard elements of M are mapped to equivalence classes of functions tending to infinity. Why? If f is a function in the image of M, and f does not tend to infinity, then choose an integer k such that f is less than k infinitely often. Since M ⊧ P A^{−}, either [f] ≤ [k] or [k] ≤ [f]. The second alternative contradicts the definition of ≤ in N. Hence [f] ≤ [k], i.e., [f] is standard.

Remark 5 Let F be a countable ordered field. Then F is embedded in ℝ^{ω}/F, where ℝ is the field of real algebraic numbers. The proof is mutatis mutandis the same as in Theorem 3, except that due to the presence of negative elements we must demonstrate differently that the mapping obtained is one to one. But this must be the case, since every homomorphism of fields has this property.

Remark 6 For any pair of LA structures A and B satisfying P A^{−}, if A is countable and if A satisfies the ∀_{1}-T h(B) then there is an embedding of A into B^{ω}/F. In particular, if M is a model of P A^{−}, then every countable extension of M satisfying the ∀_{1}-T h(M) can be embedded in M^{ω}/F.

Remark 7 Given Theorem 1, one can ask, what is a necessary and sufficient condition for a function to belong to a model of arithmetic inside N? For a partial solution to this question, see [3].

3 The Uncountable Case

We now show that some of the restrictions of Theorem 1 can be to some extent relaxed, i.e. we will prove Theorem 1 for models M of cardinality ℵ_{1} and with an arbitrary regular filter D in place of the cofinite filter. We note that for filters D on ω for which B^{ω}/D is ℵ_{1}-saturated, where B is the two element Boolean algebra, this follows from the result of Shelah in [5], that the reduced power ℕ^{ω}/D is ℵ_{1}-saturated, by a simple model-theoretic argument.

Our strategy is similar to the strategy of the proof of Theorem 1, in that we give an inductive proof on larger and larger initial segments of the elementary diagram of M. However we must now consider formulas whose variables are taken from a set of ℵ_{1} variables. This requires representing each ordinal α < ω_{1} in terms of finite sets u_{n}^{α}, which sets determine the variables handled at each stage of the construction. The other technicality we require is the use of the following function g(x, y), which bounds the size of the formulas handled at each stage of the induction.

Let h(n, m) = the total number of non-equivalent Diophantine formulas ϕ(x_{1}, … x_{m}) of length ≤ n. Define

g(n, n) = h(n, 0)
g(n, m − 1) = 2 + h(g(n, m), m) · (g(n, m) + 3), for m ≤ n.

Theorem 8 Let M be a model of P A^{−} of cardinality ℵ_{1} which is Diophantine correct and let D be a regular filter on ω. Then M can be embedded in ℕ^{ω}/D.

For a result concerning arbitrary structures and other cardinals, see [4].

Proof. Let M = {a_{α} : α < ω_{1}}. Let {A_{n}}_{n∈ω} be a family witnessing the regularity of D. We define, for each α < ω_{1} a function f_{α} ∈ ℕ^{ℕ}. Our embedding is then a_{α} ↦ [f_{α}]. We need first a lemma:

Lemma 9 There exists a family of sets u_{n}^{α}, with α < ω_{1}, and n ∈ ℕ, such that for each n, α

(i) |u_{n}^{α}| < n + 1

(ii) α ∈ u_{n}^{α} ⊆ u_{n+1}^{α}

(iii) ⋃_{n} u_{n}^{α} = α + 1 (iv) β ∈ u_{n}^{α} ⇒ u_{n}^{β} = u_{n}^{α} ∩ (β + 1)

(v) lim_{n→∞} \frac{|u_{n}^{α}|}{n+1} = 0

Suppose we have the lemma and suppose we have defined f_{β} for all β < α. We choose f_{α} ∈ ℕ^{ℕ} componentwise, i.e. we choose f_{α}(n) for each n separately so that f_{α}(n) satisfies the following condition:

(∗)_{α,n}: If ϕ = ϕ(..., x_{β}, ...)_{β∈u_{n}^{α}} is a Diophantine formula, such that the length of ϕ is ≤ g(n, |u_{n}^{α}|), then

M ⊧ ϕ(..., a_{β}, ...)_{β∈u_{n}^{α}} ⇒ ℕ ⊧ ϕ(..., f_{β}(n), ...)_{β∈u_{n}^{α}}.

(A formula ϕ is said to be Diophantine if it has the form

∃x_{0}, …, ∃x_{n−1}(t_{1}(x_{0}, …, x_{n−1}) = t_{2}(x_{0}, …, x_{n−1})),

where t_{1} and t_{2} are LA-terms.) Now suppose α = 0, n > 0. By (ii) and (iii), u_{n}^{0} = {0} for all n. We claim that (∗)_{0,n} holds for each n. To see this, fix n and let

Φ = {ϕ(x) | M ⊧ ϕ(a_{0}), where ϕ is Diophantine with |ϕ| ≤ g(n, 1)}.

This is – up to equivalence – a finite set of formulas. Also, M ⊧ ∃x ⋀{ϕ(x) | ϕ ∈ Φ} and therefore by Diophantine correctness ℕ ⊧ ∃x ⋀{ϕ(x) | ϕ ∈ Φ}. If k witnesses this formula, set f_{0}(n) = k. Clearly now (∗)_{0,n} holds.

Now assume (∗)_{β,n} holds for all β < α and for each n. We choose f_{α}(n) for each n as follows. Fix n < ω and let

Φ = {ϕ(x_{0}, x_{1}, … x_{k}) | M ⊧ ϕ(a_{α}, ..., a_{β}, ...)_{β∈u_{n}^{α}\{α}}),
where ϕ is Diophantine and |ϕ| ≤ g(n, |u_{n}^{α}|)},

for k = |u_{n}^{α}| − 1 (the case that |u_{n}^{α}| ≤ 1 reduces to the previous case). This is again a finite set of formulas, up to equivalence. Now

M ⊧ ⋀{ϕ(a_{α}, ⟨a_{β}⟩_{β∈u_{n}^{α}\{α}})|ϕ ∈ Φ}

and therefore

M ⊧ ∃x ⋀{ϕ(x, ⟨a_{β}⟩_{β∈u_{n}^{α}\{α}})|ϕ ∈ Φ}.

Let ϕ′(x_{1}, …, x_{k}) ≡ ∃x ⋀{ϕ(x, x_{1}, …, x_{k})|ϕ ∈ Φ}. Note that

|ϕ′| ≤ 2 + h(g(n, |u_{n}^{α}|), |u_{n}^{α}|) · (g(n, |u_{n}^{α}|) + 3) = g(n, |u_{n}^{α}| − 1).

Now let γ= max (u_{n}^{α} \ {α}). Then u_{n}^{γ} = u_{n}^{α} \ {α}, by (iv) of the lemma. Since (∗)_{γ,n} holds for each n and we know that M ⊧ ϕ′(⟨a_{β}⟩_{β∈u_{n}^{γ}}) then we know by the induction hypothesis that ℕ ⊧ ϕ′(⟨f_{β}(n)⟩_{β∈u_{n}^{γ}}). Thus ℕ ⊧ ∃x ⋀{ϕ(x, ..., f_{γ}(n), ...)_{β∈u_{n}^{γ}})|ϕ ∈ Φ}. Let k witness this formula and set f_{α}(n) = k. Then (∗)_{α,n} holds with a_{α} ↦ [⟨f_{α}(n)⟩].

This mapping is an embedding of M into ℕ^{ω}/D. To see this, suppose M ⊧ ϕ(a_{α}, a_{β}, a_{γ}) where ϕ is the formula x_{0} + x_{1} = x_{2}. Let n = n_{0} be large enough so that |ϕ| ≤ g(n_{0}, |u_{n_{0}}^{δ}|), where δ is chosen so that u_{n_{0}}^{δ} contains α, β, γ. Then for all n ≥ n_{0}, (∗)_{δ,n} holds and ℕ ⊧ f_{α}(n)+f_{β}(n) = f_{γ}(n), for all n ≥ n_{0}. Let A_{n_{1}} be an element of the chosen regular family of D such that A_{n_{1}} ∩ {0, …, n_{0}} = ∅. Then since f_{α}(n) + f_{β}(n) = f_{γ}(n), for n ≥ n_{0}, this holds also for n ∈ A_{n_{1}}. The proof that multiplication is preserved is the same so we omit it. Finally, as in the countable case, we note that our mapping is one-to-one and order preserving, hence an embedding.

We now prove the lemma, by induction on α. Let u_{n}^{0} = {0} for all n < ω.

Case 1. α is a successor ordinal, i.e. α = β +1. Let n_{0} be such that n ≥ n_{0} implies \frac{|u_{n}^{β}|}{n} < \frac{1}{2}. then we set

u_{n}^{α} = \{ \begin{matrix}\{α\} & n < n_{0} \\ u_{n}^{β} ∪ \{α\} & n ≥ n_{0}. \end{matrix}

Then (i), (ii) and (iii) are trivial. Proof of (iv): Suppose γ ∈ u_{n}^{α} = u_{n}^{β} ∪{α}.

Case 1.1. γ = α. Then

u_{n}^{γ} = u_{n}^{α}
= u_{n}^{α} ∩ α + 1
= u_{n}^{α} ∩ (γ + 1).

Case 1.2. γ ∈ u_{n}^{β}. Then by the induction hypothesis

u_{n}^{γ} = u_{n}^{β} ∩ (γ + 1)
= u_{n}^{α} ∩ (γ + 1),

since γ ∈ u_{n}^{β} implies γ ≤ β.

Proof of (v):

lim_{n→∞} \frac{|u_{n}^{α}|}{n} ≤ lim_{n→∞} \frac{|u_{n}^{β}| + 1}{n} = 0,

by the induction hypothesis.

Case 2. δ is a limit ordinal > 0. Let δ_{n} be an increasing cofinal ω-sequence converging to δ, for all δ < ω_{1}. Let us choose natural numbers n_{0}, n_{1}, ... such that δ_{i} ∈ u_{n_{i}}^{δ_{i+1}} and n ≥ n_{i+1} implies n_{i} · |u_{n}^{δ_{i+1}}| < n. Now we let

u_{n}^{α} = u_{n}^{δ_{i}} ∪ {α}, if n_{i} ≤ n < n_{i+1}.

To prove (iv), let γ ∈ u_{n}^{α}. We wish to show that u_{n}^{γ} = u_{n}^{α} ∩ (γ + 1). Suppose n_{i} ≤ n < n_{i+1}. Then u_{n}^{α} = u_{n}^{δ_{i}} ∪ {α}. But then γ ∈ u_{n}^{α} implies γ ∈ u_{n}^{δ_{i}} ∪ {α}. If γ = α, then as before, u_{n}^{γ} = u_{n}^{α} ∩ (γ + 1). So suppose γ ∈ u_{n}^{δ_{i}}. Then

u_{n}^{γ} = u^{δ_{i}} ∩ (γ + 1) = u_{n}^{α} ∩ (γ + 1).

Finally, we prove (iii): Let γ ∈ u_{n}^{δ}, δ a limit. Let n_{i} be such that u_{n}^{α} = u_{n_{i}}^{δ_{i}} ∪ {α}. We have u_{n_{i}}^{δ_{i}} = u_{n_{i}}^{δ_{i+1}} ∩ (δ_{i} + 1). Therefore γ ∈ u_{n_{i}}^{δ_{i+1}} ∪ {δ} = u_{n+1}^{δ}. To prove (v), let ϵ > 0 and choose i so that ϵ · n_{i} > 2. We observe that n_{i} ≤ n implies

lim_{n→∞} \frac{|u_{n}^{α}|}{n} = lim_{n→∞} \frac{|u_{n}^{δ_{i}}|}{n} + \frac{1}{n} < \frac{1}{n_{i}} + \frac{1}{n} < ϵ.

□

In [4] models of higher cardinality are considered, and embedding theorems are obtained under a set theoretic assumption.

References

[1] B. Jónsson and P. Olin, Almost direct products and saturation, Compositio Math., 20, 1968, 125–132 [2] R. Kaye. Models of Peano Arithmetic. Oxford Logic Guides. Oxford:

Oxford University Press, 1991.

[3] J. Kennedy. On embedding models of arithmetic into reduced powers. Ph.D. thesis, City University of New York Graduate Center, 1996.

[4] J. Kennedy and S. Shelah, On regular reduced products, Journal of Symbolic Logic, to appear.

[5] S. Shelah, For what filters is every reduced product saturated?, Israel J. Math., 12, 1972, 23–31