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