# 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.

Symbol | Formula | Free variables | Description |

is non-empty | |||

is an upper bound of | |||

is bounded | |||

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.