# Does it follow?

1. Nov 22, 2009

### tauon

Here's a math problem that's giving me a head ache (though to some of you it might seem to be quite trivial)

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

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

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

So there is a family of $$r+1$$ 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 $$A_s$$ might contain no element from $$\bigcap_{i=1,r+1} A_i$$ so in the end it is possible $$\bigcap_{i=1,s} A_i = \emptyset$$ for some arbitrary $$A_k$$ 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. Nov 23, 2009

### bpet

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.

3. Nov 23, 2009

### tauon

oh, yes. I think you're right.

what do you mean?

edit: never mind, I understand what you meant now. thanks.

Last edited: Nov 23, 2009