# Explanation of a Set problem

I am to show that $$A\subset B \Leftrightarrow A\cap B=A \Leftrightarrow A \cup B =B.$$ My question has more to do with understanding what to show than how to show it. So I would be grateful if I could be pointed in the right direction. I'm not used to proving stuff with double implication in them.

Thanks.

-
To prove a double implication, you prove one implication, then the other. So in total there are four implications to prove. Which ones are you having trouble with? –  Qiaochu Yuan Aug 30 '11 at 21:52
So Do I prove $A\subset B \Leftrightarrow A \cap B=A$ and $A \cap B =A \Leftrightarrow A \cup B=B$ ? –  Kuku Aug 30 '11 at 21:57
You want to prove $A \cup B \rightarrow A \cap B = A$, $A \cap B = A \rightarrow A \subset B$, $A \cap B = A \rightarrow A \cup B = B$, and $A \cup B = B \rightarrow A \cap B = B$. –  Dan W Aug 30 '11 at 22:02
If P, Q, and R are statements, then "$P \Leftrightarrow Q \Leftrightarrow R$" is shorthand for "$P \Leftrightarrow Q$ and $Q \Leftrightarrow R$", or, in other words, "the statements P, Q, and R are either all true, or all false". There are tons of ways to prove that three statements are all equivalent, but they all come down to proving that they imply each other. Simply keep in mind that once you've proved that P implies Q and Q implies R, you no longer have to bother proving that P implies R. –  Tanner Swett Aug 30 '11 at 22:17
Instead of a total of 4 (2 two way implications) we can get away with 3- Show A->B->C->A. –  Ragib Zaman Aug 30 '11 at 23:23

First let us see what does that mean $X\iff Y$. The meaning is:

if $X$ is known to be true then $Y$ can be shown true, and if $Y$ is known to be true then $X$ can be shown true as well.

The above can be plainly written as $$X\implies Y\land Y\implies X$$ where $\land$ is "logical and" (i.e. conjuction) connective.

In the question above we have $X\iff Y\iff Z$, which translates to: $$X\iff Y \land Y\iff Z$$

From this we can prove that $X\iff Z$ using $Y$ as an interpolant. That is assume that $X$ is true, prove $Y$ is also true, and use the proof of $Y\iff Z$ to show that $Z$ is true, and similarly for the other direction.

We need, if so, to prove three equivalences, each by proving a double implication. We can reduce this into two equivalences:

1. $X\iff Y$,
2. $Y\iff Z$.

As we have seen how this would prove $X\iff Z$ as well. This means we need only two equivalences instead of six, which translates as four implications. However we can instead prove these three:

1. $X$ implies $Y$,
2. $Y$ implies $Z$,
3. $Z$ implies $X$.

From this we can deduce that $Y\implies X$, this time by using $Z$ as an interpolant, and the same for $Z\implies Y$. (It can be shown that no less than three proofs are sufficient, this is a graphical proof really: you cannot close a path between three points with only two edges.)

To prove an implication $X\implies Y$ we assume that $X$ is true, and show that in this case $Y$ is also true.

From here things should be clearer, and we can actually approach the proof.

1. Assume that $A\subseteq B$, in this case $A\cap B=\{a\in A\mid a\in B\}$ however our assumption was that $a\in A\rightarrow a\in B$, therefore $A\cap B=A$.

2. Assume $A\cap B=A$, now $a\in A\cup B$, either $a\in A$ or $a\in B$. If $a\in A$ then $a\in A\cap B$ therefore $a\in B$. We conclude that $a\in A\cup B\rightarrow A\in B$. From this $A\cup B=B$ follows.

3. Assume $A\cup B=B$. Take $a\in A$ therefore $a\in A\cup B$, from our assumption $a\in B$. By definition we have that $A\subseteq B$.

In each of the three steps, we assumed a condition is being met and proved something else to be true as well. From this we can see how assuming $A\subseteq B$ will give us a proof that $A\cup B=B$. We simply "combine" the proofs.

Therefore to show that $A\cap B=A\implies A\subseteq B$ we can use the proofs in (2) and (3) combined, and similarly to have that $A\cup B=B\implies A\cap B=A$.

-
So it suffices just to show 1,2 and 3? –  Kuku Aug 30 '11 at 22:25
@Kuku: I tried to elaborate a little bit. I hope it is somewhat readable, I will try to work on the formatting soon. –  Asaf Karagila Aug 30 '11 at 22:31

In general, a good stategy for these kinds of problems is to convert statements about the sets, like
"$A\subset B$ ", into statements about their elements; in the case of $A\subset B$, this is equivalent to the statement that for any $x$, we have $x\in A\implies x\in B$.

Note that the statement that two sets $C$ and $D$ are equal, i.e. $C=D$, is true when they have the same elements, i.e. for any $x$, we have $x\in C\iff x\in D$.

So the three statements we are looking at:

1. $A\subset B$
2. $A\cap B=A$
3. $A\cup B=B$

become

1. $x\in A\implies x\in B$
2. $x\in A\cap B\iff\ x\in A$
3. $x\in A\cup B\iff x\in B$

Can you specify the conditions under which $x\in A\cap B$, in terms of whether $x\in A$ and whether $x\in B$? What about the conditions when $x\in A\cup B$?

-
Yes I can...Thanks. –  Kuku Aug 30 '11 at 22:25
@Kuku: So now the proof comes down to showing that $$x\in A\implies x\in B$$ $$(x\in A \text{ AND } x\in B)\iff x\in A$$ $$(x\in A\text{ OR }x\in B)\iff x\in B$$ are all logically equivalent. –  Zev Chonoles Aug 30 '11 at 22:27

To restate the same a bit differently to aid intuition: the task in a dual implication is to show that each statement means the other is true. Then since all that can be done with one can be done with the other, they are equivalent forms of the same thing.

Following these thoughts, the first dual implication is true since:

1. If A is contained within B, then what is within A and B must be exactly A.

2. If the intersection of A and B is all of A, then all of A must be within B.

Similar if-then structures are possible for the second dual implication.

Notice that equivalency is transitive, that is, since the first and the third statements are equivalent to the second, then the first and the third statements are equivalent to each other. The middle statement can be thought of as a bridge between the two. Transitivity is a general concept, and is observed often in algebra: A = B, and B = C, implies A = C.

-
thanks Roberto... –  Kuku Aug 31 '11 at 1:38