新传学院 订阅/关注/阅文/评论/公号
      4天前 北大袁萌最新内集理论是处理非标准分析的新方法

内集理论是处理非标准分析的新方法

1977年,Nenlson1932-2014)给自己的

 代表作起了这个古怪的名字。原文如下:             

     Nenlson E., “Internal set theory. A new approach to nonstandard analysis,” Bull. Amer. Math. Soc., 83, No. 6, 1165–1198 ( 1977).

 大家春节好!

袁萌 陈启清  123

附件:

Internal Set Theory1

Ordinarily in mathematics, when one introduces a new concept one denes it. For example, if this were a book on “blobs” I would begin with a denition of this new predicate: x is a blob in case x is a topological space such that no uncountable subset is Hausdor. Then we would be all set to study blobs. Fortunately, this is not a book about blobs, and I want to do something dierent. I want to begin by introducing a new predicate “standard” to ordinary mathematics without dening it. The reason for not dening “standard” is that it ys a syntactical, rather than a semantic, role in the theory. It is similar to the use of “xed” in informal mathematical discourse. One does not dene this notion, nor consider the set of all xed natural numbers. The statement “there is a natural number bigger than any xed natural number” does not appear paradoxical. The predicate “standard” will be used in much the same way, so that we shall assert “there is a natural number bigger than any standard natural number.” But the predicate “standard”— unlike “xed”—will be part of the formal language of our theory, and this will allow us to take the further step of saying, “call such a natural number, one that is bigger than any standard natural number, unlimited.” We shall introduce axioms for handling this new predicate “standard” in a consistent way. In doing so, we do not enlarge the world of mathematical objects in any way, we merely construct a richer language to discuss the same objects as before. In this way we construct a theory extending ordinary mathematics, called Internal Set Theory1 that axiomatizes a portion of Abraham Robinson’s nonstandard analysis. In this construction, nothing in ordinary mathematics is changed. 1It was rst presented in [Ne] Edward Nelson, “Internal set theory: A new approach to nonstandard analysis,” Bulletin American Mathematical Society 83 (1977), 1165–1198. A good introductory account is [Rt] Alain Robert, “Analyse non standard,” Presses polytechniques romandes, EPFL Centre Midi, CH–1015 Lausanne, 1985; translated by the author as “Nonstandard Analysis,” Wiley, New York, 1988.

1

2 CHAPTER 1. INTERNAL SET THEORY

1.1 External concepts

Let us begin by adjoining to ordinary mathematics a new predicate called standard. Using this new predicate, we can introduce new notions. For example, we can make the following denitions, in which the variables range over R, the set of all real numbers: x is innitesimal in case for all standard ε > 0 we have|x| ε, x is limited in case for some standard r we have |x| r, x ' y (x is innitely close to y) in case x−y is innitesimal, x  y (x is strongly less than y) in case x < y and x 6' y, x  y (x is strongly greater than y) in case y x, x ' in case x 0 and x is unlimited (i.e., not limited), x '− in case −x ', x in case x 6', x − in case x 6'−, x < y (x is nearly less than y) in case x y + α for some innitesimal α, x > y (x is nearly greater than y) in case y < x. A formula of ordinary mathematics—one that does not involve the new predicate “standard”, even indirectly—is called internal; otherwise, a formula is called external. The eleven denitions given above are all external formulas. Notice that the adjectives “internal” and “external” are metamathematical concepts—they are properties of formulas and do not apply to sets. One of the basic principles of ordinary mathematics, or internal mathematics as I shall call it from now on, is the subset axiom. This asserts that if X is a set then there is a set S, denoted by {x X : A}, such that for all x we have x S ↔ x X & A. Here A is a formula of internal mathematics. Usually it will have x as a free variable, but it may have other free variables as well. When we want to emphasize its dependence on x, we write it as A(x). Nothing in internal mathematics has been changed by introducing the new predicate, so the subset axiom continues to hold. But nothing in internal mathematics refers to the new predicate, so nothing entitles us to apply the subset axiom to external formulas. For example, we cannot prove that there exists a set I such that x I ↔ x R & x is innitesimal. The notation {x R : x '0} is not allowed; it is an example of illegal set formation. Only internal

§1.2 THE TRANSFER PRINCIPLE 3 formulas can be used to dene subsets. (Nevertheless, in Chapter 4 we shall nd a way to introduce so-called external sets.) Certain set formations that might at rst sight appear to be illegal are perfectly legitimate. For example, suppose that we have an innitesimal x > 0. Then we can form the closed interval [−x,x] consisting of all y such that −x y x. This is simply because we already know that for any x > 0 we can form the set [−x,x]. Exercises for Section 1.1 1. Let n be a nonstandard natural number. Can one form the set of all natural numbers k such that k n? Is this set nite? 2. Can one form the set of all limited real numbers? 3. Can one prove that every standard positive real number is limited? 4. Can one form the set of all standard real numbers x such that x2 1? 5. Assume that 1 is standard. Can one form the set of all limited real numbers x such that x2 1? 6. Can one prove that the sum of two innitesimals is innitesimal?

1.2 The transfer principle

We cannot yet prove anything of interest involving “standard” because we have made no assumptions about it. Our rst axiom is the transfer principle (T). The notation st means “for all standard”, and st means “there existsastandard”. LetAbeaninternalformulawhoseonlyfreevariables are x, t1, ..., tn. Then the transfer principle is stt1•••sttn[stxA↔xA]. (1.1) We may think of the t1, ..., tn as parameters; we are mainly interested in x. Then the transfer principle asserts that if we have an internal formula A, and all the parameters have standard values, and if we know that A holds for all standard x, then it holds for all x. (The converse direction is trivial, and we could have stated (T) with just instead of ↔.)The intuition behind (T) is that if something is true for a xed, but arbitrary, x then it is true for all x. Notice that two formulas are equivalent if and only if their negations are. But we have ¬x¬A ↔ xA, so if we apply (T) to ¬A we obtain the dual form of the transfer principle: stt1•••sttn[stxA↔xA]. (1.2)

4 CHAPTER 1. INTERNAL SET THEORY Let us write A B (A is weakly equivalent to B) to mean that for all standard values of the free variables in the formulas, we have A↔B. Then we can rewrite the two forms of (T) as stxAxA and stxA xA whenever A is an internal formula. Applying these rules repeatedly, we see that any internal formula A is weakly equivalent to the formula Ast obtained by replacing each by st and by st. Then t1,...,tn are standard Ast, where t1, ..., tn are the free variables in A, is called the relativization of A to the standard sets. Consider an object, such as the empty set, the natural numbers N, or the real numbers R, that can be described uniquely within internal mathematics. That is, suppose that there is an internal formula A(x) whose only free variable is x such that we can prove existence xA(x) and uniqueness A(x1) & A(x2) x1 = x2. By the dual form of transfer, stxA(x); so by uniqueness, the x such that A(x) holds is standard. For example, let A(x) be y[y / x]. There is a unique set, the empty set ,that satises A( x). Therefore is standard. The formulas describing Nand R are longer, but by the same reasoning, N and R are standard. Any object that can be uniquely described within internal mathematics is standard: the real numbers 0, 1, and π, the Hilbert space L2(R,dx) where dx is Lebesgue measure, the rst uncountable ordinal, and the loop space of the fteen dimensional sphere are all standard. The real number 10−100 is standard, so if x is innitesimal then |x|10−100. The same reasoning applies to internal formulas A(x) containing parameters—provided the parameters have standard values. For example, if t is a standard real number then so is sint (let A(x,t) be x = sint) and if X is a standard Banach space so is its dual. As an example of transfer, we know that for all real x > 0 there is a natural number n such that nx 1; therefore, for all standard x > 0 there is a standard n such that nx 1. But suppose that x > 0 is innitesimal. Do we know that there is a natural number n such that nx 1? Of course; we already know this for all x > 0. But if we try to argue as follows—“there is an n such that nx 1; therefore, by the dual form of transfer, there is a standard n such that nx 1”—then we have made an error: transfer is only valid for the standard values of the parameters (in this case x) in the formula. This is an example of illegal transfer. It is the most common error in learning nonstandard analysis. Before applying transfer, one must make sure that any parameters in the formula—even those that may be implicit in the discussion—have standard values.

§1.3 THE IDEALIZATION PRINCIPLE 5 Another form of illegal transfer is the attempt to apply it to an external formula. For example, consider “for all standard natural numbers n, the number n is limited; by transfer, all natural numbers are limited”. This is incorrect. Before applying transfer, one must check two things: that the formula is internal and that all parameters in it have standard values.

Exercises for Section 1.2 1. Can one prove that the sum of two innitesimals is innitesimal? 2. If r and s are limited, so are r + s and rs. 3. If x ' 0 and |r|, then xr ' 0. 4. If x 6= 0, then x is innitesimal if and only if 1/x is unlimited. 5. Is it true that the innitesimals are a maximal ideal in the integral domain of limited real numbers? What does the quotient eld look like? 6. Consider the function f:x 7 x2 on a closed interval. Then f is bounded, and since it is standard it has a standard bound.—Is this reasoning correct? 7. Let x and y be standard with x < y. Prove that x y. 1.3 The idealization principle

So far, we have no way to prove that any nonstandard objects exist. Our next assumption is the idealization principle (I). The notation stn means “for all standard nite sets”, and stn means “there exists a standard nite set such that”. Also, xX means “for all x in X”, andxX means “there exists x in X such that”. Let A be an internal formula. Then the idealization principle is stnx0yxx0A↔ystxA. (1.3) There are no particular pitfalls connected with this assumption: we must just be sure that A is internal. It can contain free variables in addition to x and y (except for x0). The intuition behind (I) is that we can only x a nite number of objects at a time. To say that there is a y such that for all xed x we have A is the same as saying that for any xed nite set of x’s there is a y such that A holds for all of them. As a rst application of the idealization principle, let A be the formula y 6= x. Then for every nite set x0, and so in particular for every standard nite set x0, there is a y such that for all x in x0 we have y 6= x. Therefore, thereexistsanonstandard y. Thesameargumentworkswhen x and y are restrictedto range overany innite set. Inother words, every

6 CHAPTER 1. INTERNAL SET THEORY

innite set contains a nonstandard element. In particular, there exists a nonstandard natural number. By transfer, we know that 0 is standard, and we know that if n is standard then so is n + 1. Do we have a contradiction here? Why can’t we say that by induction, all natural numbers are standard? The induction theorem says this: if S is a subset of N such that 0 is in S and such that whenever n is in S then n + 1 is in S, then S = N. So to apply induction to prove that every natural number is standard, we would need a set S such that n is in S if and only if n is standard, and this we don’t have. As a rough rule of thumb, until one feels at ease with nonstandard analysis, it is best to apply the familiar rules of internal mathematics freely to elements, but to be careful when working with sets of elements. (From a foundational point of view, everything in mathematics is a set. For example, a real number is an equivalence class of Cauchy sequences of rational numbers. Even a natural number is a set: the number 0 is the empty set, the number 1 is the set whose only element is 0, the number 2 is the set whose only elements are 0 and 1, etc. When I refer to “elements” or “objects” rather than to sets, only a psychological distinction is intended.) We can prove that certain subsets of R and N do not exist. Theorem 1. There does not exist S1, S2, S3, S4, or S5 such that, for all n in N and x in R, we have n S1 ↔ n is standard, n S2 ↔ n is nonstandard, x S3 ↔ x is limited, x S4 ↔ x is unlimited, or x S5 ↔ x is innitesimal. Proof. As we have seen, the existence of S1 would violate the induction theorem. If S2 existed we could take S1 = N\S2, if S3 existed we could take S1 = NS3, if S4 existed we could take S3 = R\S4, and if S5 existed we could take S4 ={x R : 1/x S5}. This may seem like a negative result, but it is frequently used in proofs. Suppose that we have shown that a certain internal property A(x) holds for every innitesimal x; then we automatically know that A(x) holds for some non-innitesimal x, for otherwise we could let S5 be the set {x R : A(x)}. This is called overspill. By Theorem 1 there is a non-zero innitesimal, for otherwise we could let S5 ={0}. We can also see this directly from (I). We denote by R+ the set of all strictly positive real numbers. For every nite subset x0 of R+ there is a y in R+ such that y x for all x in x0. By (I), there is a y in R+ such that y x for all standard x in R+. That is, there exists an innitesimal y > 0.

§1.3 THE IDEALIZATION PRINCIPLE 7 Notice that in this example, to say that y is smaller than every elementof x0 isthesameassayingthat y issmallerthantheleastelement of x0, so the nite set really plays no essential role. This situation occurs so frequently that it is worth discussing it in a general context in which the idealization principle takes a simpler form. Recall that a directed set is a set D together with a transitive binary relation such that every pair of elements in D has an upper bound. For example, R+ is a directed set with respect to . (In this example, the minimum of two elements is an upper bound for them.) Let A be a formula with the free variable x restricted to range over the directed set D. We say that A lters in x (with respect to D and) in case one can show that whenever x z and A(z), then A(x). (Here A(z) is the formula obtained by substituting z for each free occurrence of x in A(x), with the understanding that z is not a bound variable of A.) Suppose that the internal formula A lters in x. Then the idealization principle takes the simpler form stxyA↔ystxA. (1.4) That is, we can simply interchange the two quantiers. The idealization principle also has a dual form. If A is internal, then stnx0yxx0A↔ystxA. (1.5) We say that A colters in x in case we can show that whenever x z and A(x), then A(z). Then (1.5) takes the simpler form: stxyA↔ystxA. (1.6) In practice, there is no need to make the distinction between ltering and coltering, and I may say “lters” when “colters” is correct. As an example of the dual form, suppose that f:RR is such that every value of f is limited. Then f is bounded, and even has a standard bound. To see this, use (1.6), where the ltering relation is on the values of the function. We know that for all y there exists a standard x such that |f(y)| x. Hence there is a standard x such that |f(y)| x for all y.

8 CHAPTER 1. INTERNAL SET THEORY

Theorem 2. Let S be a set. Then S is a standard nite set if and only if every element of S is standard. Proof. Let S be a standard nite set, and suppose that it contains a nonstandard y. Then there exists a y in S such that for all standard x we have y 6= x, so by (I), for all standard nite sets x0, and in particular for S, there is a y in S such that for all x in S we have y 6= x. This is a contradiction, so every element of S is standard. Conversely, suppose that every element of S is standard. We already know that S must be nite, because every innite set contains a nonstandard element. Let x and y range over S and apply the dual form of idealization to the formula x = y. We know that for all y there is a standard x with x = y, so there is a standard nite set x0 such that for all y there is an x in x0 with x = y. Then x0 S; that is, S x0 where denotes the power set. But x0 is standard, so by (T) x0 is standard. Also, x0 is nite, so x0 is a standard nite set. By the forward direction of the theorem established in the preceding paragraph, every element of x0 is standard, so S is standard.2 This has the following corollary. Theorem 3. Let n and k be natural numbers, with n standard and k n. Then k is standard. Proof. Let S = {k N : k n}. By (T), S is standard. It is nite, so all of its elements are standard. Therefore we can picture the natural numbers as lying on a tape, with the standard numbers to the left and the nonstandard numbers to the right. The demarcation between the two portions is strange: the left portion is not a set, and neither is the right. I want to emphasize that we did not start with the left portion and invent a new right portion to be tacked on to it—we started with the whole tape, the familiar set N of all natural numbers, and invented a new way of looking at it. Theorem 4. There is a nite set that contains every standard object. Proof. This is easy. Just apply (I) to the formula x y & y isnite. If we think of “standard” semantically—with the world of mathematical objects spread out before us, some bearing the label “standard” and others not—then these results violate our intuition about nite sets. But recall what it means to say that X is a nite set. This is an internal 2I am grateful to Will Schneeberger for pointing out a gap in my rst proof of this theorem.

§1.3 THE IDEALIZATION PRINCIPLE 9 notion, so it means what it has always meant in mathematics. What has it always meant? There are two equivalent characterizations. For n in N, we let In ={k N : k < n}. Then a set X is nite if and only if there is a bijection of X with In for some n. There is also the Dedekind characterization: X is nite if and only if there is no bijection of X with a proper subset of itself. Consider the set In where n is a nonstandard natural number. This certainly satises the rst property. Nothing was said about n being standard; this cannot even be formulated within internal mathematics. But does it satisfy the Dedekind property? Suppose that we send each nonstandard element of In to its predecessor and leave the standard elements alone; isn’t this a bijection of In with In−1? No, its denition as a function would involve illegal set formation.—Perhaps it is fair to say that “nite” does not mean what we have always thought it to mean. What have we always thought it to mean? I used to think that I knew what I had always thought it to mean, but I no longer think so. In any case, intuition changes with experience. I nd it intuitive to think that very, very large natural numbers and very, very small strictly positive real numbers were there all along, and now we have a suitable language for discussing them.

Exercises for Section 1.3 1. A natural number is standard if and only if it is limited. 2. Does there exist an unlimited prime? 3. What does the decimal expansion of an innitesimal look like? 4. Let H be a Hilbert space. Does there exist a nite dimensional subspace containing all of its standard elements? Is it closed? 5. Suppose that the Sn, for n in N, are a sequence of disjoint sets with union S, and suppose that every element x in S is in Sn for some standard n. Can one show that all but a nite number of them are empty? Can one show that all but a standard nite number of them are empty? 6. Prove Robinson’s lemma: Let n 7 an be a sequence such that an ' 0 for all standard n. Then there is an unlimited N such that an ' 0 for all n N. 7. Let n 7 an be a sequence such that an  for all standard n. Is there an unlimited N such that an for all n N? 8. We have been saying “let x range over X” to mean that each xA should be replaced by x[x X A] and each xA should be replaced by x[x X & A]. Let nX be the set of all non-empty nite subsets of X. Show that if x ranges over X, then (I) can be written as stx0yxx0A ↔ystxA where x0 ranges over nX.

10 CHAPTER 1. INTERNAL SET THEORY

1.4 The standardization principle

