Would anyone like to comment on my proof?

[Jyan]

I previously posted this related thread https://www.physicsforums.com/showthread.php?p=4663806&posted=1#post4663806

I am working on some MIT OCW for probability theory (http://ocw.mit.edu/courses/electric...y-fall-2008/assignments/MIT6_436JF08_hw01.pdf) I attempted exercise 3a and wrote it out here, but quickly realized it was wrong because you can't necessarily find an ordering that is so convenient. I've been working on this problem for hours though, anyone able to provide some assistance?

My previous attempt:

Given $$f : A\times B \rightarrow \mathbb{R}$$

Where A,B are finite and non-empty.

Prove: $$\max_{x\in A} \min_{y\in B} f(x,y) \le \min_{y\in B} \max_{x\in A} f(x,y)$$

proof:

Let N be the number of elements in A, and M the number of elements in B.

Construct an ordered list of tuples,

$$C = \big[(x_0, y_0), ... , (x_0, y_M), (x_1, y_0), ... ,(x_1, y_M), ... , (x_N, y_0), ... , (x_N, y_M)\big]$$

According to

$$(x,y) \le (x', y') \Longleftrightarrow f(x,y) \le f(x', y')$$

That is, C is ordered such that the smallest elements of C produce the smallest values of f, and the largest elements of C produce the largest values of f.

Now construct two new sets A' and B' where

$$A' = Range \big\{\min_{y\in B} f(x,y)\big\} = \big\{f(x,y_0): x\in A\big\}$$

$$B' = Range \big\{\max_{x\in a} f(x,y)\big\} = \big\{f(x_N, y): y\in B\big\}$$

By the ordering on C

$$\forall a,b \in A', B' \space a \le b$$

$$\blacksquare$$

I feel like I'm pretty close... I just need to fix the problem with creating the ordering for C.

 

[pasmith]

You're overthinking this.

I previously posted this related thread https://www.physicsforums.com/showthread.php?p=4663806&posted=1#post4663806

I am working on some MIT OCW for probability theory (http://ocw.mit.edu/courses/electric...y-fall-2008/assignments/MIT6_436JF08_hw01.pdf) I attempted exercise 3a and wrote it out here, but quickly realized it was wrong because you can't necessarily find an ordering that is so convenient. I've been working on this problem for hours though, anyone able to provide some assistance?

My previous attempt:

Given $$f : A\times B \rightarrow \mathbb{R}$$

Where A,B are finite and non-empty.

Prove: $$\max_{x\in A} \min_{y\in B} f(x,y) \le \min_{y\in B} \max_{x\in A} f(x,y)$$

Let's unpack this. Imagine a grid, in which the columns are labelled by $A$ and the rows are labelled by $B$. Then
$$g(x) = \min_{y \in B} f(x,y)$$
is the smallest element in column $x$ and
$$h(y) = \max_{x \in A} f(x,y)$$
is the largest element in row $y$. Now you're asked to show that
$$\max_{x \in A} g(x) \leq \min_{y \in B} h(y).$$
The way to do that is to show that, for all $x \in A$ and all $y \in B$, we have
$$g(x) \leq h(y)$$
or, in other words, the smallest element in column $x$ is less than or equal to the largest element in row $y$.

We know that column $x$ and row $y$ have a common element: $f(x,y)$.

Can you use that common element to show that $g(x) \leq h(y)$?

 

[FactChecker]

Since for all x, y,
$$f(x,y) \le \max_{z\in A} f(z,y)$$
Minimizing both sides over y in B, we have, for all x,
$$\min_{y\in B} f(x,y) \le \min_{y\in B} \max_{z\in A} f(z,y)$$

So
$$\max_{x\in A} \min_{y\in B} f(x,y) \le \min_{y\in B} \max_{x\in A} f(x,y)$$

 

[Jyan]

$$g(x) = \min_{y\in B}f(x,y)$$

$$h(y) = \max_{x\in A}f(x,y)$$

$$\forall x,y \in A,B \space \space g(x) \le f(x,y), \space h(y) \ge f(x,y)$$

$$\therefore g(x) \le f(x,y) \le h(y)$$

And,

$$\max_{x\in A} \min_{y\in B} f(x,y) \le \min_{y\in B} \max_{x \in A} f(x,y)$$

Is this correct?

 

[Jyan]

I don't see any complications for the non-finite case either. Just replace min with inf and max with sup. Am I mistaken?

 

[FactChecker]

I don't see any complications for the non-finite case either. Just replace min with inf and max with sup. Am I mistaken?

Looks good to me.

 

[Stephen Tashi]

I don't see any complications for the non-finite case either. Just replace min with inf and max with sup. Am I mistaken?

Are we going to allow an infimum to be a "number" like $-\infty$ ?

 

[Jyan]

Are we going to allow an infimum to be a "number" like $-\infty$ ?

That is typical for the infimum isn't it? Does this cause problems?

 

[FactChecker]

That is typical for the infimum isn't it? Does this cause problems?

Since "minimum" often implies that the minimum value is actually attained, the proofs are better on infinite sets with "infimum". ∞ should not be a problem, as long as we agree that -∞ = -∞ and ∞ = ∞.