1

I'm trying to understand the meaning of the solution of the following problem:

enter image description here

enter image description here

Formally, what are we actually proving here? When I prove things by induction, I try to write the predicate I'm trying to prove. In this case, I guess the predicate is:

Define $M(n):=\{x: x \in \Bbb{N}:x>n\}$, then we have:

$$P(n) := [ (m\in M(n) )\implies (m-n\in \Bbb{N}) ]$$

This is the only way I found that I think it makes sense. When we assume the inductive hypothesis (following the proof given above), we have that $m>n$ for $m\in \Bbb{N}$, then $m-n\in \Bbb{N}$ but then we suppose that $m>n+1$ and then $m-1>n$ and the proof follows because we assumed the inductive hypothesis but in it, we have $m$, in the second case we're talking about $m-1$, it's not too clear to me what is $m$. When I write it in the way I wrote above, I guess it makes it clearer that $m$ is actually "anything larger than $n$". Does this makes any sense at all? Excuse-me beforehand if I'm writing nonsense.

Red Banana
  • 23,956
  • 20
  • 91
  • 192
  • $m$ can be any natural number. If $m\le n$ then $m > n$ is false and so $m > n$ will vacuously imply $m-n\in \mathbb N$. For example: Suppose $n = 7$. Now let's take $m = 3$. The statement $(3 > 7) \implies 3-7 \in \mathbb N$ is TRUE(!!!) because $3> 7$ is false and a false hypothesis implies anything. – fleablood Jan 11 '24 at 00:24

3 Answers3

1

$m > n \implies m - n > 0$

Suppose $ m - n \not \in N$
Then $m - n \leq 0$

$(m - n > 0) \wedge (m - n \leq 0)$ This is a $\bot$

This proves that $m - n$ can't be either $0$ or a negative number.

Agent Smith
  • 951
1

Overall, we are proving the statement true for all possible values of $m$ and $n$. For the purposes of the induction, though, we are deciding to apply induction only on $n$, and so $m$ remains free (up to the restriction that it is a natural number greater than $n$). There are a lot of ways we could express this - your expression is one possibility, but we could also write it purely in set notation as something like

$$S(n) := \{ m - n : m \in \mathbb{N} \land m > n\}$$

(in which case we are proving that $S(n) \subseteq \mathbb{N}$ for all $n \in \mathbb{N}$).

ConMan
  • 24,300
1

The predicate you are trying to prove is $P(n):=$, if $m$ is any natural number and $m > n$ then $m-n$ is a natural number. (If $m$ is $m\le n$ we don't have to worry about it).

The induction step works because if we assume $P(n)$ is true and $m$ is any natural number we have either $m> n+1$ or $m\le n+1$. If $m \le n+1$ we don't have to worry about it. If $m > n+1$ then we know $m-1 > n$. Then by $P(n)$ we know that $(m-1) - n \in \mathbb N$. But as $(m-1)-n = m-(n+1)$ we have: for any $m$ if $m > n+1$ then $m -(n+1) \in \mathbb N$.

So we have proven by induction: For all natural number $n$, if $m$ is any natural number, then if $m > n$ we have $m-n \in \mathbb N$.

....

To use the set $S$ we have $S = \{n\in \mathbb N| P(n) = \text{TRUE}\} =\{n\in \mathbb N|(m\in \mathbb N\text{ and } m > n)\implies m-n \in \mathbb N\}$.

The proof goes on to prove that $S = \mathbb N$.

And as $\mathbb N = S$ then $\{n\in \mathbb N| P(n)=\text{TRUE}\} =\mathbb N$ so for all $n\in \mathbb N$ we have $P(n)$ is true.

Oh, I didn't address the base case, $P(1)$. Well: Let $n = 1$. Let $m$ be any natural number. If $m \le 1$ we don't have to worry about it. If $m > 1$ then $m$ has a precursor, $m-1$. (I'm assuming that is what TH. 1.3 is about) so $m - 1\in \mathbb N$. So $P(1)$ is true.

fleablood
  • 124,253