The Element’s-Eye View – Foundations of Mathematics

There are three things to keep in mind when it comes to set-theory proofs (which most of our proofs hereafter will be):

Sets are defined by their membership. Because of this, we nearly always take an element's-eye view of any proof involving sets. Notice that in the proofs we presented above, the first thing we did to get going was say something like ``Let $x\in$ . . .".
Generally, the way to go to prove two sets are equal is to show (separately) that each is a subset of the other.
Keep in mind what your goal is. That is, pay attention to the consequent. Your goal is to translate from the language of the consequent into the language of the antecedent.

These three principles are not only good advice for writing a proof, but they are in fact good advice for {\em figuring out} a proof as well. The following examples will illustrate principles 1 and 3.

Theorem. If $A$ and $B$ are sets with $2^A\subseteq 2^B$ , then $A\subseteq B$ .

Proof. Let $A$ and $B$ be set with $2^A\subseteq 2^B$ . Since we have to show $A\subseteq B$ , let $x\in A$ . Then $\{x\}\subseteq A$ , so $\{x\}\in 2^A$ . Since $2^A\subseteq 2^B$ , we have $\{x\}\in 2^B$ . But this means $\{x\}\subseteq B$ . Since $x\in\{x\}$ , we see that $x\in B$ .

So we've shown every $x\in A$ also has $x\in B$ , i.e. $A\subseteq B$ . $\Box$

Theorem. If $A$ and $B$ are sets with $A\subseteq B$ , then $2^A\subseteq 2^B$ .

Proof. Let $A$ and $B$ be sets with $A\subseteq B$ . Since we have to show $2^A\subseteq 2^B$ , let $x\in 2^A$ . Then $x\subseteq A$ . Since $A\subseteq B$ , and set inclusion is transitive, we have $x\subseteq B$ . But this is exactly the statement that $x\in 2^B$ .

So we've show that every $x\in 2^A$ also has $x\in 2^B$ , i.e. $2^A\subseteq 2^B$ . $\Box$

Notice that in both cases, we were concerned with the {\em consequent} of the conditional we'd be asked to show (principle III), and that we proceeded by following elements (principle I). In the first proof, we translated from the language of elements of $A$ and $B$ to the language of subsets of $A$ and $B$ to the language of elements of $2^A$ and $2^B$ , applied our assumption, and translated back. In the second proof, we translated from the language of elements of $2^A$ and $2^B$ to the language of subsets of $A$ and $B$ , applied our assumptions, and translated back.

Activity Consider the following couplet:

Heffalumps and woozles are very confuzle.
A heffalump or woozle's very sly.

Explain why both lines are talking about the same thing as follows. First, give a mathematical name to what they describe. Then explain why each line takes a different perspective on that mathematical object, and why those perspectives are not contradictory, the difference between ``and" and ``or" notwithstanding.