Show that an elementary equivalent structure of $\mathbb{R}$ and definable from points is Dedekind complete

Question

On page 103, A Mathematical Introduction to Logic, Herbert B. Enderton（2ed),

Assume that $\mathfrak {A} \equiv \mathfrak R$ ($\mathfrak {R} = (\mathbb{R},<,+,\cdot)$). Show that any subset of $\mathfrak {|A|}$ that is nonempty, bounded (in the ordering$<^\mathfrak{A}$), and definable from points in $\mathfrak{A}$ has a least upper bound in $\mathfrak{|A|}$.

Definitions of elementary equivalence and definable from points:

Two structures $\mathfrak{A}$ and $\mathfrak{B}$ for the language are said to be elementarily equivalent (written $\mathfrak{A} ≡ \mathfrak{B}$) iff for any sentence $σ$, $\vDash_\mathfrak{A} σ ⇔ \vDash_\mathfrak{B} σ$.

Consider a fixed structure $\mathfrak{A}$. Expand the language by adding a new constant symbol $c_a$ for each $a \in \mathfrak{|A|}$. Let $\mathfrak{A}^{+}$ be the structure for this expanded language that agrees with $\mathfrak{A}$ on the original parameters and that assigns to $c_a$ the point $a$. A relation $R$ on $\mathfrak{|A|}$ is said to be definable from points in $\mathfrak{A}$ iff $R$ is definable in $\mathfrak{A}^{+}$.

Here's how far I understand this problem. First, we need a full characterization of subsets of $\mathfrak{R}$definable from points. My question is that is it the case that a subset of $\mathfrak{R}$, iff it's the union of finitely many intervals?

The second question is how to to carry over the above characterization into $\mathfrak{A}$?

It's quite confusing, since the property we want to prove is a second-order statement, but all we can utilize are first-order sentences implied by elementary equivalence.

Answer 1

Apostolos' answer is certainly the most efficient way to answer this problem, but I wanted to point out that there's a little more going on here.

You ask "is it the case that a subset of $\mathfrak{R}$ is definable iff it's the union of finitely many intervals?"

The answer is yes. (To be clear, by an interval we mean something of the form $\langle a, b\rangle$, where $\langle$ is $($ or $[$, $\rangle$ is $]$ or $)$, and $a,b\in \mathbb{R}\cup\{\pm\infty\}$. A singleton $\{a\}$ is the interval $[a,a]$.) Here's how to see this:

1. Show that Th$(\mathbb{R},<,+,\cdot,0,1)$ has quantifier elimination. This is well known (Tarski's theorem) and not terribly hard.
2. Check that every quantifier free formula with parameters relative to Th$(\mathbb{R},<,+,\cdot,0,1)$ defines a finite union of intervals in $\mathbb{R}$. This is easy, since every atomic formula is equivalent to $p(x) = 0$ or $p(x) < 0$ for some polynomial $p$ with real coefficients.

In fact, this argument works for any structure which is elementarily equivalent to $\mathbb{R}$. You need the intermediate value theorem for polynomials to see that $p(x) < 0$ defines a finite union of intervals, but that's okay because each instance of IVP is first-order expressible.

Now it's easy to see that in a structure all of whose definable subsets are finite unions of intervals, nonempty bounded subsets have least upper bounds: just take the greatest element appearing as a right endpoint of one of the intervals.

This observation about finite unions of intervals is actually at the heart of the field of o-minimality, which has been very active in the last 25 years.

A structure is called o-minimal if it is linearly ordered by $<$ and every definable subset (with parameters) is a finite union of intervals in the sense above. The theory of real closed fields (RCF = Th$(\mathbb{R},<,+,\cdot,0,1)$) is the canonical example. Other examples include DLO (the theory of dense linear orders without endpoints), ODAG (the theory of ordered divisible abelian groups), and various expansions of the real field - you can include the real exponential function, restricted analytic functions, and/or various other things without losing o-minimality.

Above, we saw that any structure elementarily equivalent to $\mathbb{R}$ is o-minimal. That is, the theory of $\mathbb{R}$ is o-minimal, which means that all of its models are o-minimal. It's a classic result that every o-minimal structure has an o-minimal complete theory. Unfortunately, the proof is rather complicated. It is contained in the paper Definable Sets in Ordered Structures II by Knight, Pillay, and Steinhorn.

A good reference for o-minimality is the book Tame Topology and o-minimal Structures by Lou van den Dries.

Answer 2

First of all we have that any bounded subset of $\mathbb{R}$ has a least upper bound, by the completeness of the real line.

Assume now that $\mathfrak{A}\equiv\mathfrak{R}$ and let $B\subset|\mathfrak{A}|$, that is non-empty, bounded and definable from points in $\mathfrak{A}$ and let $\phi(x,a_1,\ldots,a_n)$ be the formula that defines $B$, where $a_1,\ldots,a_n\in|\mathfrak{A}|$. First define the formulas: $$\psi(x_1,\ldots,x_n)\equiv(\exists x\phi(x,x_1,\ldots,x_n))\land((\exists y)(\forall x)(\phi(x,x_1,\ldots,x_n)\to (x\leq y))$$ and $$\sigma(x,x_1,\ldots,x_n)\equiv\forall y\forall z((\phi(z,x_1,\ldots,x_n)\to y\geq z)\to x\leq y)\land(\forall z((\phi(z,x_1,\ldots,x_n)\to x\geq z))$$

Observe that $$\mathfrak{A}\models\psi[a_1,\ldots,a_n].$$

Now notice that due to the completeness of the real line we have $$\mathfrak{R}\models\forall x_1,\ldots,x_n(\psi(x_1,\ldots,x_n)\to\exists x\sigma(x,x_1,\ldots,x_n)).$$ By the elementary equivalence of the $\mathfrak{A}$ and $\mathfrak{R}$ we have that $$\mathfrak{A}\models\forall x_1,\ldots,x_n(\psi(x_1,\ldots,x_n)\to\exists x\sigma(x,x_1,\ldots,x_n)).$$

This implies that $$\mathfrak{A}\models\psi[a_1,\ldots,a_n]\to\exists x\sigma[x,a_1,\ldots,a_n]$$ which yields that $$\mathfrak{A}\models\exists x\sigma[x,a_1,\ldots,a_n]$$ which is what we wanted.