How does one establish that the set of even and odd numbers partition the set of integers? Question:
How does one establish that the set of even and odd numbers partition the set of integers?
In short, how do we know that all integers are either even or odd?
 A: This is quite the stumper. Of course each integer is either odd or even! I know it and I believe it. But how to prove it to someone who neither knows it nor believes it?
I guess we'd have to start with the very basics, with those facts we normally think need no explanation, like, what is an integer? Zero is an integer and one is another integer; if our nonbeliever accepts these two facts, maybe we can get him to accept the fact that each integer is either even or odd.
An integer is any number that can be obtained by repeatedly adding one to zero, or by repeatedly subtracting one from zero. You can obtain $-47$, 1729 and a googolplex this way, to give just three examples (of course, in the case of a googolplex it would be extremely tedious). You can't obtain $\frac{1}{2}$ nor $\pi$ this way. We say that the integers are "closed under addition" (which of course also includes subtraction and multiplication). Adding an integer to another integer results in an integer. The same goes for the subtraction and multiplication of integers.
So then what is an even integer? Any number that can be obtained by repeatedly adding 2 to zero, or by repeatedly subtracting 2 from zero. If $n$ is an integer, then so is $2n$. We can then say that an even integer is a number of the form $2n$, provided it's clear that $n$ is also an integer.
And what is an odd integer? A number of the form $2n + 1$, where, again, as before, $n$ is also an integer. Given another integer $m$, notice that $2m + 2n = 2(m + n)$, which is also even, and $(2m + 1) + (2n + 1) = 2(m + n + 1)$, which again is even, but $2m + (2n + 1) = 2(m + n) + 1$, which is odd.
Zero is even, which can be verified by the fact that $2 \times 0 = 0$. And one is odd, which can be verified with $2 \times 0 + 1 = 1$. Normally, all the foregoing would be way too obvious and basic to be worth mentioning. But this kind of rigor (or dullness, some might say) is necessary to give an answer more satisfying than "That's just the way it is."
If there exists an integer $x$ which is neither even nor odd, it can be expressed as $0 + 1 + 1 + 1 + \ldots + 1$ (the dots stand in for a bunch more "$+ \, 1$"s) or $0 - 1 - 1 - 1 - \ldots - 1$ (the dots stand in for a bunch more "$- \, 1$"s), but it can't be expressed as $2n$ nor $2n + 1$.
Now take the "unary" representation of $x$, and, starting at the left, replace the first occurrence of "$+ \, 1 + 1$" with "$+ \, 2$", or the first occurrence of "$- \, 1 - 1$" with "$- \, 2$". If there's another instance of "$+ \, 1 + 1$" or "$- \, 1 - 1$", replace it accordingly. Keep going until there's only a "$+ \, 1$" or "$- \, 1$" left, or maybe you only have a zero followed by a bunch of 2's separated by plus or minus signs.
How many 2's have you written? The number of 2's is an integer: write another zero above the zero and a 1 above each 2, and plus or minus signs between them to match, call $n$ the number represented by this expression. By the definition given earlier, $n$ is an integer. You have written $n$ 2's. If every 1 was paired up, this means $x = 2n$. But if there was a single 1 left on the right after a whole bunch of 2's, then $x = 2n + 1$. But this contradicts the earlier assertion that $x$ can't be represented in this way, meaning that $x$ is either odd or even.

If you want to be super formal about it, you can say that $\langle 2 \rangle$ and its coset $\langle 2 \rangle + 1$ (or $1 + \langle 2 \rangle$, same thing) form all of $\mathbb{Z}$.
A: Hint: Through the equivalence relation $\equiv \mod 2$ you may get this result. You'll have 
$$\mathbb Z_2=\{\overline 0, \overline 1\}$$
which is a partition of $\mathbb Z$.
