Well Ordering

As I have said in my previous post, I was struggling to understand the principle of well-ordering. Thankfully, someone in Piazza kindly posted a link (go to page 43) that explains it in a very good way.

Basically, what we do in well-ordering is assume that a set of counter-examples to P(n) called C exists and that c is the smallest element of C. In the link I provided, P(n): 1 + 2 + 3 + ... + n = n(n + 1)/2

• Then, for all n < c (e.g. n = c - 1), P(n) holds, since the smallest value of n where P(n) is false is n = c.
  
• With this in mind, we show P(c - 1):
  1 + 2 + 3 + ... + (c - 1) = c(c - 1)/2
  
• Then we modify P(c - 1) to be P(c) and show that P(c) is in fact, true:
  1 + 2 + 3 + ... + (c - 1) + c = c(c - 1)/2 + c    # add c to both sides
                                             = (c^2 - c + 2c)/2
                                             = (c^2 + c)/2
                                             = c(c + 1)/2         # P(c + 1)!
  
• But P(c) is suppose to be false, this is a contradiction!
  
• Then, P(c) should be true and there is no counter-example to P(n).
  
• Therefore for all n, P(n) holds.

Thanks to Alex for the awesome post!