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

Does it follow?

  1. Nov 22, 2009 #1
    Here's a math problem that's giving me a head ache (though to some of you it might seem to be quite trivial)

    [tex]r,s\in N^\ast[/tex] , [tex]r+1\leq s[/tex] ; [tex]|A_i|=r, \forall i\in \{1,2,...,s\}[/tex]
    the intersection of any [tex]r+1[/tex] of sets [tex]A_i[/tex] is nonempty [1]

    prove that
    [tex]\bigcap_{i=1,s} A_i \neq \emptyset[/tex] [C]
    At first I thought about it like this:

    by reductio ad absurdum, suppose
    [tex]\bigcap_{i=1,s} A_i = \emptyset[/tex]
    we can arbitrarily chose an [tex] A_k =\{x_1 , ..., x_r\}[/tex] then [tex]\exists i_1, ... , i_r \in \{1, ... ,s\}[/tex] so that [tex] x_1 \not\in A_{i_1}, ... , x_r \not\in A_{i_r}[/tex]
    [tex]\Rightarrow A_k\cap A_{i_1} \cap ... \cap A_{i_r} = \emptyset[/tex] (dem: if the contrary is true and the intersection is nonempty then at least one element of [tex]A_k[/tex] is in all the sets- contradiction with how the [tex]A_{i_j}[/tex] family of sets was defined)

    So there is a family of [tex]r+1[/tex] sets with an empty interesection- contradiction with [1] therefore [C] is true.

    But then I thought: wait a minute. That doesn't prove [C], it only "verifies" [1], since the last [tex]A_s[/tex] might contain no element from [tex]\bigcap_{i=1,r+1} A_i[/tex] so in the end it is possible [tex]\bigcap_{i=1,s} A_i = \emptyset[/tex] for some arbitrary [tex]A_k[/tex] thus constructed.

    And now I'm confused and I don't know if I solved the problem right or not... what part am I doing wrong here?

    ps: sorry for the messy post, I'm a beginner with the math bbcode.
  2. jcsd
  3. Nov 23, 2009 #2
    No your original proof looks right - only note that the i1,...,ir are not necessarily distinct but this is easy to fix - shows why r+1<=s is necessary.
  4. Nov 23, 2009 #3
    oh, yes. I think you're right.

    what do you mean?

    edit: never mind, I understand what you meant now. thanks. :smile:
    Last edited: Nov 23, 2009
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook