AMATH101 Real Analysis: Mathematical Reasoning, Peano Axioms, and the Construction of Natural Numbers

Foundations of Mathematical Analysis and the Need for Rigor

• Course and Institutional Context:

  • Course: AMATH101 Real Analysis.

  • Lecture: Mathematical Reasoning and Natural Numbers.

  • Academic affiliation: University Mohammed VI Polytechnic (UM6P), The UM6P Vanguard Center.

• The Scope and Objective of Real Analysis:

  • Real analysis provides the rigorous foundation for real numbers, sequences, series, and real-valued functions.

  • While elementary calculus supplies computational recipes and operational rules, analysis investigates and establishes the exact domain of validity for those rules.

  • The analytical method builds mathematics deductively from fundamental axioms, constructing number systems and arithmetic operations entirely through formal proof rather than intuitive assumptions.

• Failure Modes of Intuitive Arithmetic:

  • Cancellation Rule Fallacy (Remark 1.1):

  • The cancellation identity stating that $ac = bc \implies a = b$ is valid strictly under the hypothesis that $c \neq 0$.

  • In the presence of zero, cancellation fails; for instance, $1 \cdot 0 = 2 \cdot 0$ is mathematically true, yet dividing or cancelling $0$ produces the false assertion $1 = 2$.

  • Convergence in Infinite Sums (Remark 1.2):

  • Algebraic manipulations cannot be extended indiscriminately from finite sums to infinite expressions without establishing convergence.

  • The convergent geometric series $1 + \frac{1}{2} + \frac{1}{4} + \cdots = 2$ represents a well-defined limit of partial sums.

  • Conversely, applying naive formal algebraic manipulations to divergent series such as $1 + 2 + 4 + \cdots$ yields nonsensical results.

• Advanced Analytical Obstacles:

  • Alternating Partial Sums: The alternating series $1 - 1 + 1 - 1 + \cdots$ possesses no ordinary sum because its sequence of partial sums oscillates indefinitely between $1$ and $0$.

  • Interchanging Analytical Operations: Exchanging the order of limits, infinite series summations, and Riemann integration requires rigorous hypotheses (such as uniform convergence); analysis supplies the criteria necessary to validate such operations.

The Peano Axiomatic Framework for Natural Numbers

• Axioms of Succession:

  • Axiom 2.1 (Existence of Zero): $0$ is a natural number ($0 \in \mathbb{N}$).

  • Axiom 2.2 (Closure under Successor): If $n$ is a natural number, then its successor, denoted by $n^{++}$, is also a natural number ($n \in \mathbb{N} \implies n^{++} \in \mathbb{N}$).

  • Axiom 2.3 (Zero as the Initial Element): $0$ is not the successor of any natural number; that is, for all $n \in \mathbb{N}$, $n^{++} \neq 0$.

  • Axiom 2.4 (Injectivity of Successor): Different natural numbers have distinct successors; equivalently, for all $n, m \in \mathbb{N}$, $n^{++} = m^{++} \implies n = m$.

• Definition 2.1 (Numerals):

  • Numerals are defined recursively starting from zero and the successor operator:

  • $1 := 0^{++}$

  • $2 := (0^{++})^{++} = 1^{++}$

  • $3 := ((0^{++})^{++})^{++} = 2^{++}$

  • and so forth for all succeeding elements.

  • Axiom 2.2 guarantees that every generated numeral is a natural number.

  • Axioms 2.3 and 2.4 ensure that each generated numeral is mutually distinct from all preceding numerals.

• Structure of the Successor Chain:

  • The succession mapping $S(n) = n^{++}$ generates an infinite linear chain beginning at $0$.

  • Injectivity prevents the chain from looping back on itself or branching into merged paths.

  • Because $0$ has no predecessor, the chain has a strict starting point and extends infinitely without cycles.

• Remark 2.1 (Interpretation of Successor Diagrams):

  • The graphical representation $0 \xrightarrow{S} 1 \xrightarrow{S} 2 \xrightarrow{S} 3 \xrightarrow{S} 4 \dots$ provides conceptual intuition.

  • Visual diagrams do not substitute for formal axiomatic deductions.

