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 A, B, and C be arbitrary sets taken from the positive integers.

I have to prove or disprove that: A ∩ B ∩ C = ∅, then (A ⊆ ~B) or (A ⊆ ~C)

Here is my disproof using a counterexample:

If A = {} the empty set, B = {2, 3}, C = {4, 5}

With these sets defined for A, B, and C, the intersection includes the disjoint set, and then that would lead to A being a subset of B or A being a subset of C which counteracts that

if A ∩ B ∩ C = ∅, then (A ⊆ ~B) or (A ⊆ ~C)

Is this a sufficient proof?

share|improve this question
1  
The empty set is a subset of any set so you do not arrive at a contradiction. I'm not sure if the "~" is significant in your notation but ignoring it, the claim is clearly false. Just take A,B, and C to be the singletons {1}, {2}, and {3} respectively. The intersection of the three is empty and none of these set s is a subset of the others. –  user3180 Aug 11 '11 at 23:29
1  
the ~ means complement, so it is important –  Krysten Aug 11 '11 at 23:31
1  
Ok, so ignore my first counterexample. But the empty set is still a subset of every set. How about this. Take A,B, and C to be {1,2}, {2,3}, and {1,3}. If I understand the question correctly, this should work. –  user3180 Aug 11 '11 at 23:34
    
Right, so why can't I use that to disprove this –  Krysten Aug 11 '11 at 23:36
1  
Sorry, I may still be confused about the question but to produce a counterexample (at least as I understand the question) you need three sets which do not all contain a common element, and the first set, A, cannot be a subset of ~B or ~C. Since the empty set is a subset of everything, it is a subset of ~B and ~C which is actually consistent with the result. –  user3180 Aug 11 '11 at 23:42
show 5 more comments

2 Answers

up vote 3 down vote accepted

Let $A=\{2,3\}$, $B=\{1,3\}$, and $C=\{1,2\}$.

The intersection of the three sets is empty. But none of them is a subset of the complement of another.

By symmetry, it is sufficient for example to show that $A$ is not a subset of the complement $B^c$ of $B$.

Note that $B^c$ consists of all integers except $1$ and $3$. Since $A$ does contain $3$, $A$ is not a subset of $B^c$.

Comment: As has been pointed out in a comment by @Joe, the empty set is a subset of every set, so setting $A=\emptyset$ cannot give you a counterexample, whatever be the choice of $B$ and $C$.

share|improve this answer
    
Isn't the intersection of A and B 3 and the intersection of A and C is 2? –  Krysten Aug 11 '11 at 23:38
    
Ahh, now I see how it works. Very Clever. –  Krysten Aug 11 '11 at 23:46
    
Yes, but $A\cap B\cap C$ is the intersection of the three sets, and there is no number which is in all three sets. –  André Nicolas Aug 11 '11 at 23:48
    
How did you know to pick those element for A, B, and C? Was it just trial and error? –  Krysten Aug 11 '11 at 23:52
    
It was clear that we would have a counterexample if $A\cap B$ and $A\cap C$ are each non-empty. So I wanted to arrange for that, and have $A \cap B \cap C$ empty. I like symmetry, hence the example. –  André Nicolas Aug 12 '11 at 0:00
show 2 more comments

As another counterexample, let $A=\mathbb{N}$, and $B$ and $C$ be disjoint sets with at least one element each.

Elaborating: On the one hand, since $B$ and $C$ are disjoint, $$ A \cap B \cap C = \mathbb{N} \cap B \cap C = B \cap C = \emptyset. $$ On the other hand, $A = \mathbb{N}$ is not contained in the complement of $B$, since $B$ is not empty, and the same for $C$.

share|improve this answer
add comment

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.