1
$\begingroup$

I'm working through a real analysis textbook, and it starts out with set theory. The first exercise is

Show that if $A$ and $B$ are sets, then $A \subseteq B$ if and only if $A \cap B = A$.

I think I proved it correctly but I'm not sure. Here's what I did. I proved that if $A \subseteq B$, then $A \cap B = A$ the same way as this answer did (https://math.stackexchange.com/a/446114/93114), but I want to make sure I proved the converse correctly because it seems really easy (yes it's the first problem in the book, but still) and math usually isn't this easy for me, even the basic stuff!

Proof of "If $A \cap B = A$, then $A \subseteq B$."

If $x \in A \cap B$, then $x \in A$ and $x \in B$, but this applies to all $x \in A$ because $A \cap B = A$. So, for any $x \in A$, we know that $x \in B$, so $A \subseteq B$.

Am I on the right track?

$\endgroup$
  • $\begingroup$ Yes, although you're doing it in a convoluted way. Let $x\in A$; since $A=A\cap B$ we have $x\in B$. $\endgroup$ – egreg Oct 12 '13 at 22:27
  • $\begingroup$ @egreg So if $x \in A$, then because $A = A \cap B$, we know that $x \in A \cap B$. By definition that implies that $x \in A$ and $x \in B$, which is enough to show that $A \subseteq B$. $\endgroup$ – M T Oct 12 '13 at 22:28
  • $\begingroup$ @egreg Sorry I replied to your other comment that disappeared, but we're doing it the same way now. $\endgroup$ – M T Oct 12 '13 at 22:30
  • $\begingroup$ I realized to have misread your argument, so I changed my first comment. $\endgroup$ – egreg Oct 12 '13 at 22:32
4
$\begingroup$

Since you are just starting, I would suggest to be verbose instead of pulling everything in a single sentence.

To prove $A \subseteq B$ iff $A \cap B = A$, you have to

  1. show $A \cap B = A$ given $A \subseteq B$. That is to
    1. show $A \cap B \subseteq A$.
    2. show $A \subseteq A \cap B$.
  2. show $A \subseteq B$ given $A \cap B = A$.

Proof:

1.1) It is trivially true. You don't need to be given $A \subseteq B$ for it to be true.

1.2) If $x \in A$, then $x \in B$ since we are given $A \subseteq B$. Then $x \in A$ and $x \in B$ are both true. Therefore, $x \in A \cap B$.

2) From $A \cap B = A$, we know $x \in A$ and $x \in B$ whenever $x \in A$. If $x \in A$, then it must be the case that $x \in B$. Therefore, $A \subseteq B$.

$\endgroup$
  • $\begingroup$ Thanks for the answer. I think I'm slowly starting to catch the hang of these proofs. $\endgroup$ – M T Oct 13 '13 at 1:58
0
$\begingroup$

Suppose $A\cap B=A$. To prove $A\subseteq B$, suppose $x\in A$. Since $A\cap B=A$, $x\in A\cap B$ and thus $x\in B$. Since $x$ was an arbitrary element of $A$, this holds for all $x$ and thus $A\subseteq B$.

The above proves $A\cap B=A\implies A\subseteq B$. You will then need to prove the reverse implication to establish $A\cap B=A\iff A\subseteq B$.

$\endgroup$
0
$\begingroup$

Here is another way to approach this type of problem: start with the most complex part (here: $\;A \cap B = A\;$), expand the definitions so that you get from the set level to the element level, then simplify using predicate logic, and finally go back to the set level as suggested by the shape of the formula.

In this case, \begin{align} & A \cap B = A \\ \equiv & \;\;\;\;\;\text{"set extensionality, i.e., the definition of $\;=\;$ for sets"} \\ & \langle \forall x :: x \in A \cap B \equiv x \in A \rangle \\ \equiv & \;\;\;\;\;\text{"definition of $\;\cap\;$"} \\ & \langle \forall x :: x \in A \land x \in B \equiv x \in A \rangle \\ \equiv & \;\;\;\;\;\text{"logic: $\;p \equiv p \land q\;$ is one way to write $\;p \Rightarrow q\;$"} \\ & \langle \forall x :: x \in A \Rightarrow x \in B \rangle \\ \equiv & \;\;\;\;\;\text{"definition of $\;\subseteq\;$"} \\ & A \subseteq B \\ \end{align}

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