Can you prove that proof-by-induction is invalid for the real interval [0, 1]

decimal-expansionfake-proofsinductionreal numberstransfinite-induction

We have a special function $S$ from the real interval $[0, 1)$ to the real-interval $(0, 1]$ which I will define near the end of this post.

Someone claims that the following proof-schema is valid:

We wish to prove some statement $P(x)$ for each real number in the closed interval $[0, 1]$.

First, we show that the statement $P(0)$ is true.

Next we let $x$ be an arbitrary element of the interval $[0, 1]$. We assume that $P(x)$ is true, and then we prove that $P \begin{pmatrix} S(x) \end{pmatrix}$ is also be true.

We conclude that $\forall x \in [0, 1], P(x)$

An answer to this stack-exchange question is a proof that the above proof-schema is correct or incorrect.

If you think that induction on real-numbers is not valid, then an answer to this question is a proof of the existence of a predicate $P$ such that:

  • $P(0)$ is true.
  • $\exists x \in (0, 1]$ such that $P(x)$ is false.
  • There is no real number $x$ in the interval $[0, 1)$ such that $P(x)$ is true and $P(S(x))$ is false. Equivalently, show that $\forall x \in [0, 1)$ if the statement $P(S(x))$ is false then the statement $P(x)$ is also false.

Informal Description of function $S$

Informally,you can compute $S(x)$ by the following procedure:

  1. STEP ONE : Get a decimal-expansion of $x$. Look only at digits to the right of the decimal point. Go from left to right until you find a digit which is not nine. For example, if $x = 0.9990123$ then the left-most digit which is not a nine is a zero. Now add one to the digit which is not a nine. After adding $1$ to the left-most-non-nine digit in $0.9990123$ we get $0.9991123$.
  2. STEP TWO: Replace the leftmost nines with zeros. if $x = 0.9990123$ then $S(x) = 0.0001123$
Approximation of $x$ Approximation of $S(x)$ $x$ $S(x)$
$0.99531416$ $0.99631416$ $ 0.995 + \frac{pi}{10^{-4}}$ $ x + 10^{-3}$
$0.141421356237$ $0.241421356237$ $\frac{\sqrt{2}}{10}$ $ 0.1 + \frac{\sqrt{2}}{10}$
$0$ $0.1$ $0$ $0.1$
$0.1$ $0.2$ $0.1$ $0.2$
$0.1$ $0.2$ $0.1$ $0.2$
$0.2$ $0.3$ $0.2$ $0.3$
$0.3$ $0.4$ $0.3$ $0.4$
$0.999991$ $0.999992$ $0.999991$ $0.999992$
$0.93$ $0.94$ $0.93$ $0.94$
$0.999999999 \dots 0000 \dots$ $0.000000000 \dots 10000 \dots$ $1- 10^{-100}$ $10^{-101}$

If $S(x) = 1$ then $x = 0.9$

If $S(x) = 0.9$ then $x = 0.8$

If $S(x) = 0.8$ then $x = 0.7$

$$\dots$$

If $S(x) = 0.2$ then $x = 0.1$

Formal Definition of Function $S$

Let $S$ be a function from the real interval $[0, 1)$ to the real-interval $(0, 1]$ such that $\forall x \in [0, 1)$, $S(x) = x +10^{-(1 + g(x))} + 10^{-g(x)}$.

Function $g$ is defined as follows:

$$\forall x \in [0, 1], g(x) =
\begin{cases}
1, & \text{if } \lfloor 10* x \rfloor \neq 9 \\
1 + g(10*x – \lfloor 10* x \rfloor), & \text{ otherwise }
\end{cases}$$

Some Notes About Function $S$

Note 1: Irrational Inputs like $\pi$ are Okay

$S(x)$ is well-defined for irrational inputs such as $x = \pi$ and $x = \sqrt{2}$

Note 2: What is $\lfloor 10* x \rfloor \neq 9$?

Note that $\lfloor 10* x \rfloor \neq 9$ if and only if the left-most digit is $9$. For example, $\frac{\pi}{10}$ is approximately $0.31459$, which has a $3$ as its left-most digit. So, $\lfloor 10*\frac{\pi}{10} \rfloor \neq 9$

$\lfloor x \rfloor$ is the "floor" function.

What if the $9$s never end?

Note that the only real number in the interval $[0, 1)$ which has only nines in its decimal-expansion is the number $1$ which can be expanded as $0.999999 \dots$. However, $1$ is not a valid input to function $S$. All numbers in $[0, 1]$ besides the number $1$ have at least one non-nine digit. As such, we can always find the left-most digit which is not-a-nine.

A Different Informal way to Compute $S(x)$

Informally, we can:

  1. Find a decimal expansion of real number $x$
  2. Delete the decimal point and write the digits in reverse order. For example, if $x = \sqrt{2} ≈ 0.1414213 \dots$ then write $\dots 3124141$
  3. Add one to the result from step $2$ as if the step $2$ result was a natural number (it is not actually a natural. The result is not eventually all zero as you move leftward).
  4. Re-reverse the digits.

Note that the result step $2$ is NOT a natural number. The result of step $2$ is a function $F$ from $\mathbb{N}$ to the digits $\begin{Bmatrix} 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\end{Bmatrix}$ such that we probably have: $\not\exists n \in \mathbb{N}: \forall m \geq n, F(m) = 0$

For example if $x = \frac{\pi}{10}$ then:

  • $F(1) = 3$
  • $F(2) = 1$
  • $F(3) = 4$
  • $F(4) = 1$
  • $F(5) = 5$
  • $F(6) = 9$
  • In general, $F(k)$ is one of the digits of the decimal expansion of $\pi$.

Best Answer

This is obviously invalid regardless of what $S$ is: let $$\mathscr{X}=\{0,S(0),S(S(0)),...\}=\{S^i(0): i\in\mathbb{N}\}$$ (using the convention that $0\in\mathbb{N}$ and $S^0(x)=x$ here), consider the property $P(x):=x\in\mathscr{X}$, and remember that $[0,1]$ is uncountable.

There is a type of argument which works on $[0,1]$ and is arguably "induction-like," but it's quite different - see these notes of Pete Clark.

Related Question