FA18:Lecture 3 proofs

From CS2800 wiki

In this lecture, we will examine several forms of proposition; for each we will discuss proof techniques for handling it: how to prove it, how to disprove it, and how to use it in a proof (if it is already known to be true).

We also introduced a few definitions you will need for the homework:

Set constructions

Ordered pairs

Definition: Ordered pair
If [math]x [/math] and [math]y [/math] are things, then [math](x,y) [/math] is the ordered pair of [math]x [/math] and [math]y [/math].


Two ordered pairs [math](x_1,y_1) [/math] and [math](x_2,y_2) [/math] are equal if [math]x_1 = x_2 [/math] and [math]y_1 = y_2 [/math].

In particular, order matters: [math](1,2) \neq (2,1) [/math] because [math]1 \neq 2 [/math].

We can also consider ordered triples, quadruples, etc. The general term is a k-tuple. For example, a pair is a 2-tuple and a triple is a 3-tuple.

Cartesian product

Definition: Cartesian product
If [math]A [/math] and [math]B [/math] are sets, then the cartesian product of [math]A [/math] and [math]B [/math] (written [math]A \href{/cs2800/wiki/index.php/%5Ctimes}{\times} B [/math]) is the set of ordered pairs of elements, one from [math]A [/math] and one from [math]B [/math]. Formally, [math]A \href{/cs2800/wiki/index.php/%5Ctimes}{\times} B \href{/cs2800/wiki/index.php/Definition}{:=} \{\href{/cs2800/wiki/index.php/Pair}{(a,b)} \mid a \href{/cs2800/wiki/index.php/%E2%88%88}{∈} A\text{ and }b \href{/cs2800/wiki/index.php/%E2%88%88}{∈} B\} [/math].

For example, [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2\}} \href{/cs2800/wiki/index.php/%5Ctimes}{\times} \href{/cs2800/wiki/index.php/Enumerated_set}{\{a,b\}} = \{\href{/cs2800/wiki/index.php/Pair}{(1,a)}, \href{/cs2800/wiki/index.php/Pair}{(1,b)}, \href{/cs2800/wiki/index.php/Pair}{(2,a)}, \href{/cs2800/wiki/index.php/Pair}{(2,b)}\} [/math]

Power set


Definition: Power set
The power set of a set [math]A [/math] (written [math]\href{/cs2800/wiki/index.php/2}{2}^A [/math])is the set of all subsets of [math]A [/math]. Formally, [math]\href{/cs2800/wiki/index.php/2}{2}^A \href{/cs2800/wiki/index.php/Definition}{:=} \href{/cs2800/wiki/index.php/Set_comprehension}{\{B \mid} B \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} A\} [/math].

Because the elements of the power set are themselves sets, it is easy to confuse elements and subsets. As with any set comprehension, the elements of [math]\href{/cs2800/wiki/index.php/2}{2}^A [/math] are the subsets of [math]A [/math]. Here are some examples:

Let [math]A := \href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2,3\}} [/math]. Then

  • [math]\href{/cs2800/wiki/index.php/2}{2}^A = \{ \href{/cs2800/wiki/index.php/Empty_set}{\{\}}, \href{/cs2800/wiki/index.php/Enumerated_set}{\{1\}}, \href{/cs2800/wiki/index.php/Enumerated_set}{\{2\}}, \href{/cs2800/wiki/index.php/Enumerated_set}{\{3\}}, \href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2\}}, \href{/cs2800/wiki/index.php/Enumerated_set}{\{1,3\}}, \href{/cs2800/wiki/index.php/Enumerated_set}{\{2,3\}}, \href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2,3\}} \} [/math], by inspection. For example, [math]\{1,2,3\} \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/2}{2}^A [/math] because [math]\{1,2,3\} \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} A [/math].
  • [math]1 \href{/cs2800/wiki/index.php/%5Cnotin}{\notin} \href{/cs2800/wiki/index.php/2}{2}^A [/math], because 1 is a number but [math]\href{/cs2800/wiki/index.php/2}{2}^A [/math] contains only sets. Put differently, [math]1 \href{/cs2800/wiki/index.php?title=%5Cnsubseteq&action=edit&redlink=1}{\nsubseteq} A [/math].
  • Therefore [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{1\}} \href{/cs2800/wiki/index.php?title=%5Cnsubseteq&action=edit&redlink=1}{\nsubseteq} \href{/cs2800/wiki/index.php/2}{2}^A [/math]
  • But note that [math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{1\}} \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/2}{2}^A [/math].
  • for any set [math]X [/math], we have [math]\href{/cs2800/wiki/index.php/%E2%88%85}{∅} \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/2}{2}^A [/math] and [math]X \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/2}{2}^X [/math], because ∅⊆X and X⊆X.

Proofs

Now that we have some definitions, we can turn our attention to proving things using those definitions. During the lecture, we listed some general techniques as we went; here we discuss the general techniques first, and then present the two proofs given.

General techniques

A proof is just an argument that something is true. While writing a proof, you will make a series of claims; each claim should be

  • clearly described (all terms have definitions)
  • true (based on the current set of assumptions)
  • obviously true based on what has already been stated.

Separate goals from knowns

While writing a proof (as with any technical writing), it is often helpful to remind the reader where you are going. However, it is important to clearly indicate that this is what you are doing.

I often write "we want to show" (abbreviated WTS) to clearly indicate that I haven't already proved what I'm stating. Failing to do so can lead to a backwards proof. For example, while trying to prove [math]A \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B [/math], I shouldn't write something like

  • [math]A \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B [/math]
  • every [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math] is in [math]A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B [/math]
  • ...

