1
$\begingroup$

The language of the first-order theory of real closed fields consists of the non-logical symbols $0$, $1$, $+$, $\cdot$, $<$, and $=$. My question is, for what subsets $X$ of $\mathbb{R}$ does there exist a formula $\phi(x)$ in the language of real closed fields such that $X=\{x\in\mathbb{R}:\phi(x)\}$?

I’ve heard people say that the semi-algebraic sets, i.e. finite unions of singletons and intervals, are what’s definable in the language of real closed fields. But I think they mean something slightly different than what I’m asking about. Because there are uncountably many singletons and intervals, but only countably many formulas.

$\endgroup$
  • $\begingroup$ I mean, you can't define infinite fields on the reals at all, since they require infinite formulas. $\endgroup$ – Don Thousand Oct 18 '19 at 7:02
  • $\begingroup$ What do you mean by define infinite fields? I’m just asking what subsets of the set of real numbers are first-order definable. $\endgroup$ – Keshav Srinivasan Oct 18 '19 at 7:02
  • 2
    $\begingroup$ I suppose it was meant that the singletons and interval endpoint all need to be algebraic numbers $\endgroup$ – Hagen von Eitzen Oct 18 '19 at 7:12
  • $\begingroup$ @HagenvonEitzen At least that’s not part of the definition of semialgebraic set: en.wikipedia.org/wiki/Semialgebraic_set But yeah, it does seem plausible that the answer to my question would be semialgebraic sets with algebraic endpoints. $\endgroup$ – Keshav Srinivasan Oct 18 '19 at 7:15
  • $\begingroup$ @KeshavSrinivasan In other words, we talk about semialgebraic sets defined over the subring $\Bbb Z$ (or equivalently, over $\Bbb Q$). $\endgroup$ – Hagen von Eitzen Oct 18 '19 at 7:21
1
$\begingroup$

Your observation is correct: With countably many formulas without parameters, only countably many subsets can be defined.

The definable subsets of $\mathbb{R}$ in the language $\mathcal{L}_{\mathrm{or}}:=\{0, 1, +, \cdot, <\}$ of ordered rings are unions of intervals (degenerated or otherwise) with algebraic endpoints, exactly as commented above by Hagen von Eitzen. A reference for this fact is Marker's Model Theory, An Introduction, Sect. 3.3.

There, it is proved that real closed fields have quantifier elimination in $\mathcal{L}_{\mathrm{or}}$, and the result follows from this.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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