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?

  • 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.2011-08-11
  • 1
    the ~ means complement, so it is important2011-08-11
  • 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.2011-08-11
  • 0
    Right, so why can't I use that to disprove this2011-08-11
  • 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.2011-08-11
  • 0
    Oh ok. Now I understand. Thanks for the clarification2011-08-11
  • 0
    Regarding the question title: you cannot "prove" a set, that verb does not fit with that direct object. Only theorems, statements, propositions, lemmas, etc. can be proved.2011-08-12
  • 0
    What would be a more appropriate title?2011-08-12
  • 0
    @Krysten: about the time you left that comment, I already edited the title to make it more in line with typical mathematical English.2011-08-12
  • 0
    lol thanks. now i know2011-08-12

2 Answers 2

3

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

  • 0
    Isn't the intersection of A and B 3 and the intersection of A and C is 2?2011-08-11
  • 0
    Ahh, now I see how it works. Very Clever.2011-08-11
  • 0
    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.2011-08-11
  • 0
    How did you know to pick those element for A, B, and C? Was it just trial and error?2011-08-11
  • 0
    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.2011-08-12
  • 0
    Symmetry meaning each set has one element that is not in the other?2011-08-12
  • 0
    @Krysten: More than that. If you permute $A$, $B$, and $C$ in any way, the basic pattern remains unchanged. Thus we get two bonuses: (i) if $X$ and $Y$ are two distinct sets chosen from $A$, $B$, $C$ then $X$ is not a subset of $Y^c$ and (ii) checking the property for one pair effectively checks it for all $6$ possible ordered pairs $(X,Y)$.2011-08-12
1

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