because the reader will believe that you are claiming what you are trying to prove is true on the very first line (remember, every claim should be obvious based on what came before). However, the following solves this problem:

  • We want to show that [math]A \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B [/math],
  • i.e. that every [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math] is in [math]A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B [/math]

Here, each sentence is obviously true: we obviously do want to prove [math]A \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B [/math], and that is obviously the same as saying that every [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math] is in [math]A \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} B [/math] (we consider definitions to be "obvious").

Plug in definitions

It is often helpful to plug in definitions; indeed, this is the whole point of clearly writing down definitions! If you are trying to prove two things are equal, find the appropriate definition of equality and plug it in.

We often indicate that we are using a definition by writing by definition, in other words, or i.e..

You can often save yourself some handwriting by expanding the outermost definitions first. For example, if you are proving [math]\href{/cs2800/wiki/index.php/2}{2}^{A \href{/cs2800/wiki/index.php/%5Ctimes}{\times} B} \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} \href{/cs2800/wiki/index.php/2}{2}^A \href{/cs2800/wiki/index.php/%5Ctimes}{\times} \href{/cs2800/wiki/index.php/2}{2}^B [/math], you could choose to expand any of the uses of the definition of the [math]\href{/cs2800/wiki/index.php/2}{2}^A [/math], of [math]A \href{/cs2800/wiki/index.php/%5Ctimes}{\times} B [/math], or of . If you reduce [math]A \href{/cs2800/wiki/index.php/%5Ctimes}{\times} B [/math] or [math]\href{/cs2800/wiki/index.php/2}{2}^A [/math] first, you will likely have to repeat its defintiion several times. If you expand [math]\href{/cs2800/wiki/index.php/%5Csubseteq}{\subseteq} [/math] first, on the other hand, you can immediately dive into the proof of [math]\href{/cs2800/wiki/index.php/%5Csubseteq}{\subseteq} [/math] without having to copy long formulas down.

A proof, in painstaking detail

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

[math]\href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2\}} \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \href{/cs2800/wiki/index.php/Enumerated_set}{\{2,3\}} = \href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2,3\}} [/math]

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

Proof: painstaking version
Let [math]\href{/cs2800/wiki/index.php/LHS}{LHS} \href{/cs2800/wiki/index.php/Definition}{:=} \href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2\}} \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \href{/cs2800/wiki/index.php/Enumerated_set}{\{2,3\}} [/math] denote the left hand side, and similarly let [math]\href{/cs2800/wiki/index.php/RHS}{RHS} \href{/cs2800/wiki/index.php/Definition}{:=} \href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2,3\}} [/math]. We want to show that [math]\href{/cs2800/wiki/index.php/LHS}{LHS} \href{/cs2800/wiki/index.php/Equality_(sets)}{=} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math], or in other words that [math]\href{/cs2800/wiki/index.php/LHS}{LHS} \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math] and [math]\href{/cs2800/wiki/index.php/RHS}{RHS} \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} \href{/cs2800/wiki/index.php/LHS}{LHS} [/math].

First, we prove LHS RHS, i.e. that for all [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/LHS}{LHS} [/math], [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} RHS [/math]. Choose an arbitrary [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/LHS}{LHS} [/math]. Then by definition of , either [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2\}} [/math] or [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/Enumerated_set}{\{2,3\}} [/math].

In the first case (when [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \{1,2\} [/math]), 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 [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math] by definition. Similarly, if x = 2, then [math]x = 1 [/math] or [math]x = 2 [/math] or [math]x = 3 [/math], so [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math] by definition. In either subcase, we have shown [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math], so we are done with the [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \{1,2\} [/math] case.

The second case, when [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \{2,3\} [/math] is similar: since [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \{2,3\} [/math], we know that [math]x = 2 [/math] or [math]x = 3 [/math]; in both of these subcases, we have [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \{1,2,3\} = \href{/cs2800/wiki/index.php/RHS}{RHS} [/math].

In both cases, we have shown that [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math], which concludes the subproof that [math]\href{/cs2800/wiki/index.php/LHS}{LHS} \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math].

Now, we need to show that [math]\href{/cs2800/wiki/index.php/RHS}{RHS} \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} \href{/cs2800/wiki/index.php/LHS}{LHS} [/math], i.e. that every [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math] is in the LHS. Choose an arbitrary [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math]; then [math]x = 1 [/math] or [math]x = 2 [/math] or [math]x = 3 [/math]. If [math]x = 1 [/math] or [math]x = 2 [/math], then [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2\}} [/math], so [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/LHS}{LHS} [/math] (by definition of ). In the third case, when [math]x = 3 [/math], we have [math]x = 2 [/math] or [math]x = 3 [/math], so [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math]. In both cases, we have [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} RHS [/math], 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 [math]\href{/cs2800/wiki/index.php/LHS}{LHS} \href{/cs2800/wiki/index.php/Definition}{:=} \{1,2\} \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \{2,3\} [/math] and [math]\href{/cs2800/wiki/index.php/RHS}{RHS} \href{/cs2800/wiki/index.php/Definition}{:=} \{1,2,3\} [/math]; we want to show that [math]LHS \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} RHS [/math] and [math]RHS \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} LHS [/math].

Choose an [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/LHS}{LHS} [/math]; then [math]x [/math] is either in [math]\{1,2\} [/math] or [math]\{2,3\} [/math]. In either case, we readily see that [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \{1,2,3\} [/math], so [math]\href{/cs2800/wiki/index.php/LHS}{LHS} \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math].

On the other hand, if we choose an [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math], we see that [math]x [/math] is either 1, 2, or 3; in the former two cases, [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \{1,2\} [/math] and thus in the LHS, while in the third case, [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \{2,3\} [/math] 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.