# Can we prove that odd and even numbers alternate without using induction?

It is a simple exercise to prove using mathematical induction that if a natural number n > 1 is not divisible by 2, then n can be written as m + m + 1 for some natural number m. (Depending on your definition of odd number, this can either be stated as "every number is even or odd", or as "every odd number is one greater than an even number". My question is, can this be proven without induction? In other words, can this be proven in Robinson arithmetic? If not, what is example of a nonstandard model of Robinson arithmetic that doesn't have this property?

The reason I'm asking this is that the proof of the irrationality of the square root of 2 is usually presented with only one use of induction (or an equivalent technique). But the proof depends on the fact if k^2 is even, then k is even, and that fact in turn depends on the fact that the square of a number not divisible by 2 is a number not divisible by 2. And that fact is, as far as I can tell, is a result of the proposition above. (I'm open to correction on that point.) So if that proposition depended on induction, then the proof that sqrt(2) is irrational would depend on two applications of induction. (The reason that the ancient Greeks wouldn't have been aware of this is that Euclid implicitly assumes the proposition above, when he defines an odd number as "that which is not divisible into two equal parts, or that which differs by a unit from an even number".)

Any help would greatly appreciated.

• It's not true without induction. It's not even clear what "alternating" means without induction. – Thomas Andrews Sep 10 '13 at 2:33
• @ThomasAndrews I phrased it imprecisely in my question title, for brevity's sake, but I stated it precisely in the body of the question: every natural number other than 1 which is not even can be written as some even number + 1. What makes you think this statement is not provable without induction? – Keshav Srinivasan Sep 10 '13 at 2:40
• This was discussed in this question of mine: math.stackexchange.com/questions/476184/… – marty cohen Sep 10 '13 at 2:50
• @martycohen I don't see any discussion of whether it's provable without induction. – Keshav Srinivasan Sep 10 '13 at 2:56

Take $M = \{P = a_nx^n + \ldots + a_0 \in \Bbb Z[x] / a_n > 0 \}$, with the usual addition and multiplication on polynomials. Interprete $S(P)$ as $P(X)+1$.

Then $M$ is a model of Robinson arithmetic, but there are long strings of "not-even" numbers, such as $X,X+1,X+2,\ldots$. So in this model, it is false that if $n$ is not even then $n+1$ is even.

If you define "$n$ is odd" as "$\exists k / n= k+k+1$", then it is false that every number is even or odd.

However, it is still true in $M$ that addition is associative and commutative, and so if $n$ is odd then $n+1$ is even, and if $n$ is even, then $n+1$ is odd. (you will need a stranger model for this to fail)

If you want a model in which $a^2-2b^2 = 0$ has a solution, you can pick $M = \{ P \in \Bbb Z[X,Y]/(X^2-2Y^2) / \lim_{y \to \infty} P(\sqrt 2 y,y) = + \infty$ or $P \in \Bbb N \}$

• In the model $M$, is the square root of 2 a rational number, i.e. are there any elements $a$ and $b$ in M such that $a^2 = 2 b^2$? – Keshav Srinivasan Sep 17 '13 at 18:39
• I don't only want sqrt(2) to be rational, I want everything (or a lot of things...) to be rational! For starters, I want $m a^2 - n b^2 = 0$ to have a solution for all $m$ and $n$. But I basically want a (countable) nonstandard model of Robinson arithmetic with as large a field of fractions as possible, for instance encompassing the constructible real numbers, so that Euclid wouldn't be able to find any irrational numbers at all. – Keshav Srinivasan Sep 18 '13 at 7:00

This is just a partial answer. Let $\mathcal L =\{S,<\}$ be the language with an unary function $S$ and a binary relation $<$. Consider the structure $(\mathbb N, S,<)$ ($S$ is the successor function), then $E=\{2n:n\in\mathbb N\}$ is not definable in $(\mathbb N, S,<)$. To see this consider the elementary extension $\mathfrak C=(\mathbb N\sqcup \mathbb Z, S,<)$, and define an automorphism $\Phi:\mathfrak C\to \mathfrak C$ as follows $\Phi(n)=n$ if $n\in\mathbb N$ and $\Phi(n)=S(n)$ otherwise. It is easy to see, using $\Phi$, that there is no formula defining $E$.

• Could you spell out how this relates to my question? And could you explain how the automorphism you've defined can be used to prove that there's no formula defining the set of even numbers? Of course, even without your proof I find it intuitively obvious that evenness wouldn't be definable in that language, but what's your point? – Keshav Srinivasan Sep 10 '13 at 4:01

I appear to have found an answer to my own question, from page 49 of Edward Nelson's book The Elements (which was a failed attempt to prove that Peano arithmetic is inconsistent):

"Here is a semantic indication that induction is necessary to prove this. Take a nonstandard model of $P$ and let $\alpha$ be a nonstandard number. Take the external set $U$ of all standard numbers together with all numbers obtained by repeatedly applying the functions symbols of $Q_{90}$ to $\alpha$. Then U is the universe of a model of $Q_{90}$, but there is no individual $\beta$ in $U$ such that either $2 \beta = \alpha$ or $2 \beta + 1= \alpha$."

Here $P$ denotes Peano arithmetic and $Q_{90}$ denotes Robinson arithmetic with basic properties of addition, multiplication, and order added.

Can anyone explain what Nelson's reasoning? Why can't there be a $\beta$ in $U$ such that either $2 \beta = \alpha$ or $2 \beta + 1= \alpha$?

• The universe is the standard natural numbers and any number of the form $\alpha + n$ or $n \alpha$ where $n$ is a standard natural number. We can't really prove there is a natural number less than $\alpha$ other than the standard natural numbers. We can prove there is no standard natural number, $n$, such that $\alpha = 2n \lor \alpha = 2n+1$. – Russell Easterly Sep 14 '13 at 7:36
• @RussellEasterly But if we can't show that only the standard natural numbers are less than $\alpha$, then how can we show that there is no $\beta$ in $U$ such that either $2 \beta = \alpha$ or $2 \beta + 1= \alpha$? – Keshav Srinivasan Sep 14 '13 at 20:39
• The only numbers less than $\alpha$ are the standard natural numbers. If $\alpha = 2n \lor \alpha = 2n+1$ where $n$ is a standard natural number then $\alpha$ is also standard contradicting our assumption $\alpha$ is non-standard. – Russell Easterly Sep 14 '13 at 22:34