Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
    
The spirit of your answer is correct, but your expression of "$x$ is a least upper bound for $\phi(A,a_1,\dots,a_n)$" (repeated four times in your answer) is incorrect. Instead, it expresses that "$x$ is less than every strict upper bound for $\phi(A,a_1,\dots,a_n)$". What you really want to say is $\exists x (\forall z \phi(z,a_1,\dots,a_n) \rightarrow z \leq x) \land (\forall y (\forall z \phi(z,a_1,\dots,a_n) \rightarrow z \leq y) \rightarrow x \leq y)$ –  Alex Kruckman Jan 26 '13 at 0:06
    
@AlexKruckman: Indeed; thanks for noticing. –  Apostolos Jan 26 '13 at 1:15
add comment

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.

share|improve this answer
    
Do you mean about the IVP thing that we add a schema for every formula $\varphi(x,y,\vec p)$ and for every $\vec p$, if $\varphi(x,y,\vec p)$ defines a continuous function then between every two points of a different sign there is a root (or every point in the proper range was realized by a point in between those two points)? –  Asaf Karagila Jan 26 '13 at 22:53
    
I mean that the theory of $\mathbb{R}$ as an ordered field contains the following schema, one sentence for each natural number, corresponding to the degree of $p$: $\forall (\text{coefficients of $p$}) \forall x, y (p(x) < 0 \land p(y) > 0) \rightarrow \exists z (x<z<y \lor y<z<x) \land p(z) = 0$. It's interesting to note that adding this schema to the ordered field axioms already gives a complete theory - it's one axiomatization of the theory of real closed fields. –  Alex Kruckman Jan 27 '13 at 5:28
    
Oh that is far more elegant than what I wrote. :-) –  Asaf Karagila Jan 27 '13 at 9:14
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.