How Can We Prove Sup g(y) ≤ Inf f(x)?

  • Thread starter Thread starter jmjlt88
  • Start date Start date
jmjlt88
Messages
94
Reaction score
0
Let X and Y be nonempty sets and let h: X x Y→ℝ
Define f: X →ℝ and g: Y→ℝ by the following:

f(x)=sup{h(x,y): y in Y} and g(y) = inf{h(x,y): x in X}

Prove that sup{g(y): y in Y} ≤ inf{f(x): x in X}

Attempt at solution:
Pick y' in Y. Then g(y')≤h(x,y') for all x in X. Hence, there exist some x' such that g(y')≤h(x',y').
Then, h(x',y')≤ sup{h(x',y): y in Y} = f(x')... Not too sure where to go from here... A small hint would be great!

Thanks!
 
Physics news on Phys.org
Wait... I think I got it..

Pick any y' and x'. Then, g(y') ≤ h(x,y') for all x; therefore g(y')≤h(x',y'). Now, h(x',y')≤sup{h(x',y) : y in Y}=f(x'). This established the following inequality:

g(y')≤f(x').​

Because x' and y' were arbitrary, we conclude g(y)≤f(x) for all x,y. Thus g(y) is a lower bound for the set {f(x): x in X} for all y; it follows that g(y)≤inf{f(x):x in X} for all y. Then, since g(y)≤inf{f(x):x in X}, inf{f(x):x in X} is an upper bound for the set {g(y): y in Y} ... the rest is history! :)
 
jmjlt88 said:
Wait... I think I got it..

Pick any y' and x'. Then, g(y') ≤ h(x,y') for all x; therefore g(y')≤h(x',y'). Now, h(x',y')≤sup{h(x',y) : y in Y}=f(x'). This established the following inequality:

g(y')≤f(x').​

Because x' and y' were arbitrary, we conclude g(y)≤f(x) for all x,y. Thus g(y) is a lower bound for the set {f(x): x in X} for all y; it follows that g(y)≤inf{f(x):x in X} for all y. Then, since g(y)≤inf{f(x):x in X}, inf{f(x):x in X} is an upper bound for the set {g(y): y in Y} ... the rest is history! :)

Sounds ok to me.
 
Thread 'Use greedy vertex coloring algorithm to prove the upper bound of χ'
Hi! I am struggling with the exercise I mentioned under "Homework statement". The exercise is about a specific "greedy vertex coloring algorithm". One definition (which matches what my book uses) can be found here: https://people.cs.uchicago.edu/~laci/HANDOUTS/greedycoloring.pdf Here is also a screenshot of the relevant parts of the linked PDF, i.e. the def. of the algorithm: Sadly I don't have much to show as far as a solution attempt goes, as I am stuck on how to proceed. I thought...
Back
Top