How to show if $A \subseteq B$, then $A \cap B = A$?

Hi I'm new to set theory. I need to prove that if $A \subseteq B$, then $A \cap B = A$. I would like to do this the formal way, without a Venn diagram. How should I proceed?

Solution 1:

The most straightforward way is to show that $A\cap B\subseteq A$ and $A\subseteq A\cap B$. Each of these inclusions can be proved by what I call element-chasing: let $x$ be an arbitrary element of the lefthand side, and show that $x$ is necessarily an element of the righthand side.

For the first inclusion this is trivial: if $x\in A\cap B$, then by definition $x\in A$, and it follows immediately that $A\cap B\subseteq A$.

The second inclusion is almost as easy. Suppose that $x\in A$. Then by hypothesis $x\in B$ (since $A\subseteq B$), so $x\in A\cap B$. (In words, is an element of both $A$ and $B$ and therefore by definition an element of $A\cap B$.)

Solution 2:

Like this:

I hope this helps ;-)

Solution 3:

Introduction

I'm editing my answer for a few reasons: First, I was a little too terse, which helps nobody. Second and more importantly, however, none of the previous posters has managed to make use of equational reasoning, and I intend to redress that balance!

Equational reasoning

What is equational reasoning? It means exploiting logical equivalence, 'iff', 'if and only if', or in symbols: $\Leftrightarrow$ and $\equiv$. Consider the way many of the previous posters have chosen to prove a set equality like $A = B$. They first prove $A \subseteq B$, and then $B \subseteq A$. But often it is possible to just prove the equality directly! Similarly, in logic, many choose to prove an 'if and only if' statement such as $A \Leftrightarrow B$ by proving $A \Rightarrow B$ and $B \Rightarrow A$. Again, it is often possible to prove the equivalence directly.

I aim to show how this can be done, to easily prove a stronger result than the original poster's question, namely:

$(*)\quad A \subseteq B \;\;\equiv\;\; A \cap B = A \quad.$

In what follows I will use $\equiv$ instead of $\Leftrightarrow$, to stress the fact that logical equivalence is equality (on the Boolean domain.)

A little bit of logic

In what follows I will need to borrow some results from elementary logic.

The first group of results I need are the properties of logical equivalence, $\equiv$. Namely, I want to use that $\equiv$ is symmetric and associative. That means if I write:

$(0) \quad P \equiv Q \equiv R \equiv S \quad,$

that means, for example, that $P$ is equivalent to $Q \equiv R \equiv S$, or that $Q$ is equivalent to $P \equiv R \equiv S$, or that $P \equiv R$ is equivalent to $Q \equiv S$, and so forth. I can freely reorder and regroup these symbols in any way I please!

A warning! Please note that formula $(0)$ does not mean that $P$, $Q$, $R$, and $S$ are all equivalent.

Finally, I need to use the following theorem about the implication:

$(1) \quad P \Rightarrow Q \;\equiv\; P \wedge Q \;\equiv\; P \quad.$

Interested readers can prove $(1)$ by truth tables if they like, or understand it by intuition, or perhaps we can explore it in a follow-up question.

Connecting set theory to logic

Set theory can be related to logic by some very simple rules of translation:

$\quad P \subseteq Q \ \ \equiv \ \ (\forall x :: \; x \in P \;\Rightarrow\; x \in Q \;)$

$\quad P = Q \ \ \equiv \ \ (\forall x :: \; x \in P \;\equiv\; x \in Q \;)$

and:

$\quad x \in P \cup Q \ \ \equiv \ \ x \in P \vee x \in Q$

$\quad x \in P \cap Q \ \ \equiv \ \ x \in P \wedge x \in Q$

$\quad x \in P^c \ \ \equiv \ \ \neg(x \in P) \quad.$

Now that we are speaking the same language, and have the same general tools in our toolkit, we can proceed to prove formula $(*)$.

An equational proof

Recall that we wish to prove:

$(*)\quad A \subseteq B \;\;\equiv\;\; A \cap B = A \quad.$

I will start at the left-hand side of formula $(*)$, and manipulate it into the right-hand side, maintaining equivalence at each step. (Just like in high school algebra.) Between each manipulation, I'll provide a little hint explaining why the manipulation is true. For example, in high school algebra, I might write:

$\quad 2x + 1 = 3$

$\equiv \quad \{$ subtracting $1$ from both sides $\}$

$\quad 2x = 2$

$\equiv \quad \{$ dividing both sides by $2$ $\}$

$\quad x = 1 \qquad.$

Hopefully this sort of proof is easy for everyone to follow. And now, without further ado, my equational proof of $(*)$:

$\quad A \subseteq B$

$\equiv \quad \{$ using the set theory/logic translation above $\}$

$\quad x \in A \;\Rightarrow\; x \in B \quad$ for all $x$

$\equiv \quad \{$ using $(1)$ above, where $\ P\ $ is $\ x \in A\ $ and $\ Q\ $ is $\ x \in B\ $ $\}$

$\quad x \in A \;\wedge\; x \in B \ \ \equiv\ \ x \in A \quad$ for all $x$

$\equiv \quad \{$ translating the left-hand side $\}$

$\quad x \in A \cap B \;\equiv\; x \in A \quad$ for all $x$

$\equiv \quad \{$ a final translation $\}$

$\quad A \cap B = A \qquad.$

And there we have it: in four painless steps, we have proven the original poster's theorem but also the converse. Why should we expect such a simple theorem from set theory to involve anything more than a little logical manipulation? Why prove set equality using subset relations? Why prove logical equivalence using logical implication? Element-chasing arguments surely have their charm, but it seems like too much ado over nothing.

In short: the theorem $(*)$ in question is essentially the analogue of a logical tautology $(1)$. (Which is in turn an instance of a much more general theorem from lattice theory.) Our proof should therefore aim to translate $(1)$ as effortlessly as possible into the language of sets, and that is what my above proof has done.

Conclusion

I've written a lot here, and that may have given some readers the impression that my approach is difficult or labored or tedious. I don't think it is at all.

I had to lay out certain terminology at the beginning of this post because not everyone is on the same page with their knowledge of basic predicate calculus and set theory. In fact, everything I wrote in the earlier sections of this post is completely general and applicable to problems from all domains of mathematics. If anyone is interested, they can explore the works of Edsger Dijkstra here, or related material here.

I appreciate and welcome any questions and comments.

Solution 4:

It is obvious that $A\cap B \subseteq A$ Choose $x\in A$. Since $A\subseteq B$, we have $x\in A$ and $x\in B$. But this says $x\in A\cap B$. We have just shown that $A\subseteq A\cap B$. We conclude $A = A\cap B$.