Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Would anyone like to comment on my proof?

  1. Feb 18, 2014 #1
    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 [tex] f : A\times B \rightarrow \mathbb{R}[/tex]

    Where A,B are finite and non-empty.

    Prove: [tex] \max_{x\in A} \min_{y\in B} f(x,y) \le \min_{y\in B} \max_{x\in A} f(x,y) [/tex]

    proof:

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

    Construct an ordered list of tuples,

    [tex] 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] [/tex]

    According to

    [tex] (x,y) \le (x', y') \Longleftrightarrow f(x,y) \le f(x', y') [/tex]

    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

    [tex] A' = Range \big\{\min_{y\in B} f(x,y)\big\} = \big\{f(x,y_0): x\in A\big\}[/tex]

    [tex] B' = Range \big\{\max_{x\in a} f(x,y)\big\} = \big\{f(x_N, y): y\in B\big\}[/tex]

    By the ordering on C

    [tex] \forall a,b \in A', B' \space a \le b [/tex]

    [tex] \blacksquare [/tex]

    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. jcsd
  3. Feb 19, 2014 #2

    pasmith

    User Avatar
    Homework Helper

    You're overthinking this.

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

    We know that column [itex]x[/itex] and row [itex]y[/itex] have a common element: [itex]f(x,y)[/itex].

    Can you use that common element to show that [itex]g(x) \leq h(y)[/itex]?
     
  4. Feb 19, 2014 #3

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

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

    So
    [tex] \max_{x\in A} \min_{y\in B} f(x,y) \le \min_{y\in B} \max_{x\in A} f(x,y) [/tex]
     
  5. Feb 19, 2014 #4
    [tex]g(x) = \min_{y\in B}f(x,y)[/tex]

    [tex]h(y) = \max_{x\in A}f(x,y)[/tex]

    [tex] \forall x,y \in A,B \space \space g(x) \le f(x,y), \space h(y) \ge f(x,y)[/tex]

    [tex] \therefore g(x) \le f(x,y) \le h(y) [/tex]

    And,

    [tex] \max_{x\in A} \min_{y\in B} f(x,y) \le \min_{y\in B} \max_{x \in A} f(x,y) [/tex]

    Is this correct?
     
  6. Feb 19, 2014 #5
    I don't see any complications for the non-finite case either. Just replace min with inf and max with sup. Am I mistaken?
     
  7. Feb 19, 2014 #6

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    Looks good to me.
     
  8. Feb 21, 2014 #7

    Stephen Tashi

    User Avatar
    Science Advisor

    Are we going to allow an infimum to be a "number" like [itex] -\infty [/itex] ?
     
  9. Feb 21, 2014 #8
    That is typical for the infimum isn't it? Does this cause problems?
     
  10. Feb 21, 2014 #9

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    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 ∞ = ∞.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Would anyone like to comment on my proof?
  1. Topology proof (Replies: 1)

  2. Proof Writing (Replies: 3)

Loading...