Continuum Induction

165 Views Asked by At

I have a question: Suppose we have a statement $P(x)$. If we show that:

  1. $\forall x \in (0,1]$, $P(x)$ is true.

  2. $P(x) \Rightarrow P(x+1)$

Then have we shown $P(x)$ holds $\forall x \in \mathbb{R}$, $x>0$?

My reasoning here is this:

$\textbf{Proposition:}$ If $(0,1] \subseteq S \subseteq \mathbb{R}$ and the implication: $x \in S$ $\Rightarrow$ $x+1 \in S$ holds, then $\mathbb{R}_{>0} \subseteq S$

$\textbf{Proof:}$ We argue for the contrapositive of the claim. Suppose $\mathbb{R}_{>0} \nsubseteq S$. If $(0,1] \nsubseteq S$ we are done so suppose $(0,1] \subseteq S$. Then $\mathbb{R}_{>0} \nsubseteq S$ implies $\exists$ $x \in \mathbb{R}_{>0}$ such that $x \notin S$. We consider two cases:

$\textit{Case 1:}$ Suppose $x \in \mathbb{N}$. Since $(0,1] \subseteq S$, $1 \in S$. Then by the inductive principle, if the implication: $y \in S$ $\Rightarrow$ $y+1 \in S$ holds, we must have $\mathbb{N} \subseteq S$, contrary to assumption. Thus said implication cannot hold.

$\textit{Case 2:}$ Suppose $x \notin \mathbb{N}$. Clearly $x \notin S$ $\Rightarrow$ $x>1$. Then if we write: $x= \left\{x\right\} + [x]$ (where $\left\{x\right\}$ is the fractional part of $x$ and $[x]$ is the floor function), $[x] \in \mathbb{N}$ and $0< \left\{x\right\}<1$. Define two sets:

$K= \left\{ \left\{x \right\}+n: n \in \mathbb{N}, \left\{x \right\}+n \notin S \right\}$

$K'= \left\{n \in \mathbb{N}: \left\{x \right\}+n \notin S \right\}$

Since $K' \subseteq \mathbb{N}$, $K'$ has a least element and thus $K$ does as well. Let $\left\{x \right\} +n$ be the least element of $K$ and for a contradiction assume the implication: $y \in S$ $\Rightarrow$ $y+1 \in S$ holds. Now $n \neq 0$, since $\left\{x\right\} +0 \in (0,1] \subseteq S$, so we must have $n \geq 1$. But taking the contrapositive of the aforementioned implication gives: $y+1 \notin S$ $\Rightarrow$ $y \notin S$, hence we have $\left\{x\right\} +n-1 \notin S$. Now if $n=1$, $\left\{x\right\} \notin S$, a contradiction, hence $n>1$. But then $\left\{x\right\} +n-1 \in K$ and $\left\{x\right\} +n-1 < \left\{x\right\} +n$ contradicting the assumption that the latter is the least element of $K$. Then $y \in S$ $\Rightarrow$ $y+1 \in S$ cannot hold.

The proof follows by contraposition $\Box$.

I think this is right but I wanted to check here before I used this anywhere.

$\textbf{Note:}$ We use the convention that $0 \notin \mathbb{N}$ and $\mathbb{R}_{>0} = \left\{x \in \mathbb{R}: x>0\right\}$

1

There are 1 best solutions below

1
On BEST ANSWER

This is correct. A somewhat slicker way to express the proof is to prove by induction on $n\in\mathbb{N}$ that $P(x)$ holds for all $x\in (n,n+1]$, and then observe that $\bigcup_{n\in\mathbb{N}}(n,n+1]=\mathbb{R}_{>0}$.