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: 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?

-

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

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

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 29, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9389934539794922, "perplexity_flag": "head"}