• Classification of Numerals and Predecessors (Full Proof):

  • Theorem: Every natural number $n$ is either $0$ or possesses a unique predecessor $m \in \mathbb{N}$ such that $m^{++} = n$.

  • Step-by-Step Proof:

  • Step 1: By Axiom 2.4, if $n^{++} = m^{++}$, then $n = m$. This establishes uniqueness of the predecessor whenever one exists.

  • Step 2: By Axiom 2.3, no successor can equal $0$.

  • Step 3: Define the induction property $P(n)$ as "$n = 0$ or $n$ is the successor of some natural number."

  • Step 4: The base case $P(0)$ holds trivially because $0 = 0$.

  • Step 5: For the inductive step, examine $n^{++}$. By definition, $n^{++}$ is the successor of $n$, meaning $P(n^{++})$ holds unconditionally, regardless of whether $P(n)$ is true.

  • Step 6: By mathematical induction, $P(n)$ holds for all $n \in \mathbb{N}$, verifying that every non-zero natural number is a successor of a unique predecessor.

Principles of Mathematical Induction and Recursion

• Axiom 2.5 (Principle of Mathematical Induction):

  • Let $P(n)$ be any property pertaining to a natural number $n$.

  • Suppose the following two conditions are satisfied:

  • Base Case: $P(0)$ is true.

  • Inductive Step: Whenever $P(n)$ is true for an arbitrary $n \in \mathbb{N}$, the statement $P(n^{++})$ is also true ($P(n) \implies P(n^{++})$).

  • Then, $P(n)$ is true for every natural number $n \in \mathbb{N}$.

• Logical Discipline in Induction (Remark 2.2):

  • In executing an induction step, one assumes the hypothesis $P(n)$ solely to prove the conditional implication $P(n) \implies P(n^{++})$.

  • Assuming $P(n)$ as an established universal truth prior to completing the inductive argument is a circular fallacy.

• Proposition 2.1 (The Recursion Principle):

  • Let $c \in \mathbb{N}$, and suppose that for each $n \in \mathbb{N}$ there exists a function $f_n : \mathbb{N} \rightarrow \mathbb{N}$.

  • Then, there exists a unique sequence $(a_n)_{n \in \mathbb{N}}$ such that:

  • $a_0 = c$

  • $a_{n^{++}} = f_n(a_n)$ for every $n \in \mathbb{N}$.

  • Significance: Arithmetic operations are not innate concepts; they are defined constructively via recursive functions governed by this principle.

