3
$\begingroup$

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.

  • 0
    Thanks to you all...you've all been immense...2011-08-31

3 Answers 3

3

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

2

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

  • 0
    @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.2011-08-30
1

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.