4.4 Ordering[27K]

Hypothesis 143

[26H] We will study an order relation \(≤\) on \(ℕ\) (not necessarily total) such that

\begin{align} ∀ x ∈ℕ , & (0≤ x) \quad , \label{eq:caratt_ le_ N_ 0} \\ ∀ x,y ∈ℕ , & (x{\lt} Sy) \iff (x ≤ y ) \quad ; \label{eq:caratt_ le_ N} \end{align}

where as usual

\[ x{\lt}y ≐ (x≤ y)∧ (x≠ y)\quad . \]
Theorem 146

[26Y] There is an unique order relation \(≤\) on \(ℕ\) such that ??,?? in 143 hold, and this ordering is well-ordered.

This theorem will be proven in the following: uniqueness in 1, well ordering in 3. The existence of such ordering is justified by the model in Z-F, as seen before and summarized in Section 4.5; otherwise the ordering can be defined using arithmetic, as shown in Section ??.

E146

[267]Suppose that \(≤\) is a (possibly partial) order relation on \(ℕ\) satisfying 143 then \(≤\) is unique. Hidden solution: [UNACCESSIBLE UUID ’270’]

E146

[271]Let

\[ P_ x =\{ z∈ ℕ, z{\lt} x\} \]

show that

\[ ∀ x,y∈ ℕ~ ,~ P_ x = P_ y ⇒ x=y \]

using the properties in Hypothesis 143.

Hidden solution: [UNACCESSIBLE UUID ’272’]

(Note the similarity with 7).

E146

[276]By setting \(n=x=y\) in ?? we obtain that \(n{\lt}Sn\).

E146

[277]Prerequisites:3,143.Using the properties in 143 and assuming that \(≤\) is a total order relation (as will be proven), prove that

\[ ∀ n,m∈ ℕ, (n{\lt} m ) ⇒ (Sn{\lt} Sm)\quad . \]

Hidden solution: [UNACCESSIBLE UUID ’278’]

E146

[26X]If \(⪯\) is a total order on \(ℕ\) then these are equivalent

\begin{align} ∀ x,y∈ ℕ , & (x⪯ y⪯ Sx ) ⇒ (x=y∨ y=Sx)\quad ,\label{eq:caratt_ le_ N_ mid}\\ ∀ x,y ∈ℕ , & (x≺ Sy) \iff (x ⪯ y ) \quad ; \\ ∀ x,y ∈ℕ , & (x≺ y) \iff (Sx ⪯ y ) \quad . \label{eq:caratt_ le_ N_ alt} \end{align}

Note the analogy with 3

Hidden solution: [UNACCESSIBLE UUID ’296’]

[UNACCESSIBLE UUID ’293’]

Ordering from arithmetic[287]

Having already defined arithmetic, a convenient definition of ordering is as follows.

Definition 150

[288] Given \(n,m∈ ℕ\), we will say that \(n≤ m\) if there exists \(k∈ℕ\) such that \(n+k=m\)

We will show that \(≤\) it is a total order relation, and is a well ordering. Let’s first see some elementary but fundamental properties.
Lemma 151

[289] Let \(n,m,k∈ℕ\).

  1. For every \(n\) we have \(0\le n\)

  2. \(n≤ m\) if and only if \(n{\lt} S(m)\).

    Note that these two points satisfy ??,?? in 143

  3. For every \(n\) we have \(n{\lt}S(n)\)

  4. \(n{\lt}m\) if and only if \(S(n)≤ m\).

  5. If \(n≤ m ≤ S(n)\) then \(m=n\) or \(m=S(n)\).

The proofs are left as exercise 1. (After we will prove that the relation is total, then by 5 the last two are equivalent.)

Proposition 152

[28B] \(≤\) is an order relation.

Proof ▼

Reflexive property: \(n+0=n\). Antisymmetric property: if \(n+k=m\) and \(m+h=n\) then \(n+k+h=n\) therefore by cancellazione 3 \(h+k=0\), and for 4 \(h=k=0\) so \(n=m\). Transitive property: if \(n+k=m\) and \(m+h=p\) then \(n+k+h=p\).

