Is this a valid proof for the Extreme Value Theorem?

  • #1
941
60
Summary:
Let ##f## be a continuous function defined on a sequentially compact set ##K##. Then there is a point ##x_0\in K## s.t. ##f(x_0)=\sup f(K)##.
If ##f## is a constant function, then choose any point ##x_0##. For any ##x\in K##, ##f(x_0)\geq f(x)## and there is a point ##x_0\in K## s.t. ##f(x_0)=\sup f(K)=\sup\{f(x_0)\}=f(x_0)##.

Now assume that ##f## is not a constant function.

Construct a sequence of points ##x_n\in K## as follows:

1. Pick an arbitrary point ##x_1\in K##.
2. Pick a point ##x_2\in K## s.t. ##f(x_2)>f(x_1)##.
3. Repeat ad-nauseum. If there comes a point where this is impossible, then the last term of the sequence ##\{x_n\}## must be the point at which ##f## achieves its maximum.

It follows from sequential compactness that there is a subsequence ##\{x_{n_k}\}## converging to some point ##x_0\in K##. By construction, ##\{f(x_{n_k})\}## is an increasing sequence of points.

If the sequence ##\{f(x_{n_k})\}## is unbounded, then there exists an integer ##m\in \mathbb{N}## s.t. ##f(x_m)>f(x_0)##. Set ##\epsilon=f(x_m)-f(x_0)##. Then there is an integer ##N\in\mathbb{N}## s.t.:

\begin{equation}
n_k\geq N\Longrightarrow |f(x_{n_k})-f(x_0)|<\epsilon
\end{equation}

If ##m\geq N##, choose ##n_k=m##:

\begin{equation}
f(x_m)-f(x_0)>f(x_m)-f(x_0)
\end{equation}

This is a blatant contradiction.

If ##m<N##, then for ##n_k\geq N##:

\begin{eqnarray}
f(x_m)-f(x_0)>f(x_{n_k})-f(x_0)\\
f(x_m)>f(x_{n_k})
\end{eqnarray}

But ##n_k>m##, which contradicts the fact that ##\{f(x_{n_k})\}## is an increasing sequence of points.

Hence, the sequence ##\{f(x_{n_k})\}## is bounded and so has finite cardinality. The last term of the sequence, therefore, is the point at which ##f## achieves its maximum on ##K##.
 
Last edited:

Answers and Replies

  • #2
Infrared
Science Advisor
Gold Member
915
507
Hence, the sequence ##\{f(x_{n_k})\}## is bounded and so has finite cardinality.
This is false.

In fact, you never used continuity of ##f## in your proof so something must be wrong, as this statement is definitely wrong for discontinuous functions!

Instead, how about you consider a sequence ##x_n## so that ##f(x_n)## converges to ##\sup f(K)?##
 
  • #3
941
60
I think I cited continuity in equation (1) but never explicitly stated it.
 
  • #4
Infrared
Science Advisor
Gold Member
915
507
I think I cited continuity in equation (1) but never explicitly stated it.

You're right, I missed that. But anyway the claim I quoted above is wrong: the set ##\{0,1/2,2/3,3/4,...\}## is bounded and does not have finite cardinality.
 
  • #5
941
60
What's the sequentially compact set that you're using to derive that sequence with the algorithm I wrote?
 
  • #6
Infrared
Science Advisor
Gold Member
915
507
Let ##f(x)=x## on the interval ##[0,2]## and use the sequence ##0,1/2,2/3,3/4,....##
 
  • #7
941
60
Oh. I see. My algorithm fails because you can choose infinitely many points less than the infimum of ##f(K)##.
 
  • #8
941
60
Let ##\{x_n\}## be a sequence contained in ##K##. By sequential compactness, there is a sequence ##\{x_{n_k}\}## whose terms converge to some ##x_0\in K##.

Choose ##\epsilon=1##. By continuity of ##f##, there is an integer ##N## with the property that:

\begin{equation}
n_k\geq N\Longrightarrow|f(x_{n_k})-f(x_0)|<1
\end{equation}

It follows that for ##n_k\geq N##, ##f(x_{n_k})<f(x_0)+1##. Denote ##M'\equiv\sup\{|a_i|:1\leq i\leq N-1\}##. For all ##n_k<N##, ##a_{n_k}\leq M'##. Now denote ##M\equiv\sup\{M',f(x_0)+1\}##. This is an upper bound for ##\{f(x_{n_k})\}## for all sequences ##\{x_{n_k}\}##.

Construct a sequence of points ##y_n\in K## as follows:

1. Pick an arbitrary point ##y_1\in K##.
2. Pick a point ##y_2\in K## s.t. ##f(y_2)>f(y_1)##.
3. Repeat ad-nauseum.

Assume without loss of generality that the sequence ##\{y_n\}## converges to some point ##y_0\in K##. We note that the sequence ##\{f(y_n)\}## is increasing and bounded from above. Therefore, it must converge to its supremum.

By continuity, the sequence ##\{f(y_n)\}## must converge to ##f(y_0)##, and it cannot converge to two different points.

Therefore, ##f(y_0)\equiv\sup \{f(x_n)\}##.

%%%

I don't think it's correct for two reasons:

