# Would anyone like to comment on my proof?

1. Feb 18, 2014

### Jyan

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.

Last edited: Feb 18, 2014
2. Feb 19, 2014

### pasmith

You're overthinking this.

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)$?

3. Feb 19, 2014

### 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)$$

4. Feb 19, 2014

### 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?

5. Feb 19, 2014

### 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?

6. Feb 19, 2014

### FactChecker

Looks good to me.

7. Feb 21, 2014

### Stephen Tashi

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

8. Feb 21, 2014

### Jyan

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

9. Feb 21, 2014

### FactChecker

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