Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 !

share|improve this question
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. –  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
    

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.