11
$\begingroup$

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$.
$\endgroup$
5
  • 2
    $\begingroup$ An interesting question is to prove (or disprove): "The set $\{ 0, S(0), S(S(0)), ...\}$ is dense in $\left[0,1\right]$." $\endgroup$
    – Stef
    Aug 21, 2022 at 10:25
  • $\begingroup$ 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. $\endgroup$
    – Teepeemm
    Aug 21, 2022 at 12:34
  • 2
    $\begingroup$ 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. $\endgroup$
    – PJTraill
    Aug 24, 2022 at 21:03
  • $\begingroup$ Surely the conclusion in your schema was not meant to be “∀x∈ℝ,P(x)” but “∀x∈[0,1],P(x)”. $\endgroup$
    – PJTraill
    Aug 24, 2022 at 21:09
  • $\begingroup$ @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)$" $\endgroup$ Aug 25, 2022 at 2:02

2 Answers 2

70
$\begingroup$

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.

$\endgroup$
1
  • 4
    $\begingroup$ What a great example. $\endgroup$
    – Randall
    Aug 20, 2022 at 23:52
36
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .