7
$\begingroup$

Consider the theorem for the continuous function:

Let $a 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?

  • 2
    Given the [Gödel-Gentzen transformation](http://en.wikipedia.org/wiki/G%C3%B6del%E2%80%93Gentzen_negative_translation) 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...2011-05-26

5 Answers 5

8

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 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 is an upper bound for $X$.

  • 1
    Is this supposed to be a proof?2011-05-26
  • 1
    @Glen, yes. Or a sketch, rather. This proof is given in full in Spivak's *Calculus*, Theorem 7-2.2011-05-26
  • 0
    Excuse me ... i can prove that $b=supX$ but i can't prove $b \in X$ ... can you please help me ?2016-12-02
5

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!

4

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.

2

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.

  • 1
    I don't see how this is any more direct than the proof outlined in the OP.2011-05-26
  • 0
    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.2011-05-26
  • 0
    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.2011-05-26
  • 0
    I guess what I meant to say is, I don't see how this is a proof. How do you know that $g(y) > 1$?2011-05-26
  • 0
    $g(y)$ is always ${1 \over 1 + |f(y)|}$, that's all you need. It's continuous because $f$ is, and you don't need anything about the magnitude of $f$ or $g$.2011-05-26
  • 0
    I just realized you don't even need $g(y)$ here; I edited the proof accordingly.2011-05-26
  • 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.2011-05-26
  • 0
    Yes, your edit does exactly what I was thinking. Beat me by 1 minute!2011-05-26
  • 0
    At any rate, I think I've made this clear enough; you're under no obligation to believe it.2011-05-26
  • 0
    @Zarrax: my apologies. Your use of $g$ was confusing; it didn't seem necessary and I couldn't figure out if you were using it to hide a step or what. It's fine now.2011-05-26
  • 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?2011-05-26
  • 0
    This is more a phylosophical question but suppose we prove $P \Rightarrow Q$ by contradiction. Is the following proof the same, or is it constructive? We break the proof in two cases: Case 1: Q is true (nothing to prove)..... Case 2: Q is false... We show that this is not possible....2011-05-26
  • 0
    @user9176: I'm breaking into infinitely many cases really, for each $M$ I am constructing a sequence of $x_n$ where $|f(x_n)| > M - {1 \over n}$. If $M$ is infinity then $|f(x_n)| > n$. Basically all that's going on here is: I have a sequence $a_k = |f(x_{n_k})|$ that either converges to a finite limit or infinity. Then I show using continuity that it's a finite limit. There's no proof by contradiction; at no point do I assume $M$ is infinity. The definition of the $x_k$ might be via cases in the above sense... but that's not the same as a proof by contradiction.2011-05-26
  • 0
    One other thing.. if the fact that it's infinity that is worrying you, you can define $x_n$ in terms of $g(x) = {1 \over 1 + |f(x)|}$ as I did before. Although this adds a layer of complication that bothered people above, this more graphically indicates why "infinity doesn't matter here". I found Gowers's blog post, and I really do not agree with him. But it does explain why I got such a response to what I thought was a relatively uncontroversial posting :)2011-05-26
  • 0
    Nice Idea. Then your proof can be simplified nicely the following way: Step 1: prove the weaker result If $f$ is continuous and bounded on $[0,1]$ then $f$ attains its maximum and minimum. Step 2: To get the result in general, apply Theorem from Step 1 to your function $g$, or maybe to $\arctan(f(x))$. Since the new function attains the maximul, it means $f$ attains its maximum thus it is bounded.....2011-05-26
1

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....