# Proof of $A \subseteq B \Leftrightarrow A \cap B = A$ (Check chain of implications)

Prove $A \subseteq B \Leftrightarrow A \cap B = A$.

My attempt:

Case $\Rightarrow$:

\begin{align} A \subseteq B & \Rightarrow & [x\in A \Rightarrow x\in B] \\ &\Rightarrow &[x \in A \Rightarrow x\in A \text{ and } x\in B] \tag{1} \\ &\Rightarrow &[x\in A \Rightarrow x\in A \cap B] \\ &\Rightarrow & A \subseteq A\cap B \end{align}

\begin{align} A \subseteq B & \Rightarrow & [x\in A \Rightarrow x\in B] \\ & \Rightarrow & [(x\in A \text{ and } x\in B) \Rightarrow x \in A] \tag{2} \\ & \Rightarrow & [x \in A \cap B \Rightarrow x \in A] \\ & \Rightarrow & A \cap B \subseteq A \end{align}

\begin{align}\therefore A \subseteq B & \Rightarrow & A \subseteq A \cap B \text{ and } A \cap B \subseteq A \\ &\Rightarrow& A \cap B = A \end{align}

Case $\Leftarrow$:

\begin{align} A \cap B = A & \Rightarrow & A \cap B \subseteq A \text{ and } A \subseteq A \cap B \\ & \Rightarrow & [(x \in A \text{ and } x \in B) \Rightarrow x \in A ] \text{ and } [x\in A \Rightarrow & (x \in A \text{ and } x \in B)] \\ & \Rightarrow & [x\in A \Rightarrow x \in B] \tag{3}\\ & \Rightarrow & A \subseteq B \end{align}

Is my proof correct? I am particularly not sure about line 1,2 and 3 since I just made those up (while making sure that the chain of implications is still true) as I already know the conclusion I want to arrive at.

• Your (2)'s second step makes no sense, but you can fix it (probably a typo?) and you are redundant on your last two steps, but not really an "error." – Adam Hughes Jul 3 '14 at 14:17
• @AdamHughes Yes, its a typo. Thanks for calling my attention to it. – mauna Jul 3 '14 at 15:21

I think you waved past a couple of steps in "Case $\Leftarrow$":

\begin{align} A \cap B = A &\Rightarrow A \cap B \subseteq A \land A \subseteq A \cap B \tag{1}\\ & \Rightarrow [(x \in A \text{ and } x \in B) \Rightarrow x \in A ]\land[x\in A \Rightarrow (x \in A \land x \in B)]\tag{2} \\ & \Rightarrow [x\in A \Rightarrow x \in B] \tag{3}\\ & \Rightarrow A \subseteq B\tag{4} \end{align}

After unpacking $A \cap B = A$ to get $(1)$ and $(2)$ (which are both perfectly correct), I think you need more work (or more justification) before concluding: $$x\in A \rightarrow x\in B\tag{3}$$

\begin{align} A \cap B = A &\Rightarrow A \cap B \subseteq A \land A \subseteq A \cap B \tag{1}\\ & \Rightarrow [(x \in A \land x \in B) \Rightarrow x \in A ]\\ &\quad \land x\in A \Rightarrow (x \in A \land x \in B)]\tag{2} \\ &\Rightarrow x\in A \Rightarrow (x \in A \land x\in B)\tag{3}\\ \\ & \quad \text{Assumption:} x\in A\tag{4}\\ &\qquad\quad {\small \Rightarrow} x\in A \land x \in B \tag{(5): 3 & 4}\\ &\qquad\quad {\small \Rightarrow} x\in B\tag{(6): from 5}\\\\ &\Rightarrow x\in A \Rightarrow x\in B\tag{(7): 4-6}\\ & \Rightarrow A \subseteq B\tag{8} \end{align}

• how did you get the assumption in line (4)? Was it based on some of the proceeding lines? – mauna Jul 3 '14 at 15:20
• You are always free to assume something, in this case, I chose to assume $x\in A$ because if we can show, given the earlier lines in the proof, that this implies $x\in B$, we have proven that $x \in A \implies x\in B$. Note that whether or not $x$ is in A doesn't matter. The aim of the proof is to show that IF x is in A, THEN x is in B. I.e., to establish that, together with the earlier part of the proof, $x \in A\implies x\in B$ – Namaste Jul 3 '14 at 15:23
• An alternative route is to know that $$x\in A \rightarrow(x\in A\land x\in B) \\ \Rightarrow [(x \in A \rightarrow x \in A) \land (x\in A \rightarrow x \in B)] \\ \Rightarrow x \in A \rightarrow x \in B\\ \Rightarrow A\subseteq B$$ – Namaste Jul 3 '14 at 15:34

$A \cap B \subseteq A$ is always true, so it's a bit misleading to say that it is implied by $A \subseteq B$ (although not incorrect). You can simply start with the statement:

$$x \in A \text{ and } x \in B \implies x \in A$$

to prove it$-$this is probably what you meant by the statement $(2)$.

For statement $(3)$ it might be more clear how you arrived at this if you say that $A \cap B = A$ implies $A \subseteq A \cap B$, and since $A \cap B \subseteq B$, this means $A \subseteq B$.

The rest of the proof is correct.


Assuming that you're only allowed to use the definitions of $\;\subseteq\;$ and $\;\cap\;$, any proof $\;A \subseteq B \;\equiv\; A \cap B = A\;$ is essentially a proof of the equivalent $$\langle \forall x :: x \in A \Rightarrow x \in B \rangle \;\equiv\; \langle \forall x :: x \in A \land x \in B \;\equiv\; x \in A \rangle$$ That statement directly follows from the following more general law of propositional logic: for any $\;P,Q\;$, $$P \Rightarrow Q \;\;\equiv\;\; P \land Q \;\equiv\; P$$ There are numerous ways to prove this, depending on what laws of logic you are allowed to use. For example, one can work from right to left:

$$\calc P \land Q \;\equiv\; P \calcop{\equiv}{split \;\equiv\; into both directions -- to introduce \;\Rightarrow\; as in our goal} (P \land Q \Rightarrow P) \;\land\; (P \Rightarrow P \land Q) \calcop{\equiv}{use \;P \equiv \text{true}\; from left hand side of \;\Rightarrow\; on right hand side, twice} (P \land Q \Rightarrow \text{true}) \;\land\; (P \Rightarrow \text{true} \land Q) \calcop{\equiv}{simplify: left part is \;\text{true}\;; \;\text{true} \land R \equiv R\;, twice} P \Rightarrow Q \endcalc$$