# Difference between revisions of "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 or . If x = 1, then or or , so by definition. Similarly, if x = 2, then or or , 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 or ; 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:

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 is either in or . 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.