SI242: Mathematical Induction II

Proof by (strong) induction - repeated from last class

Here is the summary of what a proof by induction is:

There is some collection of objects, and we are trying to prove that some property $P$ is satisfied by all objects in the collection.
In our example, the collection of objects is "all propositional formulas that contain only ands, ors and implications", and the property is "evaluates to true under interpretation $I$", recalling that $I$ is the interpretation in which all variables are assigned the value "true".
There is a non-negative integer "size" for each object in the collection.
In our example, the size is "the number of propositional operators in the formula".
The argument then goes like this:
1. We prove that property $P$ holds for all objects of size 0.
  [Note: this is called the "base case".]
2. We prove that, for any size $n > 0$: ($P$ holds for all objects of size less than $n$) $\Rightarrow$ ($P$ holds for all objects of size $n$).
  [Note: this is called the "inductive case", and the left-hand side of the implicationis called the inductive hypothesis.] In practice, we prove this by:
  a. assume the inductive hypothesis, and
  b. prove the property holds of all objects of size $n$.
  This suffices, since, closing the assumption, this proves the above implication.
3. We deduce that property $P$ holds for objects of all sizes.
  [Note: this is actually where we apply induction as a new deduction rule.]

Spotting the elements of an inductive proof in the wild

Below is our first example of an inductive proof (from last class). Some of the key features are hightlighted:

size
base case
inductive case
applying the inductive hypothesis

If $F$ is a propositional formula that only contains ands, ors, implications ($\wedge,\vee,\Rightarrow$) and the variables $x_1,\ldots,x_n$, and $I$ is the interpretation in which each $x_i = \text{true}$, then $F$ is true under interpretation $I$.

We will prove this by induction on $n$, the number of operators in $F$.
If $n=0$, then $F$ is a variable $x_i$, which is true under interpretation $I$.
If $n>0$, then $F$ is one of $(A)\wedge(B)$, $(A)\vee(B)$ or $(A)\Rightarrow(B)$. Assume the inductive hypothesis, i.e. that formulas containing only $\wedge,\vee\Rightarrow$ with less than $n$ operators evaluate to true under $I$. Since $A$ and $B$ both have fewer than $n$ operators and only include $\wedge,\vee,\Rightarrow$, both $A$ and $B$ evaluate to true under $I$. So, under $I$, formula $F$ evaluates to one of true∧true, true∨true or true⇒true, all of which are true.
So by the principle of induction, we deduce that for any number of operators, a formula containing only $\wedge,\vee,\Rightarrow$ evaluates to true under interpretation $I$.

Note: Here is a nice single page version of that proof.

In-class activity

We had a very important in-class activity that looked at four different inductive proofs (or supposed proofs that are actually flawed) and asked questions about them.

An xor fact

It turns out that $n$ variables xor'd together evaluates to true if and only if the number of variables assigned to true is odd. But how to prove such a thing? Induction of course!

$x_1 \oplus x_2 \oplus \cdots \oplus x_n$ evaluates to true under interpretation $I$ if and only if the number of variables in $x_1,\ldots,x_n$ that are true under $I$ is odd.

We will prove this by induction on $k$, the the number of $\oplus$'s. If $k=0$ then the formula is the single variable $x_1$, and so is true when $x_1$ is true (odd number of trues) and false when $x_1$ is false (even number of trues, since zero is even!). So consider the case when $k > 0$. Let's call the original formula "$F$". The last variable is $x_{k+1}$, since $n = k+1$, so we get: $$ F := \underbrace{x_1 \oplus x_2 \oplus \cdots \oplus x_k}_{\text{call this $G$, note $k-1$ $\oplus$'s}} \oplus x_{k+1} $$ Thus, the original formula $F = G \oplus x_{k+1}$, where $G$ has $k-1$ xors. By the inductive hypothesis, $G$ is true if and only if an odd number of $x_1,\ldots,x_{k}$ is true. We have four cases, and we show the theorem holds in all four:

case	$G$	$x_{k+1}$	num. trues in $G$	num. trues in $F$	$G \oplus x_{k+1} = F$
1.	F	F	even	even	F⊕F = F
2.	F	T	even	odd	F⊕T = T	In all four cases, "the number of trues in $F$ is odd" $\Leftrightarrow$ "$F$ is true".
3.	T	F	odd	odd	T⊕F = T
4.	T	T	odd	even	T⊕T = F
			↑ these entries are justified by the inductive hypothesis

So, by the principle of induction, we deduce that the theorem holds for any number of $\oplus$'s.

Obviously this is a more complicated inductive proof than the others you have seen. I encourage you to identify the different elements of an inductive proof in this. I also want you to realize that propositional logic deductions and first order logic deductions are still at play here ... we just leave out the details. Here's case 2 in all it's details:

1: ~(G evaluates to true)                                            [Given]
2: x_k+1 evaluates to true                                             [Given]
3: G evaluates to true <=> number of true variables in G is odd      [Inductive hypothesis] 
4: number of true variables in G is odd => G evaluates to true       [Equivalence splitting on 3]
5: ~(G evaluates to true) => ~(number of true variables in G is odd) [Contrapositive of 4]
6: ~(number of true variables in G is odd)                           [Modus Ponens on 5 and 1]
7: number of true variables in G is even                             [from 6. OK ... this involves some deductions about even/odd that I won't do]
8: number of true variables in G⊕x_k+1 is odd                          [2 and 7 ... more even/odd deductions]
9: G⊕x_k+1 evaluates to true                                           [1 and 2 and the definition of xor]
>>> 8 and 9 together mean that the theorem holds in this case!