2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ There is something called transfinite induction that let's you "do" induction of uncountable many things but it won't be for use here because you need to find bijective function between an interval to an ordinal which means that we can pinpoint $|\Bbb R|$ and we can't do this. So final answer is no $\endgroup$ – ℋolo Sep 12 '18 at 23:30
  • 1
    $\begingroup$ @Holo doesn't the axiom of choice imply that every set is well-orderable, so there is indeed a bijection between $\mathbb{R}$ and some ordinal? We just can't know what that ordinal is? $\endgroup$ – Sambo Sep 12 '18 at 23:50
  • 1
    $\begingroup$ @Sambo indeed, but for induction we need well ordering, without knowing to define the well ordering we can't use the induction(even though we know that the ordering exists) $\endgroup$ – ℋolo Sep 12 '18 at 23:53
  • $\begingroup$ @Holo Well technically one can always disguise a standard proof as "induction" by never effectively use the inductive assumption. "inductive step: since $x \neq 1$ and since we know by $P(n)$ whatever $P(n)$ is saying, adding one on both sides we get $x+1 \neq 2$" :) $\endgroup$ – N. S. Sep 13 '18 at 0:55
7
$\begingroup$

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://math.uga.edu/~pete/realinduction.pdf.

$\endgroup$
  • $\begingroup$ Downvoter, care to comment on how this answer can be improved? $\endgroup$ – Mike Earnest Sep 13 '18 at 0:15
  • $\begingroup$ I think I may have downvoted your answer by mistake when I meant to upvote it. Apologies! Fixed now. $\endgroup$ – Rob Arthan Sep 13 '18 at 19:01
  • $\begingroup$ @RobArthan No worries, thanks :) $\endgroup$ – Mike Earnest Sep 13 '18 at 19:33
  • $\begingroup$ There is much further discussion in the 2010 thread Induction on Real Numbers. $\endgroup$ – Bill Dubuque Oct 5 '18 at 0:45
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ But the question is: can you prove it using induction? $\endgroup$ – Szeto Sep 13 '18 at 0:01
  • 2
    $\begingroup$ You can prove anything that is provable by an apparent induction that makes no use of the inductive hypotheses. (This was the drift of a good, if satirical, answer to this question that has now been delieted.) $\endgroup$ – Rob Arthan Sep 13 '18 at 0:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.