4
$\begingroup$

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?

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

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

$\endgroup$
7
  • $\begingroup$ Isn't the intersection of A and B 3 and the intersection of A and C is 2? $\endgroup$
    – Krysten
    Aug 11 '11 at 23:38
  • $\begingroup$ Ahh, now I see how it works. Very Clever. $\endgroup$
    – Krysten
    Aug 11 '11 at 23:46
  • $\begingroup$ 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. $\endgroup$ Aug 11 '11 at 23:48
  • $\begingroup$ How did you know to pick those element for A, B, and C? Was it just trial and error? $\endgroup$
    – Krysten
    Aug 11 '11 at 23:52
  • $\begingroup$ 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. $\endgroup$ Aug 12 '11 at 0:00
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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