7

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?

Community
  • 1
  • 3
    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 07:15

6 Answers6

7

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

lhf
  • 216,483
  • 2
    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
  • Excuse me ... i can prove that $b=supX$ but i can't prove $b \in X$ ... can you please help me ? – Arman Malekzadeh Dec 02 '16 at 12:52
  • Indeed, is there a constructive proof that $b \in X$ ? By continuity, you can bound $f$ on $[b-\eta, b]$ and assert that $b-\eta$ is not $\sup X$. But does this allow you to assert that there constructively exists a point $y\in X$ above $b-\eta$ ? – V. Semeria Jan 03 '19 at 11:25
4

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!

Yuval Filmus
  • 57,157
3

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.

Najib Idrissi
  • 54,185
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.

Zarrax
  • 44,950
  • 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
  • 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$? – Qiaochu Yuan May 26 '11 at 16:22
  • $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$. – Zarrax May 26 '11 at 16:36
  • I just realized you don't even need $g(y)$ here; I edited the proof accordingly. – Zarrax May 26 '11 at 16:54
  • 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
  • Yes, your edit does exactly what I was thinking. Beat me by 1 minute! – Eric Naslund May 26 '11 at 16:58
  • At any rate, I think I've made this clear enough; you're under no obligation to believe it. – Zarrax May 26 '11 at 17:01
  • @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. – Qiaochu Yuan May 26 '11 at 17:37
  • 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
  • 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.... – N. S. May 26 '11 at 18:30
  • @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. – Zarrax May 26 '11 at 20:09
  • 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 :) – Zarrax May 26 '11 at 20:23
  • 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..... – N. S. May 26 '11 at 23:00
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....

N. S.
  • 132,525
0

Choose $x_n=\inf\{x:|f(x)|>n\}$, and note that this is bounded by $b$ and (non-strictly) increasing by construction. Now consider:

$$\sup_n {x_n}=\lim_{n \rightarrow \infty} x_n=x_\infty$$

Since $f$ is a real valued function also defined on the end points, there is some $M$ such that $f(x_\infty)=M-1$. Furthermore, since $f$ is continuous $$f(x_\infty)=\lim_{n \rightarrow \infty}f(x_n)=M-1.$$

Which concludes the proof. However, I would not consider this constructively acceptable since the least upper bound property is not constructively acceptable and we did not even construct the supremum. This is a direct proof, however.

Constructively the theorem may not even be true or relevant. According to Brouwer every function is uniformly continuous, while in Russian recursive mathematics it is possible to disprove the claim by use of Specker sequence. Hence Bishop's analysis (consistent with set theory) limits itself to uniformly continuous functions and the claim is unproved.

Dole
  • 2,653