# Proof of set membership by analytic proof

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.

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

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

• That certainly works! I suppose a proof that doesn't rely on contradiction would be longer and more involved. – yroc Dec 21 '15 at 18:36
• @yroc Not really, see my edit. – angryavian Dec 21 '15 at 18:41
• 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. – yroc Dec 21 '15 at 18:56
• @yroc Oops, yes you are right. – angryavian Dec 21 '15 at 18:57

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.

• Thank you for your proof (and for the reference -- I'll definitely have a look :-) Set theory assumptions would be naive. – yroc Dec 21 '15 at 18:52
• 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). – Simon_Peterson Dec 21 '15 at 19:00

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.