Notes and Questions

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

What properties must a sensible ordering function have?

Trichotomy. A relation, $\prec$, satisfies the axiom of trichotomy if exactly one of these is true for all elements $a$ and $b$: $a \prec b$, $b \prec a$ or $a = b$.

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