Class 2: Proof Methods

# Notes and Questions An integer, $z$, is **even** if there exists an integer $k$ such that $z = 2k$. Is this a _definition_, _axiom_, or _proposition_? # An integer, $z$, is **odd** if there exists an integer $k$ such that $z = 2k + 1$. (Note that there is no connection between the variables used here, and to define even above.) To prove an implication, $P \implies Q$: 1. assume $P$. 2. Show chain of logical deductions that leads to $Q$. **Odd-Even Lemma:** If an integer is not even, it is odd. Note: A _lemma_ is just a name for a theorem, typically used for proving another theorem.

How should one decide what can be accepted as an axiom, and what must be proven?

What is the purpose of a proof? (in cs2102? in software development? in algorithm design?)

Proof from Class

Proposition: If the product of $x$ and $y$ is even, at least one of $x$ or $y$ must be even.

Our goal is to prove the implication, $P \implies Q$, where:

• $P$ is “the product of $x$ and $y$ is even”
• $Q$ is “at least one of $x$ and $y$ must be even”

We will prove the contrapositive. The inference rule,

$$ \infer{P \implies Q}{NOT(Q) \implies NOT(P)} $$ will be the last step in our proof. To be able to use this rule, we need to make the antecedent true. So, our goal is to prove $NOT(Q) \implies NOT(P)$.

To prove an implication, we assume the left side and short the right side. So, our proof begins:

1. We prove the contrapositive.
2. Assume NOT(at least one of $x$ and $y$ must be even).
3. By the meaning of negation, this means both $x$ and $y$ are not even.
4. By the “Odd-Even Lemma”, both $x$ and $y$ are odd.
5. By the definition of odd, there exist integers $k$ and $m$ such that $x = 2k + 1$ and $y = 2m + 1$.
6. Substituting, $xy = (2k + 1)(2m + 1) = 4mk + 2m + 2k + 1 = 2(2mk + m + k) + 1$.
7. By the closure of addition and multiplication over the integers, there is some integer $r = 2mk + m + k$, so $xy = 2r + 1$.
8. By the definition of odd, $xy$ is odd.
9. By the (not proven) “Even-Odd Lemma”, this means $xy$ is not even.
10. So, we have shown NOT(the product of $x$ and $y$ is even).
11. Since we concluded this starting from the assumption (step 2), this proves the implication: NOT(at least one of $x$ and $y$ must be even) $\implies$ NOT(the product of $x$ and $y$ is even).
12. Using the contrapositive inference rule, we can conclude: the product of $x$ and $y$ is even $\implies$ at least one of $x$ and $y$ must be even. \QEDA

\dbox{ {\bf Challenge Problem Opportunity.} I wasn’t very satisfied with my proof of the “Odd-Even Lemma” in class. I hope a student will come up with a better proof. A proof that passes the “skeptical reader” test and would convince someone with no prior knowledge of odd and even numbers is worth up to 10 bonus points. }

Proving “If and Only If”

Strategy: To prove $P$ if and only if $Q$:

1. Prove $P \implies Q$.
2. Prove $Q \implies P$.

Definition. The standard deviation of a sequence of values $x_1, x_2, \ldots, x_n$ is $$ \sqrt{\frac{(x_1 - \mu)^2 + (x_2 - \mu)^2 + \ldots + (x_n - \mu)^2}{n}} $$ where $\mu$ is the mean of the values: $$ \mu ::= \frac{x_1 + x_2 + \ldots + x_n}{n} $$.

Theorem 1.6.1. The standard deviation of a sequence of values, $x_1, x_2, \ldots, x_n$ is $0$ if and only if all of the $x_i$ values are equal to the mean of $x_1, x_2, \ldots, x_n$.

The book proves this using a chain of iff implications; prove it using the two-implications strategy.

#

#

#

#

#

#

#

#

In physics, your solution should convince a reasonable person. In math, you have to convince a person who’s trying to make trouble. Frank Wilczek