Here's a math problem that's giving me a head ache (though to some of you it might seem to be quite trivial)(adsbygoogle = window.adsbygoogle || []).push({});

[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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Does it follow?

**Physics Forums | Science Articles, Homework Help, Discussion**