8
$\begingroup$

This question arose today at Yevgeny Gordon's talk, "Will nonstandard analysis be the analysis of the future?" at the CUNY Logic Workshop. Here is my way of asking it.

Consider the ordered real field $\newcommand\R{\mathbb{R}}\R$ with a predicate for the natural numbers, and a nonstandard version of it $\R^*$, the hyper-reals, which an ordered field extending $\R$ and having the transfer property, a map $a\mapsto a^*$, which preserves the truth of any statement in the language of ordered fields, allowing also the predicate for the natural numbers. The hyper-real numbers of the form $a^*$ are referred to as the standard elements of $\R^*$.

Question. Suppose that a hyper-real number $a\in\R^*$ is definable in $\R^*$ by a formula $\varphi$ in the language of ordered fields with a predicate for natural numbers, but where the scope of the quantifiers is only over the standard elements. Must $a$ be algebraic?

It is easy to see that every algebraic hyper-real number is definable in this way. For example, the hyper-real $\sqrt{2}$ is definable in $\R^*$ as the unique $x$ for which $x^2=2$ and $0<x$. Similarly, any algebraic hyper-real (algebraic over the standard integers) is the unique solution in $\R^*$ in a certain standard rational interval of a polynomial equation over the standard integers. So in fact, every algebraic hyper-real is quantifier-free definable in $\R^*$, even without the predicate for the natural numbers. So the question is equivalent to asking:

Question. If a hyper-real is definable by a formula whose quantifiers have scope restricted to the standard reals (allowing a predicate for the natural numbers), then is it quantifier-free definable?

Meanwhile, if you think about numbers like $e$ and $\pi$, it is not clear how to define them in $\R^*$ without quantifying over all the (possibly nonstandard) natural numbers. For example, $e$ is the limit of $(1+\frac 1n)^n$, and so $e^*$ is the unique $x$ in $\R^*$ such that $$\forall \epsilon>0\ \exists N\ \forall n\geq N \ |(1+\frac 1n)^n-x|<\epsilon.$$ This definition can be undertaken in $\R$, using the predicate for $\mathbb{N}$, which allows one to define exponentiation and so on. But in $\R^*$, these quantifiers are not only over the standard numbers; we have to quantify also over the nonstandard numbers. If you restrict to standard $\epsilon$ and standard $N$ and $n$ only, then there will be an entire interval of hyper-reals that are that close to those numbers---anything infinitesimally close to $e$ will do. So the restricted-scope version of the definition will not succeed as a definition.

Similarly, it is not clear how to define $\pi$ or indeed any other transcendental hyper-real number while quantifying only over standard numbers.

I believe that Tarski's theorem on real-closed fields will prove the positive result for the special case of the question, where $\varphi$ does not use the predicate for the natural numbers (but still has the scope of all quantifiers restricted to the standard hyper-reals). My reason for this expectation is that I believe we can apply Tarski's elimination of quantifiers procedure to such a $\varphi$ and thereby prove that $\varphi(x)$ is equivalent to a quantifier-free assertion in the language of ordered fields. Then, using the fact the algebraic numbers form an elementary substructure of the reals, as ordered fields, it follows that the existence of a solution in $\R$ is equivalent to the existence of a solution in the algebraic numbers. And so the given number must be algebraic.

But I am a little fuzzy on the details of how the scope-restriction affects this argument, and so if you can affirm or refute it, I would be grateful.

$\endgroup$
  • 4
    $\begingroup$ What if you add $\exists y(x=y)$ to your definition of $e$? Wouldn't the restricted-scope version work now? $\endgroup$ – Ramiro de la Vega Feb 4 '17 at 6:44
  • $\begingroup$ So the language we are working in is $\{0,1,+,\cdot,\leq,{\bf N}^*,{\bf R}^{\textrm{st}}\}$, where ${\bf N}^*$ is a predicate for natural numbers and ${\bf R}^{\textrm{st}}$ is a predicate for standard reals? Which definition of hyperreals do you have in mind? $\endgroup$ – tomasz Feb 4 '17 at 11:16
  • $\begingroup$ @RamirodelaVega I think you may be right! $\endgroup$ – Joel David Hamkins Feb 4 '17 at 12:18
  • $\begingroup$ @tomasz Adding those predicates to the language is stronger than merely restricting the scope of all quantifiers to the standard reals, since in your language you can also quantify over the non-standard reals, if you want. As for which hyper-reals, take one that you like. I would be interested to know whether the answer depends on this. $\endgroup$ – Joel David Hamkins Feb 4 '17 at 12:20
  • $\begingroup$ @RamirodelaVega: I have not read your comment before. I see now that you're saying basically the same thing as I did in my answer. Sorry about that! $\endgroup$ – tomasz Feb 4 '17 at 12:27
7
$\begingroup$

$\newcommand{\st}{\textrm{st}}\newcommand{\bR}{{\bf R}}\newcommand{\bN}{{\bf N}}$ I think the limit of any definable convergent sequence $(a_n)$ (including $e$) is definable by the formula $$\varphi(x)=(\exists x'\in {\bR}^\st\, x'=x)\land \forall N\in\bN^\st\exists n_0\in \bN^\st\forall n\in \bN^\st_{>n_0}(a_n-x)^2<N^{-1}.$$

Since the language includes natural numbers, we have all of Peano arithmetic, so I think by a similar argument, every computable (and I guess every definable in PA) real should be definable. The point is that if you allow quantifiers which range over a given set, then you automatically make that very set definable, so you have at least as much strength as you would have in the smaller structure.

Edit: The idea was first mentioned by Ramiro de la Vega in comments, which I neglected to read before writing this answer.

$\endgroup$
  • $\begingroup$ Thank you! In the seminar, we had somehow overlooked the idea of just using $\exists x' (x=x')$. $\endgroup$ – Joel David Hamkins Feb 4 '17 at 12:31
  • $\begingroup$ Oh, I had thought at first that this answer had been posted by Ramiro, who had made the observation in a comment. Tomasz, could you edit your answer to say that Ramiro had mentioned the idea in the comments? $\endgroup$ – Joel David Hamkins Feb 4 '17 at 12:34
  • $\begingroup$ @JoelDavidHamkins: Sure, I've added a remark to that effect. $\endgroup$ – tomasz Feb 4 '17 at 12:44

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.