Proof:Union computation

To demonstrate a few proof techniques, we will do a proof of the following fact, in painstaking detail:

We begin with the completed proof; we'll circle back and look at the proof techniques below.

Proof: painstaking version

Let denote the left hand side, and similarly let . We want to show that , or in other words that and .

First, we prove LHS ⊆ RHS, i.e. that for all , . Choose an arbitrary . Then by definition of ∪, either or .

In the first case (when ), by definition of {1,2}, we know that [math]x = 1 [/math] or [math]x = 2 [/math]. If x = 1, then [math]x = 1 [/math] or [math]x = 2 [/math] or [math]x = 3 [/math], so by definition. Similarly, if x = 2, then [math]x = 1 [/math] or [math]x = 2 [/math] or [math]x = 3 [/math], so by definition. In either subcase, we have shown , so we are done with the case.

The second case, when is similar: since , we know that [math]x = 2 [/math] or [math]x = 3 [/math]; in both of these subcases, we have .

In both cases, we have shown that , which concludes the subproof that .

Now, we need to show that , i.e. that every is in the LHS. Choose an arbitrary ; then or or . If or , then , so (by definition of ∪). In the third case, when , we have or , so . In both cases, we have , which completes the proof.

Proof techniques

This proof used only a few proof techniques:

plug in definitions
to prove "P and Q", prove both
to prove "P or Q", prove either
to prove "for all [math]x [/math], P", choose an arbitrary [math]x [/math] and prove P for that [math]x [/math]
to use "P or Q" in a proof, do case analysis

We will review these and other techniques more systematically in the following lecture. It is a good exercise to read through this proof and identify which of these techniques is being applied in each step.

Eliding detail

I have expanded the proof above in painstaking detail; most proofs would elide some of this detail. Here is a more typical proof of the above fact:

Proof: short version

Let and ; we want to show that and .

Choose an ; then [math]x [/math] is either in [math]\{1,2\} [/math] or [math]\{2,3\} [/math]. In either case, we readily see that , so .

On the other hand, if we choose an , we see that is either 1, 2, or 3; in the former two cases, and thus in the LHS, while in the third case, and is again in the LHS.

When you leave out detail, you are implicitly claiming that the steps you skip are obvious; you should prove them to yourself to convince yourself that they are, in fact, obvious.