Section 2.2: Problem 25 Solution
Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.
James R. Munkres
Consider a fixed structure . Expand the language by adding a new constant symbol for each . Let be the structure for this expanded language that agrees with on the original parameters and that assigns to the point . A relation on is said to be definable from points in iff is definable in . (This differs from ordinary definability only in that we now have parameters in the language for members of .) Let .
(a) Show that if is a subset of consisting of the union of finitely many intervals, then is definable from points in (cf. Exercise 12).
(b) Assume that . Show that any subset of that is non-empty, bounded (in the ordering ), and definable from points in has a least upper bound in .
Digression: Often when people speak of definability within a structure, this is the concept they mean. The more standard phrase is “definable from parameters”; here “points” is used because the word “parameter” is used in a different sense in this chapter.
The real ordered field can be characterized up to isomorphism by saying that it is a complete ordered field. (This fact should be included in any analysis course.) But completeness (i.e., that nonempty bounded sets have least upper bounds) is not a first-order property. See Example 4 in Section 4.1 for its second-order statement. The first-order “image” of completeness is given by the schema obtained from that second-order statement by replacing by a first-order formula . The resulting schema (i.e., the set of sentences you get by letting vary and taking universal closure) says that the least-upper-bound property holds for the sets that are definable from points. Ordered fields satisfying those sentences are called “real-closed ordered fields.”
The surprising fact is that such fields were not invented by logicians. They were previously studied by algebraists and you can read about them in van der Waerden’s Modern Algebra book (volume I). Of course, he uses a characterization of them that does not involve logic.
What Tarski showed is that any real-closed ordered field is elementarily equivalent to the field of real numbers. From this it follows that the theory of the real-closed ordered fields is decidable.
(a) Compared to Exercise 12, the difference here is that we don’t need to specify points via equations, we have constants. Moreover, for simplicity we are given predicate symbol here. The union of intervals such that defines , can be defined as . An interval can be defined as . For other intervals (open, closed and the other half-open) we may add points ( ) and remove them ( ). For infinite intervals we skip the corresponding boundary condition.
(b) As noted in the digression, the problem here is that we cannot express the notion of “for every subset of ” in the first-order logic. Instead, we have to restrict our attention to those subsets that are definable by formulas. This is somewhat similar to Exercise 12, where we had to define endpoints of intervals via equations rather than any arbitrary points.
Here, however, we have expanded the structure to include all sets definable from points, i.e. using any constants. The idea seems to be that, since we are to show a property that holds for any definable from points set, we can get rid of specific constants by substituting them with some variables and using universal quantifiers on these variables. That is, we are going to show the property not for a particular subset, but for all subsets defined by the same formula but with different constants.
So, suppose is a non-empty, bounded and definable from points in subset of . Let be a formula that defines it having the only free variable . Now, is a finite string of symbols, so, suppose, it has constant symbols . Let be the formula obtained from by substituting for , . Note, that has free variables . We will also use the notation to denote each set defined by when variables are assigned some values and emphasize the fact that can define each such set in when we assign particular constants to each . Later, in the language of , we will bind each by a corresponding universal quantifier, so, in essence, we will consider all subsets defined by with different constant values at once. To simplify things, let us also denote by the formula obtained from the formula by substituting variable for variable . The table below lists different formulas with explanation.
|is an upper bound of|
|is less or equal to any upper bound of|
Using these formulas the following formula describes the existence of a least upper bound of when the set is non-empty and bounded:
This formula has free variables . Therefore, the following formula is a sentence that states that there exists a least upper bound of any subset of definable from points in by formulas obtained from by substituting different constants. This sentence does not use any constant symbols, and, therefore, is a sentence in the language of , and if we show that is a model of , then will be true under any , in particular, we will show that which states that has a least upper bound. Now, since is a formula in the language of , it is also a formula in the language of . Moreover, in it states that some particular non-empty and bounded subsets of have a least upper bound, which is true for any such subsets of . Therefore, is a model of , and, hence, is a model of as well.