Notes and Questions

Well-Ordering Principle Proof

Odd Summation. (Problem 2.12) Prove that for all $n > 0$, the sum of the first $n$ odd numbers is $n^2$.

# # ## Notations Mathematics and other domains often use many symbols to mean the same thing. Section 3.2 of the book gives some common notations, but there are others in common use. \begin{center} \begin{tabular}{cccc} English & Logic & C, Java, Rust & Python \\ \hline $P$ \smallcaps{implies} $Q$ & $P \implies Q$ {\em or} $P \longrightarrow Q$ & - & - \\ \smallcaps{not}$(P)$ & $\neg P$ {\em or} $\overline{P}$ & \verb+!p+ & \verb+not p+ \\ $P$ \smallcaps{and} $Q$ & $P \wedge Q$ & \verb+p && q+ & \verb+p and q+ \\ $P$ \smallcaps{or} $Q$ & $P \vee Q$ & \verb+P || Q+ & \verb+p or q+ \\ $P$ \smallcaps{xor} $Q$ & $P \oplus Q$ & \verb+p ^ q+ (bitwise) or \verb+p != q+ & \verb+p ^ q+ \\ \end{tabular} \end{center} For what values in Java or C are \verb+p ^ q+ and \verb+p != q+ both valid, but have different meanings? ## Logical Formulas \begin{center} \begin{tabular}{c|c|c} $P$ & \smallcaps{not}$(P)$ & \_\_\_\_\_\_\_\_ \\ \hline \T & \F & \\ \F & \T & \\ \end{tabular} \end{center} How many one-input Boolean operators are there? How many do we need to produce them all? # \begin{center} \begin{tabular}{cc|c|c|c|c|c} $P$ & $Q$ & $P \wedge Q$ & $P \vee Q$ & $P \implies Q$ & \_\_\_\_\_\_\_\_ & $P \oplus Q$ \\ \hline \T & \T & \T & \T & & \T & \F \\ \T & \F & & \T & & \F & \T \\ \F & \T & & \T & & \F & \T \\ \F & \F & & \F & & \T & \F \\ \end{tabular} \end{center} How many two-input Boolean operators are there? # **De Morgan's Laws:** $$\neg(P \wedge Q) \equiv (\neg P) \vee (\neg Q) \qquad \neg(P \vee Q) \equiv (\neg P) \wedge (\neg Q)$$ How can these be written without the $\neg$ in front? ## Prove that it is possible to make all two-input Boolean operators using just \smallcaps{not} and any _odd_ two-input operator. (An operator is _odd_, if the number of outputs that are **True** are odd.) ## **Definition: valid.** A logical formula is _valid_ if there is no way to make it **false**. That is, no matter what truth values its variables have, it is always **true**. (Another name for this is a _tautology_.) **Definition: satisfiable.** A logical formula is _satisfiable_ if there is _some_ way to make it **true**. That is, there is at least one assignment of truth value to its variables that makes the forumla true. For each of the formulas below, determine if it is _valid_ and if it is _satisfiable_. 1. $(P \vee \neg P)$ 2. $(P \vee Q) \wedge (\neg P \vee Q)$ 3. $((P \implies Q) \wedge (Q \implies P)) \vee (P \xor Q)$

Notes and Questions

Definition. A set is well-ordered with respect to an ordering function (e.g., <), if all of its non-empty subsets has a minimum element.

What properties must a sensible ordering function have?

Trichotomy. A relation, $\prec$, satisfies the axiom of trichotomy if exactly one of these is true for all elements $a$ and $b$: $a \prec b$, $b \prec a$ or $a = b$.

Which of these are well-ordered?

• The set of non-negative integers, comparator $<$.
• The set of integers, comparator $<$.
• The set of integers, comparator $|a| < |b|$.
• The set of integers, comparator if |a| = |b|: $a < b$, else: $|a| < |b|$.
• The set of national soccer teams, comparator winning games.

Prove the set of positive rationals is not well-ordered under $<$.

#

Provide a comparison function that can be used to well-order the positive rationals.

Template for Well-Ordering Proofs (Section 2.2)

To prove that $P(n)$ is true for all $n \in \mathbb{N}$:

1. Define the set of counterexamples, $C ::= { n \in \mathbb{N} | NOT(P(n)) }$.
2. Assume for contradiction that $C$ is ______________.
3. By the well-ordering principle, there must be __________________ , $m \in C$.
4. Reach a contradiction (this is the creative part!). One way to reach a contradiction would be to show $P(m)$. Another way is to show there must be an element $m’ \in C$ where $m’ < m$.
5. Conclude that $C$ must be empty, hence there are no counter-examples and $P(n)$ always holds.

Example: Betable Numbers. A number is betable if it can be produced using some combination of \$2 and \$5 chips. Prove that all integer values greater than \$3 are betable.

# # # **Example: Division Property.** Given integer $a$ and positive integer $b$, there exist integers $q$ and $r$ such that: $a = qb + r$ and $0 \le r < b$. # # _The whole problem with the world is that fools and fanatics are always so certain of themselves, and wiser people so full of doubts._ Bertrand Russell

# 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

### Notes and Questions Why is most of the math used in computer science _discrete_?

Why is most of the math you have used in school previously continuous?

What are the differences between how scientists, lawyers, and mathematicians establish ``truth”?

A proposition is a statement that is either ________ or _________.

A predicate is a proposition whose truth may depend on the value of variables.

Proof

A theorem is a ____________ that has been proven true.

An axiom is a proposition that is accepted to be true. Axioms are not proven; they are assumed to be true.

Definition. A mathematical proof of a proposition is a chain of logical deductions starting from a set of accepted axioms that leads to the proposition.

Rules of Inference

The possible steps that can be used in a proof are logical deductions based on inference rules.

Inference rules are written as: $$ \infer{\textrm{\emph{conclusion}}}{\textrm{\emph{antecedents}}} $$ This means if everything on top of the rule is established to be true, then you can conclude what is on the bottom.

Modus Ponens: To prove Q, (1) prove P and (2) prove that P implies Q. ($P \implies Q$ is a notation for $P$ implies $Q$).

$$ \infer{Q}{P,\quad P \implies Q} $$

An inference rule is sound if can never lead to a false conclusion.

Which of these inference rules are sound?

$$ \infer{Q}{P} \qquad \infer{false}{P, P \implies Q} \qquad \infer{true}{P, NOT(P)} \qquad \infer{P \implies NOT(P)}{P, NOT(P)} \qquad \infer{NOT(Q) \implies P}{NOT(P) \implies Q} $$

##

Contrapositive:

$$ \infer{NOT(Q) \implies NOT(P)}{P \implies Q} \qquad \infer{P \implies Q}{NOT(Q) \implies NOT(P)} $$

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