Well-ordering principle

For every set \(S\), where \(S \subseteq \mathbb{Z}\) and \(|S| \neq 0\), there exists an integer \(m \in S\) such that for all integers \(x \in S\): $$m \leq x$$

Theorem: If the well-ordering principle is true, then the principle of mathematical induction is also true.
Proof by contradiction: In proofs by contradiction, we always assume the negation of the theorem and show that it must lead to a contradiction. Logically speaking, the negated theorem would be "The well-ordering principle is true and the principle of mathematical induction is false." Remember the principle of mathematical induction is itself the statement "If a base case \(P(b)\) is true and \(P(k) \rightarrow P(k+1)\) for all \(k \geq b\), then \(P(n)\) is true for all \(n \geq b.\)" Assuming that it's false would mean assuming its negation: "A base case \(P(b)\) is true and \(P(k) \rightarrow P(k+1)\) for all \(k \geq b\), but there exists some \(n \geq b\) such that \(P(n)\) evaluates as false." That gives us the following assumptions to work with from that lengthy introduction:

1. The well-ordering principle is true.
2. A base case \(P(b)\) is true.
3. \(P(k) \rightarrow P(k+1)\) for all \(k \geq b.\)
4. There exists some \(n \geq b\) such that \(P(n)\) evaluates as false.

Alright, now we need to use these assumptions to reach a contradiction. Let's define a set \(F\): $$F = \set{x \in \mathbb{Z} : \lnot P(x) \land x \geq b}$$ \(F\) is the set of all integers greater than or equal to \(b\), for which \(P(n)\) evaluates as false. By assumption #4, there exists some \(n \geq b\) such that \(P(n)\) evaluates as false, meaning it would qualify as a member of this set. Therefore, \(F\) is non-empty. Additionally, since \(F\) draws its elements from the set of integers, it is a subset of the set of integers. By assumption #1, the well-ordering principle is true, which means the non-empty subset of the set of integers, \(F\), has a minimum element, \(m.\) Since a minimum \(m\) exists, anything smaller than \(m\), like \(m - 1\) for example, cannot also be in the set \(F.\) Because that would contradict the fact that \(m\) is the minimum, you know? Generally, any integer \(y\) that is not in \(F\) is less than \(b\) or makes \(P(y)\) hold true. Since \(m\) is in \(F\), we know \(m \geq b.\) Let's explore these two cases:
1. \(m = b\)
If \(m = b\), then \(P(b)\) cannot be true, as that's a requirement for being an element of \(F.\) By assumption #2, we know that a base case \(P(b)\) is true. Contradiction!
2. \(m > b\)
If \(m > b\), then \(m - 1 > b - 1\), which can be alternatively written as \(m - 1 \geq b\), since \(m\) and \(b\) are integers. As we discussed before, anything smaller than \(m\) cannot be in \(F.\) Therefore, \(m - 1\) is not in \(F.\) Since \(m - 1 \geq b\), the reason it was not included in \(F\) must have been because \(P(m - 1)\) held true. So, we can be certain that \(P(m - 1)\) holds true. By assumption #3, \(P(k) \rightarrow P(k+1)\) for all \(k \geq b\), and because \(m - 1 \geq b\), \(P(m - 1) \rightarrow P(m).\) Since \(P(m - 1)\) holds true, \(P(m)\) holds true too. But wait, isn't \(P(m)\) supposed to be false as a requirement of \(m\) being in the set \(F\)? That's right. Contradiction!
Thus, no matter which of the two cases you choose, you will always arrive at a contradiction. This indirectly proves that the well-ordering principle implies the principle of mathematical induction. \(■\)

Theorem: For any two integers \(n\) and \(d\), where \(d > 0\), some integers \(q\) and \(r\) exist, with \(0 \leq r \leq d - 1\), to satisfy the equation \(n = qd + r.\)
Proof by contradiction: Let's assume the logical negation of the theorem, which is: "There exist two integers \(n\) and \(d\), where \(d > 0\), such that no integers \(q\) and \(r\) exist that satisfy both \(0 \leq r \leq d - 1\) and \(n = qd + r.\)" Got it. That means \(n\) and \(d\) exist such that for any integers \(q\) and \(r\), at least one of these conditions is true:

1. \(r < 0\)
2. \(r > d - 1\)
3. \(n \neq qd + r\)

Our job is to show \(q\) and \(r\) exist that make all three of these conditions false. Now, let's consider a set \(S\) defined as follows: $$S = \set{x \in \mathbb{Z}^{\geq 0} : x = n - td \land t \in \mathbb{Z}}$$ This is the set of all non-negative integers that can be written in the form \(n - td\), where \(t\) is any integer, and \(n\) and \(d\) are the two integers from our assumption. Intuitively, the set \(S\) cannot be empty because \(t\) can be any integer, capable of bringing \(x = n - td\) into the non-negative range. Therefore, by the well-ordering principle, \(S\) has a minimum, which we'll just happen to call \(r.\) Likewise, the specific value of \(t\) for which \(r = n - td\) will be denoted \(q.\) So, \(r\) can be written as: $$r = n - qd$$ If you rearrange, you'll realize that, at this point, we have shown there are integers \(q\) and \(r\) such that \(n = qd + r.\) We've therefore found \(q\) and \(r\) that can make that third condition false. What about the other two conditions? Well, since \(r\) is defined as the minimum element of \(S\), it must, like any other element of \(S\), be non-negative, as that is a requirement for membership. Therefore, the specific \(r\) we are working with makes the first condition, \(r < 0\), false. Now, realize we have knocked down two of the three conditions. When we assumed the negation of the theorem, we claimed at least one of these conditions will always be true, but we just found \(q\) and \(r\) such that \(r \geq 0\) and \(n=qd + r.\) If \(r> d - 1\) is also found to be false, a contradiction is inevitable. So, let's assume \(r > d - 1.\) If \(r > d - 1\), then \(r \geq d\), which further implies \(r - d \geq 0.\) In other words, \(d\), a positive integer, could be subtracted from \(r\) to obtain a non-negative integer smaller than \(r.\) Let's do just that: $$r - d = n - qd - d = n - (q + 1)d$$ Well, since \(q\) is an integer, \(q + 1\) is also an integer. This means \(r - d\) can be written in the form \(n - td\) for some integer \(t\), which in this case is \(q + 1.\) Combine that with the fact that it's non-negative, and \(r - d\) qualifies as a member of \(S\), smaller than \(r.\) Hey, wasn't \(r\) supposed to be the minimum? Yeah... Contradiction!
Thus, it is indirectly proven that for any \(n\) and \(d\), where \(d > 0\), there will always be integers \(q\) and \(r\) such that \(0 \leq r \leq d - 1\) and \(n = qd + r.\) \(■\)