14
$\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?

$\endgroup$
  • $\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 Apr 24 '17 at 12:05
  • $\begingroup$ You wrote subtraction $-$, but did you mean multiplication? $\endgroup$ – Joel David Hamkins Apr 24 '17 at 13:11
  • $\begingroup$ In particular, without multiplication, I think things would be considerably easier. $\endgroup$ – Joel David Hamkins Apr 24 '17 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 Apr 24 '17 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 supports Monica Apr 24 '17 at 18:28
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.

$\endgroup$
  • $\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 Apr 24 '17 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. Apr 24 '17 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 Apr 24 '17 at 11:56
  • 6
    $\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 Apr 24 '17 at 12:29
5
$\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.

$\endgroup$
  • 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$ – Matt F. Apr 24 '17 at 20:34
  • $\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 Apr 25 '17 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 Apr 25 '17 at 8:32
  • $\begingroup$ $(\forall x\, \exists y>x\, \phi(y))\rightarrow (\exists x\,\forall y>x\, \phi(y))$ $\endgroup$ – Matt F. Aug 16 at 18:01
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.

$\endgroup$
  • $\begingroup$ I think you mean "recursively axiomatizable" not "finitely axiomatizable". $\endgroup$ – Philip Ehrlich Apr 24 '17 at 13:29

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.