TransWikia.com

What is the intersection of inductive definable subsets of a real closed field?

Mathematics Asked on November 24, 2021

Let $X$ be a real closed field. Let us call a subset of $X$ definable if it is definable using a first-order formula in the language of ordered fields without parameters from $X$. And let us call a subset of $X$ inductive if it contains $0$ and if it contains $x$, then it contains $x+1$. And let $M$ be the intersection of all definable inductive subsets of $X$.

Then my question is, what are the properties of $M$, as a model for the language for first-order arithmetic? I don’t think $M$ is necessarily isomorphic to $mathbb{N}$, but clearly it satisfies the axioms of Robinson arithmetic at least. But how strong a form of induction must it satisfy?

2 Answers

If $varphi(x)$ is a formula and $M$ is a model, I will write $varphi(M)$ for the subset of $M$ defined by $varphi(x)$.

In any real closed field $R$, a formula with one free variable (even with parameters from $R$) defines a finite union of points of $R$ and intervals with endpoints in $R$ or $pm infty$ (this is called o-minimality). If $varphi(x)$ is such a formula without parameters, then we can interpret this formula in $mathbb{Q}^r$, the field of real algebraic numbers (this is the real closure of $mathbb{Q}$, and the prime model of the theory of real closed fields). Since $R$ is an elementary extension of $mathbb{Q}^r$, it follows that $varphi(R)$ is a finite union of points in $mathbb{Q}^r$ and intervals with endpoints in $mathbb{Q}^r$ or $pm infty$.

[For example, if $varphi(mathbb{Q}^r) = {0}cup (sqrt{2},infty)$, then $mathbb{Q}^rmodels forall x(varphi(x) leftrightarrow (x = 0lor sqrt{2}<x))$, so also $Rmodels forall x(varphi(x) leftrightarrow (x = 0lor sqrt{2}<x))$, and hence $varphi(R) = {0}cup (sqrt{2},infty)$.]

Now if $varphi(R)$ is inductive, then $varphi(mathbb{Q}^r)$ is unbounded above in $mathbb{Q}^r$. Thus there is a real algebraic number $a$ such that $varphi(mathbb{Q}^r)$ contains $(a,infty)$, and hence $varphi(R)$ also contains $(a,infty)$. In particular, $varphi(R)$ contains $mathbb{N}cup {xin Rmid x > mathbb{N}}$.

It remains to show that the intersection of all inductive definable sets (without parameters) in $R$ is exactly $mathbb{N}cup {xin Rmid x > mathbb{N}}$. This is just as in nombre's answer: For each natural number $n$, the set $S_n = {0,1,dots,n}cup (n,infty)$ is definable, and $bigcap_{nin mathbb{N}} S_n = mathbb{N}cup {xin Rmid x > mathbb{N}}$.

Note that if $R$ is Archimedean, then $mathbb{N}cup {xin Rmid x > mathbb{N}} = mathbb{N}$. But if $R$ is non-Archimedean, this set is much larger, and it doesn't look much like a model of arithemetic. In particular, the infinite elements are densely ordered. (Though my earlier comment was wrong: it seems it does satisfy the axioms of Robinson artithmetic. I forgot how weak the axioms of Q are.)


Regarding induction: If $R$ is Archimedean, then $M = mathbb{N}$ so of course it satisfies full (second-order) induction.

If $R$ is non-Archimedean, then $M$ fails induction already for the formula $psi(x)$ which says "$x$ is odd or $x+1$ is odd": $$forall y,forall z, (y+y neq x) lor (z+zneq x+1).$$

This formula is false for all infinite elements of $M$, but it is true for all finite elements, so it defines $mathbb{N}$ in $M$. Really, you should think of $M$ as looking like a definable copy of $mathbb{N}$ with a bunch of extraneous densely-ordered junk on top. If you're trying to find a reasonable model of arithmetic inside a real closed field, I think nombre's comment above about integer parts is much more relevant than this construction.


Quantifier-free induction: In the comments, you asked whether $M$ satisfies induction for quantifier-free formulas. The answer is yes, but this is a bit silly, since quantifier-free formulas just define finite unions of points and intervals.

Suppose $varphi(x)$ is a quantifier-free formula. Let's allow $varphi$ to have parameters and include the symbol $leq$. Since $varphi$ is quantifier-free, $varphi(M) = varphi(R)cap M$. Suppose $varphi(M)$ is inductive. Then it contains $mathbb{N}$, so we can focus on the infinite elements of $varphi(M)$, which are exactly the infinite elements of $varphi(R)$. Suppose for contradiction that $varphi(M)neq M$. Since $varphi(R)$ is a finite union of points and intervals with endpoints in $R$ or $pm infty$, and $varphi(R)$ is unbounded in $mathbb{N}$, there is some infinite $ain R$ such that $(-infty,a)cap {xin Rmid x > mathbb{N}}$ is contained in $varphi(R)$, but there exists $varepsilon$ such that $0<varepsilon < 1$, and $a+varepsilonnotin varphi(R)$. Then $a+varepsilon - 1in varphi(R)$, contradicting inductiveness.

Answered by Alex Kruckman on November 24, 2021

The intersection is actually isomorphic to $mathbb{N}$.

Indeed, for $x > mathbb{N}$ in $X$ and $n in mathbb{N}$, consider the set $S_{x,n}:={0,1,..,n-1} cup [n,x)$. This set is semialgebraic and inductive. The intersection of all $S_{x,n}$ is $mathbb{N}$, so your intersection is $mathbb{N}$.

As a general rule, it is not so easy to find non-standard models of large segments of $Th(mathbb{N})$ in a given ordered field, especially in a canonical way.

Answered by nombre on November 24, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP