Strong Induction from Tao

Question

I've already read this, this, and this, and I feel like the answers are only more confusing me more.

---

Definitions and Properties Available:

Axioms related to natural numbers:

• $0 \in \mathbb{N}$
• If $n \in \mathbb{N}$, then $n\mathrm{++} \in \mathbb{N}$, where $n\mathrm{++}$ denotes the successor of $n$.
• We define $1:= 0\mathrm{++}$, $2:= (0\mathrm{++})\mathrm{++})$, etc.
• For each $n \in \mathbb{N}$, $n\mathrm{++} \neq 0$.
• If $n\mathrm{++} = m\mathrm{++}$, then $n = m$.
• Let $P(n)$ be a property regarding $n \in \mathbb{N}$. Then suppose both (a) $P(0)$ is true and (b) $P(n)$ is true implies that $P(n\mathrm{++})$ is true for each $n\in \mathbb{N}$. Then $P(n)$ is true for each $n \in \mathbb{N}$.

Addition over natural numbers:

• Definition: $0 + m := m$, $(n\mathrm{++}) + m := (n+m)\mathrm{++}$.
• $n + 0 = n$
• Commutativity, associativity
• $a+b = a+c \implies b = c$

A positive number is a natural number not equal to $0$.

• If $a$ is positive and $b \in \mathbb{N}$, then $a+b$ is positive.
• If $a, b \in \mathbb{N}$ with $a + b = 0$, then $a = b = 0$.
• Let $a$ be positive. Then there is a unique $b \in \mathbb{N}$ with $b\mathrm{++} = a$.

Ordering of natural numbers:

• $n \geq m$ if $n = m + a$ for some $a \in \mathbb{N}$.
• $n > m$ if $n \geq m$ and $n \neq m$
• Reflexivity, transitivity, anti-symmetric, addition preserves order
• $a < b$ iff $a\mathrm{++} \leq b$
• $a < b$ iff $b = a + d$ for some $d$ positive.
• If $x \geq y$, then one of $x > y$ or $x = y$ is true.
• Trichotomy of order in $\mathbb{N}$

---

Let $m_0 \in \mathbb{N}$, and let $P(m)$ be a property pertaining to $m \in \mathbb{N}$ arbitrary. Suppose for each $m \geq m_0$ ($m \in \mathbb{N}$) that $$P(m^{\prime}) \text{ true }\forall m_0 \leq m^{\prime} < m \text{ natural numbers } \implies P(m)\text{ true.}$$ Then $P(m)$ is true for all natural numbers $m \geq m_0$.

Attempt

I use induction as provided in the axioms above.

Define the property $$Q(n): P(m)\text{ true } \forall m_0 \leq m < n\text{.}$$

Consider $Q(0)$. Because $m_0 \in \mathbb{N}$, we have $m_0 = m_0 + 0$, hence $m_0 \geq 0 = n$. Thus, $Q(0)$ is vacuously true.

Now let $k \in \mathbb{N}$ and assume $Q(k)$ is true. This implies that $P(m)$ is true for all $m_0 \leq m < k$.

Consider $Q(k\mathrm{++})$. I need to show somehow that $P(m)$ is true for all $m_0 \leq m < k\mathrm{++}$, or simply that $P(k)$ is true, but I don't understand the discussions in the links above and how they fit into the results I have available.

Answer 1

I think the most difficult thing about this problem is sorting through the notation, and trying to understand how the assumptions all come together.

Here's my proof of this statement, after asking the question and getting an excellent answer above.

Assumptions: Suppose $m_0 \in \mathbb{N}$, and for each $m \geq m_0$, $P(m^{\prime})$ true for all $m_0 \leq m^{\prime} < m$ implies $P(m)$ true.

Claim. $P(m)$ true for all $m \geq m_0$.

Proof. As in the hint in the text, define the property $$Q(n): P(m)\text{ true }\forall m_0 \leq m < n\text{.}\tag{1}$$ Suppose $n = 0$. Since $m_0 \in \mathbb{N}$, it follows that $m_0 = m_0 + 0$, or $m_0 \geq 0$, but since the claim $Q(n)$ has $m_0 < n$, we have that $Q(0)$ is vacuously true.

Suppose $Q(k)$ is true for some $k \in \mathbb{N}$. By definition of $Q(n)$ in $(1)$, we have that $P(m)$ is true $\forall m_0 \leq m < k$.

Since $k \in \mathbb{N}$ is arbitrary, consider two situations.

Suppose $k < m_0$. Then this implies that $P(k)$ is vacuously true.

Suppose $k \geq m_0$. Since $k \geq m_0$ and $P(m)$ is true for all $m_0 \leq m < k$, it follows by assumption that $P(k)$ is true.

Thus we have shown that $Q(k)$ is true implies that $P(k)$ is true.

We need to show that $Q(k\mathrm{++})$ is true. That is, $$Q(k\mathrm{++}): P(m)\text{ true }\forall m_0 \leq m < k\mathrm{++}\text{.}$$ By the induction hypothesis, $Q(k)$ is true. Thus $P(m)$ is true $\forall m_0 \leq m < k$. But as shown above, $Q(k)$ being true implies that $P(k)$ is true. Thus $P(m)$ is true $\forall m_0 \leq m < k\mathrm{++}$, and hence $Q(k\mathrm{++})$ holds.

Hence by induction, $Q(n)$ holds for all $n \in \mathbb{N}$. Thus $P(m)$ is true for all $m \geq m_0$.

Answer 2

Assume that

$\tag 1 (\forall m \in \Bbb N) \; \text{IF } \big [ \text{ if } m_0 \le m^{\prime} \lt m \text{ then } P(m^{\prime}) \big] \text{ THEN } P(m)$

Define

$\tag 2 Q(n) : (\forall m \in \Bbb N) [\text{ If } m_0 \le m \lt n \text{ Then } P(m)]$

Suppose we've proved that $Q(k)$ is always true. If $m \ge m_0$ set $k = m + 1$. So since $Q(k)$ is true and $m \lt k$ we have to take $P(m)$ as true.

We prove that $Q(k)$ is true for $k \ge 0$ using the OP's induction axiom.

The base case $Q(0)$ is vacuously true.

Step Case on $k$:

Assume $Q(k)$ is true. But setting $m = k$ in $\text{(1)}$ allows us to write as true

$\tag 3 \text{IF } \big [ \text{ if } m_0 \le m^{\prime} \lt k \text{ then } P(m^{\prime}) \big] \text{ THEN } P(k)$

But the hypothesis in $\text{(3)}$ is precisely the statement $Q(k)$. So $P(k)$ is true. But

$\tag 4 Q(k) \land P(k) \text{ implies } Q(k+1)$

and the induction is complete.