Peano Axioms

The naturals are defined as a set of objects which obey the following axioms:

1. $0$ is natural.
2. If $n$ is a natural, then $n{+\!+}$ is also natural.
3. $n{+\!+} ≠ 0$.
4. $n{+\!+} = m{+\!+}$ can be rewritten as $n = m$.
5. Let $P$ be a proposition over any natural $n$. If $P(0)$ is true, and if whenever $P(n)$ is true we also have $P(n{+\!+})$ is true, then $P$ is true for any natural.

Logical Assumptions

Let $a, b, c$ be naturals.

Set Theory with 2nd Order Logic

Definition 1: Addition

Addition $+$ is a closed binary operator over any pair of naturals $(n,m)$.

Proposition 1: $n + 0 = n$

We use induction to ask if the proposition $P(n) ↦ n + 0 = n$ is true for any natural $n$.

Base Case

We evaluate the base case $P(0)$ which maps to the proposition $0 + 0 = 0$.

We use the definition of addition to rewrite the left-hand side of the equation to arrive at $0 = 0$, which we know to be reflexively true.

Inductive Case

For any specific $n$, is assuming $P(n)$ is sufficient to know $P(n{+\!+})$?

The case of $P(n{+\!+})$ can be written as $P(n)$. By the inductive axiom we know that $P(n)$ is true for all naturals.

Proposition 2: $n + (m{+\!+}) = (n + m){+\!+}$

Using induction we ask if $P(n) ↦ n + m{+\!+} = (n + m){+\!+}$ is true for any $n, m ∈ ℕ$. Informally we are wondering whether we can use a “reversed” rule for addition as a stepping stone to commutativity.

Base Case

Inductive Case

1. This is our inductive hypothesis.
2. We rewrite the expression on both sides according to definition of addition.
3. We removed a layer of succession from both sides by the 4th Peano axiom.

The case of $P(n{+\!+})$ can be rewritten as $P(n)$.

Corollary 1: $n{+\!+} = n + 1$

Theorem 1: Commutativity of Addition

We ask whether $P(n) ↦ n + m = m + n$ is always true.

Base Case

$P(0) \stackrel{✓}{=} 0 + m = m + 0$

Inductive Case

We want to know if assuming $P(n)$ implies $P(n{+\!+})$.

The case of $P(n{+\!+})$ can be rewritten as $P(n)$.

Proposition: Associativity of Addition

Base Case

Inductive Case

The case of $P(n{+\!+})$ can be rewritten as $P(n)$.

Theorem 3: Cancellation of Addition

Base Case

Inductive Case

Definition: Positivity

Any non-zero natural is positive.

Proposition: Positive Addition

If $m$ is positive, then $(n + m)$ is also positive.

Base Case

Inductive Case

This also means that both $n, m$ must be $0$ for the expression $(n + m = 0)$.

Corollary: Positives have unique predecessor

Argument. For every positive natural $n$ there exists a unique natural $a$ such that $n = a{+\!+}$.

Proof. Let’s say there exists another natural $b$ where $(b{+\!+} = n)$. Then $(a{+\!+} = b{+\!+})$ which implies $(a = b)$. This means all predecessors are unique. Now let’s say that for all positive $n$ we have $(n = a{+\!+})$.

Definition: Greater/Lesser or Equal

For any naturals $\{ a, b \}$ the partial order $(a ≤ b)$ is defined as the proposition that there exists a natural $n$ where $(a + n = b)$ is true.

Since $n$ could be $0$ it’s possible that $a = b$. If $n$ were positive then we know that $a ≠ b$, which is how we define the strict order operator:

This definition can be restated as:

Lemma: Trichotemy of the Naturals

For any two naturals $\{ a, b \}$ only one of these statements can be true at a time. This can be finitely proven through truth tabling.

We have $(a ≠ b)$ by definition which leaves whether $(b < a)$.

If we set $(b = 0)$ then we reach a contradiction right away because a successor cannot be $0$.

Proposition: Reflexivity of Partial Order

Proof

Proposition: Transitivity with Partial Order

Proof

Since $b + n_1$ and $a + n_2$ both equal $c$, we use substitution to produce this expression:

I use substitution for $b = a + n_0$:

In a way this is saying that the addition of “intervals” are linear.

Proposition of Anti-Reflexivity

Proof

I use substitution on $b = a + n_0$ to produce the expression:

Therefore $(a + n_0 = b) ∧ (b + n_1 = a)$ implies $a = b$.

Addition Preserves Order

Base Case

Inductive Case

Strict Order and Succession

I rewrite the left predicate by the definition of strict order and I rewrite the right predicate by the definition of partial order.