# Union and intersections

Let's define $X_i$, $i \in \{1,2,...,n\}$ $n$ sets and $E_k$ the subset of the power set of $\{1,2,...,n\}$ whose elements have a cardinality $k$.

If $\displaystyle P=\bigcap_{I \in E_k}\,\bigcup_{i \in I}\:X_i$ and $\displaystyle Q=\bigcup_{I \in E_k}\,\bigcap_{i \in I\:}X_i$, how do I prove :

• if $k \leq\frac{n+1}{2}$ then $P \subset Q$.
• if $k \geq\frac{n+1}{2}$ then $Q \subset P$.

It's a homework so I don't want any complete answer, just a little bit of help to be able to start. I've tried to translate what I have and what I want to prove in terms of $\forall$ and $\exists$ but I don't know how to get further...

-
I am quite sure you mean $P\subseteq Q$ and $Q\subseteq P$. The element relation $\in$ doesn't seem to make sense here. – Stefan Geschke Dec 23 '11 at 13:54
Right, I made a little mistake when writing the question. I have changed it ! – Skydreamer Dec 23 '11 at 13:59
For the first problem, I can't see why the cardinality of J can lead to $P \subset Q$ that's to say in fact $x \in Q$ – Skydreamer Dec 23 '11 at 14:27
Thank you a lot :) I'm trying to solve the second now ! – Skydreamer Dec 23 '11 at 17:54

First of all, see my comment. Does this help?

Moreover, if $x\in P$, then for all $I\in E_k$ there is $i\in I$ with $x\in X_i$. But this means that there are at most $k-1$ different $i\in\{1,\dots,n\}$ with $x\not\in X_i$. If $k$ is small relative to $n$, then you will find $I\in E_k$ such that for all $i\in I$, $x\in X_i$.

The second part is similar.

-
I don't understand how you deduce there are at most $k-1$ different $i\in\{1,\dots,n\}$ with $i\not\in X_i$. But then ok, this proves what Davide said in his comment on the question with the J set and I don't know how this helps with the final deduction. Moreover, I can't suppose k is small relative to n I think ? – Skydreamer Dec 23 '11 at 14:19
By "$k$ is small relative to $n$" I mean $k\leq\frac{n+1}{2}$. And about the $k-1$ different $i\in\{1,\dots,n\}$, first of all, there is a typo, I meant $x\in X_i$, of course. I will edit this. Now for the argument: Suppose there are $k$ different $i$ such that $x\not\in X_i$. Then there is $I\in E_k$ such that for all $i\in I$, $x\not\in X_i$. But now $x\not\in\bigcup_{i\in I}X_i$ and hence $x\not\in P$, contradicting our assumption. – Stefan Geschke Dec 25 '11 at 7:23
Okay, I've managed to conclude I think :) Now, what should I prove first for the second problem to conclude it in a similiar way ? I've tried to found it out but definitely can't understand where this comes from... Thank you in advance ! – Skydreamer Dec 25 '11 at 12:33
For the second problem, take $x\in Q$. This means that for some $I\in E_k$, $x$ is an element of all $X_i$, $i\in I$. Now use $k\geq\frac{n+1}{2}$ to show that for all $I\in E_k$, there is $i\in I$ with $x\in X_i$. This gives you $x\in P$. – Stefan Geschke Dec 25 '11 at 14:00
Thank you ! I think I've found the second one. – Skydreamer Dec 26 '11 at 15:30