15
$\begingroup$

It is a well-known fact that $\mathbb{Z}$ is not definable in the structure $\mathcal{R}=(\mathbb{R}, +, ., < , 0, 1)$. This follows from Tarski's quantifier elimination, and in fact, we can conclude that the structure $\mathcal{R}$ is an o-minimal structure.

Another proof, suggested in the answer by Mikhail Katz, is to use the Godel's incompleteness theorem and the fact that the theory of the structure is complete.

Question. Is there a more direct proof of the above undefinability result?

I essentially mean a proof which does not use the above results of Tarski or Godel or its variants.

In general, what other different proofs of the above result exist? Providing references is appreciated.

In the paper A dichotomy for expansions of the real field a criteria is given for the undefinability of $\mathbb{Z}$ in expansions of the real field. A natural question is if we can use this criteria and prove the theorem directly?

Improve this question
$\endgroup$
8
  • $\begingroup$ I am mainly interested in an argument like this: suppose $\mathbb{Z}$ is definable in the structure $\mathcal{R}$, by some formula and then work with the structure and the formula to get a contradiction. $\endgroup$
    – Mohammad Golshani
    Commented Apr 24, 2017 at 12:05
  • $\begingroup$ You wrote subtraction $-$, but did you mean multiplication? $\endgroup$
    – Joel David Hamkins
    Commented Apr 24, 2017 at 13:11
  • $\begingroup$ In particular, without multiplication, I think things would be considerably easier. $\endgroup$
    – Joel David Hamkins
    Commented Apr 24, 2017 at 13:23
  • 3
    $\begingroup$ @MohammadGolshani How can you hope to work with the structure of some formula without eliminating quantifiers from that formula and thus proving quantifier elimination? $\endgroup$
    – Will Sawin
    Commented Apr 24, 2017 at 17:21
  • 3
    $\begingroup$ @NateEldredge The statement that if it were definable, it could be written as a finite union of solution sets of systems of polynomial inequalities, is correct, but nontrivial. Indeed, this is exactly the Tarski’s theorem on quantifier elimination mentioned in the question. $\endgroup$
    – Emil Jeřábek
    Commented Apr 24, 2017 at 18:28

3 Answers 3

Reset to default
7
$\begingroup$

This is not a real answer but rather an observation. The undefinability of $\mathbb{Z}$ follows from the fact that every infinite definable set in such a structure has uncountable cardinality. This property is strictly weaker than both o-minimality and quantifier elimination. Nevertheless, I do not know any proof of this fact that does not use neither of those. I guess this simply induces a nice sub-question of the original one.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Or: from the similarly weak fact about Th(R) that $\forall x \exists y>x \,\phi(y) \rightarrow \exists x \forall y>x \,\phi(y)$ for any potential definition $\phi$. This might be easier to prove than quantifier elimination, without all the technicalities of Sturm's lemma, just focusing on the easy algebraic geometry near infinity. $\endgroup$
    – user44143
    Commented Apr 24, 2017 at 20:34
  • 1
    $\begingroup$ @MattF, it would be nice to have some parentheses in the formula you presented. Without them this is a bit tricky to read. $\endgroup$
    – Mikhail Katz
    Commented Apr 25, 2017 at 7:18
  • 2
    $\begingroup$ @MattF. True, indeed this is some sort of "o-minimality near infinity": every cofinal definable set contains an interval of the form $(a,+\infty)$ for some $a\in \mathbb{R}$. This property implies of course that cofinal definable sets are uncountable, but also states the stronger condition of containing an interval. I guess the we can weaken then the property that implies the undefinability of $\mathbb{Z}$ to be just ''cofinal definable sets are uncountable''. $\endgroup$
    – Cubikova
    Commented Apr 25, 2017 at 8:32
  • $\begingroup$ $(\forall x\, \exists y>x\, \phi(y))\rightarrow (\exists x\,\forall y>x\, \phi(y))$ $\endgroup$
    – user44143
    Commented Aug 16, 2019 at 18:01
6
$\begingroup$

The theory of real closed fields is complete and if the integers were definable in $\mathbb R$ this would contradict Goedel's incompleteness result.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks, are there proofs avoiding Godel's incompleteness theorem too. When writing the question, I had the idea of some different proof (maybe not using Godel's theorem). $\endgroup$
    – Mohammad Golshani
    Commented Apr 24, 2017 at 11:53
  • 1
    $\begingroup$ I am not a specialist, but "naively", if you have a "real closed field" $K$, cannot you define $\mathbb{Z}$ as the ring generated by $1_K$ ? $\endgroup$
    – Duchamp Gérard H. E.
    Commented Apr 24, 2017 at 11:56
  • 2
    $\begingroup$ It is not definable in that structure. Note that by definability, I mean first order definable in the structure $\endgroup$
    – Mohammad Golshani
    Commented Apr 24, 2017 at 11:56
  • 7
    $\begingroup$ Said another way: "ring generated by" is a second-order concept. It cannot be stated in the first-order language of $(\mathbb{R}, +, -, < , 0, 1)$. $\endgroup$
    – Gerald Edgar
    Commented Apr 24, 2017 at 12:29
3
$\begingroup$

This is very similar to the answer of Mikhail Katz, but we can avoid the incompleteness theorem by using the halting problem instead.

That is, since the theory of real-closed fields is computably axiomatizable and complete, it is decidable. So if $\mathbb{Z}$ were definable in $\langle\mathbb{R},+,\cdot,0,1,<\rangle$, then arithmetic truth would be decidable, contradicting the undecidability of the halting problem.

This argument still relies, however, on Tarski's quantifier-elimination.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I think you mean "recursively axiomatizable" not "finitely axiomatizable". $\endgroup$
    – Philip Ehrlich
    Commented Apr 24, 2017 at 13:29

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