1
$\begingroup$

In the analysis book I am studying, in the chapter about the real number field, there is the standard question about the intersection of nested intervals (link1), and it is (unlike in link1) presented as the intersection of infinitely many intervals: $\cap_{i=1}^{\infty} A_i $ with Ai being the closed intervals.

I first wrote a proof by induction, which is very simple and possible, but it turns out that a proof by induction will prove something else, namely that this holds true up to 'any' natural $\cap_{i=1}^{n}A_i$, but it does not prove what is requested.

Now I definitely agree that what I proved is something else, and I can intuitively see why, so the question is not about that.

The question is: What is the formal/rigorous explanation of the exact difference between what an induction proof proves, and what is being requested, which can only be proved using the 'completeness axiom' (or equivalent).

(I am aware of the seemingly similar question, but it was quite vague and was therefore closed)

  • 1
    You may want to write out the entire problem and the problem you are trying to solve. The link is no longer working.2012-12-20

2 Answers 2

1

You proved:

$\forall n: P(\bigcap_{i=1}^n A_i)$

for some predicate, $P$.

That is a different statement than:

$P(\bigcap_{i=1}^\infty A_i)$

It's not clear what more you want for an answer, but induction always proves "$\forall n\in \mathbb N:\dots$". (There are other types of induction, but I am assuming we are talking about this case.)

Basically, $\infty$ is not a natural number.

In way to see this is to try a simpler example. Let $Q(n)$ be the statement "$n$ is not infinite." Then, assuming the axiom:

If $x$ is not infinite, then $x+1$ is not infinite.

You could prove $\forall n:Q(n)$ by induction, but $Q(\infty)$ would not be true.

From your question in comments, I add, the first formulation isn't interesting. Indeed, the first formulation is true for any sequence of nested non-empty sets.

The second formulation is not true in general, but is true when the $A_i$ are nested closed intervals. It is interesting precisely because it is not obviously true.

For example, if the condition were only that the $A_i$ are closed but not necessarily intervals, it would not be true.

If the condition were that the $A_i$ were intervals, but possible open on one or both ends, then it would not be true.

There is something, then, that is different about "closed intervals."

  • 0
    Yeah, it is quite possible that the second formulation is used only as a lemma to get to B-W. But it is an interesting formulation of the idea of "completeness" that has merit on its own - in particular, the notion that you need both "closed" and "interval" for it to work. It turns out, there is a notion you might encounter later called "compactness", and this theorem is true if the $A_i$ are "compact," which, in this instance, means "closed and bounded."2012-12-20
1

Induction proves that a proposition $P$ holds for all natural numbers, given that the induction hypotheses are satisfied.

Using induction you can indeed prove that $\cap_{i=1}^n A_i=A_n$ for every $n$, but that does not buy you anything. You are still stuck with the $A_i$'s.

The difference between the two is this:

Induction: You prove "$A_n$ is exactly the set of points in the first $n$ intervals" for all $n$

What you really want to prove: "there is exactly one point contained in all of the $A_i$".