Prove, by induction, $x\ne 1\implies x+1\ne2$ for all $x$ in $[0,1]$

Question

Suppose we have a statement concerning $x$, called statement 1.

Statement 2 states that statement 1 is true for all $x$ in $[a,b]$.

In general, is it always possible to prove statement 2 by induction, if statement 2 is true?

For instance, can we prove, by induction, that $x\ne 1\implies x+1\ne2$ for all $x$ in $[0,1]$?

---

I think it is difficult to prove these kind of ‘continuous statements’ by induction, as induction only proves countably many cases, but proving continuous statements requires proving uncountably many cases.

---

Any ideas?

Thanks in advance.

Answer 1

The following can be seen as a generalization of induction to real numbers, and may be along the lines of what you want.

Let $a>0$ be a real number, and let $P(x)$ be a proposition depending on a real variable $x$. If

• $P(x)$ is true for all $x$ in $[0,a)$, and
• for all $x,$ $P(x)$ implies $P(x+a)$,

then $P(x)$ is true for all $x ≥ 0.$

Note that you need a continuum of base cases.

We can use this technique to prove that $\mathbb Q$ is dense in $\mathbb R^+$. Specifically, for $n\in \mathbb N$, let $P_n(x)$ be the proposition that there exists an integer $m$ for which $|{x}-\frac{m}n|\le \frac1n$. Note $P_n(x)$ is true for all $x\in [0,\frac1n)$; just pick $m=0$. Furthermore, if $|x-\frac{m}n|\le \frac1n$, then $|(x+\frac1n)-\frac{m+1}n|\le \frac1n$ as well, so $P(x)$ implies $P(x+\frac1n)$. Therefore, $P_n(x)$ is true for all $x\ge 0$, so any positive real number is within $\frac1n$ of a rational for all $n$.

There is a second concept of "proof by induction" for real numbers.

Let $P(x)$ be a proposition depending on a real variable $x$. If

• $P(0)$ is true,
• the truth of $P(y)$ for all $0\le y<x$ implies $P(x)$,
• for all $x$, there exists an $\epsilon>0$ such that $P(x)$ implies the truth of $P(y)$ for all $x\le y <x+\epsilon$.

then $P(x)$ is true for all $x ≥ 0.$

Here you need one base case, but two inductive steps. There are many applications of this concept; you can use it to prove the intermediate value theorem, the extreme value theorem, and that $[0,1]$ is compact. For a survey, see http://alpha.math.uga.edu/~pete/realinduction.pdf.

Answer 2

As you are talking about the interval $[0, 1]$, I presume that you are working in a context where you have constructed the real numbers and demonstrated that they are an ordered field (so that the notion of the interval $[0, 1]$ makes sense). The fact that $x + 1 \neq 2$ for $x \in [0, 1]$ is then an easy consequence of the ordered field axioms. Proof by induction is irrelevant.

Answer 3

A little introduction to transfinite induction:

A natural number, in ZF is constructed by ordinal numbers, and such you can continue and construct more, larger numbers, assuming choice we also know for every that every set $S$ there is an unique ordinal $\kappa$ such $|S|=|\kappa|$, so we can define $|S|:=\kappa$.

Each ordinal is exactly one from the following: $0$, $\mu+1$(where $\mu$ is an ordinal), a limit ordinal.

Induction is a way to show take a statement from $0$ to the smallest limit ordinal($\Bbb N=\aleph_0=\omega$), now if we also prove that the statement is true if it is true for every ordinal before the limit ordinal it is also true for the limit ordinal we basically cover all the cases, hence it is true for all the ordinals beneath some ordinal.

This is only a little, the general idea.

Now we use the fact that the ordinals are well ordered, the problem is that we don't know what $|\Bbb R|$ is, we know it is an ordinal but don't know which one. Even more, we don't know how to create a well ordering for $\Bbb R$(or any interval of reals)(we do know such order exists), so we can't use the traditional induction.

That being said, there are other ways, that are not exactly but very close to induction, @Mike Earnest gave two great examples