1
$\begingroup$

Given the sets $A,B,C,D$ and the axioms:

  1. $A\cap B\ne\emptyset$
  2. $A\cap C\ne\emptyset$
  3. $B\cap C\ne\emptyset$
  4. $A\cap B\cap C\ = \emptyset$
  5. $D\subsetneq A$
  6. $B\cap D = \emptyset$
  7. $C\cap D\ne\emptyset$

prove analytically that $A\nsubseteq C$

I can easily show this using a Venn diagram, but that's not "analytic" solution. Is it correct that analytic means transforming the statements into "set builder notation", for example:

$A\cap B = \{x\mid x\in A \vee x\in B\}$

and

$D\subsetneq A = \{x\mid x\in D\rightarrow x\in A \wedge \exists x(x\in A \wedge x\notin D)\}$

and then using propositional logic somehow? But also I don't know how to handle the intersected sets equaling or not equaling the empty set. I'm hoping for a hint to get me started or a good reference that talks about this kind of proof.

$\endgroup$
2
$\begingroup$

From 1. we see that since $A \cap B \neq \emptyset$ that there is some $x \in A \cap B \subset A$.

From 4. we see that $(A \cap B) \cap C = \emptyset$, hence $x \notin C$.

Hence $ A \not\subset C$.

$\endgroup$
1
$\begingroup$

Suppose otherwise that $A \subseteq C$. Then $D \subsetneq A \subseteq C$. Since $B \cap D \ne \varnothing$, there exists an element in $B$ that is also in $A$ and $C$, which violates condition 4, a contradiction.


Proof without contradiction: By conditions 5 and 7 there exists an element in $A \cap B$. It must not lie in $C$ because of condition 4. We have found an element of $A$ that does not lie in $C$, so $A \not\subseteq C$.

$\endgroup$
  • $\begingroup$ That certainly works! I suppose a proof that doesn't rely on contradiction would be longer and more involved. $\endgroup$ – yroc Dec 21 '15 at 18:36
  • $\begingroup$ @yroc Not really, see my edit. $\endgroup$ – angryavian Dec 21 '15 at 18:41
  • $\begingroup$ True enough. But I think $A\cap B\ne\emptyset$ is given as condition 1, so apparently all that's really needed is conditions 1 and 4. I can see from your solutions that I was making these proofs out to be more complicated that they really are. $\endgroup$ – yroc Dec 21 '15 at 18:56
  • $\begingroup$ @yroc Oops, yes you are right. $\endgroup$ – angryavian Dec 21 '15 at 18:57
1
$\begingroup$

First of all, I asked a colleague of mine what an 'analytic' proof is, and they told me this is how some people refer to 'real' proofs, or 'rigorous' proofs. For me, this is just what a proof is, so I am going to proceed under this assumption of the interpretation of 'analytic'. If you need general advice on how to construct proofs, I have found this article very useful, especially Part II.

So, my first approach would be a proof by contradiction, assuming that $A\subseteq C$. From axiom 4, we would have that $\emptyset=A\cap B \cap C=B\cap C$, where the second equality follows from symmetry of $\cap$ and our assumption (since $A\subseteq C$ implies $A\cap C=A$). This, however, contradicts axiom 3, that $B\cap C\neq\emptyset$.

Of course, whether this proof counts as rigorous or not depends on what sort of assumptions you are allowed to make in your set theory course. Do you take the Zermelo-Fraenkel axioms, or are you using naive set theory? The proof above uses the latter.

$\endgroup$
  • $\begingroup$ Thank you for your proof (and for the reference -- I'll definitely have a look :-) Set theory assumptions would be naive. $\endgroup$ – yroc Dec 21 '15 at 18:52
  • $\begingroup$ No problem! And as for the level of detail, it's mostly because sometimes set-theoretic proofs require more pedantry than 'other' maths does (and not because I believe it adds clarity). $\endgroup$ – Simon_Peterson Dec 21 '15 at 19:00
1
$\begingroup$

1) $A \cap B \ne \emptyset$

Let $x \in A \cap B \implies x \in A$.

4) $A \cap B \cap C = \emptyset$

$x \in C => x \in (A \cap B) \cap C = A \cap B \cap C = \emptyset$ but that's a contradiction. So $x \in C$. So $A \not \subseteq C$. 2,3,5,6 and 7 were superfluous.

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