It cannot be formulated with the first-order theory of the real numbers with addition and multiplication. It is easily formulated within, say, the second-order theory of the real numbers (n is a whole number iff it’s in every subset S of R such that 0 is in S and, for every m in S, m+1 is in S), or within the first-order theory of the complex numbers if you allow not only addition and multplication but also exponentiation (n is an integer iff for every z such that e^z=1, e^nz is also 1).
I don’t even understand what you’re talking about when you speak of algorithms on real numbers. Computers can’t work with real numbers. Are you assuming some sort of hypercomputation, like a Blum-Shub-Smale computer? Or how are you restricitng your input? (Computable reals, via taking a Turing machine as input? Definable reals handled… somehow?)
(Of course, my answer to any of those questions is “I don’t know, this isn’t really my area, but you could probably look it up pretty easily”—but my point is that your question doesn’t seem to make sense as asked.)
In any case, we’re just talking about defining subsets here, not computing them. There’s a pretty big gap between being first-order-definable and being computable. And that “first condition” is the same as being a whole number so you could just ask that.
Your questions seem to be predicated on a number of confusions. I think you should really go back and read some standard stuff on this first.
EDIT a few minutes later: Of course, if you stick to first-order stuff, then reals are equivalent to definable reals, or to just computable reals—or to just algebraic reals, even—so perhaps your question could be formulated there? But it still seems ill-founded, i.e., I doubt it gets at what you actually want to know. You seem to be confused about the distinction between computation, first-order description, and description more generally.
It cannot be formulated with the first-order theory of the real numbers with addition and multiplication. It is easily formulated within, say, the second-order theory of the real numbers (n is a whole number iff it’s in every subset S of R such that 0 is in S and, for every m in S, m+1 is in S), or within the first-order theory of the complex numbers if you allow not only addition and multplication but also exponentiation (n is an integer iff for every z such that e^z=1, e^nz is also 1).
Thanks. Is there a terminating algorithm which tests the first condition for any given n?
I don’t even understand what you’re talking about when you speak of algorithms on real numbers. Computers can’t work with real numbers. Are you assuming some sort of hypercomputation, like a Blum-Shub-Smale computer? Or how are you restricitng your input? (Computable reals, via taking a Turing machine as input? Definable reals handled… somehow?)
(Of course, my answer to any of those questions is “I don’t know, this isn’t really my area, but you could probably look it up pretty easily”—but my point is that your question doesn’t seem to make sense as asked.)
In any case, we’re just talking about defining subsets here, not computing them. There’s a pretty big gap between being first-order-definable and being computable. And that “first condition” is the same as being a whole number so you could just ask that.
Your questions seem to be predicated on a number of confusions. I think you should really go back and read some standard stuff on this first.
EDIT a few minutes later: Of course, if you stick to first-order stuff, then reals are equivalent to definable reals, or to just computable reals—or to just algebraic reals, even—so perhaps your question could be formulated there? But it still seems ill-founded, i.e., I doubt it gets at what you actually want to know. You seem to be confused about the distinction between computation, first-order description, and description more generally.