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.

## Links

*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}$:

- Define the set of counterexamples, $C ::= { n \in \mathbb{N} | NOT(P(n)) }$.
- Assume for contradiction that $C$ is ______________.
- By the well-ordering principle, there must be __________________ , $m \in C$.
- 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$.
- 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.