Our nal assumption about the new predicate “standard” is the standardization principle (S). It states that stXstYstz[z Y ↔ z X & A]. (1.7) Here A can be any formula (not containing Y), external or internal. It may contain parameters (free variables in addition to z and X). The intuition behind (S) is that if we have a xed set, then we can specify a xed subset of it by giving a criterion for judging whether each xed element is a member of it or not. Twosetsareequaliftheyhavethesameelements. By(T),twostandard sets are equal if they have the same standard elements. Therefore, the standard set Y given by (S) is unique. It is denoted by S{z X : A}, which may be read as the standard set whose standard elements are those standard elements of X such that A holds. Unfortunately, any shortening of this cumbersome phrase is apt to be misleading. For standard elements z, we have a direct criterion for z to be an element of S{z X : A}, namely that A(z) hold. But for nonstandard elements z, this is not so. It may happen that z is in S{z X : A}but A(z) does not hold, and conversely A(z) may hold without z being in S{z X : A}. For example, let X = S{z R : z ' 0}. Then X = {0} since 0 is the only standard innitesimal. Thus we can have z ' 0 without z being in X. Let Y = S{z R :|z|}. Then Y = R since every standard number is limited. Thus we can have z Y without z being limited. The standardization principle is useful in making denitions. Let x range over the standard set X. When we make a denition of the form: for x standard, x is something-or-other in case a certain property holds, this is understood to mean the same as x is something-or-other in case x S{x X : a certain property holds}. For example, let f:R R and let us say that for f standard, f is nice in case every value of f is limited. Thus f is nice if and only if f N, where we let N = S{f RR : every value of f is limited}. (The notation XY signies the set of all functions from Y to X.) I claim that f is nice if and only if f is bounded. To prove this, we may, by (T), assume that f is standard. We already saw, in the previous section, that if every value of f is limited, then f is bounded. Conversely, let f be bounded. Then by (T) it has a standard bound, and so is nice. This proves the claim. But, one might object, the rst transfer is illegal because “nice” was dened externally. The point is this: being nice is the same as being

§1.4 THE STANDARDIZATION PRINCIPLE 11 in the standard set N, so the transfer is legal. In complete detail, (T) tells us that for all standard N we have stf[f N ↔ f is bounded]f[f N ↔ f is bounded]. Inotherwords, thiskindofdenitionbymeansof(S)isawayofdening, somewhat implicitly, an internal property. Let x and y range over a set V , let ˜ y range over V V , and let A be internal. Then xyA(x,y)↔˜ yxAx, ˜ y(x). The forward direction is the axiom of choice, and the backward direction is trivial. If we apply transfer to this, assuming that V is standard, we obtain stxstyA(x,y)st˜ ystxAx, ˜ y(x). But we can do much better than this. Let A be any formula, external or internal. Then stxstyA(x,y)↔st˜ ystxAx, ˜ y(x). (1.8) The backward direction is trivial, so we need only consider the forward direction. Suppose rst that for all standard x there is a unique standard y such that A(x,y). Then we can let ˜ y = S{hx,yi : A(x,y)}. Inthe general case, let e Y = S{hx,Yi: Y = S{y : A(x,y)}}. Then e Y is a standard set-valued function whose values are non-empty sets, so by the axiom of choice relativized to the standard sets, it has a standard cross-section ˜ y of the desired form. We call (1.8) the functional form of standardization (eS). It has a dual form: stxstyA(x,y)↔st˜ ystxAx, ˜ y(x). (1.9)The requirements in (1.8) and (1.9) are that x and y range over some standard set V and that ˜ y range over V V . This includes the case that x and y range over dierent standard sets X and Y, with ˜ y ranging over Y X, becausewecanalwayslet V = XY andincludetheconditions x X and y Y in the formula A. If X is a set, contained in some standard set V , we let SX = S{x V : x X}.

12 CHAPTER 1. INTERNAL SET THEORY

This clearly does not depend on the choice of V , and in practice the requirement that X be contained in some standard set is not restrictive. Then SX is the unique standard set having the same standard elements as X. It is easy to see that if f is a function then so is Sf. The theory obtained by adjoining (I), (S), and (T) to internal mathematics is Internal Set Theory (IST). So far, we have not proved any theorems of internal mathematics by these new methods. Here is a rst example of that, a theorem of de Brujn and Erdos3 on the coloring of innite graphs. By a graph I mean a set G together with a subset R of G×G. Wedene a k-coloring of G, where k is a natural number, to be a function g:G {1,...,k} such that g(x) 6= g(y) whenever hx,yi R. An example is G = R2 and R = {hx,yi : |x−y| = 1} where |x−y| is the Euclidean metric on R2. (This graph is known to have a 7-coloring but no 3-coloring.) The theorem asserts that if every nite subgraph of G has a k-coloring, so does G. This is not trivial, because if we color a nite subgraph, we may be forced to go back and change its coloring to color a larger nite subgraph containing it. To prove the theorem, we assume, by (T), that G and k are standard. By (I), there is a nite subgraph F of G containing all its standard elements, and by hypothesis F has a k-coloring f. Let g = Sf. Since f takes only standard values, every standard element of G is in the domain of g. By (T), every element of G is in the domain of g. To verify that g is a k-coloring, it suces, by (T), to examine the standard elements, where it agrees with f. This concludes the proof.

Exercises for Section 1.4 1. Show that if f is a function, so is Sf. What can one say about its domain and range? 2. Deduce (S) from (eS). 3. Dene f by f(x) = t/π(t2 + x2) where t > 0 is innitesimal. What isR f(x)dx? What is Sf? 4. Establish external induction: Let A(n) be any formula, external or internal, containing the free variable n and possibly other parameters. Suppose that A holds for 0, and that whenever it holds for a standard n it also holds for n + 1. Then A(n) holds for all standard n. 5. Let the Greek variables range over ordinals. Establish external transnite induction: stαA(α) stβ[A(β) & stγ[A(γ) β γ]]. 6. Deduce (I) from the forward direction of (I). 3N. G. de Brujn and P. Erdos, “A colour problem for innite graphs and a problem in the theory of relations,” Indagationes Mathematicae 13 (1951), 371–373.

§1.5 ELEMENTARY TOPOLOGY 13 1.5 Elementary topology

In this section I shall illustrate IST with some familiar material. In the following denitions by (S), we assume that E R, that f:E R, and that x,y E. For f and x standard, f is continuous at x in case whenever y ' x we have f(y)' f(x). For f and E standard, f is continuous on E in case for all standard x, whenever y ' x we have f(y)' f(x). For f and E standard, f is uniformly continuous on E in case whenever y ' x we have f(y)' f(x). For E standard, E is compact in case for all x in E there is a standard x0 in E with x ' x0. For E standard, E is open in case for all standard x0 in E and all z in R, if z ' x0 then z is in E. For E standard, E is closed in case for all x in E and standard x0 in R, if x ' x0 then x0 is in E. For E standard, E is bounded in case each of its elements is limited. It can be shown that these denitions are equivalent to the usual denitions, but rather than worry about that now, let us develop a direct intuition for these formulations by examining them in various familiar situations. Let us prove that [0,1] is compact. Notice that it is standard. Let x be in [0,1]. Then it can be written as x =P n=1 an2−n where each an is 0 or 1, and conversely each number of this form is in [0,1]. This binary expansion is determined by a function a:N+ {0,1}. Let b = Sa. Then bn = an for all standard n, so if we let x0 =P n=1 bn2−n then x0 is standard, x0 ' x, and x0 is in [0,1]. Therefore [0,1] is compact. This has the following corollary. Theorem 5. Each limited real number is innitely close to a unique standard real number. Proof. Let x be limited. Then [x] is a limited, and therefore standard, integer. Since x−[x] is in the standard compact set [0,1], there is a standard y0 innitely close to it, so if we let x0 = y0 +[x] then x0 is standard and innitely close to x. The uniqueness is clear, since 0 is the only standard innitesimal.

14 CHAPTER 1. INTERNAL SET THEORY

If x is limited, the standard number that is innitely close to it is called the standard part of x, and is denoted by stx. Now let us prove that a continuous function f on a compact set E is bounded. By (T), we assume them to be standard. Let K ', and let x be in E. It suces to show that f(x) K. There is a standard x0 in E with x ' x0, and since f(x0) is standard we have f(x0)  K. But by the continuity of the standard function f we have f(x)' f(x0), so f(x) K, which concludes the proof. (It may seem like cheating to produce an unlimited bound. By (T), if a standard function f is bounded, then it has a standard bound. But this is a distinction that can be made only in nonstandard analysis.) Somewhat more ambitiously, let us show that a continuous function f on a compact set E achieves its maximum. Again, we assume them to be standard. By (I), there is a nite subset F of E that contains all the standard points, and the restriction of f to the nite set F certainly achieves its maximum on F at some point x. By compactness andcontinuity, thereisastandard x0 in E with x0 ' x and f(x0)' f(x). Therefore f(x0) > f(y) for all y in F. Since every standard y is in F, wehave f(x0) > f(y) whenever y is standard, but since both numbers are standard we must have f(x0) f(y) whenever y is standard. By (T), this holds for all y, and the proof is complete. The same device can be used to prove that if f is continuous on [0,1] with f(0)0 and f(1)0, then f(x) = 0 for some x in [0,1]. The proof that a continuous function on a compact set is uniformly continuous requires no thought; it is a simple verication from the definitions. It is equally easy to prove that a subset of R is compact if and only if it is closed and bounded (use Theorem 5 for the backward direction). All of this extends to Rn. Notice that Rn is standard if and only if n is, so in the denitions by (S), include “for n standard”. For a general metric space hX,di, where d is the metric, we dene x ' y to mean that d(x,y) is innitesimal. Much of what was done above extends to metric spaces. In denitions by (S), include “for X and d standard”. For X and d standard, a metric space hX,di is complete in case for all x, if for all standard ε > 0 there is a standard y with d(x,y) ε, then there is a standard x0 with x ' x0. This is equivalent to the usual denition. I shall sketch a proof of the Baire category theorem to illustrate an important point about nonstandard analysis. Let hX,di be a complete non-empty metric space, and let the Un be a sequence of open dense sets with intersection U. We want to show that U is non-empty. We denote the ε-neighborhood of x by N(ε,x). There are x1 and 0 < ε1 < 1/2

§1.5 ELEMENTARY TOPOLOGY 15 such that N(ε1,x1) U1. Since U2 is open and dense, there are x2 and 0 < ε2 < 1/22 such that N(ε2,x2) U2 N(ε1/2,x1). Continue in this way by induction, constructing a Cauchy sequence xn that converges to some point x, since X is complete. This x is in each Un, and so is in U. This proof is just the usual proof, and that is the important point. Nonstandard analysis is not an alternative to internal mathematics, it is an addition. By the nature of this book, almost all of the material consists of nonstandard analysis, but I emphatically want to avoid giving the impression that it should somehow be separated from internal mathematics. Nonstandard analysis supplements, but does not replace, internal mathematics. Let X be a standard topological space, and let x be a standard point in it. Then we dene the relation y ' x to mean that y is in every standard neighborhood of x. The external discussion of continuity and compactness given above for R extends to this setting. Let E be a subset of the standard topological space X. Then we dene the shadow of E, denoted by E, as follows: E = S{x X : y ' x for some y in E}. (1.10) Theorem 6. Let E be a subset of the standard topological space X. Then the shadow of E is closed. Proof. Let z be a standard point of X in the closure of E. Then every open neighborhood of z contains a point of E, so by (T) every standard open neighborhood U of z contains a standard point x of E. But for a standard point x of E, there is a y in E with y ' x, so y is in U. That is to say, stUy[y E U]. The open neighborhoods of z are a directed set under inclusion and this formula lters in U, so by the simplied version (1.4) of (I) we have ystU[y E U]; that is, yE[y ' z]. Thus z is in E. We have shown that every standard point z in the closure of E is in E, so by (T) every point z in the closure of E is in E. Thus E is closed. There is a beautiful nonstandard proof of the Tychonov theorem. Let T be a set, let Xt for each t in T be a compact topological space, and let be the Cartesian product =QtT Xt with the product topology. We want to show that is compact. By (T), we assume that t 7 Xt is standard, so that is also standard. Let ω be in . For all standard t there is a standard point y in Xt such that y ' ω(t), so by (eS) there is a standard η in such that for all standard t we have η(t) ' ω(t). By the denition of the product topology, η ' ω, so is compact.

16 CHAPTER 1. INTERNAL SET THEORY

Exercises for Section 1.5 1. Precisely how is (eS) used in the proof of the Tychonov theorem? 2. Let X be a compact topological space, f a continuous mapping of X onto Y . Show that Y is compact. 3. Is the shadow of a connected set connected? 4. Let x be in R. What is the shadow of {x}? 5. Let f(x) = t/π(t2 + x2), where t > 0 is innitesimal. What is the shadow of the graph of f? 6. Let E be a regular polygon of n sides inscribed in the unit circle. What is the shadow of E?

1.6 Reduction of external formulas

It turns out that (with a proviso which I shall discuss shortly) every external formula can be reduced to a weakly equivalent internal formula. This is accomplished by a kind of formal, almost algebraic, manipulation of formulas, using (eS) and (I) to push the external quantiers st and st to the left of the internal quantiers and , and then using (T) to get rid of them entirely. In this way we can show that the denitions made using (S) in the previous section are equivalent to the usual ones. More interestingly, we can reduce the rather weird external theorems that we have proved to equivalent internal form. The proviso, which has only nuisance value, is that whenever we use (eS) to introduce a standard function ˜ y(x), then x and y must be restricted to range over a standard set, to give the function ˜ y a domain. (Actually, it suces to make this restriction on x alone.) I will not make this explicit all of the time. To reduce a formula, rst eliminate all external predicates, replacing them by their denitions until only “standard” is left. Even this should be eliminated, replacing “x is standard” by sty[y = x]. Second, look for an internal quantier that has some external quantiers in its scope. (If this never happens, we are ready to apply (T) to obtain a weakly equivalent internal formula.) If the internal quantier is , use (eS) to pull the st’s to the left of the st’s (if necessary, thereby introducing standard functions), where they can then be pulled to the left of . If the internal quantier is , proceed by duality. Third, whenever ystxA (or its dual) occurs with A internal, use (I), taking advantage of its simplication (1.4) whenever A lters in x. One thing to remember in using this reduction algorithm is that the implication stxA(x) B is equivalent to stx[A(x) B], and dually stxA(x) B is equivalent to stx[A(x) B], provided in both cases that x does not occur free in B. (This has nothing to do with the superscript “st”; it is a general fact about quantiers in the hypothesis of an

§1.6 REDUCTION OF EXTERNAL FORMULAS 17 implication. For example, let A(s) be “s is an odd perfect number” and let B be the Riemann hypothesis. Then sA(s)B and s[A(s)B] say the same thing.) If B begins with an external quantier, it comes out of the implication unchanged, but we have our choice of which quantier to take out rst. The idea is to do this in such a way as to introduce as few functions as possible. If we have an equivalence, we must rewrite it as the conjunction of two implications and rename the bound variables, since they come out of the implications in dierent ways. For example, the formula stxA(x)↔styB(y) is equivalent to [stxA(x)styB(y)] & [stuB(u)stvA(v)], which in turn is equivalent to stxstustystv[A(x)B(y)] & [B(u)A(v)) and also to stystvstxstu[A(x)B(y)] & [B(u)A(v)) . If all of this is preceded by t, where t is a free variable in A or B, the second form is advantageous; if it is preceded by t, one should use the rst form. Let us illustrate the reduction algorithm with the denitions by (S) in the previous section of “continuous at x”, “continuous”, and “uniformly continuous”. The formulas in question are respectively yy ' x f(y)' f(x) , stxyy ' x f(y)' f(x) , xyy ' x f(y)' f(x) .We must eliminate '. With ε and δ ranging over R+, we obtain ystδ[|y−x| δ]stε[|f(y)−f(x)| ε] , (1.11) stxystδ[|y−x| δ]stε[|f(y)−f(x)| ε] , (1.12) xystδ[|y−x| δ]stε[|f(y)−f(x)| ε] . (1.13) In all of these formulas, f is a standard parameter, and x is a standard parameter in (1.11). First bring stε out; it goes all the way to the left.