• Proposition 3.7 (Strong Principle of Induction):

  • Let $m_0 \in \mathbb{N}$. Suppose that for every $m \geq m_0$, whenever $P(m')$ holds for all $m'$ in the range $m_0 \leq m' < m$, it necessarily follows that $P(m)$ is true.

  • Then, $P(m)$ is true for every natural number $m \geq m_0$.

• Derivation of Strong Induction from Ordinary Induction (Full Proof):

  • Objective: Establish the validity of Proposition 3.7 using Axiom 2.5.

  • Proof Procedure:

  • Step 1: Assume the strong inductive hypothesis: for any $n \geq m_0$, if $P(k)$ holds for all $m_0 \leq k < n$, then $P(n)$ holds.

  • Step 2: Formulate the auxiliary property $Q(n)$ defined as: "$P(k)$ holds for every $k$ satisfying $m_0 \leq k \leq n$".

  • Step 3 (Base Case): For $n = m_0$, the set of predecessors $\{k \in \mathbb{N} \mid m_0 \leq k < m_0\}$ is empty. Vacuously, the premise holds, which directly implies $P(m_0)$. Consequently, $Q(m_0)$ is established.

  • Step 4 (Inductive Step): Assume $Q(n)$ holds for some $n \geq m_0$. This means $P(k)$ is true for all $m_0 \leq k \leq n$.

  • Step 5: Consider the case $n^{++}$. Every integer $k$ satisfying $m_0 \leq k < n^{++}$ satisfies $k \leq n$. By the induction hypothesis $Q(n)$, $P(k)$ holds for all such $k$.

  • Step 6: Applying the original strong induction hypothesis gives $P(n^{++})$.

  • Step 7: Since both $Q(n)$ (covering $m_0 \leq k \leq n$) and $P(n^{++})$ hold, their conjunction implies $Q(n^{++})$ (covering $m_0 \leq k \leq n^{++}$).

  • Step 8: By Axiom 2.5, $Q(n)$ holds for all $n \geq m_0$. Because $Q(n) \implies P(n)$, it follows that $P(n)$ holds for all $n \geq m_0$.

Formal Construction and Properties of Addition

• Definition 3.1 (Addition of Natural Numbers):

  • Addition is defined recursively on the first argument:

  • Base Case: For any $m \in \mathbb{N}$, $0 + m := m$.

  • Recursive Step: For any $n, m \in \mathbb{N}$, $(n^{++}) + m := (n + m)^{++}$.

• Directionality of the Recursive Definition (Remark 3.1):

  • The definition operates strictly by unwinding the first summand: $0 + m = m$ and $(n^{++}) + m = (n + m)^{++}$.

  • The identity $n + 0 = n$ is not an immediate consequence of Definition 3.1 and requires an independent proof by induction.

• Lemma 3.1 (Right Identity of Addition):

  • For any natural number $n$, $n + 0 = n$.

  • Example 3.1: While Definition 3.1 explicitly gives $0 + n = n$, computing $1 + 0$ requires applying the recursive step: $1 + 0 = (0^{++}) + 0 = (0 + 0)^{++} = 0^{++} = 1$.

  • Full Proof by Induction on $n$:

  • Step 1 (Base Case): For $n = 0$, Definition 3.1 directly evaluates $0 + 0 = 0$. Thus, the base case holds.

  • Step 2 (Induction Hypothesis): Assume $n + 0 = n$ for some $n \in \mathbb{N}$.

  • Step 3 (Inductive Step): Compute $(n^{++}) + 0$ using Definition 3.1:       $(n^{++}) + 0 = (n + 0)^{++}$

  • Step 4: Substitute the induction hypothesis into the expression:       $(n + 0)^{++} = n^{++}$

  • Step 5: By Axiom 2.5, $n + 0 = n$ holds for every natural number $n \in \mathbb{N}$.

• Lemma 3.2 (Successor Shift in the Second Argument):

  • For any natural numbers $n$ and $m$, $n + (m^{++}) = (n + m)^{++}$.

  • Remark 3.3: Symmetry cannot be assumed prior to proving commutativity; the behavior of $n + (m^{++})$ must be derived separately from $(n^{++}) + m$.

  • Full Proof by Induction on $n$ with $m$ Fixed:

  • Step 1 (Base Case): Let $n = 0$. By Definition 3.1:       $0 + (m^{++}) = m^{++}$       Simultaneously, $0 + m = m$, so:       $(0 + m)^{++} = m^{++}$       Thus, $0 + (m^{++}) = (0 + m)^{++}$, confirming the base case.

  • Step 2 (Induction Hypothesis): Assume $n + (m^{++}) = (n + m)^{++}$.

  • Step 3 (Inductive Step): Compute $(n^{++}) + (m^{++})$ using Definition 3.1 on the first argument:       $(n^{++}) + (m^{++}) = (n + (m^{++}))^{++}$

  • Step 4: Apply the induction hypothesis to the inner term:       $(n + (m^{++}))^{++} = ((n + m)^{++})^{++}$

  • Step 5: Using Definition 3.1 in reverse, observe that $(n^{++}) + m = (n + m)^{++}$. Applying succession to both sides gives:       $((n^{++}) + m)^{++} = ((n + m)^{++})^{++}$

  • Step 6: Equating the two expressions yields:       $(n^{++}) + (m^{++}) = ((n^{++}) + m)^{++}$

  • Step 7: By induction on $n$, the identity holds for all $n \in \mathbb{N}$. Because $m$ was arbitrary, the relation holds for all $n, m \in \mathbb{N}$.

• Proposition 3.1 (Commutativity of Addition):

  • For any natural numbers $n$ and $m$, $n + m = m + n$.

  • Remark 3.4: Commutativity is not self-evident and cannot be justified by asserting that order is irrelevant; it depends entirely on Lemma 3.1 and Lemma 3.2.

  • Full Proof by Induction on $n$ with $m$ Fixed:

  • Step 1 (Base Case): For $n = 0$, evaluate both sides:       $0 + m = m$       By Lemma 3.1, $m + 0 = m$. Hence, $0 + m = m + 0$.

  • Step 2 (Induction Hypothesis): Assume $n + m = m + n$.

  • Step 3 (Inductive Step): Evaluate $(n^{++}) + m$ using Definition 3.1:       $(n^{++}) + m = (n + m)^{++}$

  • Step 4: Apply the induction hypothesis:       $(n + m)^{++} = (m + n)^{++}$

  • Step 5: By Lemma 3.2, $(m + n)^{++} = m + (n^{++})$. Combining the equalities gives:       $(n^{++}) + m = m + (n^{++})$

  • Step 6: By induction, $n + m = m + n$ holds for all $n, m \in \mathbb{N}$.

• Proposition 3.3 (Associativity of Addition):

  • For any natural numbers $a, b, c$, $(a + b) + c = a + (b + c)$.

  • Full Proof by Induction on $a$ with $b, c$ Fixed:

  • Step 1 (Base Case): Let $a = 0$. By Definition 3.1:       $(0 + b) + c = b + c$       and       $0 + (b + c) = b + c$       Thus, $(0 + b) + c = 0 + (b + c)$.

  • Step 2 (Induction Hypothesis): Assume $(a + b) + c = a + (b + c)$.

  • Step 3 (Inductive Step): Compute $((a^{++}) + b) + c$ using Definition 3.1:       $((a^{++}) + b) + c = ((a + b)^{++}) + c = ((a + b) + c)^{++}$

  • Step 4: Apply the induction hypothesis:       $((a + b) + c)^{++} = (a + (b + c))^{++}$

  • Step 5: Applying Definition 3.1 to the right-hand expression gives:       $(a + (b + c))^{++} = (a^{++}) + (b + c)$

  • Step 6: Conclude by induction that $(a + b) + c = a + (b + c)$ for all $a, b, c \in \mathbb{N}$. (Note: This derivation is independent of commutativity).

• Proposition 3.4 (Cancellation Law for Addition):

  • For any natural numbers $a, b, c$, if $a + b = a + c$, then $b = c$.

  • Full Proof by Induction on $a$:

  • Step 1 (Base Case): Let $a = 0$. The relation $0 + b = 0 + c$ simplifies directly by Definition 3.1 to $b = c$.

  • Step 2 (Induction Hypothesis): Assume cancellation holds for $a$: $a + b = a + c \implies b = c$.

  • Step 3 (Inductive Step): Suppose $(a^{++}) + b = (a^{++}) + c$.

  • Step 4: By Definition 3.1, this is equivalent to:       $(a + b)^{++} = (a + c)^{++}$

  • Step 5: By Axiom 2.4 (injectivity of successor):       $a + b = a + c$

  • Step 6: By the induction hypothesis, $a + b = a + c \implies b = c$.

  • Step 7: Induction establishes that additive cancellation holds for all $a \in \mathbb{N}$.

• Positivity and the Vanishing Sum Characterization:

  • Definition 3.2 (Positive Numbers): A natural number $n$ is defined to be positive if and only if $n \neq 0$.

• Lemma 3.3 (Unique Predecessors): Every positive natural number $a$ has a unique predecessor $b \in \mathbb{N}$ satisfying $b^{++} = a$.

• Corollary 3.1 (Zero Sum Property): If $a + b = 0$ for natural numbers $a, b$, then $a = 0$ and $b = 0$.

• Full Proof of Corollary 3.1:

  • Step 1: Suppose towards contradiction that $a \neq 0$.

• Step 2: Since $a$ is positive, Lemma 3.3 guarantees the existence of some $c \in \mathbb{N}$ such that $a = c^{++}$.

• Step 3: Substitute this into the sum:   $a + b = (c^{++}) + b = (c + b)^{++}$

• Step 4: By Axiom 2.3, no successor can equal $0$. Thus, $(c + b)^{++} \neq 0$, contradicting the premise $a + b = 0$.

  • Step 5: Hence, $a$ cannot be positive, which means $a = 0$.

  • Step 6: Substituting $a = 0$ into the original equation yields $0 + b = 0$, which simplifies to $b = 0$.

  • Step 7: Therefore, $a + b = 0 \implies a = b = 0$.

• Proposition 3.2 (Sum of the First $n$ Odd Numbers):

  • For every natural number $n$, the sum of the first $n$ odd natural numbers equals $n^2$:     $\sum_{k=0}^{n-1} (2k + 1) = n^2$     where the empty sum (when $n = 0$) is defined to equal $0$.

  • Empirical Validation (Example 3.4):

  • $n = 1$: $1 = 1^2 = 1$.

  • $n = 2$: $1 + 3 = 4 = 2^2$.

  • $n = 3$: $1 + 3 + 5 = 9 = 3^2$.

  • Full Proof by Induction on $n$:

  • Step 1 (Base Case): For $n = 0$, the summation is empty, evaluating to $0$. The right side is $0^2 = 0$. The identity holds.

  • Step 2 (Induction Hypothesis): Assume $\sum_{k=0}^{n-1} (2k + 1) = n^2$.

  • Step 3 (Inductive Step): The $(n + 1)\text{st}$ odd number is given by $2n + 1$. Partition the sum:       $\sum_{k=0}^{n} (2k + 1) = \left( \sum_{k=0}^{n-1} (2k + 1) \right) + (2n + 1)$

  • Step 4: Substitute the inductive hypothesis:       $\sum_{k=0}^{n} (2k + 1) = n^2 + 2n + 1$

  • Step 5: Factor the resulting polynomial:       $n^2 + 2n + 1 = (n + 1)^2$

  • Step 6: By induction, the identity holds for all $n \in \mathbb{N}$.

The Formal Order Structure on the Natural Numbers

• Definition 3.3 (Ordering on $\mathbb{N}$):

  • For $n, m \in \mathbb{N}$, $n \geq m$ (or $m \leq n$) if and only if there exists some $a \in \mathbb{N}$ such that $n = m + a$.

  • The strict relation $n > m$ (or $m < n$) holds if and only if $n \geq m$ and $n \neq m$.

  • Order is defined through additive differences rather than an axiomatic geometric continuum.

• Proposition 3.5 (Structural Properties of Order):

  • Reflexivity: For every $a \in \mathbb{N}$, $a \leq a$.

  • Proof: $a = a + 0$. Since $0 \in \mathbb{N}$, $a \leq a$.

  • Transitivity: For any $a, b, c \in \mathbb{N}$, if $a \leq b$ and $b \leq c$, then $a \leq c$.

  • Proof: By definition, $b = a + u$ and $c = b + v$ for some $u, v \in \mathbb{N}$. Substituting $b$ gives $c = (a + u) + v = a + (u + v)$. By closure, $u + v \in \mathbb{N}$, so $a \leq c$.

  • Antisymmetry: For any $a, b \in \mathbb{N}$, if $a \leq b$ and $b \leq a$, then $a = b$.

  • Proof: There exist $u, v \in \mathbb{N}$ such that $b = a + u$ and $a = b + v$. Combining yields $a = (a + u) + v = a + (u + v)$. Applying additive cancellation gives $0 = u + v$. By Corollary 3.1, $u = v = 0$, which proves $b = a + 0 = a$.

  • Compatibility with Addition: If $a \leq b$, then $a + c \leq b + c$ for any $c \in \mathbb{N}$.

  • Proof: $b = a + t \implies b + c = (a + t) + c = (a + c) + t$, hence $a + c \leq b + c$.

  • Successor Step Equivalence: For any natural numbers $a, b$, $a < b \iff a^{++} \leq b$.

• Proposition 3.6 (Trichotomy of Order):

  • For any two natural numbers $a, b \in \mathbb{N}$, exactly one of the following relations holds:     $a < b, \quad a = b, \quad a > b$

  • Full Proof by Induction on $a$:

  • Step 1 (Base Case): Let $a = 0$. Every natural number $b$ either equals $0$ or is positive ($b = c^{++}$). If $b = 0$, then $a = b$. If $b = c^{++}$, then $b = 0 + c^{++}$, so $0 < b$. Hence, trichotomy holds for $a = 0$.

  • Step 2 (Induction Hypothesis): Assume trichotomy holds between $a$ and every element $c \in \mathbb{N}$.

  • Step 3 (Inductive Step): Consider $a^{++}$ compared against an arbitrary $b \in \mathbb{N}$.

  • Step 4: If $b = 0$, then because $a^{++} \neq 0$, we have $a^{++} > 0 = b$.

• Step 5: If $b \neq 0$, then $b = c^{++}$ for some unique predecessor $c$. By the induction hypothesis, compare $a$ against $c$:

  • If $a = c$, taking successors gives $a^{++} = c^{++} = b$.

  • If $a < c$, then $c = a + (t^{++})$ for some $t \in \mathbb{N}$. Taking successors gives $b = c^{++} = (a + (t^{++}))^{++} = a^{++} + (t^{++})$, so $a^{++} < b$.

  • If $a > c$, then $a = c + (t^{++})$. Taking successors gives $a^{++} = (c + (t^{++}))^{++} = c^{++} + (t^{++}) = b + (t^{++})$, so $a^{++} > b$.

• Step 6: Mutual exclusivity follows from antisymmetry and the fact that a positive successor cannot vanish. Thus, trichotomy holds for all $a, b \in \mathbb{N}$.

Formal Construction and Properties of Multiplication

• Definition 3.4 (Multiplication of Natural Numbers):

  • Multiplication is defined recursively on the first argument:

  • Base Case: For any $m \in \mathbb{N}$, $0 \times m := 0$.

  • Recursive Step: For any $n, m \in \mathbb{N}$, $(n^{++}) \times m := (n \times m) + m$.

• Essential Auxiliary Multiplication Identities:

  • Identity 1 (Right Multiplication by Zero): For all $m \in \mathbb{N}$, $m \times 0 = 0$.

  • Proof: For $m = 0$, $0 \times 0 = 0$. Assuming $m \times 0 = 0$, evaluate $(m^{++}) \times 0 = (m \times 0) + 0 = 0 + 0 = 0$. By induction, the identity holds universally.

  • Identity 2 (Successor in the Second Factor): For all $n, m \in \mathbb{N}$, $m \times (n^{++}) = (m \times n) + m$.

  • Proof by induction on $m$ with fixed $n$:

    • Base case ($m = 0$): $0 \times (n^{++}) = 0$ and $(0 \times n) + 0 = 0 + 0 = 0$. Base case holds.

    • Induction step: Assume $m \times (n^{++}) = (m \times n) + m$. Compute $(m^{++}) \times (n^{++})$:         $(m^{++}) \times (n^{++}) = (m \times (n^{++})) + (n^{++})$

    • Substitute the induction hypothesis:         $((m \times n) + m) + (n^{++}) = (m \times n) + (m + (n^{++})) = (m \times n) + ((m + n)^{++})$

    • By commutativity and associativity of addition:         $(m \times n + n^{++}) + m = ((m \times n + n)^{++}) + m = ((m^{++} \times n)) + (m^{++})$

    • The inductive step is verified for all $m \in \mathbb{N}$.

• Lemma 3.4 (Commutativity of Multiplication):

  • For all $n, m \in \mathbb{N}$, $n \times m = m \times n$.

  • Full Proof by Induction on $n$ with $m$ Fixed:

  • Step 1 (Base Case): For $n = 0$, Definition 3.4 yields $0 \times m = 0$. Identity 1 yields $m \times 0 = 0$. Hence, $0 \times m = m \times 0$.

  • Step 2 (Induction Hypothesis): Assume $n \times m = m \times n$.

  • Step 3 (Inductive Step): Compute $(n^{++}) \times m$ using Definition 3.4:       $(n^{++}) \times m = (n \times m) + m$

  • Step 4: Substitute the induction hypothesis:       $(n \times m) + m = (m \times n) + m$

  • Step 5: By Identity 2, $(m \times n) + m = m \times (n^{++})$. Combining the equalities yields:       $(n^{++}) \times m = m \times (n^{++})$

  • Step 6: By induction, $n \times m = m \times n$ for all $n, m \in \mathbb{N}$.

• Proposition 3.8 (Distributive Law):

  • For all natural numbers $a, b, c$, $a(b + c) = ab + ac$.

  • Full Proof by Induction on $a$:

  • Step 1 (Base Case): Let $a = 0$. Then $0(b + c) = 0$, and $0b + 0c = 0 + 0 = 0$. Both sides agree.

  • Step 2 (Induction Hypothesis): Assume $a(b + c) = ab + ac$.

  • Step 3 (Inductive Step): Compute $(a^{++})(b + c)$:       $(a^{++})(b + c) = a(b + c) + (b + c)$

  • Step 4: Apply the induction hypothesis:       $a(b + c) + (b + c) = (ab + ac) + (b + c)$

  • Step 5: Regroup terms using the associativity and commutativity of addition:       $(ab + ac) + (b + c) = (ab + b) + (ac + c)$

  • Step 6: By Definition 3.4, $ab + b = (a^{++})b$ and $ac + c = (a^{++})c$. Thus:       $(a^{++})(b + c) = (a^{++})b + (a^{++})c$

  • Step 7: By induction, distributivity holds for all $a, b, c \in \mathbb{N}$.

• Proposition 3.9 (Associativity of Multiplication):

  • For all natural numbers $a, b, c$, $(ab)c = a(bc)$.

  • Full Proof by Induction on $a$:

  • Step 1 (Base Case): Let $a = 0$. Then $(0 \cdot b)c = 0 \cdot c = 0$, and $0(bc) = 0$. Base case holds.

  • Step 2 (Induction Hypothesis): Assume $(ab)c = a(bc)$.

  • Step 3 (Inductive Step): Compute $((a^{++})b)c$:       $((a^{++})b)c = (ab + b)c$

  • Step 4: Apply the distributive property (Proposition 3.8):       $(ab + b)c = (ab)c + bc$

  • Step 5: Substitute the induction hypothesis:       $(ab)c + bc = a(bc) + bc$

  • Step 6: By Definition 3.4, $a(bc) + bc = (a^{++})(bc)$. Thus:       $((a^{++})b)c = (a^{++})(bc)$

  • Step 7: By induction, multiplication is associative on $\mathbb{N}$.

• Lemma 3.5 (No Zero Divisors / Null Factor Law):

  • For any natural numbers $n, m$, $nm = 0 \iff n = 0 \text{ or } m = 0$.

  • Full Proof:

  • Step 1: If $n = 0$ or $m = 0$, then $nm = 0$ directly by Definition 3.4 and Lemma 3.4.

  • Step 2: For the converse, assume towards contradiction that $nm = 0$ while both $n \neq 0$ and $m \neq 0$.

• Step 3: By Lemma 3.3, positive numbers have predecessors; express $n = k^{++}$ and $m = \ell^{++}$.

• Step 4: Using Definition 3.4, expand the product:   $nm = (k^{++})m = km + m$

• Step 5: Because $m = \ell^{++}$, $m \neq 0$. By Corollary 3.1, a sum of natural numbers can equal zero only if both summands vanish.

• Step 6: Because $m \neq 0$, the sum $km + m$ cannot be zero, which contradicts $nm = 0$.

  • Step 7: Therefore, $nm = 0$ implies $n = 0$ or $m = 0$.

• Order Preservation and Cancellation in Multiplication:

  • Proposition 3.10 (Monotonicity of Multiplication): If $a < b$ and $c > 0$, then $ac < bc$.

  • Proof: If $a < b$, then $b = a + t^{++}$ for some $t \in \mathbb{N}$. Multiplying by $c$ yields $bc = (a + t^{++})c = ac + (t^{++})c$. Since $t^{++} \neq 0$ and $c > 0$, Lemma 3.5 guarantees $(t^{++})c > 0$. Thus, $bc = ac + u$ with $u > 0$, proving $ac < bc$.

• Corollary 3.2 (Multiplicative Cancellation Law): If $ac = bc$ and $c \neq 0$, then $a = b$.

  • Proof: By trichotomy (Proposition 3.6), exactly one of $a < b$, $a = b$, or $a > b$ must hold. If $a < b$, then $ac < bc$ (since $c > 0$), contradicting $ac = bc$. Similarly, if $a > b$, then $ac > bc$, contradicting $ac = bc$. Hence, $a = b$.

• Proposition 3.11 (Euclidean Division Theorem):

  • For any natural number $n \in \mathbb{N}$ and any positive natural number $q \in \mathbb{N}$ ($q > 0$), there exist unique natural numbers $m, r \in \mathbb{N}$ such that:     $n = mq + r \quad \text{with} \quad 0 \leq r < q$

  • Existence Proof (Strong Induction on $n$ with Fixed $q > 0$):

  • Step 1: Assume the division statement holds for every natural number $t < n$.

  • Step 2: Compare $n$ with $q$ via trichotomy.

  • Step 3: If $n < q$, set $m = 0$ and $r = n$. This gives $n = 0 \cdot q + n$ with $0 \leq n < q$, satisfying the claim.

  • Step 4: If $n \geq q$, there exists $t \in \mathbb{N}$ such that $n = q + t$. Because $q > 0$, it follows that $t < n$.

  • Step 5: By the strong induction hypothesis, Euclidean division applies to $t$: there exist $m', r \in \mathbb{N}$ such that $t = m'q + r$ with $0 \leq r < q$.

  • Step 6: Substitute this decomposition into the expression for $n$:       $n = q + (m'q + r) = (m'q + q) + r = (m'^{++})q + r$

  • Step 7: Setting $m = m'^{++}$ establishes the existence of the decomposition $n = mq + r$ with $0 \leq r < q$.

  • Uniqueness Proof:

  • Step 1: Suppose there exist two representations: $n = mq + r = m'q + r'$ with $0 \leq r < q$ and $0 \leq r' < q$.

  • Step 2: By trichotomy, either $m = m'$, $m < m'$, or $m > m'$.

  • Step 3: If $m = m'$, then $mq + r = mq + r'$. Applying additive cancellation gives $r = r'$.

  • Step 4: If $m < m'$, then $m' = m + k^{++}$ for some $k \in \mathbb{N}$. Substituting this gives:       $m'q + r' = (m + k^{++})q + r' = mq + (k^{++})q + r' \geq mq + q$       However, the original identity states $mq + r = m'q + r'$. Because $r < q$, we have $mq + r < mq + q$, which contradicts $m'q + r' \geq mq + q$.

  • Step 5: An identical contradiction arises if $m' < m$.

  • Step 6: Therefore, $m = m'$ and $r = r'$, establishing uniqueness.

Exponentiation on the Natural Numbers

• Definition 3.5 (Recursive Definition of Exponentiation):

  • For any base $m \in \mathbb{N}$:

  • Base Case: $m^0 := 1$ (incorporating the formal convention $0^0 := 1$ within this system).

  • Recursive Step: For any $n \in \mathbb{N}$, $m^{n^{++}} := m^n \times m$.

  • Standard Numerical Consequences:

  • $m^1 = m^{0^{++}} = m^0 \times m = 1 \times m = m$

  • $m^2 = m^{1^{++}} = m^1 \times m = m \times m$

  • $m^3 = m^{2^{++}} = m^2 \times m = (m \times m) \times m$

• Theorem (Fundamental Law of Exponents):

  • For all natural numbers $m, n, p \in \mathbb{N}$:     $m^{n+p} = m^n m^p$

  • Full Proof by Induction on $p$ with $m, n$ Fixed:

  • Step 1 (Base Case): For $p = 0$, evaluate the left side using Lemma 3.1:       $m^{n+0} = m^n$       Evaluate the right side using Definition 3.5:       $m^n m^0 = m^n \times 1 = m^n$       Thus, $m^{n+0} = m^n m^0$, verifying the base case.

  • Step 2 (Induction Hypothesis): Assume $m^{n+p} = m^n m^p$.

  • Step 3 (Inductive Step): Evaluate $m^{n + (p^{++})}$ using Lemma 3.2 and Definition 3.5:       $m^{n + (p^{++})} = m^{(n + p)^{++}} = m^{n+p} \times m$

  • Step 4: Substitute the induction hypothesis into the product:       $m^{n+p} \times m = (m^n m^p) \times m$

  • Step 5: By associativity of multiplication (Proposition 3.9):       $(m^n m^p) \times m = m^n (m^p \times m)$

  • Step 6: By Definition 3.5, $m^p \times m = m^{p^{++}}$. Substituting this term yields:       $m^n (m^p \times m) = m^n m^{p^{++}}$

  • Step 7: By induction, the exponent law $m^{n+p} = m^n m^p$ holds for all $p \in \mathbb{N}$.