0

I have been given the following (non-predicate form) definitions for the Principle of Mathematical Induction (weak and strong,respectively) as follows:

$I$: Let $U\subseteq\mathbb{N}$ with $1\in U$ and $a+1\in U$ whenever $a\in U$ , then $U=\mathbb{N}$.

$I_1$: Let $V\subseteq\mathbb{N}$with $1\in V$ and $a+1\in V$ whenever $x\in V$ such that $1\le x\le a+1$ then $V=\mathbb{N}$.

I wish to prove $I_1\Rightarrow\ I$.

I have managed to prove this by proving $I_1\Rightarrow\ Well Ordering Principle\Rightarrow\ I$, but I am looking for a more direct proof. Any help or input would be great!

Lgate8
  • 445
  • Is that second statement if $V\subset \mathbb{N}$ with $1\in V$ and $a+1\in V$ whenever it is the case that $x\in V$ for all $x\in [1,a]$, then $V=\mathbb{N}$. As this is the form of strong induction I have seen. – jgon Sep 23 '15 at 00:03

2 Answers2

0

I'm assuming the statement of strong induction mentioned in the comments.

Suppose $U$ is a set with the property in $I$, then it has the property $I_1$, for if $[1,a]\subset U$, then $a\in U$, so by the property $I$ $a+1\in I$. Then by $I_1$, $U=\mathbb{N}$ as desired. And thus $I$ holds.

jgon
  • 28,469
  • But how do I know $[1,a]\subset U$ ? For $I$, I know that $a\in U\Rightarrow\ a+1\in U$, but for all positive integers before $a$, how do I know they are also in U is my problem with this proof. – Lgate8 Sep 23 '15 at 00:15
  • @geo17 Isn't the statement that $V$ has property $I_1$ if whenever $[1,a]\subset V$ then $a+1\in V$. So you don't need to show $[1,a]\subset U$, just that if $[1,a]\subset U$, then $a+1$ is in $U$. Right? Unless I am misinterpreting the statement, which is totally possible. – jgon Sep 23 '15 at 00:20
  • I am assuming $I_1$ is true. Then, assuming some set called U satisfies $1\in U$ and $a+1\in U$ when $a\in U$, I have to show $U=\mathbb{N}$. So basically $U$ actually satisfies the criteria laid out in $I_1$. Hopefully that made sense ? – Lgate8 Sep 23 '15 at 00:28
  • So say $a\in U$. I know $a+1\in U$. But in order to apply $I_1$, I need to know all positive integers $x$ where $x\le a$ are also in U – Lgate8 Sep 23 '15 at 00:30
  • @geo17 I'm not really sure what you're trying to say, sorry. – jgon Sep 23 '15 at 19:33
0

So you have $$1 \in V \land (\forall a ~:~ [1,a] \subseteq V \implies a+1 \in V) \implies V = \mathbb N$$

This is equivalent to

$$[1, 1] \subseteq V \land (\forall a ~:~ [1,a] \subseteq V \implies [1, a+1] \in V) \implies V = \mathbb N$$

Define $U$ as $k \in U \iff [1 .. k] \subseteq V$, equivalently that is to choose a $V$ such that for arbitrary $U$, $V = \{k \text{ s.t. } \forall j \le k ~:~ j \in U\}$

$$1 \in U \land (\forall a ~:~ a \subseteq U \implies a+1 \subseteq U) \implies V = \mathbb N$$

Now just to show that $V = \mathbb N$ implies $U = \mathbb N$ depends on your logic/set theory and how formal you want to be, but:

$$\{k \text{ s.t. } \forall j \le k ~:~ j \in U\} = \mathbb N$$ $$\forall k \forall j ~:~ j \le k \implies j \in U$$ $$\forall j ~:~ (\exists k ~:~ j \le k) \implies j \in U$$ $$\forall j ~:~ j \in U$$ $$U = \mathbb N$$

DanielV
  • 23,556