Recap: Well-ordering Principle

(#0)

The proof for 1) 0 <= r <= n and 2) q, r unique with the set R = {r in natural numbers | There exists q in natural numbers. m = qn+r} (which has a smallest element) for each m and n was very messy in my mind.
--------
Alright, I was going to write a problem-solving episode here, but I believe I understand the proof well now. Part of the confusion was the lack of emphasis on the def'n of well ordering in class, as simple as it sounds. Then there was the separation between needing to show parts 1) and 2). At the very least, now I see that:
- We can do double induction on m and n.
- Since we assumed m to be arbitrary, it helps show us that the set R is nonempty by choosing q = 0.
- Well-ordering is probably the most tricky type of induction for me. Let's try to find some patterns, as in the proof below.

The proof for all natural numbers n > 3. P(n):"Every round-robin tournament w/ n players that has a cycle has a 3-cycle" was cool (since analysing a game takes away any boredom a CS course could bring).
- This gave me intuition on how to use WOP #-1. Firstly, I learned that a set should be constructed when we are looking to prove a particular element is the smallest element of the set wrt to the claim we have to prove. Then, I also learned that the elements should be natural numbers (to show the set is a subset of the natural numbers) and that the claim can help us show the set is nonempty (since the claim asks to prove that an element of the set is the smallest one, but this assumes that the element exists in the  set in the first place, which is hidden somewhere in the claim itself).
- An important thing to remind myself is that to prove the element is the smallest, we can do a proof by contradiction. We assume the smallest element is larger than that which we want to show is the smallest element, then we show how this assumption leads to a contradiction, oftentimes by being able to find a smaller element or failing to remain in an assumed domain.
- Finally, I only noticed that the two cases: p1 > p3 and p3 > p1 actually fulfills the law of the excluded middle, and can hence be used ain a proof by cases.

Just reading MIT's MCS book, their suggestion on the WOP goes along the lines of:
- Create a set C that is all the counter-examples to the claim.
- Assume the set is non-empty and that by the WOP, it has a smallest element n.
- Show that this assumption leads to a contradiction.
- Then the assumption is wrong, C is empty, and the claim holds.
In this form of a WOP proof, I noticed that one way the contradiction is found is by noticing that all elements smaller than n do have the claim hold. This is similar to the induction hypothesis holding in a complete induction proof. Then we can take the constituent parts of n and use the induction hypothesis on each of those parts to show that the claim does indeed hold for n. This contradicts the assumption that n is the smallest counterexample, because it isn't a counterexample. This is enough to show that the WOP doesn't hold, which means that the assumption is wrong, so the claim holds.

Okay, back to studying.

#0: I want to meet the prof who wrote this book since his style would be very similar to mine. Very complete but easy to fall asleep with as a result. In fact, the symbols here are so frequent that the text becomes very hard to read. Have you seen MIT's MCS book? Perfect textbook.

#-1: oppa gangnam style