1. In line 3, I described an upper bound for the images of the terms of the subsequence of the original sequence but not for images of the terms that were discarded in order to yield aforementioned subsequence.
2. It might not even be true that ##\sup \{f(x_n)\}\equiv \sup f(K)##.
 
  • #10
Infrared
Science Advisor
Gold Member
915
507
You're correct in the reason why your argument fails. I'm also unsure what your first paragraph has to do with the rest of your argument.

Instead, can you follow the suggestion I gave in post 2?
Instead, how about you consider a sequence ##x_n## so that ##f(x_n)## converges to ##\sup f(K)?##
Depending on how you write the argument, you may need to first show that ##f(K)## is bounded.

@Svein Using the axiom of choice is the least of the issues here.
 
  • #11
941
60
I'm also unsure what your first paragraph has to do with the rest of your argument.
I had to prove that ##f## is bounded, by proving that ##\{f(y_{n_k})\}## is bounded, which was sort of dumb in hindsight.

you may need to first show that ##f(K)## is bounded.
I'm not sure if it is possible to do this with the notion of sequential compactness alone. I think I would have to use the notion of compactness in order to do so. I actually have learned it in my real analysis class three years ago, but it hasn't yet been covered in the book I'm using. Truthfully, I just saw the author's proof for the Extreme Value Theorem, thought it wasn't all that well-explained, then tried to write my own proof of it.

%%%p. 114 of this book

Theorem 4.3.2 Let ##K## be sequentially compact and let ##f :K\rightarrow\mathbb{R}## be continuous. Then ##f## achieves its maximum and its minimum on ##K##. This means there exist ##x_1, x_2\in K## such that for all ##x\in K##, ##f (x_1)\leq f(x)\leq f (x_2)##.

Proof: Let ##M\equiv \sup \{f (x) : x \in K\}##. From the definition of the supremum, there exists ##f(x_n)## such that ##\lim_{n\rightarrow\infty} f(x_n) = M##. This is because if ##l < M##, there must be some ##x## such that ##f(x)\in (l, M]## since otherwise ##M## is not as defined. By sequential compactness, there is a subsequence ##\{x_{n_k}\}## such that ##\lim_{k\rightarrow\infty} x_{n_k}=x\in K##. Then by continuity, ##f(x) = \lim_{k\rightarrow\infty} f (x_{n_k}) = M##. That ##f## achieves its minimum is proved exactly the same way. In particular, this shows that every function continuous on a sequentially compact set is bounded.

%%%

I'm contemplating using another book or something, but I am not fond of the idea of starting over with another one. Anyway, I'll get started on the proof revision tomorrow. Thanks for all the feedback you gave me today. It was helpful.
 
Last edited:
  • #12
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
4,527
571
It's easy to show f is bounded with sequential compactness. Suppose it has no upper bound. Then you can find a sequence ##x_n## such that ##f(x_n)>n##. Pick a convergent subsequence. What do you get?
 
  • #13
941
60
What do you get?
I think you have a sequence of ##f(x_{n_k})## that increase without bound and somehow converge to some real number ##L## at the same time. This isn't possible, because you can always find natural numbers bigger than ##L## (by the Archimedean principle), and by proxy, terms of the sequence whose distance from ##L## is non-negligible.
 
  • #14
941
60
Suppose ##f## is unbounded. Construct a sequence ##\{x_n\}\subset K## with the property that ##f(x_n)>n##. By sequential compactness, there exists a subsequence ##\{x_{n_k}\}## whose terms converge to some point ##x_0\in K##.

By the Archimedean principle, there is an integer ##N_0\in \mathbb{N}## s.t. ##N_0>f(x_0)##. Set ##\epsilon=N_0-f(x_0)##. There exists an integer ##N## with the property that ##n_k\geq N\Longrightarrow |f(x_{n_k})-f(x_0)|<N_0-f(x_0)##. As a result:

\begin{equation}
n_k<f(x_{n_k})<N_0
\end{equation}

If ##N_0<N##, then this is a contradiction by the transitive property.
If ##N_0\geq N##, then it suffices to choose ##n_k=N_0+1##, which would yield yet another contradiction.

Hence, ##f## must be bounded.

Denote ##y\equiv \sup f(K)##. There exists a sequence of ##z_n## s.t. the terms ##f(z_n)## converge to ##y##. Moreover, there is a subsequence ##z_{n_k}## that converges to some ##z_0\in K##. By continuity, ##f(z_{n_k})## must converge to ##f(z_0)##. Also, ##f(z_{n_k})## is a term of a subsequence originally belonging to a convergent sequence. Therefore, ##f(z_{n_k})## must converge to the limit of its parent sequence and so we conclude that ##y=f(z_0)## with ##z_0\in K##.
 
  • #15
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
4,527
571
This looks right to me!

I don't like the part where you have a string of inequalities and then say "by the transitive property", since it's not obvious which of the inequalities you are using. I think you should just restate it. But I think everything you wrote here is correct. This is definitely that best attempt at a proof that I have seen you post here, nice work.
 

Related Threads on Is this a valid proof for the Extreme Value Theorem?

Replies
9
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
21
Views
2K
  • Last Post
Replies
2
Views
1K
Replies
2
Views
1K
Replies
4
Views
21K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
2
Views
2K
Top