算术的非标准模型（修改稿）

算术的非标准模型包括无穷大自然数，是非标准分析的先驱。

鲁宾逊无穷小微积分（超实数）就是传统微积分的非标准模型。

深入学习、理解算术的非标准模型对于正确理解无穷小微积分是十分有益的。

    建议读者仔细研读本文附件。，

袁萌  陈启清   12月10日

附件：算术的非标准模型

Non-Standard Models of Arithmetic

Asher M. Kach

1 May 2004

Abstract Almost everyone, mathematician or not, is comfortable with the standard model (N : +,·) of arithmetic. Less familiar, even among logicians, are the non-standard models of arithmetic. In this talk we prove their existence, explore their structure, discuss their uniqueness, and examine various model and computability theoretic properties they possess. As much as is reasonably possible, the history of their discovery and study will be integrated into the talk.

Denitions and Notation

Throughout we will refer to N0 = (N : +,·) as the standard model of arithmetic. Any model of Th(N0) not isomorphic to N0 will be termed a non-standard model of arithmetic, or more briey a non-standard model. An element x ∈M will be called nite if x ∈N0; otherwise x will be called innite. Working in a model M, we will say that x is less than or equal to y, denoted x ≤ y, if there is a z ∈M such that x + z = y. We dene y− · x to be z if such a z exists and 0 if no such z exists. We will use N, Z, Q, and R to denote both the usual set and its order type. If α and β are order types, we will use αβ to denote the order type obtained by replacing each element of β by a copy of α.

Existence of Non-Standard Models

Theorem: (Skolem, 1934 / 1955) There is a countable non-standard model of arithmetic. Proof 1: (Idea) Letting F ={fi : i ∈ ω} be the set of denable functions in N0, dene a one-to-one increasing function g that allows an ordering to be put on equivalence classes of F. Dene addition and multiplication to be pointwise and verify that (F/≡: +/≡,·/≡)∈Mod(Th(N0)).

Proof 2: (Idea) After augmenting the language with a constant c, use the Compactness Theorem to show the consistency of an innite number via the set of sentences Φ ={c > n : n ∈ ω}.

Order Types of Non-Standard Models

Theorem: (Henkin, 1950) The order type of any non-standard model of arithmetic is of the form N+Zθ for some dense linear order θ without endpoints. Proof: (Sketch) For denseness, between any two elements a  b, either q = (a + b)/2 or q = (a + b +1)/2 exists. In either case, it must be that a  q  b. Extend q to a Z-chain by adding and subtracting nite integers. For unboundedness, for any innite a, the element 2a must satisfy a 2a. Corollary: Any countable non-standard model of arithmetic has order type N+ZQ. Proof: Up to isomorphism, the only countable dense linear order without endpoints is Q.

Continuum Many Countable Non-Standard Models

Theorem: There are exactly 2ℵ0 non-isomorphic countable non-standard models of arithmetic. Proof: (Sketch) Augment the language with an extra constant c. Let P be any set of (nite) prime numbers and let ΦP be the set of sentences {p | c : p ∈ P}∪{p6| c : p 6∈ P}. Use the Compactness Theorem to show consistency of ΦP and L¨owenheim - Skolem to get a countable model. Finally argue that if there were fewer than continuum many countable models, then not all types would be realised.

The Overspill Principle

Theorem: Let M be a non-standard model of arithmetic and let b be any element of M.

(Weak Overspill) Let (x,y) have free variables x and y. Then ∀x ∈ ω[M|= (x,b)] if and only if ∃a innite [M|= (∀x < a)(x,b)].

Proof: (Sketch) Show that the set of natural numbers ω ⊂ M is not denable (using parameters) in M. For the non-trivial direction, if there was no such innite a, use that ω is not denable to contradict that M was assumed to be a non-standard model.

The Overspill Principle (Continued)

(Strong Overspill) Let (x,y,z) have free variables x, y, and z, and suppose (x,y,b) denes a function F : M → M. Then ∀x ∈ ω[F(x) is innite] if and only if ∃a innite ∀x < a[F(x) is innite]. Proof: For the non-trivial direction, apply Weak Overspill to the formula (x) given by Fx > x.

Corollary: For any innite integer a, there is an innite integer c with 2c < a. Proof: As 2x is nite for all nite integers x, and hence smaller than a, there must be an innite integer c with 2c < a by Weak Overspill.

Order Type of the Reals Not Realised

Theorem: (Klaus Pottho) There is no non-standard model of arithmetic with order type N+ZR. Proof: (Sketch) Assume there was a non-standard model of order type N+ZR, and let a be any innite element of it. Identify real numbers r with the corresponding Z-chain, Zr. Let rn for n ∈ ω be the Zr in which the element na resides. As the rn are increasing and bounded by the copy of Z in which the element a2 resides, the sequence {rn} converges to some real number r. Let b be any element of Zr, choosing b smaller than the multiple of a in Zr if one exists. Dene S ={x : a|x and x < b}. Then ω ={n : na ∈ S}, a contradiction to ω not being denable in any non-standard model of arithmetic.

Extension Types

Let M⊆N be models of arithmetic, not necessarily non-standard. Denition: An element a ∈ N −M is said to be M-innite if a > b for all b ∈ M; otherwise it is said to be M-nite. Denition: If every element of N −M is M-innite, then N is said to be an end extension of M. We write M⊆e N in this case. If every element of N −M is M-nite, then N is said to be a conal extension of M. We write M⊆c N in this case. If N−M contains both M-nite and M-innite integers, then N is said to be a mixed extension of M. We write M⊆m N in this case.

Extension Existence

Theorem: Every non-standard model M of PA has a proper elementary mixed extension (trivial), a proper elementary end extension (MacDowell and Specker, 1961), and a proper elementary conal extension (Rabin, 1962).

Theorem: (Gaifman, 1971) Let M⊆N be models of PA. Then there is a unique model ˆ M of PA such that M⊆c ˆM⊆e N. Moreover, the conal extension M⊆c ˆ M is elementary.

Corollary: Conal extensions are necessarily elementary. Proof: Let M⊆N be any conal extension. Then ˆ M=N by uniqueness and so the extension is elementary.

Recovering a Structure From End Segments

Theorem: (Smoryn´ski, 1977) Let M be a model of arithmetic with M = I ∪E, an initial segment and end segment. Then M can be completely recovered from the structure E = (E : +,·). Proof: (Idea) Similar to the construction of a eld of quotients from an integral domain. In E, dene x < y, S(x) = y (i.e. x +1 = y), and x|y. With M0 ={(a,b)∈ E2 : E |= b|a}, argue that M∼ = (M0/≡: +/≡,·/≡), where ≡ is the equivalence relation given by (a,b)≡(c,d) if and only if ad = b

(qww 1-14.

C. Smoryn´ski, Lectures on nonstandard models of arithmetic: Commemorating Guise