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?
[Math] How does one establish that the set of even and odd numbers partition the set of integers
elementary-number-theorynumber theory
Related Solutions
Yes. The generalization is provided by modular arithmetic. The properties you are observing all come from the fact that taking the remainder modulo $n$ respects addition and multiplication, and this generalizes to any $n$. More generally in abstract algebra we study rings and their ideals for the same reasons.
The notion of evenness and oddness of functions is closely related, but it is somewhat hard to explain exactly why. The key point is that there is a certain group, the cyclic group $C_2$ of order $2$, which is behind both concepts. For now, note that the product of two even functions is even, the product of an even and odd function is odd, and the product of two odd functions is even, so even and odd functions under multiplication behave exactly the same way as even and odd numbers under addition.
There are also huge generalizations depending on exactly what you're looking at, so it's hard to give a complete list here. You mentioned chessboards; there is a more general construction here, but it is somewhat hard to explain and there are no good elementary references that I know of. Once you learn some modular arithmetic, here is the modular arithmetic explanation of the chessboard idea: you can assign integer coordinates $(x, y)$ to each square (for example the coordinate of the lower left corner), and then you partition them into black or white squares depending on whether $x + y$ is even or odd; that is, depending on the value of $x + y \bmod 2$. Then given two points $(a, b)$ and $(c, d)$ you can consider the difference $c + d - a - b \bmod 2$, and constraints on this difference translate to constraints on the movement of certain pieces. This idea can be used, for example, to prove that certain chessboards (with pieces cut out of them) cannot be tiled with $1 \times 2$ or $2 \times 1$ tiles because these tiles must cover both a white square and a black square. Of course there are generalizations with $2$ replaced by a larger modulus and larger tiles.
As for matrices and vectors, let's just say that there are a lot of things this could mean, and none of them are straightforward generalizations of the above concept.
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.
Best Answer
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}$.