- #1

tauon

- 90

- 0

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