cs2102
Discrete Mathematics

Class 3: Well-Ordering Principle


Schedule

This week, you should read MCS Chapter 2 and MCS Chapter 3 (at least through the end of Section 3.4).

Problem Set 1 is due Friday at 6:29pm.

Office hours started Monday afternoon. See the course calendar for the full office hours schedule.

See PDF Version for Notes and Questions.

The Well-Ordering Theorem: one of the Greatest Mathematical Controversies of All Time, Kathryn Mann.

Notes and Questions

What properties must a sensible ordering function have?

Definition. A set is ordered with respect to an ordering relation (e.g., $<$), if two things hold. (1) Every pair of inequal elements $a,b$ in $A$ either satisfy $a<b$ or $b<a$. (2) for every three elements $a$, $b$, and $c$, $a < b$ and $b < c$ imply that $a < c$ (this is called transitivity).

Definition. An ordered set,with respect to an ordering relation (e.g., $<$), is well-ordered if all of its non-empty subsets has a minimum element.

Which of these are well-ordered?

  • The set of non-negative integers, comparator $<$.
  • The set of integers, comparator $<$.
  • The set of integers, comparator $|a| < |b|$.
  • The set of integers, comparator if |a| = |b|: $a < b$, else: $|a| < |b|$.
  • The set of national soccer teams, comparator winning games.

Prove the set of positive rationals is not well-ordered under $<$.

#

Provide a comparison function that can be used to well-order the positive rationals.

Template for Well-Ordering Proofs (Section 2.2)

To prove that $P(n)$ is true for all $n \in \mathbb{N}$:

  1. Define the set of counterexamples, $C ::= { n \in \mathbb{N} | NOT(P(n)) }$.
  2. Assume for contradiction that $C$ is ______________.
  3. By the well-ordering principle, there must be __________________ , $m \in C$.
  4. Reach a contradiction (this is the creative part!). One way to reach a contradiction would be to show $P(m)$. Another way is to show there must be an element $m’ \in C$ where $m’ < m$.
  5. Conclude that $C$ must be empty, hence there are no counter-examples and $P(n)$ always holds.

Example: Betable Numbers. A number is betable if it can be produced using some combination of \$2 and \$5 chips. Prove that all integer values greater than \$3 are betable.

# # # **Example: Division Property.** Given integer $a$ and positive integer $b$, there exist integers $q$ and $r$ such that: $a = qb + r$ and $0 \le r < b$.
# # _The whole problem with the world is that fools and fanatics are always so certain of themselves, and wiser people so full of doubts._ Bertrand Russell