4
$\begingroup$

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

Thank you in advance !

  • 1
    I am quite sure you mean $P\subseteq Q$ and $Q\subseteq P$. The element relation $\in$ doesn't seem to make sense here.2011-12-23
  • 0
    Right, I made a little mistake when writing the question. I have changed it !2011-12-23
  • 0
    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$2011-12-23
  • 0
    Thank you a lot :) I'm trying to solve the second now !2011-12-23
  • 0
    possible duplicate of [An Intuition to An Inclusion: "Union of Intersections" vs "Intersection of Unions"](http://math.stackexchange.com/questions/18138/an-intuition-to-an-inclusion-union-of-intersections-vs-intersection-of-union)2014-12-11

1 Answers 1

3

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.

  • 0
    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 ?2011-12-23
  • 0
    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.2011-12-25
  • 0
    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 !2011-12-25
  • 0
    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$.2011-12-25
  • 0
    Thank you ! I think I've found the second one.2011-12-26