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.

# 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