# Given real numbers: define integers?

I have only a basic understanding of mathematics, and I was wondering and could not find a satisfying answer to the following:

Integer numbers are just special cases (a subset) of real numbers. Imagine a world where you know only real numbers. How are integers defined using mathematical operations?

Knowing only the set of complex numbers $a + bi$, I could define real numbers as complex numbers where $b = 0$. Knowing only the set of real numbers, I would have no idea how to define the set of integer numbers.

While searching for an answer, most definitions of integer numbers talk about real numbers that don't have a fractional part in their notation. Although correct, this talks about notation, assumes that we know about integers already (the part left of the decimal separator), and it does not use any mathematical operations for the definition. Do we even know what integer numbers are, mathematically speaking?

-
Mmh, I dont think this question is well-phrased. You say "Although correct, this talks about notation, assumes that we know about integers already" and what is about $a+bi$? same thing. a and b are real numbers, therefore this assumes that we already know the real numbers. Check out the gauss function however, there is a sum formula for it aswell –  CBenni Dec 21 '12 at 15:13
Are you familiar with equivalence classes, peano axioms, and so on? –  007resu Dec 21 '12 at 15:15
I think the gist of the idea is correct, that the "language" and logic of real numbers do not allow us to distinguish the special subset of integers. –  hardmath Dec 21 '12 at 15:15
What do you know (or what can we assume to know) about the real numbers? If you know that the real numbers form a field, you know it has the unique multiplicative identity, which allows you to define the ring of integers. (Essentially Asaf's answer.) Your question is not very well posed until you say what the real numbers are! –  Willie Wong Dec 21 '12 at 17:01
Actually, if you only know the complex numbers and the four basic arithmetic operations, you can't define the real numbers. Your method of picking out the real numbers depends crucially on also knowing how to represent a complex number through its real and imaginary parts. Complex conjugation is enough additional information to pick out the real numbers, though. –  Hurkyl Dec 22 '12 at 13:41

There are several ways to interpret this question.

The naive way would be simply to give some sort of definition to the set of integers. This is not very difficult, we can recognize $1$ in the real numbers, because it is the unique number $x$ such that $r\cdot x=r$ for all $r\in\mathbb R$.

Now consider the set obtained by repeatedly adding $1$ to itself, or subtracting $1$ from itself. Namely $\{0,1,-1,1+1,-1-1,1+1+1,-1-1-1,\ldots\}$. One can show that this set is indeed the integers. Every integer is a finite summation of $1$ or the additive inverse of such set.

One could also define, like Nameless did, what is being an inductive set, then define $\mathbb N$ as the least inductive set, and $\mathbb Z$ as the least set containing $\mathbb N$ and closed under addition and subtraction.

However one could also interpret this question by asking "Is the set $\mathbb Z$ first-order definable in $\mathbb R$ in the language of ordered fields?", namely if you live inside the real numbers, is there some formula in the language $0,1,+,\cdot,<$ such that only integers satisfy it?

The answer to this question is negative. The integers are not first-order definable in $\mathbb R$. This is a nontrivial result in model theory. But it is important to note it, because it is a perfectly valid interpretation of the question, and it results in a completely different answer than the above one.

In particular it helps understanding first-order definability vs. second-order definability, and internal- vs. external-definability.

I am adding some more to the answer because of a recent comment by the OP to the original question. I feel that some clarification is needed to my answer here.

First we need to understand what does "define" mean from a logic-oriented point of view. It means that there is a language such that the real numbers interpret the language in a coherent way, and there is a formula in one free variable which is true if and only if we plug an integer into it.

For example we cannot define $\mathbb R$ within $\mathbb C$ if we only have $0,1,+,\times$, but we can do that if we also have the conjugation map in our vocabulary - as shown in the question.

Naively speaking, when we approach to mathematics we may think that everything is available to us, which is true to some extent. But when we want to talk about logic, and in particular first-order logic, then we need to first understand that only things within a particular language are available to us and we cannot expect people to guess what this language is if we don't specify that.

This question did not specify the language, which makes it not unreasonable to think that we are talking about the real numbers in the language of ordered fields. So in our language we only have $0,1,+,\times,<$ (and equality, we always have equality). In this language we cannot define the integers within the real numbers with a first-order formula.

Ah, but what is a first-order formula? Well, generally in a formula we can have variables which are objects of our structure (in this case, real numbers) and we can have sets of real numbers and we can have sets of sets of real numbers and so on. First-order formulas allow us only to quantify over objects, that is real numbers. So variables in first-order logic are elements of the universe, which in our case means simply real numbers. Second-order logic would allow us to quantify over sets (of real numbers) as well, but not sets of sets of real numbers, and so on.

So for example, we can write a definition for $2$ using a first-order formula, e.g. $x=1+1$. There is a unique element which satisfies this property and this is $2$. And we can write the definition of an inductive set using a second-order formula, $0\in A\land\forall x(x\in A\rightarrow x+1\in A)$.

But as it turns out we cannot express the property of being an inductive set (and we certainly cannot express the property of being the minimal inductive set) in first-order logic when we restrict ourselves only to the real numbers as an ordered field. The proof, as I remarked, is not trivial.

The comment I referred to says:

@WillieWong I don't know the real number field: to me real numbers form a line. – Virtlink

Which gives yet another way to interpret this approach. We can consider the real numbers simply as an ordered set. We ignore the fact it is a field, and we simply look at the order.

But this language has even less expressive powers than that of an ordered field, for example we cannot even define the addition and multiplication. In fact we can't even define $0$ and $1$ in this language. We only have the order to work with, and that's really not much to work with.

It is much easier to show that simply as an ordered set all the results about undefinability hold, I won't get into this but I'll just point out that definability is "immune to automorphisms", and $\mathbb R$ has plenty of automorphisms which preserve the order and move every element.

Beyond that one runs into philosophy of mathematics pretty quick. What are the real numbers? Are they sets? Are they any structure which interpret a particular language in a particular way? Do we construct the integers from the real numbers or do we construct the real numbers from the integers? (First we have to construct the rational numbers, of course.)

Those are interesting questions, but essentially moot if one simply wishes to talk about first-order definability in a particular language or another. But if one is approaching this in a "naive" way which allows higher order quantification, and the usage of any function we know about then the answer becomes quite simple (although it is possible to run into circularity if one is not careful enough).

I hope this explains, amongst other things, why I began my answer with "There are several ways to interpret this question". We simply can see the real numbers as different structure in different languages, and we may or may not allow formulas to use sets of real numbers. In each of these interpretation of the question we may have a different answer, and different reasons for this answer to be true!

(I should stop writing this monograph now, if you're read this far - you're a braver [wo]man than I am!)

But wait, there's more!

-
Sorry if this is a naive question. But when we say that we will do that repeatedly, I assume that we are using a bottom up definition. We define $A_0=\{0\}$ and $A_{n+1}=\{1+a|a\in A_n\}$. Then we let $A=\cup_{n\in N} A_n$ be the set of natural numbers. Isnt this problematic because the union is done over all naturals that we are still trying to define ? –  Amr Dec 21 '12 at 15:34
@Amr: This is an external definition, which is fine. Because looking from the outside we do know what the integers are. –  Asaf Karagila Dec 21 '12 at 15:39
@Amr: But the definition of an inductive set is second-order or external. You can use that, but it would be the same thing really. The issue here is whether or not your metatheory is the theory of the real numbers. If it is then there is no chance for defining the integers, if your metatheory is ZFC (or so) then you can define the integers from outside the real numbers (again, external definition). –  Asaf Karagila Dec 21 '12 at 15:53
@Willie Wong: Anything that covers the basic model theory of fields. Marker's Introduction to Model Theory, for example. Here's a quick proof if you know some standard decidability results: If we could define the integers, we could define the naturals (as the sums of four squares). But the theory of the real field is decidable (Tarski) and so this would let us decide the theory of the naturals, contra Godel. –  Chris Eagle Dec 21 '12 at 17:07
@WillieWong: math.stackexchange.com/questions/253946/… for more. –  Chris Eagle Dec 21 '12 at 17:09

The main problem is to define the natural numbers $0,1,2,...$. Let's think about what makes $$\mathbb{N}=\left\{0,1,2,...\right\}$$ so special.

First of all, $0\in \mathbb{N}$. In addition, if $k\in \mathbb{N}$ then $k+1\in \mathbb{N}$. However, other sets like $$S=\left\{0,1,2,...\right\}\cup \left\{\frac12,\frac32,\frac52,...\right\}$$ have this property as well but $S\neq \mathbb{N}$. If you think about this, the characterising property of $\mathbb{N}$ is that, out of all sets that have the above property, $\mathbb{N}$ is the smallest of them. With that in mind we can construct the following definition:

A subset $A$ of $\mathbb{R}$ is said to be inductive if $0\in A \text{ and }(k\in A \implies k+1\in A)$

It can be proven that intersections of inductive sets are inductive.

Let the family of every inductive set in $\mathbb{R}$ be $(N_i)_{i\in I}$.The set of natural numbers is defined as: $$\mathbb{N}:=\bigcap\limits_{i\in I }N_i$$ or in other words, $\mathbb{N}$ is the smallest inductive set in $\mathbb{R}$

The set of integers can then be defined as:

$$\mathbb{Z}:=\mathbb{N}\cup \left\{-n:n\in \mathbb{N}\right\}$$

Using these definitions all of your familiar properties of integers can be proven!

Sidenotes:

1. From this definition, a fundumental property of $\mathbb{N}$ can easily be proven. Principle of Mathematical Induction: If $A\subseteq \mathbb{N}$ is inductive then $A=\mathbb{N}$.
2. You may want to think how we can define rational and especially irrational numbers...
-
I don't see how $\mathbb{N}$ is the smallest set with the characterizing inductive property. S has as the same cardinality as $\mathbb{N}$, as the bijection B, B(x)=(x/2) if x is even or x=0, B(x)=(x-1)/2 if x is odd makes clear. I don't see any smaller sets than $\mathbb{N}$, but there exist at least a countable infinity of sets with the same cardinality, and at least a countable infinity of sets like S. –  Doug Spoonwood Dec 22 '12 at 11:27
@DougSpoonwood By smallest I mean it is included in any other inductive set –  Nameless Dec 22 '12 at 11:29

It looks like you want to understand what distinguishes the integers from the other real numbers.

If you're allowed to use the operations of addition and multiplication, then you should be able to see that $0$ and $1$ have very special properties that no other real numbers have: $0+x=x$ and $1x=x$ for every real number $x$.

Having "found" $0$ and $1$, you can proceed like Nameless to "find" the other integers: repeatedly adding $1$ to itself produces the positive integers, and solving the problem $x+n=0$ for each fixed positive integer $n$ gives the negative integers.

-

You could define the integers as the solutions $x$ to the equation $$\sin(\pi x) = 0,$$ for instance. Of course, this assumes you "know" the $\sin$ function without defining it using its series.

-

To give one more approach, if your theory allows you to talk about functions from $\mathbb{R} \to \mathbb{R}$, then define $\sin(x)$ as the function $f(x)$ which obeys $f''(x) = -f(x)$, $f(0)=0$ and $f'(0)=1$. (The $(\delta, \epsilon)$ definition of derivative, written out explicitly, is just a list of inequalities and logical quantifiers applied to function compositions. So, if you can talk about functions, and if you have any reasonable tools for talking about $\mathbb{R}$, you can talk about derivatives.)

As mentioned above, then $\pi$ is the smallest positive number $x$ with $\sin(x)=0$, and the integers are $\{ x/\pi : \sin(x)=0 \}$.

As Asaf says, you can't do this purely with first order tools. You need something like sets, or functions, or infinite sums ... all of which are second order tools.

-
once you choose the number 1 (to specify $f'(0) = 1$) don't you already fix the integers? –  Willie Wong Dec 21 '12 at 16:58
Normally, I would assume that a language for talking about $\mathbb{R}$ contains, at a minimum, symbols for $0$, $1$, $+$, $\times$, $=$, $<$, the logical connectives and logical quantifiers. But, if you insist, if you insist, $1$ is the unique number which satisfies $x \times x = x$ and $x+x \neq x$. –  David Speyer Dec 21 '12 at 17:01
As Asaf discusses, given the symbols I describe above, you can say "$x=1$". You can say "$x=1$ OR $x=1+1$". You can say "$x=1$ OR $x=1+1$ OR $x=1+1+1$". And so forth. But you can't say "$x$ is an integer". –  David Speyer Dec 21 '12 at 17:03
But given the symbols you described above, how do you define "the function that verifies an ODE"? (In particular, I remain unconvinced you can demonstrate existence and uniqueness of ODEs if you cannot define the integers.) –  Willie Wong Dec 21 '12 at 17:04
You can't. That list of symbols is first order logic for $\mathbb{R}$, and is the minimum I want in order to be able to talk about $\mathbb{R}$. And first order logic over $\mathbb{R}$ can't define integers. What I am pointing out is that adding symbols for functions (and function evaluation) to $\mathbb{R}$ let's you get the integers. This is different from the other answers, which use symbols for sets or some sort of infinite sum/algorithm. –  David Speyer Dec 21 '12 at 17:07

A simplistic concept: Given $0$, integers are numbers that can be obtained using the number $1$ any number of times, restricted to operators $+$ or $-$.

Some examples:

1. $19 = \underbrace{0}_{original} + 1 + 1 + 1 + 1 + 1 + 1 + 1+ 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1+ 1$

2. $-7 = \underbrace{0}_{original} - 1 -1-1 -1 -1 -1 -1$

-

How about the values (Image) of $$\lfloor x\rfloor:=x-\frac{1}{2}+\frac{1}{\pi}\sum_{k=1}^\infty\frac{\sin(2\pi k x)}{k}$$

But this is nonsense; we sum over the positive integers, and such, we can just define the integers as $$x_0:=0\\x_{k+1}=x_k+1\\ x_{-k}=-x_k$$

-
what is the index set of the summation? –  robjohn Dec 21 '12 at 17:46
@robjohn guess what I say afterwards. –  CBenni Dec 21 '12 at 20:03

This may be a bit of a cheat, but a real number n is an integer if and only if $n\equiv 0\ (mod\ 1)$, or equivalently, $n\mod 1 = 0$.

It's a cheat because modulo division is defined in terms of integers, and so the modular equivalence statement above is only ever seen with integer values AFAIK. You would therefore have to define integers some other way in order to define modulo. A world in which we did not differentiate between integers and all other reals may well not have modulo division as a possible mathematical operation.

-
without integers, how do you define $\bmod$? –  robjohn Dec 21 '12 at 17:46
... which is why I said it was probably cheating. –  KeithS Dec 21 '12 at 18:31
Looking at $\mathbb{R}$ as an $\mathbb{R}$-module, you may say $<1>$ is the cyclic group generated by $1$ and $\mathbb{R}/<1>$ is the quotient module of "real numbers modulo 1". But in doing this, the integers are present because $\mathbb{Z} = <1> \subset \mathbb{R}$. –  andybenji Dec 21 '12 at 19:00
$9.99999999999\ldots$ is an integer –  Henry Dec 22 '12 at 10:15