Question: 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.

Thank You in Advance.

Answer: 
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 \}$
I know this is a pretty old post, but I want to share some of my own insights.

First, I want to highlight a slight error in the answer by mercio. It is a correct model of PA - induction, but Robinson Arithmetic is PA - induction + $\forall n (n = 0 \vee \exists m (n = S(m)))$. Their model does not satisfy this additional axiom, as $X$ does not have a predecessor. Now that I think of it, I am not sure if this is also addressed in the model in the Elements?

Let me add a model of my own. Take $N$ together with two non-standard elements $a$ and $b$. Extend $S$ by $S(a) = a$ and $S(b) = b$, addition by $a + n = a$ for $n \in N$ and all other new combinations result in $b$, and multiplication by $n \* 0 = 0$ always, and any other new combination results in $b$.

It is some annoying work to check that this satisfies all the axioms (which I formalized in Agda, for good measure), and it can be verified that $a$ is neither even nor odd (i.e. there does not exist $n$ such that any of $n + n = a$, $2\*n=a$, $n + n + 1 = a$ or $2\*n+1=a$ are true).