Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider the theorem for the continuous function:

Let $a<b$ be real numbers, and let $f:[a,b]\to{\bf R}$ be a function continuous on $[a,b]$. Then $f$ is a bounded function.

The proof in the classical textbook on real analysis uses the Heine-Borel theorem. It dose not say how to find the bound for $f$, but it show that having $f$ unbounded leads to a contradiction.

Here are my questions:

  • Is there a direct [EDITED: constructive] proof for this theorem?

  • More generally, can a theorem in mathematics always have a constructive proof? Or what kind of statements do not have any constructive proof, say, one has to use techniques such as "proof by contradiction" in order to prove it?

share|improve this question
1  
Given the Gödel-Gentzen transformation you could argue that any theorem in mathematics (ZF(C)) can be proved constructively. You actually prove a classically equivalent statement (and it is not informative given that the final result is a negation) but... –  gallais May 26 '11 at 7:15
add comment

5 Answers 5

up vote 7 down vote accepted

There's a natural proof using sup. Consider the set $X=\{ x \in [a,b] : f \mbox{ is bounded in } [a,x] \}$. Then $X$ is non-empty and no $t<b$ is an upper bound for $X$. Hence $b=\sup X$ and $f$ is bounded in the whole interval. This argument is actually the same one used in Heine-Borel: for continuous functions in compact sets, locally bounded implies globally bounded. That $f$ is locally bounded comes from continuity and is used to prove that no $t<b$ is an upper bound for $X$.

share|improve this answer
1  
Is this supposed to be a proof? –  Glen Wheeler May 26 '11 at 14:21
1  
@Glen, yes. Or a sketch, rather. This proof is given in full in Spivak's Calculus, Theorem 7-2. –  lhf May 26 '11 at 14:58
add comment

There is no a-priori bound on the function: consider the constant function $f = M$. Also, the maximum can be attained at any given point - just take any appropriate quadratic.

As for the second question, that really depends on your notion of "directly".

In constructive mathematics, I believe that a continuous function is supplied with some "modulus of continuity" which immediately implies (directly) boundedness. Whether one can prove intuitionistically that the $\epsilon-\delta$ definition of continuity implies boundedness - probably not, but ask an expert!

share|improve this answer
add comment

As for your question about statements that can be proven "directly" or not, I find that this article by Tim Gowers and the resulting discussion in the comments is very interesting. It even addresses the Heine-Borel theorem.

share|improve this answer
add comment

Let $\{x_n\}_{n=1}^{\infty}$ be a sequence of points such that $|f(x_n)|$ converges to $M = \sup_x |f(x)|$. You can pass to a convergent subsequence $\{x_{n_k}\}_{k=1}^{\infty}$ which converges to some $y \in [a,b]$. Then by continuity of $f(x)$ $$|f(y)| = \lim_{k \rightarrow \infty} |f(x_{n_k})| = M$$ So $f(y) = \pm M$; therefore $M$ is finite and $|f(y)|$ achieves the value $M$. The proof of the existence of convergent subsequences as in the proof of the Bolzano-Weierstrass theorem, using divisions into halves and so on, is not by contradiction and is reasonably constructive.

share|improve this answer
1  
I don't see how this is any more direct than the proof outlined in the OP. –  Qiaochu Yuan May 26 '11 at 15:42
    
it's not a proof by contradiction, the existence of a convergent subsequence is not proven in that way. This is what the poster asked for. –  Zarrax May 26 '11 at 16:00
    
Also, the usual proof of the existence of convergent subsequences; i.e. repeated dividing into halves as in the Heine-Borel theorem, is appropriately constructive given the generality of the question. –  Zarrax May 26 '11 at 16:13
1  
@Qiaochu, @Zarrax: I agree with Qiaochu here, this proof doesn't completely work for me. It seems like you are saying this: "Let $M$ be the supremum. Then by sequence argument, and continuity, there exists $y$ such that $f(y)=M$. But $f(y)\in\mathbb{R}$ so $M<\infty$." Worded this way, it doesn't completely make sense, and is just a proof by contradiction in disguise. I feel the $g(x)$ you made is just to disguise this further. –  Eric Naslund May 26 '11 at 16:56
1  
This is exactly the proof in Tim Gower's article, few posts above ;) And he makes an interesting point about it: how do you prove that $x_n$ exists? If $M$ is finite, there is nothing to prove, but if $M$ is infinite, the existence of $x_n$ is based on the assumption that $M$ is infinite, how is this different than contradiction? –  N. S. May 26 '11 at 18:20
show 10 more comments

Would this be considered a direct proof?

Pick $x_n$ a sequence which is dense in $[0,1]$. Let $y_n =f(x_n)$ and $z_n =\max_{1 \leq i \leq n} y_i$.

Then $z_n$ is increasing, and thus has a limit.

Let $A:= \{ m | z_m > z_{m-1} \}$. If $A$ is finite, it has a maximum $k$ and since $y_n \leq z_k$ for each $n$, it follows that $z_m$ is the maximum of $f(x)$.

If $A$ is infinite, then order its elements incresingly $n_1 < n_2 < ..< n_k< ...$. Then by the definition of $A$, the sequence $y_{n_k}$ is increasing and

$$y_{n_k}=z_{n_k}= \max_{1 \leq i \leq n_k} y_i (*) \,.$$

Finally pick a convergent subsequence $x_{m_l}$ of $x_{n_k}$. Let $a$ be the limit of this.

By continuity

$$\lim_{l \to \infty} y_{m_l}= f(a) \,.$$

Since $y_{m_l}$ is a subsequence of $y_{n_k}$, and $y_{n_k}$ is increasing we get

$$\lim_{k \to \infty} y_{n_k}= f(a) \,.$$

But then, since $y_{n_k}$ is increasing, we get from $(*)$ that $y_n \leq f(a)$ for all $n$. Now the density of $\{ x_n \}$ completes the proof.

Note We actually used Heine-Borel theorem in the proof, when we picked a convergent subsequence of $x_{k_n}$ (unless of course one defines compactness that way). No matter what proof one tries, since the same theoremfails for $(0,1)$, somehow compactness is bounded to come in play....

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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