18 CHAPTER 1. INTERNAL SET THEORY Then bringstδ out; it changes tostδ, and since the formula lters in δ, it goes to the left of y, and also of x in (1.13). This yields stεstδy|y−x| δ |f(y)−f(x)| ε , stεstxstδy|y−x| δ |f(y)−f(x)| ε , stεstδxy|y−x| δ |f(y)−f(x)| ε . Now apply transfer; this simply removes the superscripts “st” and shows that our denitions are equivalent to the usual ones. Now consider xstx0[x ' x0]; that is, xstx0stε|x−x0| ε . (1.14)It is understood that x and x0 range over the standard set E; this was our denition by (S) of E being compact. First we move stε to the left, by (eS), introducing the standard function ˜ ε:E R+. Thus (1.14)becomes st˜ εxstx0|x−x0| ˜ ε(x0) . (1.15)Now use (I). There is no ltering in (1.15), so it becomes st˜ εstnx0 0xx0x0 0|x−x0| ˜ ε(x0) .Now apply (T). We obtain ˜ εnx0 0xx0x0 0|x−x0| ˜ ε(x0) ,where n means “there exists a nite set such that” (and similarly n means “for all nite sets”). But this is mathematically equivalent to the usual denition of a set being compact. Denitions by (S) are an external way of characterizing internal notions, but they simultaneously suggest new external notions. These are often indicated by the prex S-. Thus we say that f is S-continuous at x in case whenever y ' x we have f(y) ' f(x). If both f and x are standard, this is the same as saying that f is continuous at x. But let t > 0 be innitesimal, and let f(x) = t/π(t2 + x2). Then f is continuous at 0 (this internal property is true for any t > 0), but it is not S-continuous at 0. Let g(x) = t for x 6= 0 and g(0) = 0. Then g is discontinuous at 0 but is S-continuous at 0. Let h(x) = x2. Then h is continuous at 1/t but is not S-continuous at 1/t. Similarly, we say that f is S-uniformly continuous in case whenever y ' x we have f(y)' f(x).

§1.6 REDUCTION OF EXTERNAL FORMULAS 19 I am not very fond of the S-notation. It seems to imply that to every internal notion there is a unique corresponding external S-notion, but this is not so. There may be distinct external notions that are equivalent for standard values of the parameters. Now let us apply the reduction algorithm to some of our external theorems. Let us split Theorem 2 into three dierent statements. (i) If every element of a set is standard, then the set is nite. That is, SySstx[y = x] S is nite , SySstxy = x S is nite , stnx0SySxx0y = x S is nite , (1.16) nx0SySxx0y = x S is nite , (1.17) nx0SS x0 S is nite .In other words, (i) is equivalent to (i 0): every subset of a nite set is nite. We used (I) for (1.16), (T) for (1.17), and then pushed quantiers back inside the implication as far as possible to make the result more readable. (ii) If every element of a set is standard, then the set is standard. That is, SySstx[y = x]stT[S = T] . (1.18)Apply (I) to the hypothesis: Sstnx0ySxx0[y = x]stT[S = T] ;simplify: Sstnx0[S x0]stT[S = T] ; pull out the quantiers and apply (I): stnx0stnT0STT0[S x0 S = T]; simplify and apply (T): nx0nT0S[S x0 S T0]. This is true for T0 = x0, where X denotes the power set of X (the set of all subsets of X). In other words, (ii) is equivalent to (ii0): the power set of a nite set is nite. When reducing an external formula, it is a

20 CHAPTER 1. INTERNAL SET THEORY

good idea to attack subformulas rst. For example, had we pulled the quantiers out of (1.18) directly, we would have obtained SstTySstx[y = x S = T], which after reduction and simplication gives: e x0nT0ShS \ TT0e x0(T) S T0i. (1.19) Every function must have a domain, so the use of (eS) to produce the nite-set valued function e x0 was illegitimate; to be honest, we should have introduced stV with all of the variables restricted to lie in V , so that after transfer the formula begins V with all of the variables restricted to lie in V . Consider this done. Here is an internal proof of (1.19). Choose any T0 and let T0 = e x0(T0){T0}. If S TTT0e x0(T), then in particular S e x0(T0) and so S T0. Thus (1.19) is an obscure way of saying that the power set of a nite set is nite. (iii) Every element of a standard nite set is standard. That is, stSS is niteySstx[y = x] .This reduces easily to Snx0[S is nite S x0]. In other words, (iii) is equivalent to (iii0): every nite set is a subset of some nite set. With the variables ranging over N, Theorem 3 is nkk n stj[j = k] ,which reduces easily to nnj0k[k n k j0]. Theorem 4, that there is a nite set containing every standard object, reduces immediately to the following triviality: for all nite sets x0 there is a nite set F such that every element of x0 is an element of F.

§1.6 REDUCTION OF EXTERNAL FORMULAS 21 Theorem 4 is shocking, but the informal statement “there is a nite set containing any xed element” appears quite reasonable. Similarly, with the variables ranging over R+, one is accustomed to saying “there is an x less than any xed ε.” Nonstandard analysis takes the further step of saying “call such an x an innitesimal.” I want to emphasize again that the predicate “standard” has no semantic content in IST; it is a kind of syntactical place-holder signifying that the object in question is to be held xed. With many objects in play at once, some depending on others, the syntax of being held xed becomes complicated, and the rules for handling the idea correctly are (I), (S), and (T). What Abraham Robinsoninventedisnothinglessthananewlogic. Hewasexplicitabout this in the last paragraph of his epoch-making book:4 Returning now to the theory of this book, we observe that it is presented, naturally, within the framework of contemporary Mathematics, and thus appears to arm the existence of all sorts of innitary entities. However, from a formalist point of view we may look at our theory syntactically and may consider that what we have done is to introduce new deductive procedures rather than new mathematical entities. One technical point is worth commenting on. It is essential to the success ofthereductionalgorithmthattheidealizationprincipleholdforinternal formulas with free variables; this feature was not present in Robinson’s notion of enlargement [Ro, §2.9]. Exercises for Section 1.6 1. Find a function f that is S-uniformly continuous without being uniformly continuous, and vice versa. 2. What is the reduction of the formula x ' 0? 3. What is the reduction of Theorem 5? 4. Show that the denitions by (S) of open, closed, and bounded in the previous section are equivalent to the usual ones. 5. Show that the denition by (S) of a complete metric space in the previous section is equivalent to the usual one. 6. Say that a sequence a:N R is S-Cauchy in case for all unlimited n and m we have an ' am. Show that a standard sequence is S-Cauchy if and only if it is Cauchy. Say that a is of limited uctuation in case for all standard ε > 0 and all k, if n1 < ••• < nk and |an1 −an2| ε, ..., |ank−1 −ank| ε, then k is limited. Show that a standard sequence is of limited uctuation if and only if it is Cauchy. Can a sequence be S-Cauchy without being of limited uctuation, or vice versa? 7. Is the unit ball of Rn, where n is unlimited, compact? 4[Ro] Abraham Robinson, ”Non-Standard Analysis,” Revised Edition, American Elsevier, New York, 1974.

22 CHAPTER 1. INTERNAL SET THEORY

8? Can the reduction of Theorem 6 be made intelligible? (The ? means that I don’t know the answer.)

1.7 Answers to the exercises

Section 1.1 1. Yes and yes; this set can be formed for any natural number, and it is a nite set. 2. No. 3. Let x be standard and positive. Then x x, so x is limited. 4. No. 5. At rst sight this looks like illegal set formation, but let S be the set of all real numbers x such that x2 1. Assuming that 1 is standard, we see that every x in S is limited, so S is the set in question. 6. Not yet; so far, nothing guarantees that if ε is standard then so is ε/2.

Section 1.2 1. Yes. Let x and y be innitesimal and let ε > 0 be standard. By transfer, ε/2 is standard, so that |x| ε/2 and |y| ε/2. Then |x + y| ε, and since ε was an arbitrary strictly positive standard number, x + y is innitesimal. 2. There are standard numbers R and S such that |r| R and |s| S. By (T), R + S and RS are standard. 3. Let ε > 0 be standard. There is a standard R, which we may take to be non-zero, such that |r| R. By (T), ε/R is standard, so |x| ε/R. Hence |xr| ε. 4. For ε > 0 and r = 1/ε, ε is standard if and only if r is standard, by the transfer principle. 5. We cannot speak of “the innitesimals” as an ideal, or of “the integral domain of limited real numbers”, without illegal set formation. If we avoid these illegal set formations, the preceding exercises essentially give an armative answer to the rst question. But to talk about “the quotient eld” we really need sets. The discussion must be postponed to Chapter 4, where we shall have external sets at our disposal. 6. No. If the closed interval is [0,b] where b is unlimited, the function has no standard bound. The transfer was illegal because the closed interval was a parameter. 7. We have x y + α where α is innitesimal and x and y are standard. Then x y + ε for all standard ε > 0, so by (T) we have x y + ε for all ε > 0. Hence x y.

§1.7 ANSWERS TO THE EXERCISES 23

Section 1.3 1. This is just a restatement of Theorem 3. 2. Yes. Euclid showed that for any natural number n there is a prime greater than n. 3. Let x > 0 be innitesimal. Then 0 < x < 1, so x is of the form x =P n=1 an10−n where each an is one of 0, ..., 9. Since 10−n is standard if n is, by (T), each an with n standard is 0. But x > 0, so not all of its decimal digits are 0. As we already know, any x > 0 has a rst non-zero decimal digit. What about the number whose decimal digits are 0 for all standard n and 7 for all nonstandard n? The question makes so sense. The decimal digits form a sequence; a sequence is a set; and I committed illegal set formation in posing the question. 4. Yes; by (I), there is a nite subset of H containing all of its standard points, so take its span. (This is by no means unique, and we cannot form the smallest such space without illegal set formation.) Any nite dimensional subspace of a Hilbert space is closed. 5. We have xstn[x Sn], where x ranges over S. By (I), we have that stnn0xnn0[x Sn], and since the sets are disjoint, all but a standard nite number of them are empty. 6. The set of all N such that |an| 1/n for all n N contains all standard N, so by overspill it contains some unlimited N. 7. Not necessarily; consider the identity function. 8. We can assume that X is non-empty, since otherwise both sides are vacuously true. The backward direction holds by (I). In the forward direction, by (I) we have some nite standard x0 that works, and we can take it to be non-empty. But by Theorem 2, x0 X is also a standard nite set, and it is an element of nX.

Section 1.4 1. Let f:X Y , and assume that X and Y are contained in some standard set. Let g = Sf. For all z, if z g then z SX × SY ; for all x in SX and y1 and y2 in SY , if hx,y1i and hx,y2i are in g, then y1 = y2. These statements hold by denition for the standard elements, and since the sets in question are standard, they hold by (T) for all elements. Thus Sf is a function from a subset of SX into SY . 2. Replace Y by its characteristic function. Let X be a standard set, let z range over X, let y range over {0,1}, and let ˜ y range over {0,1}X. We clearly have stzsty[y = 1 ↔ A], so by (eS) we have st˜ ystz[˜ y(z) = 1 ↔ A]. Then we let Y = {z X : ˜ y(z) = 1}. 3. By elementary calculus, this integral is equal to 1 for any t > 0. There are no standard pairs hx,f(x)i, so Sf is the empty set. 4. Let S = S{n N : A(n)}. Then 0 is in S. By assumption, for all standard n, if n is in S then n + 1 is in S, so by (T) this is true for all n. By induction, S = N. In particular, every standard n is in S, so A(n) holds for every standard n.

24 CHAPTER 1. INTERNAL SET THEORY

5. Let

S = S{γ α : A(γ)}. Then every standard element of S is an ordinal, so the same is true by (T) for all elements of S. Since S is non-empty (it contains α), it contains a least β, which is standard by (T). Then β α. Consider a standard γ such that A(γ). If α < γ, then certainly β γ; if γ α then γ S, so again β γ. This concludes the proof. This is often used to prove stαB(α). Argue indirectly. If not, there is a least standard α such that A(α) where A is ¬B. If we can show that α cannot be 0, a successor, or a limit ordinal, then the proof will be complete. 6. To establish (I), we need only show (without using the backward direction of the idealization principle) that every element of a standard nite set x0 is standard. We do this by external induction on the cardinality n of x0. By transfer, n is standard. The statement is vacuously true for n = 0. For n > 0, the set x0 contains an element, so by (T) it contains a standard element. Delete this element; what remains is a set of cardinality n−1 and by (T) it is a standard set. By the external induction hypothesis, all of the remaining elements are also standard.

Section 1.5 1. An element η of is a function from T toStT Xt such that η(t) Xtfor all t in T. So if we know that for all standard t there is a y in Xt with y ' ω(t), then (eS) tells us that there is a standard η (a ˜ y) in such that η(t) ' ω(t) for all standard t. By the denition of the product topology and (T), a standard basic neighborhood of η is given by a standard nite set of ti in T and a standard nite set of neighborhoods Ui of the η(ti), so η ' ω. 2. By (T), assume that f, X, and Y are standard. Let y be in Y . Then there is an x in X with f(x) = y and a standard x0 in X with x0 ' x. By (T), f(x0) is standard, and by continuity, f(x0) ' f(x). Hence Y is compact. 3. Not necessarily. In the plane, consider the x-axis and the parallel line one unit above it together with the vertical interval of length 1 with x unlimited joining them. 4. If x is limited, then {x} is {stx}; otherwise it is the empty set. 5. If we graph f, what we see is the union of the x-axis and the positive half of the y-axis, and this is the shadow of the graph of f. Let x 6= 0 be standard; then hx,f(x)i ' hx,0i. Let y > 0 be standard; then the positive solution x of f(x) = y is innitesimal, so hx,f(x)i ' h0,yi. Theorem 6 tells us that the origin too must be in the shadow. To see this directly, choose x = t1/4, for example; then hx,f(x)i'h0,0i. 6. Suppose that n is standard. If one, and hence all, of the vertices is standard, then E is standard and since it is closed E = E; otherwise E is obtained by an innitesimal rotation of E. If n is nonstandard, E is the unit circle.

§1.7 ANSWERS TO THE EXERCISES 25

Section 1.6 1. Let t > 0 be innitesimal, and let f(x) = t/π(t2 + x2). Then f is uniformly continuous but not S-uniformly continuous. For an example in the other direction, let g(x) = t for x 6= 0 and g(0) = 0. 2. The formula x ' 0, i.e., stε[|x| ε] where ε ranges over R+, is weakly equivalent to the internal formula ε[|x| ε], which is equivalent to x = 0. The only standard innitesimal is 0. 3. We have x[str[|x| r] stx0stε[|x−x0| ε]], strxstx0stε[|x| r |x−x0| ε], strst˜ εstnx0 0xxx0 0[|x| r |x−x0|≤˜ ε(x0)]; then remove the superscripts “st”. This says that every interval [−r,r] is compact. 4. For “open” we have stx0EzR[stε[|z−x0| ε] z E]. Bring stε out as stε, which lters past zR. Then use (T) to obtain x0εzR[|z−x0| ε z E].

Similarly, the formula for “closed” reduces to x0RεxE[|x−x0| ε x0 E], which is perhaps more readable if we push xE inside the parentheses as xE. For “bounded”, use the ltering form of (I) and (T) to obtain the usual formulation rxE[|x| r]. 5. Let hX,di be a standard metric space. To avoid confusion, let us temporarily call it nice in case for all x, if for all standard ε > 0 there is a standard y with d(x,y) ε, then there is a standard x0 with x ' x0. Suppose that X is incomplete. By (T), there is a standard Cauchy sequence xn with no limit. Let ν ' and let ε > 0 be standard. Consider the set S of all n such that d(xn,xν) ε. This set contains all unlimited n, so by overspill it contains some limited n, for which xn is standard. But there is no standard x0 with xν ' x0, for then it would be the limit of the xn. Thus an incomplete standard metric space is not nice. Conversely, let X be complete and let x be a point in X such that for all standard ε > 0 there is a standard y with d(x,y) ε. Then for all standard n there is a standard y with d(x,y) 1/n, so by (eS) there is a standard sequence yn such that d(x,yn) 1/n for all standard n. By the triangle inequality and (T), yn is a Cauchy sequence and so has a limit x0, which is standard by (T), and x ' x0. Thus a complete

26 CHAPTER 1. INTERNAL SET THEORY

standard metric space is nice, and our denition by (S) of a metric space being complete is equivalent to the usual one. It is also interesting to approach this problem via the reduction algorithm. We have x[stεsty[d(x,y) ε]stx0stδ[d(x,x0) δ]]. Use (eS) before pulling anything out, to avoid spurious arguments of the functions, and then pull out the resulting functions. We obtain st˜ δst˜ yxstx0stε[d(x,˜ y(ε)) ε d(x,x0) ˜ δ(x0)],

which by (I) and (T) is equivalent to ˜ δ˜ ynε0nx0 0xx0x0 0[ε∈ε0(d(x,˜ y(ε)) ε) d(x,x0) ˜ δ(x0)], where ε∈ε0 was pushed back inside the implication. Now we have the internal problem of seeing that this is equivalent to completeness of the metric space. Only the Cauchy ˜ y are relevant (to obtain a more customary notation, we could let yn = ˜ y(1/n)), for otherwise we can nd a two-point set ε0 that violates the hypothesis of the implication, by the triangle inequality. If the space X is complete, just let x0 0 be the singleton consisting of the limit as ε 0 of ˜ y(ε). To construct a counterexample when X is not complete, let ˜ y be Cauchy without a limit, and let ˜ δ(x0) be the distance from x0 to the limit (in the completion) of ˜ y(ε). 6. The S-Cauchy condition is nm[str[n r & m r] stε[|an −am| ε]].

The r lters out to give the usual denition of a Cauchy sequence. The limited uctuation condition is stεk[A(k,ε,a) str[k r]],

where A(k,ε,a) is an abbreviation for the assertion that the sequence a contains k ε-uctuations. Again the r lters out, and a standard sequence is of limited uctuation if and only if for all ε > 0 there is a bound r on the number of ε-uctuations, which is the same as being Cauchy. Now let a be an S-Cauchy sequence, not necessarily standard, and let ε > 0 be standard. Consider the set of all n such that for all m > n we have |an −am| ε; this set contains all unlimited n, so by overspill it contains some limited n. Consequently, an S-Cauchy sequence is of limited uctuation. But let ν ' and let an = 0 for n < ν and an = 1 for n ν. This sequence is of limited uctuation but is not S-Cauchy. Thus we have two distinct external concepts that agree on standard objects. 7378.

 

Nelson E., “Internal set theory. A new approach to nonstandard analysis,” Bull. Amer. Math. Soc., 83, No. 6, 1165–1198 (1977).

 



 

回复(0)

共 786 条12345››... 40
9天前 北大袁萌无穷分析的珍贵文献(542篇)

无穷分析的珍贵文献(542篇)

  上世纪下半叶,无穷小分析(非标准分析)得以快速发展。

  在这一期间,在国际一流学术期刊上,相关研究论文出现“井喷”。

  实际情况是,有数百家大学及其学者参与其中。请见本文附件。

  反观我们国内,相关研究几乎完全是空白,… …其余的话就不用多说了。

袁萌 陈启清  118

附件:

References

1. Akilov G. P. and Kutateladze S. S., Ordered Vector Spaces [in Russian], Nauka, Novosibirsk (1978).

2. AksoyA.G.andKhamsi M.A., NonstandardMethodsinFixedPointTheory, Springer-Verlag, Berlin etc. (1990). 3. Albeverio S., Fenstad J. E., et al., Nonstandard Methods in Stochastic Analysis and Mathematical Physics, Academic Press, Orlando etc. (1990).

4. Albeverio S., Luxemburg W. A. J., and Wol M. P. H. (eds.), Advances in Analysis, Probability and Mathematical Physics: Contributions of Nonstandard Analysis, Kluwer Academic Publishers, Dordrecht (1995).

5. Albeverio S., Gordon E. I., and Khrennikov A. Yu., “Finite dimensional approximations of operators in the Hilbert spaces of functions on locally compact abelian groups,” Acta Appl. Math., 64, No. 1, 33–73 (2000).

6. Alekseev M. A., Glebski L. Yu., and Gordon E. I., On Approximations of Groups, Group Actions, and Hopf Algebras [Preprint, No. 491], Inst. Applied Fiz. Ros. Akad. Nauk, Nizhni Novgorod (1999).

7. Alexandrov A. D., Problems of Science and the Researcher’s Standpoint [in Russian], Nauka (Leningrad Branch), Leningrad (1988).

8. Alexandrov A. D., “A general view of mathematics,” in: Mathematics: Its Content, Methods and Meaning. Ed. by A. D. Alexandrov, A. N. Kolmogorov, and M. A. Lavrentev. Dover Publications, Mineola and New York (1999). (Reprint of the 2nd 1969 ed.)

9. Aliprantis C. D. and Burkinshaw O., Locally Solid Riesz Spaces, Academic Press, New York etc. (1978).

10. Aliprantis C. D. and Burkinshaw O., Positive Operators, Academic Press, New York (1985). 11. Anderson R. M., “A nonstandard representation of Brownian motion and Itˆ o integration,” Israel J. Math. Soc., 25, 15–46 (1976).

12. AndersonR.M., “Star-niterepresentationsofmeasurespaces,” Trans.Amer. Math. Soc., 271, 667–687 (1982).

386 References

13. Andreev P. V., “On the standardization principle in the theory of bounded sets,” Vestnik Moskov. Univ. Ser. I Mat. Mekh., No. 1, 68–70 (1997).

14. Andreev P. V. and Gordon E. I., “The nonstandard theory of classes,” Vladikavkaz. Mat. Zh., 1, No. 4, 2–16 (1999). (http://alanianet.ru/omj/journal.htm) 15. Anselone P. M., Collectively Compact Operator Approximation. Theory and Applications to Integral Equations, Englewood Clis, Prentice Hall (1971).

16. Archimedes, Opera Omnia, Teubner, Stuttgart (1972).

17. Arens R. F. and Kaplansky I., “Topological representation of algebras,” Trans. Amer. Math. Soc., 63, No. 3, 457–481 (1948).

18. Arkeryd L. and Bergh J., “Some properties of Loeb–Sobolev spaces,” J. London Math. Soc., 34, No. 2, 317–334 (1986). 19. Arkeryd L. O., Cutland N. J., and Henson W. (eds.), Nonstandard Analysis. Theory and Applications (Proc. NATO Advanced Study Institute on Nonstandard Anal. and Its Appl., International Centre for Mathematical Studies, Edinburgh, Scotland, 30 June–13 July), Kluwer Academic Publishers, Dordrecht etc. (1997). 20. Arveson W., “Operator algebras and invariant subspaces,” Ann. of Math., 100, No. 2, 433–532 (1974). 21. Arveson W., An Invitation to C-Algebras, Springer-Verlag, Berlin etc. (1976). 22. Attouch H., Variational Convergence for Functions and Operators, Pitman, Boston etc. (1984). 23. Aubin J.-P. and Ekeland I., Applied Nonlinear Analysis, Wiley-Interscience, New York (1979). 24. AubinJ.-P.andFrankowskaH., Set-ValuedAnalysis, Birkh¨auser-Verlag, Boston (1990). 25. Auslander L. and Tolimieri R., “Is computing with nite Fourier transform pure or applied mathematics?” Bull. Amer. Math. Soc., 1, No. 6, 847–897 (1979). 26. Bagarello F., “Nonstandard variational calculus with applications to classical mechanics. I: An existence criterion,” Internat. J. Theoret. Phys., 38, No. 5, 1569–1592 (1999).

27. Bagarello F., “Nonstandard variational calculus with applications to classical mechanics. II: The inverse problem and more,” Internat. J. Theoret. Phys., 38, No. 5, 1593–1615 (1999). 28. Ballard D., Foundational Aspects of “Non”-Standard Mathematics, Amer. Math. Soc., Providence, RI (1994). 29. Bell J. L., Boolean-Valued Models and Independence Proofs in Set Theory, Clarendon Press, New York etc. (1985).

References 387

30. Bell J. L., A Primer of Innitesimal Analysis, Cambridge University Press, Cambridge (1998). 31. Bell J. L. and Slomson A. B., Models and Ultraproducts: an Introduction, North-Holland, Amsterdam etc. (1969). 32. Berberian S. K., Baer -Rings, Springer-Verlag, Berlin (1972). 33. BerezinF.A.andShubin M.A., TheSchr¨odingerEquation,KluwerAcademic Publishers, Dordrecht (1991). 34. Berkeley G., The Works. Vol. 1–4, Thoemmes Press, Bristol (1994). 35. Bigard A., Keimel K., and Wolfenstein S., Groupes et Anneaux R´eticul´es, Springer-Verlag, Berlin etc. (1977). (Lecture Notes in Math., 608.) 36. Birkho G., Lattice Theory, Amer. Math. Soc., Providence (1967). 37. Bishop E. and Bridges D., Constructive Analysis, Springer-Verlag, Berlin etc. (1985). 38. Blekhman I. I., Myshkis A. D., and Panovko A. G., Mechanics and Applied Mathematics. Logics and Peculiarities of Mathematical Applications [in Russian], Nauka, Moscow (1983). 39. Blumenthal L.M., Theory andApplicationsofDistanceGeometry, Clarendon Press, Oxford (1953). 40. Bogolyubov A. N., “Read on Euler: he is a teacher for all of us,” Nauka v SSSR, No. 6, 98–104 (1984). 41. Boole G., An Investigation of the Laws of Thought on Which Are Founded the Mathematical Theories of Logic and Probabilities, Dover Publications, New York (1957). 42. Boole G., Selected Manuscripts on Logic and Its Philosophy, Birkh¨auserVerlag, Basel (1997). (Science Networks. Historical Studies, 20.) 43. Borel E., Probability et Certitude, Presses Univ. de France, Paris (1956). 44. Bourbaki N., Set Theory [in French], Hermann, Paris (1958). 45. Boyer C. B., A History of Mathematics, John Wiley & Sons Inc., New York etc. (1968). 46. Bratteli O. and Robinson D., Operator Algebras and Quantum Statistical Mechanics, Springer-Verlag, New York etc. (1982). 47. Bukhvalov A. V., “Order bounded operators in vector lattices and in spaces of measurable functions,” J. Soviet Math., 54, No. 5, 1131–1176 (1991). 48. Bukhvalov A. V., Veksler A. I., and Geler V. A., “Normed lattices,” J. Soviet Math., 18, 516–551 (1982). 49. Bukhvalov A. V., Veksler A. I., and Lozanovski G. Ya., “Banach lattices: some Banach aspects of their theory,” Russian Math. Surveys, 34, No.2, 159–212 (1979). 50. Burden C. W. and Mulvey C. J., “Banach spaces in categories of sheaves,” in: Applications of Sheaves (Proc. Res. Sympos. Appl. Sheaf Theory to

388 References

Logic, Algebra and Anal., Durham, 1977), Springer-Verlag, Berlin etc., 1979, pp. 169–196. 51. Canjar R. M., “Complete Boolean ultraproducts,” J. Symbolic Logic, 52, No. 2, 530–542 (1987). 52. Cantor G., Works on Set Theory [in Russian], Nauka, Moscow (1985). 53. Capinski M. and Cutland N. J., Nonstandard Methods for Stochastic Fluid Mechanics, World Scientic Publishers, Singapore etc. (1995). (Series on Advances in Mathematics for Applied Sciences, Vol. 27.) 54. Carnot L., Reections on Metaphysics of Innitesimal Calculus [Russian translation], ONTI, Moscow (1933). 55. Castaing C. and Valadier M., Convex Analysis and Measurable Multifunctions, Springer-Verlag, Berlin etc. (1977). (Lecture Notes in Math., 580.) 56. Chang C. C. and Keisler H. J., Model Theory, North-Holland, Amsterdam (1990). 57. Chilin V. I., “Partially ordered involutive Baer algebras,” in: Contemporary Problems of Mathematics. Newest Advances [in Russian], VINITI, Moscow, 27, 1985, pp. 99–128. 58. Church A., Introduction to Mathematical Logic, Princeton University Press, Princeton (1956). 59. Ciesielski K., Set Theory for the Working Mathematician, Cambridge University Press, Cambridge (1997). 60. Clarke F. H., “Generalized gradients and applications,” Trans. Amer. Math. Soc., 205, No. 2, 247–262 (1975). 61. ClarkeF.H.,OptimizationandNonsmoothAnalysis,NewYork,Wiley(1983). 62. Cohen P.J., SetTheory andthe Continuum Hypothesis, Benjamin, NewYork etc. (1966). 63. Cohen P. J., “On foundations of set theory,” Uspekhi Mat. Nauk, 29, No. 5, 169–176 (1974). 64. Courant R., A Course of Dierential and Integral Calculus. Vol. 1 [Russian translation], Nauka, Moscow (1967). 65. CourantR.andRobbinsH.,WhatIsMathematics? AnElementaryApproach to Ideas and Methods. Oxford University Press, Oxford etc. (1978). 66. Cozart D. and Moore L. C. Jr., “The nonstandard hull of a normed Riesz space,” Duke Math. J., 41, 263–275 (1974). 67. Cristiant C., “Der Beitrag G¨odels f¨ur die Rechfertigung der Leibnizschen Idee von der Innitesimalen,” ¨Osterreich. Akad. Wiss. Math.-Natur. Kl. Sitzungsber. II, Bd 192, No. 1–3, 25–43 (1983). 68. Curtis T., Nonstandard Methods in the Calculus of Variations, Pitman, London (1993). (Pitman Research Notes in Mathematics, 297.) 69. Cutland N. J., “Nonstandard measure theory and its applications,” Bull. London Math. Soc., 15, No. 6, 530–589 (1983).

References 389

70. Cutland N. J., “Innitesimal methods in control theory, deterministic and stochastic,” Acta Appl. Math., 5, No. 2, 105–137 (1986). 71. Cutland N. J. (ed.), Nonstandard Analysis and Its Applications, Cambridge University Press, Cambridge (1988). 72. Dacunha-Castelle D. and Krivine J.-L., “Applications des ultraproduits a l’etude des espaces et des algebres de Banach,” Studia Math., 41, 315–334 (1972). 73. Dales H. and Woodin W., An Introduction to Independence for Analysts, Cambridge University Press, Cambridge (1987). 74. Dauben J. W., Abraham Robinson. The Creation of Nonstandard Analysis, a Personal and Mathematical Odyssey, Princeton University Press, Princeton (1995). 75. Davis M., Applied Nonstandard Analysis, John Wiley & Sons, New York etc. (1977). 76. Day M., Normed Linear Spaces, Springer-Verlag, New York and Heidelberg (1973). 77. de Jonge E. and van Rooij A. C. M., Introduction to Riesz Spaces, Mathematisch Centrum, Amsterdam (1977). 78. Dellacherie C., Capacities and Stochastic Processes [in French], SpringerVerlag, Berlin etc. (1972). 79. Demyanov V. F. and Vasilev L. V., Nondierentiable Optimization [in Russian], Nauka, Moscow (1981). 80. Demyanov V. F. and Rubinov A. M., Constructive Nonsmooth Analysis, Verlag Peter Lang, Frankfurt/Main (1995). 81. Diener F. and Diener M., “Les applications de l’analyse non standard,” Recherche, 20, No. 1, 68–83 (1989). 82. Diener F. and Diener M. (eds.), Nonstandard Analysis in Practice, SpringerVerlag, Berlin etc. (1995). 83. Diestel J., Geometry of Banach Spaces: Selected Topics, Springer-Verlag, Berlin etc. (1975). 84. Diestel J. and Uhl J. J., Vector Measures, Amer. Math. Soc., Providence, RI (1977). (Math. Surveys; 15.) 85. Digernes T., Husstad E., andVaradarajanV., “FiniteapproximationsofWeyl systems,” Math. Scand., 84, 261–283 (1999). 86. Digernes T., Varadarajan V., and Varadhan S., “Finite approximations to quantum systems,” Rev. Math. Phys., 6, No. 4, 621–648 (1994). 87. Dinculeanu N., Vector Measures, VEB Deutscher Verlag der Wissenschaften, Berlin (1966). 88. Dixmier J., C-Algebras and Their Representations [in French], GauthierVillars, Paris (1964).

390 References

89. Dixmier J., C-Algebras, North-Holland, Amsterdam, New York, and Oxford (1977). 90. Dixmier J., Les Algebres d’Operateurs dans l’Espace Hilbertien (Algebres de von Neumann), Gauthier-Villars, Paris (1996). 91. Dolecki S., “A general theory of necessary optimality conditions,” J. Math. Anal. Appl., 78, No. 12, 267–308 (1980). 92. DoleckiS., “Tangencyanddierentiation: marginalfunctions,” Adv. inAppl. Math., 11, 388–411 (1990). 93. Dragalin A. G., “An explicit Boolean-valued model for nonstandard arithmetic,” Publ. Math. Debrecen, 42, No. 3–4, 369–389 (1993). 94. Dunford N. and Schwartz J. T., Linear Operators. Vol. 1: General Theory, John Wiley & Sons Inc., New York (1988). 95. Dunford N. and Schwartz J. T., Linear Operators. Vol. 2: Spectral Theory. Selfadjoint Operators in Hilbert Space, John Wiley & Sons Inc., New York (1988). 96. Dunford N. andSchwartz J. T., LinearOperators. Vol.3: Spectral Operators, John Wiley & Sons Inc., New York (1988). 97. Dunham W., Euler: The Master of Us All, The Mathematical Association of America, Washington (1999). (The Dolciani Mathematical Expositions, 22.) 98. Eda K., “A Boolean power and a direct product of abelian groups,” Tsukuba J. Math., 6, No. 2, 187–194 (1982). 99. Eda K., “On a Boolean power of a torsion free abelian group,” J. Algebra, 82, No. 1, 84–93 (1983). 100. Ekeland I. and TemamR., Convex Analysisand VariationalProblems, NorthHolland, Amsterdam (1976). 101. Eklof P., “Theory of ultraproducts for algebraists,” in: Handbook of Mathematical Logic, North-Holland, Amsterdam, 1977. 102. Ellis D., “Geometry in abstract distance spaces,” Publ. Math. Debrecen, 2, 1–25 (1951). 103. Emelyanov `E. Yu., “Invariant homomorphisms of nonstandard enlargements of Boolean algebras and vector lattices,” Siberian Math. J., 38, No. 2, 244– 252 (1997). 104. EngelerE.,MetamathematicsofElementaryMathematics[inGerman], Springer-Verlag, Berlin etc. (1983). 105. Ershov Yu. L. and Palyutin E. A., Mathematical Logic [in Russian], Nauka, Moscow (1987). 106. Esenin-Volpin A. S., “Analysis of potential implementability,” in: Logic Studies [in Russian], Izdat. Akad. Nauk SSSR, Moscow, 1959, pp. 218–262. 107. Espanol L., “Dimension of Boolean valued lattices and rings,” J. Pure Appl. Algebra, No. 42, 223–236 (1986).

References 391

108. Euclid’s “Elements.” Books 7–10 [Russian translation], Gostekhizdat, Moscow and Leningrad (1949). 109. Euler L., Introduction to Analysis of the Innite. Book I [Russian translation], ONTI, Moscow (1936); [English translation], Springer-Verlag, New York etc. (1988). 110. Euler L., Dierential Calculus [Russian translation], Gostekhizdat, Leningrad (1949). 111. Euler L., Integral Calculus. Vol. 1 [Russian translation], Gostekhizdat, Moscow (1950). 112. Euler L., Opera Omnia. Series Prima: Opera Mathematica. Vol. 1–29, Birkh¨auser-Verlag, Basel etc. 113. Euler L., Foundations of Dierential Calculus, Springer-Verlag, New York (2000). 114. Faith C., Algebra: Rings, Modules, and Categories. Vol. 1, Springer-Verlag, Berlin etc. (1981). 115. Fakhoury H., “Repr´esentations d’op´erateurs `a valeurs dans L1(X,Σ,μ),” Math. Ann., 240, No. 3, 203–212 (1979). 116. Farkas E. and Szabo M., “On the plausibility of nonstandard proofs in analysis,” Dialectica, 38, No. 4, 297–310 (1974). 117. Fattorini H. O., The Cauchy Problem, Addison-Wesley (1983). 118. Foster A. L., “Generalized ‘Boolean’ theory of universal algebras. I. Subdirect sums and normal representation theorems,” Math. Z., 58, No. 3, 306–336 (1953). 119. FosterA.L., “Generalized‘Boolean’theory ofuniversal algebras.II.Identities and subdirect sums of functionally complete algebras,” Math. Z., 59, No. 2, 191–199 (1953). 120. Fourman M. P., “The logic of toposes,” in: Handbook of Mathematical Logic, North-Holland, Amsterdam, 1977. 121. Fourman M. P. and Scott D. S., “Sheaves and logic,” in: Applications of Sheaves (Proc. Res. Sympos. Appl. Sheaf Theory to Logic, Algebra and Anal., Durham, 1977), Springer-Verlag, Berlin etc., 1979, pp. 302–401. 122. Fourman M. P., Mulvey C. J., and Scott D. S. (eds.), Applications of Sheaves (Proc. Res. Sympos. Appl. Sheaf Theory to Logic, Algebra and Anal., Durham, 1977), Springer-Verlag, Berlin etc., 1979. 123. Fraenkel A. and Bar-Hillel I., Foundations of Set Theory, North-Holland, Amsterdam (1958). 124. Fuchs L., Partially Ordered Algebraic Systems, Pergamon Press, Oxford (1963). 125. Fuller R. V., “Relations among continuous and various noncontinuous functions,” Pacic J. Math., 25, No. 3, 495–509 (1968).

392 References

126. Gandy R. O., “Limitations to mathematical knowledge,” in: Logic Colloquium-80, North-Holland, New York and London, 1982, pp. 129–146. 127. Georgescu G. and Voiculescu I., “Eastern model theory for Boolean-valued theories,” Z. Math. Logik Grundlag. Math., No. 31, 79–88 (1985). 128. GlazmanI.M.andLyubich Yu.I., Finite-DimensionalLinearAnalysis, M.I.T. Press, Cambridge (1974). 129. G¨odel K., “What is Cantor’s continuum problem?” Amer. Math. Monthly, 54, No. 9, 515–525 (1947). 130. G¨odel K., “Compatibility of the axiom of choice and the generalized continuum hypothesis with the axioms of set theory,” Uspekhi Mat. Nauk, 8, No. 1, 96–149 (1948). 131. Goldshten V. M., Kuzminov V. I., and Shvedov I. A., “The K¨unneth formula for Lp-cohomologies of warped products,” Sibirsk. Mat. Zh., 32, No. 5, 29–42 (1991). 132. Goldshten V. M., Kuzminov V. I., and Shvedov I. A., “On approximation of exact and closed dierential forms by compactly-supported forms,” Sibirsk. Mat. Zh., 33, No. 2, 49–65 (1992). 133. Goldblatt R., Topoi: Categorical Analysis of Logic, North-Holland, Amsterdam etc. (1979). 134. Goldblatt R., Lectures on the Hyperreals: An Introduction to Nonstandard Analysis, Springer-Verlag, New York etc. (1998). 135. Goodearl K. R., Von Neumann Regular Rings, Pitman, London (1979). 136. Gordon E. I., “Real numbers in Boolean-valued models of set theory and K-spaces,” Dokl. Akad. Nauk SSSR, 237, No. 4, 773–775 (1977). 137. GordonE.I., “K-spaces inBoolean-valuedmodelsofsettheory,”Dokl. Akad. Nauk SSSR, 258, No. 4, 777–780 (1981). 138. Gordon E. I., “To the theorems of identity preservation in K-spaces,” Sibirsk. Mat. Zh., 23, No. 3, 55–65 (1982). 139. Gordon E. I., RationallyCompleteSemiprime CommutativeRingsin Boolean Valued Models of Set Theory, Gorki, VINITI, No. 3286-83 Dep (1983). 140. Gordon E. I., “Nonstandard nite-dimensional analogs of operators in L2(Rn),” Sibirsk. Mat. Zh., 29, No. 2, 45–59 (1988). 141. Gordon E. I., “Relatively standard elements in E. Nelson’s internal set theory,” Sibirsk. Mat. Zh., 30, No. 1, 89–95 (1989). 142. Gordon E. I., “Hypernite approximations of locally compact Abelian groups,” Dokl. Akad. Nauk SSSR, 314, No. 5, 1044–1047 (1990). 143. Gordon E. I., Elements of Boolean Valued Analysis [in Russian], Gorki State University Press, Gorki (1991). 144. Gordon E. I., “Nonstandard analysis and compact Abelian groups,” Sibirsk. Mat. Zh., 32, No. 2, 26–40 (1991).

References 393

145. Gordon E. I., “On Loeb measures,” Izv. Vyssh. Uchebn. Zaved. Mat., No. 2, 25–33 (1991). 146. Gordon E. I., Nonstandard Methods in Commutative Harmonic Analysis, Amer. Math. Soc., Providence, RI (1997). 147. Gordon E. I. and Lyubetski V. A., “Some applications of nonstandard analysis in the theory of Boolean valued measures,” Dokl. Akad. Nauk SSSR, 256, No. 5, 1037–1041 (1981). 148. Gordon E. I. and Morozov S. F., Boolean Valued Models of Set Theory [in Russian], Gorki State University, Gorki (1982). 149. Gra¨tzer G., General Lattice Theory, Birkh¨auser-Verlag, Basel (1978). 150. Grayson R. J., “Heyting-valued models for intuitionistic set theory,” Applications of Sheaves (Proc. Res. Sympos. Appl. Sheaf Theory to Logic, Algebra and Anal., Durham, 1977), Springer-Verlag, Berlin etc., 1979, pp. 402–414. 151. Gurari V. P., Group Methods in Commutative Harmonic Analysis [in Russian], VINITI, Moscow (1988). 152. Gutman A. E., “Banach bering in lattice normed space theory,” in: Linear Operators Compatible with Order [in Russian], Sobolev Institute Press, Novosibirsk, 1995, pp. 63–211. 153. GutmanA.E., “Locallyone-dimensional K-spacesand σ-distributiveBoolean algebras,” Siberian Adv. Math., 5, No. 2, 99–121 (1995). 154. Gutman A. E., Emelyanov `E. Yu., Kusraev A. G., and Kutateladze S. S., Nonstandard Analysis and Vector Lattices, Kluwer Academic Publishers, Dordrecht (2000). 155. Hallet M., Cantorian Set Theory and Limitation of Size, Clarendon Press, Oxford (1984). 156. Halmos P. R., Lectures on Boolean Algebras, Van Nostrand, Toronto, New York, and London (1963). 157. Hanshe-Olsen H. and St¨ormer E., Jordan Operator Algebras, Pitman Publishers Inc., Boston etc. (1984). 158. Harnik V., “Innitesimals from Leibniz to Robinson time—to bring them back to school,” Math. Intelligencer, 8, No. 2, 41–47 (1986). 159. HatcherW., “Calculusisalgebra,” Amer. Math. Monthly, 89, No. 6, 362–370 (1989). 160. Heinrich S., “Ultraproducts of L1-predual spaces,” Fund. Math., 113, No. 3, 221–234 (1981). 161. Helgason S., The Radon Transform, Birkh¨auser-Verlag, Boston (1999). 162. Henle J. M. and Kleinberg E. M., Innitesimal Calculus, Alpine Press, Cambridge and London (1979). 163. Henson C. W., “On the nonstandard representation of measures,” Trans. Amer. Math. Soc., 172, No. 2, 437–446 (1972).

394 References

164. Henson C. W., “When do two Banach spaces have isometrically isomorphic nonstandard hulls?” Israel J. Math., 22, 57–67 (1975). 165. Henson C. W., “Nonstandard hulls of Banach spaces,” Israel J. Math., 25, 108–114 (1976). 166. Henson C. W., “Unbounded Loeb measures,” Proc. Amer. Math. Soc., 74, No. 1, 143–150 (1979). 167. Henson C. W., “Innitesimals in functional analysis,” in: Nonstandard Analysis and Its Applications, Cambridge University Press, Cambridge etc., 1988, pp. 140–181. 168. Henson C. W. and Keisler H. J., “On the strength of nonstandard analysis,” J. Symbolic Logic, 51, No. 2, 377–386 (1986). 169. Henson C. W. andMoore L. C.Jr. “Nonstandard hulls oftheclassical Banach spaces,” Duke Math. J., 41, No. 2, 277–284 (1974). 170. Henson C. W. and Moore L. C. Jr., “Nonstandard analysis and the theory of Banach spaces,” in: Nonstandard Analysis. Recent Developments, SpringerVerlag, Berlin etc., 1983, pp. 27–112. (Lecture Notes in Math., 983.) 171. HensonC.W., KaufmannM.,andKeislerH.J.,“Thestrengthofnonstandard methods in arithmetic,” J. Symbolic Logic, 49, No. 34, 1039–1057 (1984). 172. Hermann R., “Supernear functions,” Math. Japon., 31, No. 2, 320 (1986). 173. HernandezE.G.,“Boolean-valuedmodelsofsettheorywithautomorphisms,” Z. Math. Logik Grundlag. Math., 32, No. 2, 117–130 (1986). 174. Hewitt E. and Ross K., Abstract Harmonic Analysis. Vol. 1 and 2, Springer -Verlag, Berlin etc. (1994). 175. Hilbert D. and Bernays P., Foundations of Mathematics. Logical Calculi and the Formalization of Arithmetic [in Russian], Nauka, Moscow (1979). 176. Hilbert’s Problems [in Russian], Nauka, Moscow (1969). 177. Hiriart-UrrutyJ.-B., “Tangentcones, generalizedgradientsandmathematical programming in Banach spaces,” Math. Oper. Res., 4, No. 1, 79–97 (1979). 178. Hobbes T., Selected Works. Vol. 1 [Russian translation], Mysl, Moscow (1965). 179. Hoehle U., “Almost everywhere convergence and Boolean-valued topologies,” in: Topology, Proc. 5th Int. Meet., Lecce/Italy 1990, Suppl. Rend. Circ. Mat. Palermo, II. Ser. 29, 1992, pp. 215–227. 180. Hofmann K. H. and Keimel K., “Sheaf theoretical concepts in analysis: Bundles and sheaves of Banach spaces, Banach C(X)-modules,” in: Applications of Sheaves, Proc. Res. Sympos., Durham, 1977, Springer-Verlag, Berlin etc., 1979, pp. 415–441. 181. Hofstedter D. R., G¨odel, Escher, Bach: an Eternal Golden Braid, Vintage Books, New York (1980). 182. Hogbe-Nlend H., Theorie des Bornologie et Applications, Springer-Verlag, Berlin etc. (1971).

References 395

183. Horiguchi H., “A denition of the category of Boolean-valued models,” Comment. Math. Univ. St. Paul., 30, No. 2, 135–147 (1981). 184. Horiguchi H., “The category of Boolean-valued models and its applications,” Comment. Math. Univ. St. Paul., 34, No. 1, 71–89 (1985). 185. Hrb´ acek K., “Axiomaticfoundations fornonstandardanalysis,” Fund. Math., 98, No. 1, 1–24 (1978). 186. Hrb´ acek K., “Nonstandard set theory,” Amer. Math. Monthly, 86, No. 8, 659–677 (1979). 187. Hurd A. E. (ed.), Nonstandard Analysis. Recent Developments, SpringerVerlag, Berlin (1983). 188. HurdA.E.andLoebH.,AnIntroductiontoNonstandardAnalysis,Academic Press, Orlando etc. (1985). 189. Ilin V. A., Sadovnichi V. A., and Sendov Bl. Kh., Mathematical Analysis [in Russian], Nauka, Moscow (1979). 190. Ionescu Tulcea A. and Ionescu Tulcea C., Topics in the Theory of Lifting, Springer-Verlag, Berlin etc. (1969). 191. Ivanov V. V., “Geometric properties of monotone functions and probabilities of random uctuations,” Siberian Math. J., 37, No. 1, 102–129 (1996). 192. Ivanov V. V., “Oscillations of means in the ergodic theorem,” Dokl. Akad. Nauk, 347, No. 6, 736–738 (1996). 193. Jae A., “Ordering the universe: the role of mathematics,” SIAM Rev., 26, No. 4, 473–500 (1984). 194. Jarnik V., Bolzano and the Foundations of Mathematical Analysis, Society of Czechosl. Math. Phys., Prague (1981). 195. Jech T. J., Lectures in Set Theory with Particular Emphasis on the Method of Forcing, Springer-Verlag, Berlin (1971). 196. Jech T. J., The Axiom of Choice, North-Holland, Amsterdam etc. (1973). 197. Jech T. J., “Abstract theory of abelian operator algebras: an application of forcing,” Trans. Amer. Math. Soc., 289, No. 1, 133–162 (1985). 198. Jech T. J., “First order theory of complete Stonean algebras (Boolean-valued real and complex numbers),” Canad. Math. Bull., 30, No. 4, 385–392 (1987). 199. Jech T. J., “Boolean-linear spaces,” Adv. in Math., 81, No. 2, 117–197 (1990). 200. Jech T. J., Set Theory, Springer-Verlag, Berlin (1997). 201. Johnstone P. T., Topos Theory, Academic Press, London etc. (1977). 202. Johnstone P. T., Stone Spaces, Cambridge University Press, Cambridge and New York (1982). 203. Jordan P., von Neumann J., and Wigner E., “On an algebraic generalization of the quantum mechanic formalism,” Ann. Math., 35, 29–64 (1944). 204. Kachurovski A. G., “Boundedness of mean uctuations in the statistic ergodic theorem,” Optimization, No. 48(65), 71–77 (1990).

396 References

205. Kachurovski A. G., “The rate of convergence in ergodic theorems,” Uspekhi Mat. Nauk, 51, No. 4, 73–124 (1996). 206. Kadison R. V. and Ringrose J. R., Fundamentals of the Theory of Operator Algebras, Vol. 1 and 2, Amer. Math. Soc., Providence, RI (1997). Vol. 3 and 4, Birkh¨auser-Verlag, Boston (19911992). 207. Kalina M., On the ergodic theorem within nonstandard models, Tatra Mt. Math. Publ., 10, 8793 (1997). 208. Kalton N. J., The endomorphisms of Lp (0 p 1), Indiana Univ. Math. J., 27, No. 3, 353–381 (1978). 209. Kalton N. J., “Linear operators on Lp for 0


 

回复(0)

14天前 北大袁萌沉痛悼念吴树青老校长

沉痛悼念吴树青老校长

沉痛悼念吴树青老校长

  2020110日,北京大学原校长吴树青教授永远离开了我们。

 袁萌与吴树青老校长前后相处四十余年。吴树青老校工作认真、治学严谨、待人和善。’

  1993年,吴树青校长亲自领导袁萌带领开发团队设计制作《邓小平文选》电子版,由人民出版社出版发行,获得成功

 吴树青具有共产党人的本色!

袁萌 陈启清  112

 




 

回复(0)

14天前 北大袁萌学习模型论的妙法

学习模型论的妙法

  大家知道,模型论教课书采用了许多新的符号、新的数学公式与概念。

  大学高年级学生为开阔数学视野,学习模型论是有益的。

  学习模型论,从何入手?

  我们推荐学习模型论的一种妙法:下载模型论电子版,查看其“Index”,将按照字典排序的“知识点”,与自己的脑袋“对接”,快速查找相关页码,反复阅读思考即可。

 

  请见本文附件。  袁萌  陈启清 112

附件:

沉痛悼念吴树青老校长

  2020110日,北京大学原校长吴树青教授永远离开了我们。

  袁萌与吴树青老校长前后相处四十余年。吴树青老校工作认真、治学严谨、待人和善。’

  1993年,吴树青校长亲自领导袁萌带领开发团队设计制作《邓小平文选》电子版,由人民出版社出版发行,获得成功。

  吴树青具有共产党人的本色!

袁萌 陈启清  112

 

 

 

 

们。

 

北大原校长吴树青逝世!系著名经济学家,曾提出学术打假不能假打

2020-01-12 22:47

112日晚间,南都记者从北京大学党委宣传部获悉,著名经济学家,北京大学原校长、哲学社会科学资深教授吴树青,因病医治无效,于20201101502分在北京医院逝世,享年88岁。

公开报道显示,吴树青于1989年至1996年任北大校长,此前曾在中国人民大学求学工作37年。20093月,时任教育部社科委主任的吴树青曾就加强高校学术风气建设在媒体撰文,提出学术打假“不能‘假打’要‘真打’,决不姑息,决不手软,让造假者付出代价。”



 

回复(0)

15天前 北大袁萌符号“|=”是什么意思?

符号“|=”是什么意思?

  在模型论中,表达式“A|=s”的意思是:A是句子集合S的模型。

  那么,A是句子集合S的模型究竟是什么意思?

  了解紧致性定理必须回答这个基本问题。

 什么是句子?什么是模型?仅仅靠“拍脑袋”,“办拔头发不解决问题。”

  解决问题的办法是:把我们推荐的模型论电子版装入手机中,查看第一章(11页),读一读,想一想即可明白了。、

  注:模型;论电子版不会污染手机。

袁萌  陈启清 112



 

回复(0)

16天前 北大袁萌无穷小的逻辑相容性

无穷小的逻辑相容性

  在传统微积分教课书里面,(实)无穷小是一个导致自相矛盾的概念。

  当前,这种陈旧的观念仍然在国内普通高校课堂里面在灌输给大学生,培养大批“小糊涂”。

  但是,数理逻辑模型理论紧致性定理对此说“不”。

  请见本文附件。

  其他废话就不说了。

袁萌  陈启清  111

附件:

A third application of the compactness theorem is the construction of nonstandard models of the real numbers, that is, consistent extensions of the theory of the real numbers that contain "infinitesimal" numbers. To see this, let Σ be a first-order axiomatization of the theory of the real numbers. Consider the theory obtained by adding a new constant symbol ε to the language and adjoining to Σ the axiom ε > 0 and the axioms ε < 1/n for all positive integers n. Clearly, the standard real numbers R are a model for every finite subset of these axioms, because the real numbers satisfy everything in Σ and, by suitable choice of ε, can be made to satisfy any finite subset of the axioms about ε. By the compactness theorem, there is a model *R that satisfies Σ and also contains an infinitesimal element ε. A similar argument, adjoining axioms ω > 0, ω > 1, etc., shows that the existence of infinitely large integers cannot be ruled out by any axiomatization Σ of the reals.

 



 

回复(0)

17天前 北大袁萌模型论处于现代数学的中心位置,为什么?

模型论处于现代数学的中心位置 ,为什么?

        进入二十世纪,数学理论是不是含有内部矛盾(相容性)成为一个首要问题,数学不是文艺小说。

         问题是,一个无限;理论系统的无矛盾性是很难判定的。

         哥德尔紧致性定理解决了这个问题。

         哥德尔的核心思想是把无限转化为有限来解决问题。这就是紧致性定理的中心意思。

         模型论处于现代数学的中心位置 ,为什么?因为模型论就是围绕紧致性定理展开的。

         模型论装入手机,现代数学就在你的手中!

         请见本文附件。

        袁萌   陈启清   110

        附件:

        模型论第一定理原文

        Theorem 1. The Compactness Theorem (Malcev) A set of sentences is satisable i every nite subset is satisable.

        Proof. There are several proofs. We only point out here that it is an easy consequence of the following theorem which appears in all elementary logic texts:

        Proposition. The Completeness Theorem (G¨odel, Malcev) A set of sentences is consistent if and only if it is satisable.

        Although we do not here formally dene “consistent”, it does mean what you think it does. In particular, a set of sentences is consistent if and only if each nite subset is consistent.

       

        Remark. The Compactness Theorem is the only one for which we do not give a complete proof. For the reader who has not previously seen the Completeness Theorem, there are other proofs of the Compactness Theorem which may be more easily absorbed: set theoretic (using ultraproducts), topological (using compact spaces, hence the name) or Boolean algebraic. However these topics are too far aeld to enter into the proofs here. We will use the Compactness Theorem as a starting point — in fact, all that follows can be seen as its corollaries. Exercise 6. Suppose T is a theory for the language L and σ is a sentence of L such that T |= σ. Prove that there is some nite T0 T such that T0 |= σ. Recall that T |= σ i T {¬σ} is not satisable. Definition 15. If L, and L0 are two languages such that LL0 we say that L0 is an expansion of L and L is a reduction of L0. Of course when we say that LL0 we also mean that the constant, function and relation symbols of L remain (respectively) constant, function and relation symbols of the same type in L0. Definition 16. Given a model A for the language L, we can expand it to amodel A0 ofL0, whereL0 is an expansion ofL, by giving appropriate interpretations to the symbols in L0\L. We say that A0 is an expansion of A to L0 and that A is a reduct of A0 to L. We also use the notation A0|L for the reduct of A0 to L. Theorem 2. If a theory T has arbitrarily large nite models, then it has an innite model. Proof. Consider new constant symbols ci for i N, the usual natural numbers, and ex



 

回复(0)

18天前 北大袁萌模型论是个宝,学习数学少不了

模型论是个宝,学习数学少不了

  当今,不会玩手机的大学生与傻呆呆差不多。

  模型论装入手机就是一个宝贝。

  我们推荐的模型论电子版第5页定义6(模型是什么),第十四页定理1(紧致性定理)与第二十七页定理10(鲁宾逊无穷小微积分定理)。

  阅读这30A4纸,现代数学真知入大脑。

  因此,模型论是个宝,学习数学少不了。

  注:进入“无穷小微积分”网站,下载模型论,装入手机即可。

袁萌  陈启清 19

 



 

回复(0)

19天前 北大袁萌型論電子版是是大學本科數學課程嗎?

型論電子版是是大學本科數學課程嗎?
去年1030日,國家教育部發文教育部关于一流本科课程建设的实施意见。
近日,我們推薦的模型論電子版是大學本科數學課程嗎?就成為一個定性問題。
根據模型論電子版作者本人的意見,答案是完全肯定的,而且遵守知識共享版權。
請見本文附件。
袁萌 陳啟清 18
附件:模型論電子版作者
William Weiss, based upon suggestions from several graduate students. The electronic version of this book may be downloaded and further modied by anyone for the purpose of learning, provided this paragraph is included in its entirety and so long as no part of this book is sold for prot.



 

回复(0)

20天前 北大袁萌模型论电子版,深入学习用手机

模型论电子版,深入学习用手机


  昨天,“模型论电子版,何处寻?”发表之后,模型论电子版,深入学习用手机

的问题就出来了。

  坦率地说,在世界上,提出“学模型,用手机”,我国是第一次。

  当前,下载世界一流水平模型论电子版已经不是难事。
 
科普模型论,比如学习第0章第6个定义,读懂了就会透彻理解实数是什么,不做糊涂人。

请见本文附件。

袁萌  陈启清  17

附件:

模型论A.B.C

CHAPTER 0

Models, Truth and Satisfaction

We will use the following symbols:

• logical symbols:

– the connectives , , ¬ , , ↔ called “and”, “or”, “not”, “implies” and “i” respectively – the quantiers , called “for all” and “there exists” – an innite collection of variables indexed by the natural numbers N v0 ,v1 , v2 , ...

– the two parentheses ), (

– the symbol = which is the usual “equal sign”

• constant symbols : often denoted by the letter c with subscripts

• function symbols : often denoted by the letter F with subscripts; each function symbol is an m-placed function symbol for some natural number m 1

• relation symbols : often denoted by the letter R with subscripts; each relational symbol is an n-placed relation symbol for some natural number n 1.

We now dene terms and formulas. Definition 1. A term is dened as follows:

(1) a variable is a term

(2) a constant symbol is a term

(3) if F is an m-placed function symbol and t1,...,tm are terms, then F(t1 ...tm) is a term.

(4) a string of symbols is a term if and only if it can be shown to be a term by a nite number of applications of (1), (2) and (3). Remark. This is a recursive denition. Definition 2. A formula is dened as follows :

(1) if t1 and t2 are terms, then (t1 = t2) is a formula. (2) if R is an n-placed relation symbol and t1,...,tn are terms, then (R(t1 ...tn)) is a formula. (3) if is a formula, then (¬) is a formula

(4) if and ψ are formulas then so are (∧ψ), (∨ψ), ( ψ) and ( ↔ ψ)

(5) if vi is a variable and is a formula, then (vi) and (vi) are formulas (6) a string of symbols is a formula if and only if it can be shown to be a formula by a nite number of applications of (1), (2), (3), (4) and (5).

Remark. This is another recursive denition. ¬ is called the negation of ; ∧ψ is called the conjunction of and ψ; and ∨ψ is called the disjunction of and ψ.

4

0. MODELS, TRUTH AND SATISFACTION  5

Definition 3. A subformula of a formula is dened as follows: (1) is a subformula of

(2) if (¬ψ) is a subformula of then so is ψ

(3) if any one of (θ∧ψ), (θ∨ψ), (θ ψ) or (θ ↔ ψ) is a subformula of , then so are both θ and ψ

(4) if either (vi)ψ or (vi)ψ is a subformula of for some natural number i, then ψ is also a subformula of

(5) A string of symbols is a subformula of , if and only if it can be shown to be such by a nite number of applications of (1), (2), (3) and (4).

Definition 4. A variable vi is said to occur bound in a formula i for some subformula ψ of either (vi)ψ or (vi)ψ is a subformula of . In this case each occurrence of vi in (vi)ψ or (vi)ψ is said to be a bound occurrence of vi. Other occurrences of vi which do not occur bound in are said to be free.

Example 1.

F(v3) is a term, where F is a unary function symbol. ((v3)(v0 = v3)(v0)(v0 = v0)) is a formula. In this formula the variable v3 only occurs bound but the variable v0 occurs both bound and free.

Exercise 1. Using the previous denitions as a guide, dene the substitution of a term t for a variable vi in a formula . In particular, demonstrate how to substitute the term for the variable v0 in the formula of the example above. Definition 5. A language L is a set consisting of all the logical symbols with perhaps some constant, function and/or relational symbols included. It is understood that the formulas of L are made up from this set in the manner prescribed above. Note that all the formulas of L are uniquely described by listing only the constant, function and relation symbols of L. We use t(v0,...,vk) to denote a term t all of whose variables occur among v0,...,vk. We use (v0,...,vk) to denote a formula all of whose free variables occur among v0,...,vk.

Example 2. These would be formulas of any language :

• For any variable vi: (vi = vi)

• for any term t(v0,...,vk) and other terms t1 and t2: ((t1 = t2) (t(v0,...,vi−1,t1,vi+1,...,vk) = t(v0,...,vi−1,t2,vi+1,...,vk)))

• for any formula (v0,...,vk) and terms t1 and t2: ((t1 = t2) ((v0,...,vi−1,t1,vi+1,...,vk) ↔ (v0,...,vi−1,t2,vi+1,...,vk))) Note the simple way we denote the substitution of t1 for vi. Definition 6. A model (or structure) A for a language L is an ordered pair hA,Ii where A is a nonempty set and I is an interpretation function with domain the set of all constant, function and relation symbols of L such that:

(1) if c is a constant symbol, then I(c) A; I(c) is called a constant

0. MODELS, TRUTH AND SATISFACTION  6

(2) if F is an m-placed function symbol, then I(F) is an m-placed function on A

(3) if R is an n-placed relation symbol, then I(R) is an n-placed relation on A. A is called the universe of the model A. We generally denote models with Gothic letters and their universes with the corresponding Latin letters in boldface. One set may be involved as a universe with many dierent interpretation functions of the language L. The model is both the universe and the interpretation function. Remark. The importance of Model Theory lies in the observation that mathematical objects can be cast as models for a language. For instance, the real numbers with the usual ordering < < < and the usual arithmetic operations, addition + + + and multiplication · · · along with the special numbers 0 and 1 can be described as a model.

Let L contain one two-placed (i.e. binary) relation symbol R0, two two-placed function symbols F1 and F2 and two constant symbols c0 and c1. We build a model by letting the universe A be the set of real numbers. The interpretation function I will map R0 to < < <, i.e. R0 will be interpreted as < < <. Similarly, I(F1) will be + + +, I(F2) will be · · ·, I(c0) will be 0 and I(c1) will be 1. So hA,Ii is an example of a model for the language described by {R0,F1,F2,c0,c1}. We now wish to show how to use formulas to express mathematical statements about elements of a model. We rst need to see how to interpret a term in a model.

Definition 7. The value t[x0,...,xq] of a term t(v0,...,vq) at x0,...,xq in the universe A of the model A is dened as follows: (1) if t is vi then t[x0,··· ,xq] is xi, (2) if t is the constant symbol c, then t[x0,...,xq] is I(c), the interpretation of c in A, (3) if t is F(t1 ...tm) where F is an m-placed function symbol and t1,...,tm are terms, then t[x0,...,xq] is G(t1[x0,...,xq],...,tm[x0,...,xq]) where G is the m-placed function I(F), the interpretation of F in A. Definition 8. Suppose A is a model for a language L. The sequencex 0,...,xq of elements of A satises the formula (v0,...,vq) all of whose free and bound variables are among v0,...,vq, in the model A, written A |= [x0,...,xq] provided we have: (1) if (v0,...,vq) is the formula (t1 = t2), then A |= (t1 = t2)[x0,...,xq] means that t1[x0,...,xq] equals t2[x0,...,xq], (2) if (v0,...,vq) is the formula (R(t1 ...tn)) where R is an n-placed relation symbol, then A |= (R(t1 ...tn))[x0,...,xq] means S(t1[x0,...,xq],...,tn[x0,...,xq]) where S is the n-placed relation I(R), the interpretation of R in A,(3) if is (¬θ), then A |= [x0,...,xq] means not A |= θ[x0,...,xq], (4) if is (θ∧ψ), then A |= [x0,...,xq] means both A |= θ[x0,...,xq] and A |= ψ[x0,...xq],

0. MODELS, TRUTH AND SATISFACTION 7

(5) if is (θ∨ψ) then A |= [x0,...,xq] means either A |= θ[x0,...,xq] or A |= ψ[x0,...,xq], (6) if is (θ ψ) then A |= [x0,...,xq] means that A |= θ[x0,...,xq] implies A |= ψ[x0,...,xq], (7) if is (θ ↔ ψ) then A |= [x0,...,xq] means that A |= θ[x0,...,xq] i A |= ψ[x0,...,xq], (8) if is viθ, then A |= [x0,...,xq] means for every x A,A |= θ[x0,...,xi−1,x,xi+1,...,xq], (9) if is viθ, then A |= [x0,...,xq] means for some x A,A |= θ[x0,...,xi−1,x,xi+1,...,xq]. Exercise 2. Each of the formulas of Example 2 is satised in any model A for any language L by any (long enough) sequence x0,x1,...,xq of A. This is where you test your solution to Exercise 1, especially with respect to the term and formula from Example 1.

We now prove two lemmas which show that the preceding concepts are welldened. In the rst one, we see that the value of a term only depends upon the values of the variables which actually occur in the term. In this lemma the equal sign = is used, not as a logical symbol in the formal sense, but in its usual sense to denote equality of mathematical objects — in this case, the values of terms, which are elements of the universe of a model. Lemma 1. Let A be a model for L and let t(v0,...,vp) be a term of L. Letx 0,...,xq and y0,...,yr be sequences from A such that p q and p r, and letx i = yi whenever vi actually occurs in t(v0,...,vp). Then t[x0,...,xq] = t[y0,...,yr] .

Proof. We use induction on the complexity of the term t. (1) If t is vi then xi = yi and so we have t[x0,...,xq] = xi = yi = t[y0,...,yr] since p q and p r. (2) If t is the constant symbol c, then t[x0,...,xq] = I(c) = t[y0,...,yr] where I(c) is the interpretation of c in A.(3) If t is F(t1 ...tm) where F is an m-placed function symbol, t1,...,tm are terms and I(F) = G, then t[x0,...,xq] = G(t1[x0,...,xq],...,tm[x0,...,xq]) and t[y0,...,yr] = G(t1[y0,...,yr],...,tm[y0,...,yr]). By the induction hypothesis we have that ti[x0,...,xq] = ti[y0,...,yr] for 1 i m since t1,...,tm have all their variables among {v0,...,vp}. So we have t[x0,...,xq] = t[y0,...,yr].


0. MODELS, TRUTH AND SATISFACTION 8

In the next lemma the equal sign = is used in both senses — as a formal logical symbol in the formal language L and also to denote the usual equality of mathematical objects. This is common practice where the context allows the reader to distinguish the two usages of the same symbol. The lemma conrms that satisfaction of a formula depends only upon the values of its free variables. Lemma 2. Let A be a model for L and a formula of L, all of whose free and bound variables occur among v0,...,vp. Let x0,...,xq and y0,...,yr (q,r p) be two sequences such that xi and yi are equal for all i such that vi occurs free in . Then A |= [x0,...,xq] i A |= [y0,...,yr] Proof. Let A and L be as above. We prove the lemma by induction on the complexity of . (1) If (v0,...,vp) is the formula (t1 = t2), then we use Lemma 1 to get: A |= (t1 = t2)[x0,...,xq] i t1[x0,...,xq] = t2[x0,...,xq] i t1[y0,...,yr] = t2[y0,...,yr] i A |= (t1 = t2)[y0,...,yr]. (2) If (v0,...,vp) is the formula (R(t1 ...tn)) where R is an n-placed relation symbol with interpretation S, then again by Lemma 1, we get: A |= (R(t1 ...tn))[x0,...,xq] i S(t1[x0,...,xq],...,tn[x0,...,xq]) i S(t1[y0,...,yr],...,tn[y0,...,yr]) i A |= R(t1 ...tn)[y0,...,yr]. (3) If is (¬θ), the inductive hypothesis gives that the lemma is true for θ. So, A |= [x0,...,xq] i not A |= θ[x0,...,xq] i not A |= θ[y0,...,yr] i A |= [y0,...,yr]. (4) If is (θ∧ψ), then using the inductive hypothesis on θ and ψ we get A |= [x0,...,xq] i both A |= θ[x0,...,xq] and A |= ψ[x0,...xq] i both A |= θ[y0,...,yr] and A |= ψ[y0,...yr] i A |= [y0,...,yr]. (5) If is (θ∨ψ) then A |= [x0,...,xq] i either A |= θ[x0,...,xq] or A |= ψ[x0,...,xq] i either A |= θ[y0,...,yr] or A |= ψ[y0,...,yr] i A |= [y0,...,yr]. (6) If is (θ ψ) then A |= [x0,...,xq] i A |= θ[x0,...,xq] implies A |= ψ[x0,...,xq] i A |= θ[y0,...,yr] implies A |= ψ[y0,...,yr] i A |= [y0,...,yr].

0. MODELS, TRUTH AND SATISFACTION 9

(7) If is (θ ↔ ψ) then A |= [x0,...,xq] i we have A |= θ[x0,...,xq] i A |= ψ[x0,...,xq] i we have A |= θ[y0,...,yr] i A |= ψ[y0,...,yr] i A |= [y0,...,yr]. (8) If is (vi)θ, then A |= [x0,...,xq] i for every z A,A |= θ[x0,...,xi−1,z,xi+1,...,xq] i for every z A,A |= θ[y0,...,yi−1,z,yi+1,...,yr] i A |= [y0,...,yr]. The inductive hypothesis uses the sequences x0,...,xi−1,z,xi+1,...,xq and y0,...,yi−1,z,yi+1,...,yr with the formula θ. (9) If is (vi)θ, then A |= [x0,...,xq] i for some z A,A |= θ[x0,...,xi−1,z,xi+1,...,xq] i for some z A,A |= θ[y0,...,yi−1,z,yi+1,...,yr] i A |= [y0,...,yr]. The inductive hypothesis uses the sequences x0,...,xi−1,z,xi+1,...,xq and y0,...,yi−1,z,yi+1,...,yr with the formula θ.


 Definition 9. A sentence is a formula with no free variables. If is a sentence, we can write A |= without any mention of a sequence fromA since by the previous lemma, it doesn’t matter which sequence from A we use. In this case we say: • A satises • or A is a model of • or holds in A • or is true in A If is a sentence of L, we write |= to mean that A |= for every model Afor L. Intuitively then, |= means that is true under any relevant interpretation (model forL). Alternatively, no relevant example (model forL) is a counterexample to — so is true. Lemma 3. Let (v0,...,vq) be a formula of the language L. There is anotherformula 0(v0,...,vq) of L such that (1) 0 has exactly the same free and bound occurrences of variables as . (2) 0 can possibly contain ¬, and but no other connective or quantier. (3) |= (v0)...(vq)( ↔ 0) Exercise 3. Prove the above lemma by induction on the complexity of . As a reward, note that this lemma can be used to shorten future proofs by induction on complexity of formulas.

Definition 10. A formula is said to be in prenex normal form whenever (1) there are no quantiers occurring in , or (2) is (vi)ψ where ψ is in prenex normal form and vi does not occur bound in ψ, or

0. MODELS, TRUTH AND SATISFACTION 10

(3) is (vi)ψ where ψ is in prenex normal form and vi does not occur bound in ψ.

Remark. If is in prenex normal form, then no variable occurring in occurs both free and bound and no bound variable occurring in is bound by more than one quantier. In the written order, all of the quantiers precede all of the connectives. Lemma 4. Let (v0,...,vp) be any formula of a language L. There is a formula of L which has the following properties: (1) is in prenex normal form (2) and have the same free occurrences of variables, and (3) |= (v0)...(vp)() Exercise 4. Prove this lemma by induction on the complexity of .

There is a notion of rank on prenex formulas — the number of alternations of quantiers. The usual formulas of elementary mathematics have prenex rank 0, i.e. no alternations of quantiers. For example: (x)(y)(2xy x2 + y2). However, the −δ denition of a limit of a function has prenex rank 2 and is much more dicult for students to comprehend at rst sight: ()(δ)(x)((0 < 0 < |x−a| < δ) |F(x)−L| < ). A formula of prenex rank 4 would make any mathematician look twice.

CHAPTER 1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

CHAPTER 0

Models, Truth and Satisfaction

We will use the following symbols: • logical symbols: – the connectives , , ¬ , , ↔ called “and”, “or”, “not”, “implies” and “i” respectively – the quantiers , called “for all” and “there exists” – an innite collection of variables indexed by the natural numbers N v0 ,v1 , v2 , ... – the two parentheses ), ( – the symbol = which is the usual “equal sign” • constant symbols : often denoted by the letter c with subscripts • function symbols : often denoted by the letter F with subscripts; each function symbol is an m-placed function symbol for some natural number m 1 • relation symbols : often denoted by the letter R with subscripts; each relational symbol is an n-placed relation symbol for some natural number n 1. We now dene terms and formulas. Definition 1. A term is dened as follows: (1) a variable is a term (2) a constant symbol is a term (3) if F is an m-placed function symbol and t1,...,tm are terms, then F(t1 ...tm) is a term. (4) a string of symbols is a term if and only if it can be shown to be a term by a nite number of applications of (1), (2) and (3). Remark. This is a recursive denition. Definition 2. A formula is dened as follows : (1) if t1 and t2 are terms, then (t1 = t2) is a formula. (2) if R is an n-placed relation symbol and t1,...,tn are terms, then (R(t1 ...tn)) is a formula. (3) if is a formula, then (¬) is a formula (4) if and ψ are formulas then so are (∧ψ), (∨ψ), ( ψ) and ( ↔ ψ) (5) if vi is a variable and is a formula, then (vi) and (vi) are formulas (6) a string of symbols is a formula if and only if it can be shown to be a formula by a nite number of applications of (1), (2), (3), (4) and (5). Remark. This is another recursive denition. ¬ is called the negation of ; ∧ψ is called the conjunction of and ψ; and ∨ψ is called the disjunction of and ψ.

4

0. MODELS, TRUTH AND SATISFACTION 5

Definition 3. A subformula of a formula is dened as follows: (1) is a subformula of (2) if (¬ψ) is a subformula of then so is ψ (3) if any one of (θ∧ψ), (θ∨ψ), (θ ψ) or (θ ↔ ψ) is a subformula of , then so are both θ and ψ (4) if either (vi)ψ or (vi)ψ is a subformula of for some natural number i, then ψ is also a subformula of (5) A string of symbols is a subformula of , if and only if it can be shown to be such by a nite number of applications of (1), (2), (3) and (4).

Definition 4. A variable vi is said to occur bound in a formula i for some subformula ψ of either (vi)ψ or (vi)ψ is a subformula of . In this case each occurrence of vi in (vi)ψ or (vi)ψ is said to be a bound occurrence of vi. Other occurrences of vi which do not occur bound in are said to be free.

Example 1.

F(v3) is a term, where F is a unary function symbol. ((v3)(v0 = v3)(v0)(v0 = v0)) is a formula. In this formula the variable v3 only occurs bound but the variable v0 occurs both bound and free.

Exercise 1. Using the previous denitions as a guide, dene the substitution of a term t for a variable vi in a formula . In particular, demonstrate how to substitute the term for the variable v0 in the formula of the example above. Definition 5. A language L is a set consisting of all the logical symbols with perhaps some constant, function and/or relational symbols included. It is understood that the formulas of L are made up from this set in the manner prescribed above. Note that all the formulas of L are uniquely described by listing only the constant, function and relation symbols of L. We use t(v0,...,vk) to denote a term t all of whose variables occur among v0,...,vk. We use (v0,...,vk) to denote a formula all of whose free variables occur among v0,...,vk.

Example 2. These would be formulas of any language : • For any variable vi: (vi = vi) • for any term t(v0,...,vk) and other terms t1 and t2: ((t1 = t2) (t(v0,...,vi−1,t1,vi+1,...,vk) = t(v0,...,vi−1,t2,vi+1,...,vk))) • for any formula (v0,...,vk) and terms t1 and t2: ((t1 = t2) ((v0,...,vi−1,t1,vi+1,...,vk) ↔ (v0,...,vi−1,t2,vi+1,...,vk))) Note the simple way we denote the substitution of t1 for vi. Definition 6. A model (or structure) A for a language L is an ordered pair hA,Ii where A is a nonempty set and I is an interpretation function with domain the set of all constant, function and relation symbols of L such that: (1) if c is a constant symbol, then I(c) A; I(c) is called a constant

0. MODELS, TRUTH AND SATISFACTION 6

(2) if F is an m-placed function symbol, then I(F) is an m-placed function on A (3) if R is an n-placed relation symbol, then I(R) is an n-placed relation on A. A is called the universe of the model A. We generally denote models with Gothic letters and their universes with the corresponding Latin letters in boldface. One set may be involved as a universe with many dierent interpretation functions of the language L. The model is both the universe and the interpretation function. Remark. The importance of Model Theory lies in the observation that mathematical objects can be cast as models for a language. For instance, the real numbers with the usual ordering < < < and the usual arithmetic operations, addition + + + and multiplication · · · along with the special numbers 0 and 1 can be described as a model.Let L contain one two-placed (i.e. binary) relation symbol R0, two two-placed function symbols F1 and F2 and two constant symbols c0 and c1. We build a model by letting the universe A be the set of real numbers. The interpretation function I will map R0 to < < <, i.e. R0 will be interpreted as < < <. Similarly, I(F1) will be + + +, I(F2) will be · · ·, I(c0) will be 0 and I(c1) will be 1. So hA,Ii is an example of a model for the language described by {R0,F1,F2,c0,c1}. We now wish to show how to use formulas to express mathematical statements about elements of a model. We rst need to see how to interpret a term in a model.

Definition 7. The value t[x0,...,xq] of a term t(v0,...,vq) at x0,...,xq in the universe A of the model A is dened as follows: (1) if t is vi then t[x0,··· ,xq] is xi, (2) if t is the constant symbol c, then t[x0,...,xq] is I(c), the interpretation of c in A, (3) if t is F(t1 ...tm) where F is an m-placed function symbol and t1,...,tm are terms, then t[x0,...,xq] is G(t1[x0,...,xq],...,tm[x0,...,xq]) where G is the m-placed function I(F), the interpretation of F in A. Definition 8. Suppose A is a model for a language L. The sequencex 0,...,xq of elements of A satises the formula (v0,...,vq) all of whose free and bound variables are among v0,...,vq, in the model A, written A |= [x0,...,xq] provided we have: (1) if (v0,...,vq) is the formula (t1 = t2), then A |= (t1 = t2)[x0,...,xq] means that t1[x0,...,xq] equals t2[x0,...,xq], (2) if (v0,...,vq) is the formula (R(t1 ...tn)) where R is an n-placed relation symbol, then A |= (R(t1 ...tn))[x0,...,xq] means S(t1[x0,...,xq],...,tn[x0,...,xq]) where S is the n-placed relation I(R), the interpretation of R in A,(3) if is (¬θ), then A |= [x0,...,xq] means not A |= θ[x0,...,xq], (4) if is (θ∧ψ), then A |= [x0,...,xq] means both A |= θ[x0,...,xq] and A |= ψ[x0,...xq],

0. MODELS, TRUTH AND SATISFACTION 7

(5) if is (θ∨ψ) then A |= [x0,...,xq] means either A |= θ[x0,...,xq] or A |= ψ[x0,...,xq], (6) if is (θ ψ) then A |= [x0,...,xq] means that A |= θ[x0,...,xq] implies A |= ψ[x0,...,xq], (7) if is (θ ↔ ψ) then A |= [x0,...,xq] means that A |= θ[x0,...,xq] i A |= ψ[x0,...,xq], (8) if is viθ, then A |= [x0,...,xq] means for every x A,A |= θ[x0,...,xi−1,x,xi+1,...,xq], (9) if is viθ, then A |= [x0,...,xq] means for some x A,A |= θ[x0,...,xi−1,x,xi+1,...,xq]. Exercise 2. Each of the formulas of Example 2 is satised in any model A for any language L by any (long enough) sequence x0,x1,...,xq of A. This is where you test your solution to Exercise 1, especially with respect to the term and formula from Example 1.

We now prove two lemmas which show that the preceding concepts are welldened. In the rst one, we see that the value of a term only depends upon the values of the variables which actually occur in the term. In this lemma the equal sign = is used, not as a logical symbol in the formal sense, but in its usual sense to denote equality of mathematical objects — in this case, the values of terms, which are elements of the universe of a model. Lemma 1. Let A be a model for L and let t(v0,...,vp) be a term of L. Letx 0,...,xq and y0,...,yr be sequences from A such that p q and p r, and letx i = yi whenever vi actually occurs in t(v0,...,vp). Then t[x0,...,xq] = t[y0,...,yr] .

Proof. We use induction on the complexity of the term t. (1) If t is vi then xi = yi and so we have t[x0,...,xq] = xi = yi = t[y0,...,yr] since p q and p r. (2) If t is the constant symbol c, then t[x0,...,xq] = I(c) = t[y0,...,yr] where I(c) is the interpretation of c in A.(3) If t is F(t1 ...tm) where F is an m-placed function symbol, t1,...,tm are terms and I(F) = G, then t[x0,...,xq] = G(t1[x0,...,xq],...,tm[x0,...,xq]) and t[y0,...,yr] = G(t1[y0,...,yr],...,tm[y0,...,yr]). By the induction hypothesis we have that ti[x0,...,xq] = ti[y0,...,yr] for 1 i m since t1,...,tm have all their variables among {v0,...,vp}. So we have t[x0,...,xq] = t[y0,...,yr].


0. MODELS, TRUTH AND SATISFACTION 8

In the next lemma the equal sign = is used in both senses — as a formal logical symbol in the formal language L and also to denote the usual equality of mathematical objects. This is common practice where the context allows the reader to distinguish the two usages of the same symbol. The lemma conrms that satisfaction of a formula depends only upon the values of its free variables. Lemma 2. Let A be a model for L and a formula of L, all of whose free and bound variables occur among v0,...,vp. Let x0,...,xq and y0,...,yr (q,r p) be two sequences such that xi and yi are equal for all i such that vi occurs free in . Then A |= [x0,...,xq] i A |= [y0,...,yr] Proof. Let A and L be as above. We prove the lemma by induction on the complexity of . (1) If (v0,...,vp) is the formula (t1 = t2), then we use Lemma 1 to get: A |= (t1 = t2)[x0,...,xq] i t1[x0,...,xq] = t2[x0,...,xq] i t1[y0,...,yr] = t2[y0,...,yr] i A |= (t1 = t2)[y0,...,yr]. (2) If (v0,...,vp) is the formula (R(t1 ...tn)) where R is an n-placed relation symbol with interpretation S, then again by Lemma 1, we get: A |= (R(t1 ...tn))[x0,...,xq] i S(t1[x0,...,xq],...,tn[x0,...,xq]) i S(t1[y0,...,yr],...,tn[y0,...,yr]) i A |= R(t1 ...tn)[y0,...,yr]. (3) If is (¬θ), the inductive hypothesis gives that the lemma is true for θ. So, A |= [x0,...,xq] i not A |= θ[x0,...,xq] i not A |= θ[y0,...,yr] i A |= [y0,...,yr]. (4) If is (θ∧ψ), then using the inductive hypothesis on θ and ψ we get A |= [x0,...,xq] i both A |= θ[x0,...,xq] and A |= ψ[x0,...xq] i both A |= θ[y0,...,yr] and A |= ψ[y0,...yr] i A |= [y0,...,yr]. (5) If is (θ∨ψ) then A |= [x0,...,xq] i either A |= θ[x0,...,xq] or A |= ψ[x0,...,xq] i either A |= θ[y0,...,yr] or A |= ψ[y0,...,yr] i A |= [y0,...,yr]. (6) If is (θ ψ) then A |= [x0,...,xq] i A |= θ[x0,...,xq] implies A |= ψ[x0,...,xq] i A |= θ[y0,...,yr] implies A |= ψ[y0,...,yr] i A |= [y0,...,yr].

0. MODELS, TRUTH AND SATISFACTION 9

(7) If is (θ ↔ ψ) then A |= [x0,...,xq] i we have A |= θ[x0,...,xq] i A |= ψ[x0,...,xq] i we have A |= θ[y0,...,yr] i A |= ψ[y0,...,yr] i A |= [y0,...,yr]. (8) If is (vi)θ, then A |= [x0,...,xq] i for every z A,A |= θ[x0,...,xi−1,z,xi+1,...,xq] i for every z A,A |= θ[y0,...,yi−1,z,yi+1,...,yr] i A |= [y0,...,yr]. The inductive hypothesis uses the sequences x0,...,xi−1,z,xi+1,...,xq and y0,...,yi−1,z,yi+1,...,yr with the formula θ. (9) If is (vi)θ, then A |= [x0,...,xq] i for some z A,A |= θ[x0,...,xi−1,z,xi+1,...,xq] i for some z A,A |= θ[y0,...,yi−1,z,yi+1,...,yr] i A |= [y0,...,yr]. The inductive hypothesis uses the sequences x0,...,xi−1,z,xi+1,...,xq and y0,...,yi−1,z,yi+1,...,yr with the formula θ.


 Definition 9. A sentence is a formula with no free variables. If is a sentence, we can write A |= without any mention of a sequence fromA since by the previous lemma, it doesn’t matter which sequence from A we use. In this case we say: • A satises • or A is a model of • or holds in A • or is true in A If is a sentence of L, we write |= to mean that A |= for every model Afor L. Intuitively then, |= means that is true under any relevant interpretation (model forL). Alternatively, no relevant example (model forL) is a counterexample to — so is true. Lemma 3. Let (v0,...,vq) be a formula of the language L. There is anotherformula 0(v0,...,vq) of L such that (1) 0 has exactly the same free and bound occurrences of variables as . (2) 0 can possibly contain ¬, and but no other connective or quantier. (3) |= (v0)...(vq)( ↔ 0) Exercise 3. Prove the above lemma by induction on the complexity of . As a reward, note that this lemma can be used to shorten future proofs by induction on complexity of formulas.

Definition 10. A formula is said to be in prenex normal form whenever (1) there are no quantiers occurring in , or (2) is (vi)ψ where ψ is in prenex normal form and vi does not occur bound in ψ, or

0. MODELS, TRUTH AND SATISFACTION 10

(3) is (vi)ψ where ψ is in prenex normal form and vi does not occur bound in ψ.

Remark. If is in prenex normal form, then no variable occurring in occurs both free and bound and no bound variable occurring in is bound by more than one quantier. In the written order, all of the quantiers precede all of the connectives. Lemma 4. Let (v0,...,vp) be any formula of a language L. There is a formula of L which has the following properties: (1) is in prenex normal form (2) and have the same free occurrences of variables, and (3) |= (v0)...(vp)() Exercise 4. Prove this lemma by induction on the complexity of .

There is a notion of rank on prenex formulas — the number of alternations of quantiers. The usual formulas of elementary mathematics have prenex rank 0, i.e. no alternations of quantiers. For example: (x)(y)(2xy x2 + y2). However, the −δ denition of a limit of a function has prenex rank 2 and is much more dicult for students to comprehend at rst sight: ()(δ)(x)((0 < 0 < |x−a| < δ) |F(x)−L| < ). A formula of prenex rank 4 would make any mathematician look twice.

CHAPTER 1

 

Models, Truth and Satisfaction

We will use the following symbols: • logical symbols: – the connectives , , ¬ , , ↔ called “and”, “or”, “not”, “implies” and “i” respectively – the quantiers , called “for all” and “there exists” – an innite collection of variables indexed by the natural numbers N v0 ,v1 , v2 , ... – the two parentheses ), ( – the symbol = which is the usual “equal sign” • constant symbols : often denoted by the letter c with subscripts • function symbols : often denoted by the letter F with subscripts; each function symbol is an m-placed function symbol for some natural number m 1 • relation symbols : often denoted by the letter R with subscripts; each relational symbol is an n-placed relation symbol for some natural number n 1. We now dene terms and formulas. Definition 1. A term is dened as follows: (1) a variable is a term (2) a constant symbol is a term (3) if F is an m-placed function symbol and t1,...,tm are terms, then F(t1 ...tm) is a term. (4) a string of symbols is a term if and only if it can be shown to be a term by a nite number of applications of (1), (2) and (3). Remark. This is a recursive denition. Definition 2. A formula is dened as follows : (1) if t1 and t2 are terms, then (t1 = t2) is a formula. (2) if R is an n-placed relation symbol and t1,...,tn are terms, then (R(t1 ...tn)) is a formula. (3) if is a formula, then (¬) is a formula (4) if and ψ are formulas then so are (∧ψ), (∨ψ), ( ψ) and ( ↔ ψ) (5) if vi is a variable and is a formula, then (vi) and (vi) are formulas (6) a string of symbols is a formula if and only if it can be shown to be a formula by a nite number of applications of (1), (2), (3), (4) and (5). Remark. This is another recursive denition. ¬ is called the negation of ; ∧ψ is called the conjunction of and ψ; and ∨ψ is called the disjunction of and ψ.

4

0. MODELS, TRUTH AND SATISFACTION 5

Definition 3. A subformula of a formula is dened as follows: (1) is a subformula of (2) if (¬ψ) is a subformula of then so is ψ (3) if any one of (θ∧ψ), (θ∨ψ), (θ ψ) or (θ ↔ ψ) is a subformula of , then so are both θ and ψ (4) if either (vi)ψ or (vi)ψ is a subformula of for some natural number i, then ψ is also a subformula of (5) A string of symbols is a subformula of , if and only if it can be shown to be such by a nite number of applications of (1), (2), (3) and (4).

Definition 4. A variable vi is said to occur bound in a formula i for some subformula ψ of either (vi)ψ or (vi)ψ is a subformula of . In this case each occurrence of vi in (vi)ψ or (vi)ψ is said to be a bound occurrence of vi. Other occurrences of vi which do not occur bound in are said to be free.

Example 1.

F(v3) is a term, where F is a unary function symbol. ((v3)(v0 = v3)(v0)(v0 = v0)) is a formula. In this formula the variable v3 only occurs bound but the variable v0 occurs both bound and free.

Exercise 1. Using the previous denitions as a guide, dene the substitution of a term t for a variable vi in a formula . In particular, demonstrate how to substitute the term for the variable v0 in the formula of the example above. Definition 5. A language L is a set consisting of all the logical symbols with perhaps some constant, function and/or relational symbols included. It is understood that the formulas of L are made up from this set in the manner prescribed above. Note that all the formulas of L are uniquely described by listing only the constant, function and relation symbols of L. We use t(v0,...,vk) to denote a term t all of whose variables occur among v0,...,vk. We use (v0,...,vk) to denote a formula all of whose free variables occur among v0,...,vk.

Example 2. These would be formulas of any language : • For any variable vi: (vi = vi) • for any term t(v0,...,vk) and other terms t1 and t2: ((t1 = t2) (t(v0,...,vi−1,t1,vi+1,...,vk) = t(v0,...,vi−1,t2,vi+1,...,vk))) • for any formula (v0,...,vk) and terms t1 and t2: ((t1 = t2) ((v0,...,vi−1,t1,vi+1,...,vk) ↔ (v0,...,vi−1,t2,vi+1,...,vk))) Note the simple way we denote the substitution of t1 for vi. Definition 6. A model (or structure) A for a language L is an ordered pair hA,Ii where A is a nonempty set and I is an interpretation function with domain the set of all constant, function and relation symbols of L such that: (1) if c is a constant symbol, then I(c) A; I(c) is called a constant

0. MODELS, TRUTH AND SATISFACTION 6

(2) if F is an m-placed function symbol, then I(F) is an m-placed function on A (3) if R is an n-placed relation symbol, then I(R) is an n-placed relation on A. A is called the universe of the model A. We generally denote models with Gothic letters and their universes with the corresponding Latin letters in boldface. One set may be involved as a universe with many dierent interpretation functions of the language L. The model is both the universe and the interpretation function. Remark. The importance of Model Theory lies in the observation that mathematical objects can be cast as models for a language. For instance, the real numbers with the usual ordering < < < and the usual arithmetic operations, addition + + + and multiplication · · · along with the special numbers 0 and 1 can be described as a model.Let L contain one two-placed (i.e. binary) relation symbol R0, two two-placed function symbols F1 and F2 and two constant symbols c0 and c1. We build a model by letting the universe A be the set of real numbers. The interpretation function I will map R0 to < < <, i.e. R0 will be interpreted as < < <. Similarly, I(F1) will be + + +, I(F2) will be · · ·, I(c0) will be 0 and I(c1) will be 1. So hA,Ii is an example of a model for the language described by {R0,F1,F2,c0,c1}. We now wish to show how to use formulas to express mathematical statements about elements of a model. We rst need to see how to interpret a term in a model.

Definition 7. The value t[x0,...,xq] of a term t(v0,...,vq) at x0,...,xq in the universe A of the model A is dened as follows: (1) if t is vi then t[x0,··· ,xq] is xi, (2) if t is the constant symbol c, then t[x0,...,xq] is I(c), the interpretation of c in A, (3) if t is F(t1 ...tm) where F is an m-placed function symbol and t1,...,tm are terms, then t[x0,...,xq] is G(t1[x0,...,xq],...,tm[x0,...,xq]) where G is the m-placed function I(F), the interpretation of F in A. Definition 8. Suppose A is a model for a language L. The sequencex 0,...,xq of elements of A satises the formula (v0,...,vq) all of whose free and bound variables are among v0,...,vq, in the model A, written A |= [x0,...,xq] provided we have: (1) if (v0,...,vq) is the formula (t1 = t2), then A |= (t1 = t2)[x0,...,xq] means that t1[x0,...,xq] equals t2[x0,...,xq], (2) if (v0,...,vq) is the formula (R(t1 ...tn)) where R is an n-placed relation symbol, then A |= (R(t1 ...tn))[x0,...,xq] means S(t1[x0,...,xq],...,tn[x0,...,xq]) where S is the n-placed relation I(R), the interpretation of R in A,(3) if is (¬θ), then A |= [x0,...,xq] means not A |= θ[x0,...,xq], (4) if is (θ∧ψ), then A |= [x0,...,xq] means both A |= θ[x0,...,xq] and A |= ψ[x0,...xq],

0. MODELS, TRUTH AND SATISFACTION 7

(5) if is (θ∨ψ) then A |= [x0,...,xq] means either A |= θ[x0,...,xq] or A |= ψ[x0,...,xq], (6) if is (θ ψ) then A |= [x0,...,xq] means that A |= θ[x0,...,xq] implies A |= ψ[x0,...,xq], (7) if is (θ ↔ ψ) then A |= [x0,...,xq] means that A |= θ[x0,...,xq] i A |= ψ[x0,...,xq], (8) if is viθ, then A |= [x0,...,xq] means for every x A,A |= θ[x0,...,xi−1,x,xi+1,...,xq], (9) if is viθ, then A |= [x0,...,xq] means for some x A,A |= θ[x0,...,xi−1,x,xi+1,...,xq]. Exercise 2. Each of the formulas of Example 2 is satised in any model A for any language L by any (long enough) sequence x0,x1,...,xq of A. This is where you test your solution to Exercise 1, especially with respect to the term and formula from Example 1.

We now prove two lemmas which show that the preceding concepts are welldened. In the rst one, we see that the value of a term only depends upon the values of the variables which actually occur in the term. In this lemma the equal sign = is used, not as a logical symbol in the formal sense, but in its usual sense to denote equality of mathematical objects — in this case, the values of terms, which are elements of the universe of a model. Lemma 1. Let A be a model for L and let t(v0,...,vp) be a term of L. Letx 0,...,xq and y0,...,yr be sequences from A such that p q and p r, and letx i = yi whenever vi actually occurs in t(v0,...,vp). Then t[x0,...,xq] = t[y0,...,yr] .

Proof. We use induction on the complexity of the term t. (1) If t is vi then xi = yi and so we have t[x0,...,xq] = xi = yi = t[y0,...,yr] since p q and p r. (2) If t is the constant symbol c, then t[x0,...,xq] = I(c) = t[y0,...,yr] where I(c) is the interpretation of c in A.(3) If t is F(t1 ...tm) where F is an m-placed function symbol, t1,...,tm are terms and I(F) = G, then t[x0,...,xq] = G(t1[x0,...,xq],...,tm[x0,...,xq]) and t[y0,...,yr] = G(t1[y0,...,yr],...,tm[y0,...,yr]). By the induction hypothesis we have that ti[x0,...,xq] = ti[y0,...,yr] for 1 i m since t1,...,tm have all their variables among {v0,...,vp}. So we have t[x0,...,xq] = t[y0,...,yr].


0. MODELS, TRUTH AND SATISFACTION 8

In the next lemma the equal sign = is used in both senses — as a formal logical symbol in the formal language L and also to denote the usual equality of mathematical objects. This is common practice where the context allows the reader to distinguish the two usages of the same symbol. The lemma conrms that satisfaction of a formula depends only upon the values of its free variables. Lemma 2. Let A be a model for L and a formula of L, all of whose free and bound variables occur among v0,...,vp. Let x0,...,xq and y0,...,yr (q,r p) be two sequences such that xi and yi are equal for all i such that vi occurs free in . Then A |= [x0,...,xq] i A |= [y0,...,yr] Proof. Let A and L be as above. We prove the lemma by induction on the complexity of . (1) If (v0,...,vp) is the formula (t1 = t2), then we use Lemma 1 to get: A |= (t1 = t2)[x0,...,xq] i t1[x0,...,xq] = t2[x0,...,xq] i t1[y0,...,yr] = t2[y0,...,yr] i A |= (t1 = t2)[y0,...,yr]. (2) If (v0,...,vp) is the formula (R(t1 ...tn)) where R is an n-placed relation symbol with interpretation S, then again by Lemma 1, we get: A |= (R(t1 ...tn))[x0,...,xq] i S(t1[x0,...,xq],...,tn[x0,...,xq]) i S(t1[y0,...,yr],...,tn[y0,...,yr]) i A |= R(t1 ...tn)[y0,...,yr]. (3) If is (¬θ), the inductive hypothesis gives that the lemma is true for θ. So, A |= [x0,...,xq] i not A |= θ[x0,...,xq] i not A |= θ[y0,...,yr] i A |= [y0,...,yr]. (4) If is (θ∧ψ), then using the inductive hypothesis on θ and ψ we get A |= [x0,...,xq] i both A |= θ[x0,...,xq] and A |= ψ[x0,...xq] i both A |= θ[y0,...,yr] and A |= ψ[y0,...yr] i A |= [y0,...,yr]. (5) If is (θ∨ψ) then A |= [x0,...,xq] i either A |= θ[x0,...,xq] or A |= ψ[x0,...,xq] i either A |= θ[y0,...,yr] or A |= ψ[y0,...,yr] i A |= [y0,...,yr]. (6) If is (θ ψ) then A |= [x0,...,xq] i A |= θ[x0,...,xq] implies A |= ψ[x0,...,xq] i A |= θ[y0,...,yr] implies A |= ψ[y0,...,yr] i A |= [y0,...,yr].

0. MODELS, TRUTH AND SATISFACTION 9

(7) If is (θ ↔ ψ) then A |= [x0,...,xq] i we have A |= θ[x0,...,xq] i A |= ψ[x0,...,xq] i we have A |= θ[y0,...,yr] i A |= ψ[y0,...,yr] i A |= [y0,...,yr]. (8) If is (vi)θ, then A |= [x0,...,xq] i for every z A,A |= θ[x0,...,xi−1,z,xi+1,...,xq] i for every z A,A |= θ[y0,...,yi−1,z,yi+1,...,yr] i A |= [y0,...,yr]. The inductive hypothesis uses the sequences x0,...,xi−1,z,xi+1,...,xq and y0,...,yi−1,z,yi+1,...,yr with the formula θ. (9) If is (vi)θ, then A |= [x0,...,xq] i for some z A,A |= θ[x0,...,xi−1,z,xi+1,...,xq] i for some z A,A |= θ[y0,...,yi−1,z,yi+1,...,yr] i A |= [y0,...,yr]. The inductive hypothesis uses the sequences x0,...,xi−1,z,xi+1,...,xq and y0,...,yi−1,z,yi+1,...,yr with the formula θ.


 Definition 9. A sentence is a formula with no free variables. If is a sentence, we can write A |= without any mention of a sequence fromA since by the previous lemma, it doesn’t matter which sequence from A we use. In this case we say: • A satises • or A is a model of • or holds in A • or is true in A If is a sentence of L, we write |= to mean that A |= for every model Afor L. Intuitively then, |= means that is true under any relevant interpretation (model forL). Alternatively, no relevant example (model forL) is a counterexample to — so is true. Lemma 3. Let (v0,...,vq) be a formula of the language L. There is anotherformula 0(v0,...,vq) of L such that (1) 0 has exactly the same free and bound occurrences of variables as . (2) 0 can possibly contain ¬, and but no other connective or quantier. (3) |= (v0)...(vq)( ↔ 0) Exercise 3. Prove the above lemma by induction on the complexity of . As a reward, note that this lemma can be used to shorten future proofs by induction on complexity of formulas.

Definition 10. A formula is said to be in prenex normal form whenever (1) there are no quantiers occurring in , or (2) is (vi)ψ where ψ is in prenex normal form and vi does not occur bound in ψ, or

0. MODELS, TRUTH AND SATISFACTION 10

(3) is (vi)ψ where ψ is in prenex normal form and vi does not occur bound in ψ.

Remark. If is in prenex normal form, then no variable occurring in occurs both free and bound and no bound variable occurring in is bound by more than one quantier. In the written order, all of the quantiers precede all of the connectives. Lemma 4. Let (v0,...,vp) be any formula of a language L. There is a formula of L which has the following properties: (1) is in prenex normal form (2) and have the same free occurrences of variables, and (3) |= (v0)...(vp)() Exercise 4. Prove this lemma by induction on the complexity of .

There is a notion of rank on prenex formulas — the number of alternations of quantiers. The usual formulas of elementary mathematics have prenex rank 0, i.e. no alternations of quantiers. For example: (x)(y)(2xy x2 + y2). However, the −δ denition of a limit of a function has prenex rank 2 and is much more dicult for students to comprehend at rst sight: ()(δ)(x)((0 < 0 < |x−a| < δ) |F(x)−L| < ). A formula of prenex rank 4 would make any mathematician look twice.

CHAPTER 1

 

 

 



 

回复(0)

21天前 北大袁萌模型论电子版教材,何处寻?

模型论电子版教材,何处寻?

  今天, 16,是国内模型论爱好者的节日,因为,世界一流水平的模型论电子版(PDF)教材已经来到我们的身边。

  百度一下“无穷小微积分”,进入该网站,下载第一篇《Model theory》即可。

  我们满怀豪情地走在模型论的大道上!

袁萌  陈启清 16

   附件:模型论电子版教材的引言原文如下

Introduction

Model Theory is the part of mathematics which shows how to apply logic to the study of structures in pure mathematics.

袁萌  陈启清 16

附件:

   Fundamentals of Model Theory

Introduction

Model Theory is the part of mathematics which shows how to apply logic to the study of structures in pure mathematics. On the one hand it is the ultimate abstraction; on the other, it has immediate applications to every-day mathematics. The fundamental tenet of Model Theory is that mathematical truth, like all truth, is relative. A statement may be true or false, depending on how and where it is interpreted. This isn’t necessarily due to mathematics itself, but is a consequence of the language that we use to express mathematical ideas. What at rst seems like a deciency in our language, can actually be shaped into a powerful tool for understanding mathematics. This book provides an introduction to Model Theory which can be used as a text for a reading course or a summer project at the senior undergraduate or graduate level. It is also a primer which will give someone a self contained overview of the subject, before diving into one of the more encyclopedic standard graduate texts. Any reader who is familiar with the cardinality of a set and the algebraic closure of a eld can proceed without worry. Many readers will have some acquaintance with elementary logic, but this is not absolutely required, since all necessary concepts from logic are reviewed in Chapter 0. Chapter 1 gives the motivating examples; it is short and we recommend that you peruse it rst, before studying the more technical aspects of Chapter 0. Chapters 2 and 3 are selections of some of the most important techniques in Model Theory. The remaining chapters investigate the relationship between Model Theory and the algebra of the real and complex numbers. Thirty exercises develop familiarity with the denitions and consolidate understanding of the main proof techniques. Throughout the book we present applications which cannot easily be found elsewhere in such detail. Some are chosen for their value in other areas of mathematics: Ramsey’s Theorem, the Tarski-Seidenberg Theorem. Some are chosen for their immediate appeal to every mathematician: existence of innitesimals for calculus, graph colouring on the plane. And some, like Hilbert’s Seventeenth Problem, are chosen because of how amazing it is that logic can play an important role in the solution of a problem from high school algebra. In each case, the derivation is shorter than any which tries to avoid logic. More importantly, the methods of Model Theory display clearly the structure of the main ideas of the proofs, showing how theorems of logic combine with theorems from other areas of mathematics to produce stunning results. The theorems here are all are more than thirty years old and due in great part to the cofounders of the subject, Abraham Robinson and Alfred Tarski. However, we have not attempted to give a history. When we attach a name to a theorem, it is simply because that is what mathematical logicians popularly call it. The bibliography contains a number of texts that were helpful in the preparation of this manuscript. They could serve as avenues of further study and in addition, they contain many other references and historical notes. The more recent titles were added to show the reader where the subject is moving today. All are worth a look. This book began life as notes for William Weiss’s graduate course at the University of Toronto. The notes were revised and expanded by Cherie D’Mello and

2

William Weiss, based upon suggestions from several graduate students. The electronic version of this book may be downloaded and further modied by anyone for the purpose of learning, provided this paragraph is included in its entirety and so long as no part of this book is sold for prot.



 

回复(0)

22天前 北大袁萌模型论对(ε,δ)方法说不!

模型论对(εδ)方法说不!

  为什么“模型论对(εδ)方法说不!”?

  有人抱着(εδ)方法亲不够。

根据模型论基础(Fundamentals)第0章最后一段话的论断,可以明显看出这一结论;

  这段话的原文如下:

There is a notion of rank on prenex formulas

— the number of alternations of quantiers. The usual formulas of elementary mathematics have prenex rank 0, i.e. no alternations of quantiers. For example: (x)(y)(2xy x2 + y2). However, the ε−δ denition of a limit of a function has prenex rank 2 and is much more dicult for students to comprehend at rst sight: (ε)(δ)(x)((0 < ε0 < |x−a| < δ) |F(x)−L| < ε). A formula of prenex rank 4 would make any mathematician look twice.

袁萌  陈启清 15

附件:

Fundamentals of Model Theory

CHAPTER 0

Models, Truth and Satisfaction

We will use the following symbols: • logical symbols: – the connectives , , ¬ , , ↔ called “and”, “or”, “not”, “implies” and “i” respectively – the quantiers , called “for all” and “there exists” – an innite collection of variables indexed by the natural numbers N v0 ,v1 , v2 , ... – the two parentheses ), ( – the symbol = which is the usual “equal sign” • constant symbols : often denoted by the letter c with subscripts • function symbols : often denoted by the letter F with subscripts; each function symbol is an m-placed function symbol for some natural number m 1 • relation symbols : often denoted by the letter R with subscripts; each relational symbol is an n-placed relation symbol for some natural number n 1. We now dene terms and formulas. Definition 1. A term is dened as follows: (1) a variable is a term (2) a constant symbol is a term (3) if F is an m-placed function symbol and t1,...,tm are terms, then F(t1 ...tm) is a term. (4) a string of symbols is a term if and only if it can be shown to be a term by a nite number of applications of (1), (2) and (3). Remark. This is a recursive denition. Definition 2. A formula is dened as follows : (1) if t1 and t2 are terms, then (t1 = t2) is a formula. (2) if R is an n-placed relation symbol and t1,...,tn are terms, then (R(t1 ...tn)) is a formula. (3) if is a formula, then (¬) is a formula (4) if and ψ are formulas then so are (∧ψ), (∨ψ), ( ψ) and ( ↔ ψ) (5) if vi is a variable and is a formula, then (vi) and (vi) are formulas (6) a string of symbols is a formula if and only if it can be shown to be a formula by a nite number of applications of (1), (2), (3), (4) and (5). Remark. This is another recursive denition. ¬ is called the negation of ; ∧ψ is called the conjunction of and ψ; and ∨ψ is called the disjunction of and ψ.

4

0. MODELS, TRUTH AND SATISFACTION 5

Definition 3. A subformula of a formula is dened as follows: (1) is a subformula of (2) if (¬ψ) is a subformula of then so is ψ (3) if any one of (θ∧ψ), (θ∨ψ), (θ ψ) or (θ ↔ ψ) is a subformula of , then so are both θ and ψ (4) if either (vi)ψ or (vi)ψ is a subformula of for some natural number i, then ψ is also a subformula of (5) A string of symbols is a subformula of , if and only if it can be shown to be such by a nite number of applications of (1), (2), (3) and (4).

Definition 4. A variable vi is said to occur bound in a formula i for some subformula ψ of either (vi)ψ or (vi)ψ is a subformula of . In this case each occurrence of vi in (vi)ψ or (vi)ψ is said to be a bound occurrence of vi. Other occurrences of vi which do not occur bound in are said to be free.

Example 1.

F(v3) is a term, where F is a unary function symbol. ((v3)(v0 = v3)(v0)(v0 = v0)) is a formula. In this formula the variable v3 only occurs bound but the variable v0 occurs both bound and free.

Exercise 1. Using the previous denitions as a guide, dene the substitution of a term t for a variable vi in a formula . In particular, demonstrate how to substitute the term for the variable v0 in the formula of the example above. Definition 5. A language L is a set consisting of all the logical symbols with perhaps some constant, function and/or relational symbols included. It is understood that the formulas of L are made up from this set in the manner prescribed above. Note that all the formulas of L are uniquely described by listing only the constant, function and relation symbols of L. We use t(v0,...,vk) to denote a term t all of whose variables occur among v0,...,vk. We use (v0,...,vk) to denote a formula all of whose free variables occur among v0,...,vk.

Example 2. These would be formulas of any language : • For any variable vi: (vi = vi) • for any term t(v0,...,vk) and other terms t1 and t2: ((t1 = t2) (t(v0,...,vi−1,t1,vi+1,...,vk) = t(v0,...,vi−1,t2,vi+1,...,vk))) • for any formula (v0,...,vk) and terms t1 and t2: ((t1 = t2) ((v0,...,vi−1,t1,vi+1,...,vk) ↔ (v0,...,vi−1,t2,vi+1,...,vk))) Note the simple way we denote the substitution of t1 for vi. Definition 6. A model (or structure) A for a language L is an ordered pair hA,Ii where A is a nonempty set and I is an interpretation function with domain the set of all constant, function and relation symbols of L such that: (1) if c is a constant symbol, then I(c) A; I(c) is called a constant

0. MODELS, TRUTH AND SATISFACTION 6

(2) if F is an m-placed function symbol, then I(F) is an m-placed function on A (3) if R is an n-placed relation symbol, then I(R) is an n-placed relation on A. A is called the universe of the model A. We generally denote models with Gothic letters and their universes with the corresponding Latin letters in boldface. One set may be involved as a universe with many dierent interpretation functions of the language L. The model is both the universe and the interpretation function. Remark. The importance of Model Theory lies in the observation that mathematical objects can be cast as models for a language. For instance, the real numbers with the usual ordering < < < and the usual arithmetic operations, addition + + + and multiplication · · · along with the special numbers 0 and 1 can be described as a model.Let L contain one two-placed (i.e. binary) relation symbol R0, two two-placed function symbols F1 and F2 and two constant symbols c0 and c1. We build a model by letting the universe A be the set of real numbers. The interpretation function I will map R0 to < < <, i.e. R0 will be interpreted as < < <. Similarly, I(F1) will be + + +, I(F2) will be · · ·, I(c0) will be 0 and I(c1) will be 1. So hA,Ii is an example of a model for the language described by {R0,F1,F2,c0,c1}. We now wish to show how to use formulas to express mathematical statements about elements of a model. We rst need to see how to interpret a term in a model.

Definition 7. The value t[x0,...,xq] of a term t(v0,...,vq) at x0,...,xq in the universe A of the model A is dened as follows: (1) if t is vi then t[x0,··· ,xq] is xi, (2) if t is the constant symbol c, then t[x0,...,xq] is I(c), the interpretation of c in A, (3) if t is F(t1 ...tm) where F is an m-placed function symbol and t1,...,tm are terms, then t[x0,...,xq] is G(t1[x0,...,xq],...,tm[x0,...,xq]) where G is the m-placed function I(F), the interpretation of F in A. Definition 8. Suppose A is a model for a language L. The sequencex 0,...,xq of elements of A satises the formula (v0,...,vq) all of whose free and bound variables are among v0,...,vq, in the model A, written A |= [x0,...,xq] provided we have: (1) if (v0,...,vq) is the formula (t1 = t2), then A |= (t1 = t2)[x0,...,xq] means that t1[x0,...,xq] equals t2[x0,...,xq], (2) if (v0,...,vq) is the formula (R(t1 ...tn)) where R is an n-placed relation symbol, then A |= (R(t1 ...tn))[x0,...,xq] means S(t1[x0,...,xq],...,tn[x0,...,xq]) where S is the n-placed relation I(R), the interpretation of R in A,(3) if is (¬θ), then A |= [x0,...,xq] means not A |= θ[x0,...,xq], (4) if is (θ∧ψ), then A |= [x0,...,xq] means both A |= θ[x0,...,xq] and A |= ψ[x0,...xq],

0. MODELS, TRUTH AND SATISFACTION 7

(5) if is (θ∨ψ) then A |= [x0,...,xq] means either A |= θ[x0,...,xq] or A |= ψ[x0,...,xq], (6) if is (θ ψ) then A |= [x0,...,xq] means that A |= θ[x0,...,xq] implies A |= ψ[x0,...,xq], (7) if is (θ ↔ ψ) then A |= [x0,...,xq] means that A |= θ[x0,...,xq] i A |= ψ[x0,...,xq], (8) if is viθ, then A |= [x0,...,xq] means for every x A,A |= θ[x0,...,xi−1,x,xi+1,...,xq], (9) if is viθ, then A |= [x0,...,xq] means for some x A,A |= θ[x0,...,xi−1,x,xi+1,...,xq]. Exercise 2. Each of the formulas of Example 2 is satised in any model A for any language L by any (long enough) sequence x0,x1,...,xq of A. This is where you test your solution to Exercise 1, especially with respect to the term and formula from Example 1.

We now prove two lemmas which show that the preceding concepts are welldened. In the rst one, we see that the value of a term only depends upon the values of the variables which actually occur in the term. In this lemma the equal sign = is used, not as a logical symbol in the formal sense, but in its usual sense to denote equality of mathematical objects — in this case, the values of terms, which are elements of the universe of a model. Lemma 1. Let A be a model for L and let t(v0,...,vp) be a term of L. Letx 0,...,xq and y0,...,yr be sequences from A such that p q and p r, and letx i = yi whenever vi actually occurs in t(v0,...,vp). Then t[x0,...,xq] = t[y0,...,yr] .

Proof. We use induction on the complexity of the term t. (1) If t is vi then xi = yi and so we have t[x0,...,xq] = xi = yi = t[y0,...,yr] since p q and p r. (2) If t is the constant symbol c, then t[x0,...,xq] = I(c) = t[y0,...,yr] where I(c) is the interpretation of c in A.(3) If t is F(t1 ...tm) where F is an m-placed function symbol, t1,...,tm are terms and I(F) = G, then t[x0,...,xq] = G(t1[x0,...,xq],...,tm[x0,...,xq]) and t[y0,...,yr] = G(t1[y0,...,yr],...,tm[y0,...,yr]). By the induction hypothesis we have that ti[x0,...,xq] = ti[y0,...,yr] for 1 i m since t1,...,tm have all their variables among {v0,...,vp}. So we have t[x0,...,xq] = t[y0,...,yr].


0. MODELS, TRUTH AND SATISFACTION 8

In the next lemma the equal sign = is used in both senses — as a formal logical symbol in the formal language L and also to denote the usual equality of mathematical objects. This is common practice where the context allows the reader to distinguish the two usages of the same symbol. The lemma conrms that satisfaction of a formula depends only upon the values of its free variables. Lemma 2. Let A be a model for L and a formula of L, all of whose free and bound variables occur among v0,...,vp. Let x0,...,xq and y0,...,yr (q,r p) be two sequences such that xi and yi are equal for all i such that vi occurs free in . Then A |= [x0,...,xq] i A |= [y0,...,yr] Proof. Let A and L be as above. We prove the lemma by induction on the complexity of . (1) If (v0,...,vp) is the formula (t1 = t2), then we use Lemma 1 to get: A |= (t1 = t2)[x0,...,xq] i t1[x0,...,xq] = t2[x0,...,xq] i t1[y0,...,yr] = t2[y0,...,yr] i A |= (t1 = t2)[y0,...,yr]. (2) If (v0,...,vp) is the formula (R(t1 ...tn)) where R is an n-placed relation symbol with interpretation S, then again by Lemma 1, we get: A |= (R(t1 ...tn))[x0,...,xq] i S(t1[x0,...,xq],...,tn[x0,...,xq]) i S(t1[y0,...,yr],...,tn[y0,...,yr]) i A |= R(t1 ...tn)[y0,...,yr]. (3) If is (¬θ), the inductive hypothesis gives that the lemma is true for θ. So, A |= [x0,...,xq] i not A |= θ[x0,...,xq] i not A |= θ[y0,...,yr] i A |= [y0,...,yr]. (4) If is (θ∧ψ), then using the inductive hypothesis on θ and ψ we get A |= [x0,...,xq] i both A |= θ[x0,...,xq] and A |= ψ[x0,...xq] i both A |= θ[y0,...,yr] and A |= ψ[y0,...yr] i A |= [y0,...,yr]. (5) If is (θ∨ψ) then A |= [x0,...,xq] i either A |= θ[x0,...,xq] or A |= ψ[x0,...,xq] i either A |= θ[y0,...,yr] or A |= ψ[y0,...,yr] i A |= [y0,...,yr]. (6) If is (θ ψ) then A |= [x0,...,xq] i A |= θ[x0,...,xq] implies A |= ψ[x0,...,xq] i A |= θ[y0,...,yr] implies A |= ψ[y0,...,yr] i A |= [y0,...,yr].

0. MODELS, TRUTH AND SATISFACTION 9

(7) If is (θ ↔ ψ) then A |= [x0,...,xq] i we have A |= θ[x0,...,xq] i A |= ψ[x0,...,xq] i we have A |= θ[y0,...,yr] i A |= ψ[y0,...,yr] i A |= [y0,...,yr]. (8) If is (vi)θ, then A |= [x0,...,xq] i for every z A,A |= θ[x0,...,xi−1,z,xi+1,...,xq] i for every z A,A |= θ[y0,...,yi−1,z,yi+1,...,yr] i A |= [y0,...,yr]. The inductive hypothesis uses the sequences x0,...,xi−1,z,xi+1,...,xq and y0,...,yi−1,z,yi+1,...,yr with the formula θ. (9) If is (vi)θ, then A |= [x0,...,xq] i for some z A,A |= θ[x0,...,xi−1,z,xi+1,...,xq] i for some z A,A |= θ[y0,...,yi−1,z,yi+1,...,yr] i A |= [y0,...,yr]. The inductive hypothesis uses the sequences x0,...,xi−1,z,xi+1,...,xq and y0,...,yi−1,z,yi+1,...,yr with the formula θ.


 Definition 9. A sentence is a formula with no free variables. If is a sentence, we can write A |= without any mention of a sequence fromA since by the previous lemma, it doesn’t matter which sequence from A we use. In this case we say: • A satises • or A is a model of • or holds in A • or is true in A If is a sentence of L, we write |= to mean that A |= for every model Afor L. Intuitively then, |= means that is true under any relevant interpretation (model forL). Alternatively, no relevant example (model forL) is a counterexample to — so is true. Lemma 3. Let (v0,...,vq) be a formula of the language L. There is anotherformula 0(v0,...,vq) of L such that (1) 0 has exactly the same free and bound occurrences of variables as . (2) 0 can possibly contain ¬, and but no other connective or quantier. (3) |= (v0)...(vq)( ↔ 0) Exercise 3. Prove the above lemma by induction on the complexity of . As a reward, note that this lemma can be used to shorten future proofs by induction on complexity of formulas.

Definition 10. A formula is said to be in prenex normal form whenever (1) there are no quantiers occurring in , or (2) is (vi)ψ where ψ is in prenex normal form and vi does not occur bound in ψ, or

0. MODELS, TRUTH AND SATISFACTION 10

(3) is (vi)ψ where ψ is in prenex normal form and vi does not occur bound in ψ.

Remark. If is in prenex normal form, then no variable occurring in occurs both free and bound and no bound variable occurring in is bound by more than one quantier. In the written order, all of the quantiers precede all of the connectives. Lemma 4. Let (v0,...,vp) be any formula of a language L. There is a formula of L which has the following properties: (1) is in prenex normal form (2) and have the same free occurrences of variables, and (3) |= (v0)...(vp)() Exercise 4. Prove this lemma by induction on the complexity of .

There is a notion of rank on prenex formulas

— the number of alternations of quantiers. The usual formulas of elementary mathematics have prenex rank 0, i.e. no alternations of quantiers. For example: (x)(y)(2xy x2 + y2). However, the ε−δ denition of a limit of a function has prenex rank 2 and is much more dicult for students to comprehend at rst sight: (ε)(δ)(x)((0 < ε0 < |x−a| < δ) |F(x)−L| < ε). A formula of prenex rank 4 would make any mathematician look twice.

CHAPTER 1



 

回复(0)

24天前 北大袁萌鲁宾逊基本定理的现实意义

鲁宾逊基本定理的现实意义

   六十年前,伟大的数学家鲁宾逊第一次证明了两条纯粹数学定理,名垂千古。

  去年11月,国家教育部发文,要求全国普通高校以及相关研究部门设立基础数学中心(也就是纯粹数学中心).

                      

  基础数学中心离不开鲁宾逊基本定理。

  鲁宾逊两条基本定理是什么?请见本文附件。

  国家的需求就是鲁宾逊基本定理的现实意义。

袁萌 陈启清 13

 

附件:

Fundamentals of Model

….   ….

Theorem 10

yRobinson nally solved the centuries old problem of innitesimals in the foundations of calculus. Theorem 10. (The Leibniz Principle) There is an ordered eld R called the hyperreals, containing the reals R and a number larger than any real number such that any statement about the reals which holds in R also holds in R.

Proof. Let R be hR,+ + +,· · ·,< < <,0 0 0,1 1 1i. We will make the statement of the theoremprecise by proving that there is some model H, in the same language L as R andwith the universe called R , such that R H and there is b R such that a < b for each a R. For each real number a, we introduce a new constant symbol ca. In addition, another new constant symbol d is introduced. Let Σ be the set of sentences in the expanded language given by: ThRR{ca < d : a is a real} We can obtain a model C |= Σ by the compactness theorem. Let C0 be the reduct of C to L. By the elementary diagram lemma R is elementarily embedded in C0, and so there is a model H for L such that C0 = H and R H. Take b to be theinterpretation of d in H.


 Remark. The element b R gives rise to an innitesimal 1/b R. Anelement x R is said to be innitesimal whenever −1/n < x < 1/n for each n N. 0 is innitesimal. Two elements x,y R are said to be innitely close, written x y whenever x−y is innitesimal, so that x is innitesimal i x 0. An element x R is said to be nite whenever −r < x < r for some positive r R. Else it is innite. Each nite x R is innitely close to some real number, called the standardpart of x, written st(x). This idea is extremely useful in understanding calculus. To dierentiate f, for each Mx R generate My = f(x + Mx)−f(x). Then f0(x) = stMy Mxwheneverthis exists and is the same for each innitesimal Mx 6= 0. This legitimises the intuition of the founders of the dierential calculus and allows us to use that intuition to move from the (nitely) small to the innitely small. Proofs of the usual theorems of calculus are now much easier. More importantly, renements of these ideas, now called non-standard analysis, form a powerful tool for applying calculus, just as its founders envisaged. The following theorem is considered one of the most fundamental results of mathematical logic. We give a detailed proof. Theorem 11. (Robinson Consistency Theorem) Let L1 and L2 be two languages with L = L1L2. Suppose T1 and T2 are satisable

3. DIAGRAMS AND EMBEDDINGS 28

theories in L1 and L2 respectively. Then T1T2 is satisable i there is no sentence σ of L such that T1 |= σ and T2 |= ¬σ. Proof. The direction is easy and motivates the whole theorem. We begin the proof in the direction. Our goal is to show that T1 T2 is satisable. The following claim is a rst step. Claim. T1 { sentences σ of L : T2 |= σ} is satisable. Proof of Claim. Using the compactness theorem and considering conjunctions, it suces to show that if T1 |= σ1 and T2 |= σ2 with σ2 a sentence of L, then {σ1,σ2}is satisable. But this is true, since otherwise we would have σ1 |= ¬σ2 and hence T1 |= ¬σ2 and so ¬σ2 would be a sentence of L contradicting our hypothesis. This proves the claim.

The basic idea of the proof from now on is as follows. In order to construct a model of T1 T2 we construct models A |= T1 and B |= T2 and an isomorphism f : A|L B|L between the reducts of A and B to the language L, witnessing that A|L = B|L. We then use f to carry over interpretations of symbols in L1 \Lfrom A to B , giving an expansion B of B to the language L1 L2. Then, sinceB |L1 = A and B|L2 = B we get B |= T1 T2. The remainder of the proof will be devoted to constructing such an A, B and f. A and B will be constructed as unions of elementary chains of An’s and Bn’s while f will be the union of fn : An , Bn. We begin with n = 0, the rst link in the elementary chain. Claim. There are models A0 |= T1 and B0 |= T2 with an elementary embeddingf 0 : A0|L , B0|L. Proof of Claim. Using the previous claim, let A0 |= T1 { sentences σ of L : T2 |= σ} We rst wish to show that Th(A0|L)A0T2 is satisable. Using the compactness theorem, it suces to prove that if σ Th(A0|L)A0 then T2 {σ} is satisable. For such a σ let ca0,...,can be all the constant symbols from LA0 \L which appear in σ. Let be the formula of L obtained by replacing each constant symbol cai by a new variable ui. We have A0|L|= [a0,...,an] and so A0|L|= u0 ...un By the denition of A0, it cannot happen that T2 |= ¬u0 ...un and so there is some model D for L2 such that D |= T2 and D |= u0 ...un. So there are elements d0,...,dn of D such that D |= [do,...,dn]. Expand D to a model D for L2 LA0, making sure to interpret each cai as di. Then D |= σ, and so D |= T2 {σ}. Let B 0 |= Th(A0|L)A0T2. Let B0 be the reduct of B 0 toL2; clearly B0 |= T2.Since B0|L can be expanded to a model of Th(A0|L)A0, the Elementary Diagram Lemma gives an elementary embedding f0 : A0|L , B0|L and nishes the proof of the claim.

3.

 



 

回复(0)

26天前 北大袁萌元旦学习模型论有感

元旦学习模型论有感

  首先,袁萌与陈启清(此刻在上海出差)向大家预祝元旦快乐  

  过去几年,袁萌经常学习本文附件关于模型论的文章,每次都有所心得。

  我们希望,数学同行们学点儿模型论知识。

  请见本文附件。

袁萌  陈启清  2020年元旦

附件;

Fundamentals of Model Theory

Contents

Chapter  0.

Models, Truth and Satisfaction 4 Formulas, Sentences, Theories and Axioms 4

Prenex Normal Form 9

Chapte   1.

Notation and Examples    11

Chapter 2. Compactness and Elementary Submodels   14

The Compactness Theorem 14 Isomorphisms, elementary equivalence and complete theories 15 The Elementary Chain Theorem 16 The L¨owenheim-Skolem Theorem    19

The L o´s-Vaught Test 20

Every complex one-to-one polynomial map is onto 22

Chapter 3.

Diagrams and Embeddings 24 Diagram Lemmas 25 Every planar graph can be four coloured 25

Ramsey’s Theorem 26

The Leibniz Principle and innitesimals 27 The Robinson Consistency Theorem 27

The Craig Interpolation Theorem  31

Chapter   4.

Model Completeness 32

Robinson’s Theorem on existentially complete theories 32 Lindstr¨om’s Test 35 Hilbert’s Nullstellensatz 37

Chapter   5.

The Seventeenth Problem 39

Positive denite rational functions are the sums of squares   39

Chapter   6.

Submodel Completeness 45 Elimination of quantiers 45

The Tarski-Seidenberg Theorem  48

Chapter   7.

Model Completions 50

Almost universal theories 52 Saturated models 54 Blum’s Test  55

Bibliography   60

Index    61

 

 



 

回复(0)

27天前 北大袁萌学习模型论,今昔对比

学习模型论,今昔对比

  去年1214日,我们向国内学界推荐了“模型论之基础”(与今年此时推荐的是同一篇文章)。

  四十年前,袁萌在科学院数学所模型论讨论班使用超滤器构造了实数的非标准模型。这是科普模型论的开端.

  今年11月,国家教育部发文要求国内各高校以及相关研究单位设立“基础数学中心”,研究模型论是意中之事。

  这就是“学习模型论,今昔对比”的核心意思。

  预祝大家新年快乐!

袁萌  陈启清  1231

附件:

学习模型论,何其难?                                     四十年过去了,在国内学习纯粹数学(例如:模型论)仍然困难重重,甚至无人问津。

 

什么是数学模型理论?国内学界不发声,不说话,令人很无奈。

 

为此,我们推荐一篇科普文章,请见本本文附件。

 

袁萌  陈启清  1214

 

 

附件:Fundamentals of Model Theory

William Weiss and Cherie D’Mello

 



 

回复(0)

1月前 北大袁萌现代模型论之基础(I)

现代模型论之基础(I

  2015年,美这模型论专家William Weiss发表“模型论基础”,指出:近二十年来,模型论发展很快。

  该书援引16本模型论专著,内容严谨、全面,具有参阅价值。

 

  注:书的篇幅较长,分为数次发表。

请见本文附件文章。

袁萌  陈启清 1228

Fundamentals of Model Theory

William Weiss and Cherie D’Mello

Department of Mathematics University of Toronto

c

2015 W.Weiss and C. D’Mello

 

1

Introduction

Model Theory is the part of mathematics which shows how to apply logic to the study of structures in pure mathematics. On the one hand it is the ultimate abstraction; on the other, it has immediate applications to every-day mathematics. The fundamental tennet of Model Theory is that mathematical truth, like all truth, is relative. A statement may be true or false, depending on how and where it is interpreted. This isn’t necessarily due to mathematics itself, but is a consequence of the language that we use to express mathematical ideas. What at rst seems like a deciency in our language, can actually be shaped into a powerful tool for understanding mathematics. This book provides an introduction to Model Theory which can be used as a text for a reading course or a summer project at the senior undergraduate or graduate level. It is also a primer which will give someone a self contained overview of the subject, before diving into one of the more encyclopedic standard graduate texts. Any reader who is familiar with the cardinality of a set and the algebraic closure of a eld can proceed without worry. Many readers will have some acquaintance with elementary logic, but this is not absolutely required, since all necessary concepts from logic are reviewed in Chapter 0. Chapter 1 gives the motivating examples; it is short and we recommend that you peruse it rst, before studying the more technical aspects of Chapter 0. Chapters 2 and 3 are selections of some of the most important techniques in Model Theory. The remaining chapters investigate the relationship between Model Theory and the algebra of the real and complex numbers. Thirty exercises develop familiarity with the denitions and consolidate understanding of the main proof techniques. Throughout the book we present applications which cannot easily be found elsewhere in such detail. Some are chosen for their value in other areas of mathematics: Ramsey’s Theorem, the Tarski-Seidenberg Theorem. Some are chosen for their immediate appeal to every mathematician: existence of innitesimals for calculus, graph colouring on the plane. And some, like Hilbert’s Seventeenth Problem, are chosen because of how amazing it is that logic can play an important role in the solution of a problem from high school algebra. In each case, the derivation is shorter than any which tries to avoid logic. More importantly, the methods of Model Theory display clearly the structure of the main ideas of the proofs, showing how theorems of logic combine with

 

回复(0)

1月前 北大袁萌现代模型论之基础(I)

现代模型论之基础(I

  2015年,美这模型论专家William Weiss发表“模型论基础”,指出:近二十年来,模型论发展很快。

  该书援引16本模型论专著,内容严谨、全面,具有参阅价值。

 

  注:书的篇幅较长,分为数次发表。

请见本文附件文章。

袁萌  陈启清 1228



 

回复(0)

1月前 北大袁萌布尔巴基的衰落与模型论的兴起

布尔巴基的衰落与模型论的兴起

  进入二十世纪,现代数学经历了一次大起大落:布尔巴基的衰落与模型论的兴起。

  七年来,我们年年讲,月月讲,天天讲模型论的兴起。

  但是,对于布尔巴基的衰落的历史,请见本文附件文章。

袁萌  陈启清  1226

附件:

评价:作为一个著名的数学学派,布尔巴基(Bourbaki)近乎完美地完成了时代赋予它的在创造新数学和推动整个数学发展的任务。在某种意义下,堪称典范。

 

我们知道,布尔巴基诞生的背景是新兴数学分支蓬勃发展而法国数学进入衰退的时期。这种衰退或者停滞不仅仅表现在在新兴分支领域中的落后,也表现在因战争的因素而导致的数学人才的匮乏上。J. Dieudoone 在他《布尔巴基的事业》中是如此评价当时法国数学和法国数学的教育状况的:

……那时第一次世界大战刚刚结束的时候,而对于这场大战,能够肯定的说,对法国数学家而言是非常惨痛的.……在1914-1918年的大战中,德国政府和法国政府对于关系到科学问题的看法并不一致.德国政府把它们的学者派去从事科学工作,用他们的发现和对发明或者方法的改进来提升军队的战斗力。而法国政府至少在战争开始的一两年认为每一个人都应该到前线去战斗,于是法国年轻的科学家和其他的法国人一样到前线去尽他们的职责。对于这种民主和爱国的精神我们只能表示尊敬,但是其后果对于法国年轻一代的科学家来说却是一场可怕的大屠杀。当我们打开战争时期高等师范学校的学生名册时,我们就会发现巨大的断层,这表明由三分之二的学生都被战争摧毁了。这种情况对法国数学产生了非常灾难性的后果。我们这些人,当时太年轻而没有直接参加战争,但是我们在战争结束之后的几年中进入大学,本来应该由那些年轻的数学家给我指导,而他们中肯定有许多人会有远大的前途。他们就是被战争残忍摧毁了的年轻人而他们的影响也被完全地磨灭掉了。

 

……当然,留下来的上一代人都是我们尊敬和景仰的大学者。像毕卡、孟代尔、E.保莱尔、若尔当、勒贝格等大师,他们都还活着并且非常活跃,但是这些数学家都已接近50岁,有些人年事更高。在他们同我们之间隔着一代人。我并不是说他们没有交给我们最好的数学,我们都是听这些数学家上第一年的课程的.但是,无可争辩的是(对于任何时期也是一样的),50岁的数学家只知道他在20或者30岁时学的数学,而对他当时(即他五十岁的时期)的数学只有一些相当模糊的观念。事实上,我们对这种情况只有接受而毫无办法。

 

……我还记得范·德·瓦尔登(B.L.Van der Waerden,1903-1996)这本书刚出版的那天。那时我对代数无知到那种程度,以至于要是现在我就进不了大学。我急忙跑向这些书,看到这个在我面前打开的新世界我简直惊呆了。当时我的代数知识不超过预科数学、行列式以及一点方程的可解性和单行曲线。我那时已经从高等师范学校毕业,却不知道什么是理想(ideal),而且刚刚才知道什么是群!这就会使你对一个年轻的法国数学家在1930年知道些什么有一点概念……

正是出于复兴法国的数学传统以及扭转法国数学在各方面所呈现出来的不良的趋势,一批年轻的法国数学家走到了一起。

 

在二战后的十几年间,布尔巴基的声望达到了顶峰。《数学原理》成为新的经典,经常作为文献征引。布尔巴基讨论班的议题无疑都是当时数学的最新成就。在国际数学界,韦伊(Weil)、H.嘉当(H. Cartan)、狄奥多涅(Dieudonné)、薛华荔(Chevalley)、塞尔(Serre)、格罗登迪克(Grothendieck)等人都有着重要的影响。也正在此时,为布尔巴基确定形象的三项工作全面展开:

以布尔巴基名义发表的论文,除了一些小论文之外,最重要的两篇《数学的建筑》 和《数学研究者的数学基础》分别在1948年和1949年发表,它们实际上是布尔巴基学派的纲领和宣言,是布尔巴基学派的原始文献。同时布尔巴基的主要成员也陆续发表他们对数学、数学史和数学发展的看法。(这两篇文章非常好,推荐阅读!)

布尔巴基的主要著作《数学原理》的进一步出版。二战时,布尔巴基的《数学原理》只出版了4册。从1947年起加快了出版,10年之内又出了18册,到1959年共出了25册,基本上把“分析的基本结构”这部分出齐了。在这期间许多册还多次再版。同时布尔巴基的思想及写作风格成为青年人效仿的对象,很快地“布尔巴基的”便成为了一个专门的形容词。

布尔巴基讨论班的建立。讨论班的报告反映了当前数学的重大进展,并非只是简单的介绍,而是经过报告者的消化、吸收甚至再创造,对于掌握当前数学动向至关重要。可以说,起源于德国的这种讨论班的形式在法国已经遍地生根了。(布尔巴基讨论班似乎现在还在继续)

此外,经过两代布尔巴基成员的努力,终于把代数拓扑学、同调代数、微分拓扑学、微分几何学、多复变量函数论、代数几何学、代数数论、李群和代数群理论、泛函分析等数学领域汇合在一起,形成现代数学的主流,法国数学家在国际数学界的领袖地位也得到大家的公认。这由他们接连荣获国际数学大奖可见一斑。

 

1970年左右,布尔巴基大体上走向自己的反面而趋于衰微。这时,布尔巴基的奠基者们和第二代相继退出,年青一代的影响不能和老一代同日而语。数学本身也发生了巨大变化,布尔巴基比较忽视的分析数学、概率论、应用数学、计算数学,特别是理论物理、动力系统理论开始蓬勃发展,而20世纪五六十年代的重点 -- 代数拓扑学、微分拓扑学、多复变量函数论等相对平稳,数学家的兴趣更集中于经典的、具体的问题,而对于大的理论体系建设并不热衷;数学研究更加趋于专业化、技术化.20世纪70年代到80年代中期的数学显示出多样化的局面,明显的表现是在近年很少有新兴学科兴起,也无法与布尔巴基成立的时期相提并论.虽然,到了20世纪80年代中期,一种新的数学大统一的趋势又在形成,不过,这已经是在布尔巴基统一基础上更高级的统一。另一方面,许多持经典的观点的数学家根本就否定这种统一,也有相当多的人只热衷于具体的、极专门甚至琐碎的问题,很难把它们融入主流数学当中。实际上,第三代、第四代的布尔巴基也大都是某个领域的专家。从20世纪70年代起,布尔巴基讨论班的报告也反映出这种专门化和技术化的趋向。在这种情况下,20世纪70年代以来,在论文中引用布尔巴基《数学原理》的人越来越少了。

 

布尔巴基在教育上的失败也是影响它衰落的原因之一。由于布尔巴基的影响,在20世纪50年代到60年代出现了所谓“新数学(New Math)”运动,把抽象数学,特别是抽象代数的内容引入中学甚至小学的教科书当中。这种突然的变革不但使学生无法接受新教材,就连教员都无法理解,造成了整个数学教育的混乱。这是布尔巴基在教育方面的大失败。在高等数学教育方面,就连布尔巴基的奠基者们后来编的教科书也破除了布尔巴基的形式体系而采用比较自然、具体、循序渐进的体系.从某种意义上来讲,这是一种否定之否定,是向老传统的回归。

 

所以,站在现在的角度来说,作为一个曾经诞生了如此众多顶级数学家的学派,同时,也作为一个曾经实践了这样一个雄心勃勃的数学统一计划的学派,其对数学本身的贡献和对数学教育的贡献都可以用伟大来形容。

 

任何一个学派都是由人组成的,布尔巴基作为一个传奇的“数学家”,最终也不可避免地走向衰老,然而布尔巴基学派所提出的思想,他们的《数学原理》,以及他们为数学的统一性所做出的努力依然会影响每一位爱好数学的人。也许,当数学再一次走向统一的时候,人们会发现,这项事业的美妙起点就是布尔巴基的事业。

 

参考文献:

[1] 狄奥多涅,《布尔巴基的事业》(Jean A. Dieudonne, The Work of Bourbaki

[2] 狄奥多涅,《布尔巴基的数学哲学》

[3] Denis Guedj,《尼古拉·布尔巴基数学家集体 克劳德·薛华荔的一次访问记》(Denis Guedj, Nicholas Bourbaki, Collective Mathematician An Interview with Claude Chevalley

[4] 狄奥多涅,《纯粹数学的当前趋势》(Jean A. Dieudonne, Present Trends in Pure Mathematics

[5] 胡作玄,《布尔巴基学派的兴衰—现代数学发展的一条主线》,198409月第1

 

 



 

回复(0)

1月前 北大袁萌超实数与布尔巴基学派

超实数与布尔巴基学派

   读者阅读“超实数的演算”一文,就会知道:构建超实数系统,必须依靠集合“滤器”(Filter)概念。

历史上,最早提出“滤器”概念的是法国近代数学泰斗昂利•嘉当(1904-2008

  1937年,布尔巴基学派领导人昂利•嘉当发表“滤器理论”(法文),开启了构建超实数系统的大门。

袁萌  陈启清  1224

附件:

尼古拉•布尔巴基

1951年布尔巴基大会

尼古拉•布尔巴基(法语:Nicolas Bourbaki,法语发音[nikla bubaki])是20世纪一群法国数学家的笔名。他们由1935年开始撰写一系列述说对现代高等数学探研所得的书籍。以把整个数学建基于集合论为目的,在过程中,布尔巴基致力于做到最极端的严谨和泛化,建立了些新术语和概念。

布尔巴基是个虚构的人物,布尔巴基团体的正式称呼是“尼古拉•布尔巴基合作者协会”,在巴黎的高等师范学校设有办公室。

目录

1

布尔巴基的著作

2

布尔巴基成员

3

布尔巴基的观点并非中性

4

布尔巴基的发言人迪厄多内

5

布尔巴基的影响

6

外部链接

布尔巴基的著作

布尔巴基在集合论的基础上用公理方法重新构造整个现代数学。布尔巴基认为:数学,至少纯粹数学,是研究抽象结构的理论。结构,就是以初始概念和公理出发的演绎系统。有三种基本的抽象结构:代数结构,序结构,拓扑结构。他们把全部数学看作按不同结构进行演绎的体系。布尔巴基在《数学原本》(Éléments de mathématique)的题名下分卷出版了如下专著:

1卷集合论

2卷代数

3卷拓扑

4卷单实变函数

5卷拓扑向量空间

6卷积分

7卷交换代数

8卷李群

9卷谱理论

最后的第9卷谱理论执笔始于1983年,出版工程至此告终。只是在20世纪末,增补了交换代数的簇理论。

《数学原本》有七千多页,是有史以来最大的数学巨著。彻底追求严格性和一般性的叙述方法被称为“布尔巴基风格”。

布尔巴基对严谨性的强调在当时产生了很大的影响。这与当时儒勒•昂利•庞加莱所强调的数学要依靠自由想像的数学直观的说法分庭抗礼。布尔巴基的影响力随时间而减弱,一个原因是由于布尔巴基的抽象并不显得比发明者原初的想法更为有用,另一个原因是因为没有包含像范畴论等重要的现代数学理论。尽管范畴论是由布尔巴基的成员艾伦堡所创立,格罗滕迪克所推广的,但是如果要容纳范畴论,就不得不对已经出版的著作进行根本性的改写。

尽管布尔巴基的一部分著作在相应的领域成了标准的参考书,但是那种近于严峻的表达方式使其难以成为教科书。布尔巴基书籍的鼎盛时期是在19501960年之间,那时很少有适合能用于研究生水平的关于纯数学的教科书。

布尔巴基引入的记号有:

{\displaystyle \varnothing }

;代表空集,黑板粗体字母表示数集(例如:

N {\displaystyle \mathbb {N} }

表示自然数集,

Q {\displaystyle \mathbb {Q} }

表示有理数集

R {\displaystyle \mathbb {R} }

表示实数集,

Z {\displaystyle \mathbb {Z} }

表示整数集),还发明了术语“单射”、“满射”和“双射”。

布尔巴基讲座在战后立即于巴黎开设,这个讲座接连不断地公开发表了各种综述性论文,这些论文采用一种固定格式,用谨慎的风格写成。

布尔巴基成员

布尔巴基的早期成员时多时少。创始者五人全是巴黎高等师范学校出身,他们是安德烈•韦伊,昂利•嘉当,克劳德•谢瓦莱,让•迪厄多内和让•戴尔萨特。当时有一个初级会议,会议记录在布尔巴基档案中有存档:“欲知初级会议的详情,请与“数学咨询组”的利丽安•布利尤接洽”;成立时的其他四名成员是让•库朗,夏尔•埃雷斯曼,瑞内•德•波塞尔和佐勒姆•门德勃罗,而让•勒瑞和保罗•杜布莱依在布尔巴基宣布正式成立之前退出。其他较后参加的有名成员有劳朗•施瓦茨,让-皮埃尔•塞尔,塞缪尔•艾伦伯格,亚历山大•格罗滕迪克,塞尔日•兰和罗杰•戈德门。

布尔巴基的最初目标是编撰一本改良的微积分教科书,不久他们就意识到有必要对整个数学进行一种综合性的统一处理。当时,布尔巴基的成员身份是非公开的,团体内情是相当保密的,他们甚至故意提供假消息为乐。在定期会议上,全体成员对提出的每一部书稿进行逐字逐句的严格讨论。布尔巴基有一条规定,成员到50岁必须退休。

布尔巴基”取名于在普法战争中法国败将的名字;至于成为学派的名字是出于一堂数学课的恶作剧的传闻,也可能与一座雕像有关。这一名称还与希腊数学有关,因为名为布尔巴基的人具有希腊血统。从字面上也可以解释这一名字暗示了欧几里得传统被移植到1930年代的法国,并对此寄予质变的期望。

布尔巴基的观点并非中性

十分明显,布尔巴基的观点虽然是“百科全书”式的,但却从来没有想要保持中立。恰好相反,他们把热情倾注于整体一致性的展示,例如对希尔伯特的形式主义和公理主义的遗产的处理上。但对现存理论总要施行一种“接纳变换”,例如把张量微积分改名成多线性代数,创建独立于消元理论的交换代数,这在其前身理想理论时已成为主要倾向。希尔伯特在1890年代时已经显示对非构造性方法的钟爱,布尔巴基的行动使非构造性方法变得更加具体。

在下面例举的领域里布尔巴基有显著的偏向:

计算性内容不上议题,几乎完全被省略

解决问题被认为次于公理

数学分析被“软”处理,没有“硬”计算

测度论掩盖了拉东测度

组合学结构被视为非结构性的

逻辑只需最低限度(佐恩引理就已足够)

应用全无提起

并且(“这是很自然的” - cela va sans dire)没有图示。

数学家总是喜欢轶事传奇。布尔巴基的数学史并不缺少学术性,而是缺少“英雄史观”,历史是由那些经过奋斗而终于得到清晰公理的获胜者写成的。

布尔巴基的发言人迪厄多内[编辑]

对布尔巴基思想的公开讨论,或者对布尔巴基的辩护,一般是由让•迪厄多内出面代表,他的最初身份是团体的“书记”,他以自己的名字发表文章。 1977年写成的“布尔巴基的选择”(le choix bourbachique)一篇综述中,他对当时展示分层结构的“重要”数学的进展直言不讳。

他还广泛地写书:有微积分,也许是出于对原始目标或原稿的一种迟到的补偿;另外还写了不少关于代数几何的题材。尽管迪奥多内可以理直气壮地谈论布尔巴基的百科全书式倾向和布尔巴基的传统;,例如在布尔巴基的例会中,像“安静点,迪奥多内!” (原文:tais-toi Dieudonné!)这样直率的提醒多得数不清,但到底有多少人赞同他关于数学写作和研究的论点还是一个疑问。尤其是塞尔,他经常批评布尔巴基著作的书写方式,倡导在法国对解题方面赋予最大的关心,特别是在布尔巴基主要课题之外的数论研究当中。

迪奥多内在评述中说道,大多数的数学工作者都在打扫地板,为未来的波恩哈德•黎曼的直觉性发现清除视野。他指出公理方法可以作为解题工具,例如像亚历山大•格罗滕迪克所做的那样。但也有人认为他与格罗滕迪克关系过于密切,不是一位公正的评论者。帕尔•图兰在1970年菲尔兹奖颁奖仪式中对阿兰•贝克进行的颁奖演说内对于建立理论和解题的评论则被认为是传统阵营在之后(四年前的1966年,格罗滕迪克在缺席的情况下被授予菲尔兹奖)的一次反击。

布尔巴基的影响最终布尔巴基宣言还是产生了影响,特别是在纯数学的研究生教育上。详见本百科全书的相关部分。

新数学对初等数学教学几乎没有影响。比如说文氏图的使用,一直可以追溯到19世纪教学法。对微积分和离散数学的分界之争至今热狂不减当年。

布尔巴基在国际数学界的带头作用可能已被1960年代的波恩工作会议计划所取代。



 

回复(0)

1月前 北大袁萌超实数的演算

超实数的演算


  进入二十一世纪,我国普通高校教授微积分不引入超对数,就是“装糊涂”。

  简而言之,无穷小放飞互联网已经1七年了,而且几乎每天都有超实数的文章放飞互联网。

难道我国普通高高校数学教师从来不上网?

  百度一下“无穷小”,进入“无穷小微积分”专业网站,下载相关文章,看看其中的内容目录即可知晓一切,… …

    本文附件文章,只有18A4纸长度,讲解了无穷小微积分的基本概念与理论。看与不看,请随便。

袁萌  陈启清 1223

附件:

hyperreal calculus

Abstract

This project deals with doing calculus not by using epsilons and deltas, but by using a number system called the hyperreal numbers. The hyperreal numbers is an extension of the normal real numbers with both innitely small and innitely large numbers added. We will rst show how this system canbecreated,andthen shows omebasicpropertiesofthe hyperreal numbers. Then we will show how one can treat the topics of convergence, continuity, limits and dierentiation in this system and we will show that the two approaches give rise to the same denitions and results.

Contents

1 Construction of the hyperreal numbers 3 1.1 Intuitive construction . . . . . . . . . . . . . . . 3

1.2 Ultralters . . . . . . 3

1.3 Formal construction . .  4

1.4 Innitely small and large numbers . . . . .. 5

1.5 Enlarging sets . . . 5

1.6 Extending functions . . . . . .  . 6

2 The transfer principle  6

2.1 Stating the transfer principle . . . . . . . . . .  6

2.2 Using the transfer principle . . . . . .  7

3 Properties of the hyperreals 8 3.1 Terminology and notation . . . .  . 8

3.2 Arithmetic of hyperreals . . . . . 9

3.3 Halos . . . . . 9

3.4 Shadows . . . . .10

4 Convergence 11

4.1 Convergence in hyperreal calculus. . . .  .

4.2 Monotone convergence  . 12

5 Continuity 13

 

 

 

5.1 Continuity in hyperreal calculus . . . . . 13

5.2 Examples . . . . . . . . . . . . . . . . . . 14

5.3 Theorems about continuity . . . . . . . . .. 15

5.4 Uniform continuity . . . . . . .. . 16

6 Limits and derivatives 17 6.1 Limits in hyperreal calculus . . . . . . .  17

6.2 Dierentiation in hyperreal calculus . . . . . .18

6.3 Examples . . . . . .  18

6.4 Increments . . . . . . . . . . . . . . . . . . 19

6.5 Theorems about derivatives . .  . 19

1

1 Construction of the hyperreal numbers

1.1 Intuitive construction We want to construct the hyperreal numbers as sequences of real numbers hrni = hr1,r2,...i, and the idea is to let sequences where limn→∞rn = 0 represent innitely small numbers, or innitesimals, and let sequences where limn→∞rn = represent innitely large numbers. However, if we simply let each hyperreal number be dened as a sequence of real numbers, and let addition and multiplication be dened as elementwise additionandmultiplicationofsequences, wehavetheproblemthatthisstructure is not a eld, since h1,0,1,0,...i
h0,1,0,1,...i=h0,0,0,0,...i. The way we solve this is by introducing an equivalence relation on the set of real-valued sequences. We want to identify two sequences if the set of indices for which the sequences agree is a large subset of N, for a certain technical meaning of large. Let us rst discuss some properties we should expect this concept of largeness to have. • N itself must be large, since a sequence must be equivalent with itself. • If a set contains a large set, it should be large itself. • The empty set
should not be large. • We want our relation to be transitive, so if the sequences r and s agree on a large set, and s and t agree on a large set, we want r and t to agree on a large set.

1.2 Ultralters Our model of a large set is a mathematical structure called an ultralter. Denition 1.1 (Ultralters). We dene an ultralter on N, F, to be a set of subsets of N such that: • If X F and X Y N, then Y F. That is, F is closed under supersets. • If X F and Y F, then X Y F. F is closed under intersections. • NF, but 6F. • For any subset A of N, F contains exactly one of A and N\A. We say that an ultralter is free if it contains no nite subsets of N. Note that a free ultralter will contain all conite subsets of N (sets with nite complement) due to the last property of an ultralter. Theorem 1.2. There exists a free ultralter on N. Proof. See [Kei76,

 

回复(0)

共 786 条12345››... 40
数据统计:24 小时内发布61条 ... 一周内发布646条 ... 总发布数 276453
新传学院 订阅/关注/阅文/评论/公号XCST填写您的邮件地址,订阅我们的精彩内容: