Set Theory: Proving Statements About Sets

Let $A, B,$ and $C$ be arbitrary sets taken from the positive integers.

I have to prove or disprove that: $$\text{If }A ∩ B ∩ C = ∅, \text{then } (A ⊆ \sim B) \text{ or } (A ⊆ \sim 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 ⊆ \sim B)$ or $(A ⊆ \sim C)$.

Is this a sufficient proof?

• 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. Aug 11 '11 at 23:29
• the ~ means complement, so it is important Aug 11 '11 at 23:31
• 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. Aug 11 '11 at 23:34
• Right, so why can't I use that to disprove this Aug 11 '11 at 23:36
• 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. Aug 11 '11 at 23:42

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

• Isn't the intersection of A and B 3 and the intersection of A and C is 2? Aug 11 '11 at 23:38
• Ahh, now I see how it works. Very Clever. 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. 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? 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. Aug 12 '11 at 0:00

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