Answering "Given $A, B \subset C$ prove that $A \subset B$ if, only if, $A \cap B^{c}=\emptyset$" with no proof by contradiction

I am trying to learn basic demonstration and reasoning in Real Analysis. The following question was presented to me with an answer in a proof by contraction format. Since I am new I wish to answer the same question in another way.

Below, you can see the question and the proof I am trying to construct. Could you please help me validate my answer? Is it enough and complete? Is something missing? Is proof by contradiction the only way to answer it?

Thank you in advance,

Given $A, B \subset C$ prove that $A \subset B$ if, only if, $A \cap B^{c}= \emptyset $

If $A \subset B$ such that $a \in A,B$ then $a \notin B^{c}$ and by definition $A \cap B^{c}=\emptyset$

If $a \notin A \cap B^{c}$ such that $ a \in A,B$ then $ A \subset B$

Solution 1:

The first part could be a bit more clear/thorough. I'm not really understanding the second part of your proof. I would write something along the lines of:

($\implies$) Suppose $A\subset B$. Let $a\in A$. Since $A\subset B$, we have that $a\in B$. Therefore, $a\notin B^c$. Hence, $A\cap B^c=\emptyset$.

($\impliedby$) Suppose $A\cap B^c=\emptyset$. Let $a\in A$. Then $a\notin B^c$. Hence, $a\in B$. Thus, $A\subset B$.

Solution 2:

Your writing isn't entirely clear, but you have the right idea. If $A \subseteq B$, then $x \in A \Rightarrow x \in B \Rightarrow x \notin B^c \Rightarrow x \notin A \cap B^c$. But $x \in A$ was arbitrary, so this proves $A \cap B^c = \varnothing$.

Conversely, if $A \nsubseteq B$, then $\exists x \in A$ such that $x \notin B$. But $x \notin B \Rightarrow x \in B^c$, and since also $x \in A$, we have $x \in A \cap B^c$ so $A \cap B^c \neq \varnothing$. This completes the proof.

The reason I say that your writing isn't entirely clear is that you're not clearly expressing the implication that $A \subseteq B \land a \in A \Rightarrow a \in B$. You're simply saying that $a \in A, B$, but it's the implication that's important to the reasoning. As you've written it, you're just picking some $a$ that's in both $A$ and $B$, without making it clear that any $a \in A$ also must necessarily be in $B$.

The logic of your second paragraph doesn't work because you're proving the contrapositive ($\lnot Q \Rightarrow \lnot P$) of the first statement, which immediately follows from your proof of the first statement. You need to prove either the converse ($Q \Rightarrow P$) or the inverse ($\lnot P \Rightarrow \lnot Q$) of the first statement.

Solution 3:

It is not possible to prove this statement unless you use some equivalent of proof by contradiction (such as the law of excluded middle or proof by contraposition).

The reason is that the statement is not true constructively.

It is constructively true that if $A \subseteq B$ then $A \cap B^c = \emptyset$.

However, the statement that if $A \cap B^c = \emptyset$ then $A \subseteq B$ is actually equivalent to proof by contradiction.

Indeed, let us assume that for all $A, B \subseteq C$, if $A \cap B^c = \emptyset$ then $A \subseteq B$. Consider an arbitrary proposition $p$.

Now suppose that $\neg \neg p$ holds. Pick any $\star$ (perhaps $\star = 0$, but it doesn't matter at all), and let $C = \{\star\}$. Let $A = \{\star\}$, and let $B = \{\star \mid p\}$. In other words, $\star \in B \iff p$.

Let us note that $B^c = C \setminus B = \emptyset$. For suppose that $x \in C \setminus B$. In particular, we have $x \in C$ and therefore $X = \star$. Then $x = \star \notin B$. Then $\neg p$. Contradiction.

Thus, in particular, we have $A \cap B^c = \emptyset$.

Therefore, $A \subseteq B$. Then $\star \in A \subseteq B$, so $\star \in B$, so $p$ in fact holds.

So we have proved that this theorem is actually equivalent to proof by contradiction. In other words, we have shown that if this theorem is true and we have $\neg \neg p$, then we also have $p$.