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

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$$.
• An interesting question is to prove (or disprove): "The set $\{ 0, S(0), S(S(0)), ...\}$ is dense in $\left[0,1\right]$."
– Stef
Commented Aug 21, 2022 at 10:25
• In "the following proof-schema", it's usually the case that $S(x)=x+1$, and you conclude $\forall x>0$. Otherwise, you could just take $S(x)=x$, which satisfies your conditions, but not the conclusion. Commented Aug 21, 2022 at 12:34
• Does someone really claim this? If so, I hope they provide an attempt to prove their method works, and it might be interesting to to see this to understand where they are going wrong. Commented Aug 24, 2022 at 21:03
• Surely the conclusion in your schema was not meant to be “∀x∈ℝ,P(x)” but “∀x∈[0,1],P(x)”. Commented Aug 24, 2022 at 21:09
• @PJTraill you are right. I should have written "$\forall x \in [0, 1], P(x)$" and not written "$\forall x \in \mathbb{R}, P(x)$" Commented Aug 25, 2022 at 2:02

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.
Let $$P(x)$$ be the predicate "$$x$$ is a terminating decimal"; that is, $$x = \frac{a}{10^n}$$ for some integers $$a, n$$. Since $$S$$ applied to any terminating decimal is a terminating decimal, the implication $$P(x) \to P(S(x))$$ holds for all $$x$$. Of course $$P(0)$$ is true as well. But (for example) $$P(1/3)$$ is false.