[298]Hence this relation “\(\le \)” defined in 150 satisfies the principle 143; we will show that any such ordering is a well order; here we present though a self contained proof for this specific case.

Proposition 153

[28Z] \(≤\) is a total order relation.

Proof ▼

Consider the proposition

\[ P(n)≐ ∀ m∈ℕ, n≤ m ∨ m≤ n \]

then \(P(0)\) is true. Let’s assume \(P(n)\); let’s fix an \(m\);

  • if \(m≤ n\) then \(m≤ S(n)\), by the lemma (point 2), so \(P(Sn)\) holds;

  • if \(¬ m≤ n\) but \(P(n)\) holds, then \(n≤ m\) must hold, but it cannot be \(n=m\), so \(n{\lt}m\) holds: but then \(S(n)≤ m\) by the lemma (point 4);

in any case \(P(S(n))\) is proven starting from \(P(n)\).

Proposition 154

[297] \(≤\) is a well ordering.

Proof ▼

Trace of proof. By Lemma 151 (point 2) we know that this relation satisfies the strong induction principle 158; so we can prove that any non empty subset has a minimal element as in Esercise 2; but we know that the ordering is total, so the minimal element is the minimum.

Definition 155 Subtraction

[28C] If \(m≥ n\), there exists an unique \(h\) such that \(m=n+h\) (uniqueness follows from 3); we will indicate this \(h\) as \(m-n\).

E155

[28D] Show properties in 151. Hidden solution: [UNACCESSIBLE UUID ’28F’]

E155

[28G]Show that if \(n≤ m\) then \(m-n≤ m\). Hidden solution: [UNACCESSIBLE UUID ’28H’]

E155

[28N] Show that if \(n≠ 0\) then \(n× m≥ m\). Hidden solution: [UNACCESSIBLE UUID ’28P’]

E155

[28J] Topics:Euclidean division.

Prove that, given \(d,n∈ℕ,d≥ 1\), two numbers \(q,r∈ℕ,0≤ r {\lt} d\) exist and are unique for which \(n=q×d +r\) (where \(n\) is the ”dividend” \(d\) is the ”divisor”, \(q\) is the ”quotient” and \(r\) is the ”remainder”) Hidden solution: [UNACCESSIBLE UUID ’28K’]

E155

[28M] (Replaces 282)

Let \(h≠ 0\), prove that if \(n× h= m× h\) then \(n= m\). (Sugg. use subtraction)

Hidden solution: [UNACCESSIBLE UUID ’28S’]

In particular the map \(n\mapsto n× h\) is injective.

Ordering and arithmetic [28Q]

The ordering is compatible with arithmetic.

Proposition 156

[28R]

  • (Addition and ordering compatibility) You have \(n≤ m\) if and only if \(n+k≤ m+k\).

  • (Multiplication and ordering compatibility) When \(k≠ 0\) you have \(n≤ m\) if and only if \(n× k≤ m× k\).

In particular (remembering 5) the map \(n\mapsto n× h\) is strictly increasing (and hence injective).

Proof ▼

We will use some properties left for exercise.

  • If \(n≤ m\), by definition \(m=n+h\), then \(n+k≤ m+k\) because \(m+k=n+h+k\) (note that we are using associativity). If \(n+k≤ m+k\) let then \(j\) the only natural number such that \(n+k+j= m+k\) but then \(n+j= m\) by cancellation 3.

  • If \(n≤ m\) then \(m=n+h\) therefore \(m× k=n× k+h× k\) so \(n× k≤ m× k\). Vice versa let \(k≠ 0\) and \(n× k≤ m× k\) i.e. \(n× k + j= m× k\): divide \(j\) by \(k\) using the division 4, we write \(j=q× k + r\) therefore for associativity \((n+q)× k + r= m× k\) but for the uniqueness of the division \(r=0\); eventually collecting \((n+q)× k = m× k\) and using 5 we conclude that \((n+q) = m\).