# Prove that no positive integer is both even and odd, and that all positive integers are either even or odd

What is says on the can:

Prove that no positive integer is both even and odd, and that all positive integers are either even or odd.

This, of course, depends on defining even and odd.

For extra credit, if $S$ is the successor function, prove that if $n$ is even then $S(n)$ is odd and if $n$ is odd then $S(n)$ is even.

I find it interesting how many questions about evenness and oddness depend on these questions.

I have an answer based on the Peano axioms and some definitions, but I an interested in seeing what others come up with.

• Extra credit? Yay! What exactly? – David Mitra Aug 26 '13 at 0:54
• My definition of odd goes like this: "$n$ is odd if there exists $k$ such that $2k+1 = n$." Evenness follows easily from there. Then the successor function will clearly enforce the separation as well. – abiessu Aug 26 '13 at 2:51

Well, it certainly depends on how you define things and how abstract you want to be but I guess I would come up with what I think is the easiest answer for me.

We define a relation on $\mathbb{Z}$: $a \equiv b \mod n \iff n \mid a-b$

If $a \equiv b \mod n$ then $\exists q \in \mathbb{Z}: nq = a-b$, but by the division algorithm we can write $b=nk+r$ such that $0 \leq r < n$. If we replace this instead of $b$ we'll have $a - (nk+r) = nq \implies a -r = nQ' \implies a \equiv r \mod n$

Therefore every integer number is congruent to some number $0\leq r<n$. If $n=2$, then $r$ is either $0$ or $1$ provided that you take the standard order on integers for granted. However, it's easy to prove that there is no positive integer between $1$ and $0$. Because if there was an integer, say $m$, such that $0<m<1$, then the set $S=\{x \in \mathbb{Z}: 0<x<1\}$ would be a non-empty subset of natural numbers and hence it has a least element by the well-ordering principle. Let $m_0 = \min(S)$. But field axioms on reals implies that $0<m_0^2<m_0<1$, that means $m_0 ^2 < m_0 \in S$ and that's contradiction. But we have already assumed a well-defined order on integers (in fact on $\mathbb{R}$ and all of its subsets) which could be challenged depending on how you want to define an order on integers and how you build them. Hence, I have so far shown that there is no integer number between 1 and 0, I guess with shifting by $n$ one can prove that there is no integer number between $n$ and $n+1$. But anyway, the relation I have defined on $\mathbb{Z}$ can be proved to be an equivalence relation. Therefore, it partitions $\mathbb{Z}$ into disjoint non-empty subsets that are our equivalence classes. We call the equivalence class of $0$ as 'even' numbers and call the equivalence class $1$ as 'odd' numbers. Your statements now are obvious because our partitioned sets are disjoint (therefore a number can't be both even and odd) and their union is all of $\mathbb{Z}$ (any number must be either even or odd). This could be proved independently by using only the definitions of partitions and equivalence relations.

Now it's easily possible to prove that our partitioned set inherits a natural algebraic structure from $\mathbb{Z}$. I.e. $[a] + [b] = [a+b]$ and $[a].[b] = [a.b]$ where $[a]$ represents the class of all elements equivalent to $a$.

I guess it should be easy to prove by induction that if $s(n)$ is in the same equivalence class as $n$ then we'll have only equivalence class, therefore, to avoid that, $s(n)$ must fall in the other equivalence class because we have only two equivalence classes in $mod 2$.

I hope my arguments aren't that terrible and naive. I'm not a logician after all.

• I posed the question thinking of the Peano axioms and the successor function. Your answer is quite different and quite good. There are many ways to have fun with even and odd. – marty cohen Aug 28 '13 at 0:47