2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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." $\endgroup$ – Adam Hughes Jul 3 '14 at 14:17
  • $\begingroup$ @AdamHughes Yes, its a typo. Thanks for calling my attention to it. $\endgroup$ – mauna Jul 3 '14 at 15:21
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ how did you get the assumption in line (4)? Was it based on some of the proceeding lines? $\endgroup$ – mauna Jul 3 '14 at 15:20
  • 1
    $\begingroup$ 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$ $\endgroup$ – Namaste Jul 3 '14 at 15:23
  • $\begingroup$ 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$$ $\endgroup$ – Namaste Jul 3 '14 at 15:34
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\calcop}[2]{\\ #1 \quad & \quad \text{"#2"} \\ \quad & } \newcommand{\endcalc}{\end{align}} $For comparison, here is a different (more "logical" :-) approach.

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

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