How to Prove It summary

“How to Prove It” by D. Velleman introduces the reader to mathematical reasoning, logic, and some set theory. In addition, it covers functions, relations, and proofs.

In my opinion, this book is the base for understanding any mathematical subject.

Programming wise, design patterns get obsolete. Programming languages get obsolete. Libraries get obsolete. Mathematics doesn’t. Besides CS foundations, logic and proofs will make you better at understanding abstractions.

Proofs are at a very high level compared to programming. However, writing proofs on a very low level is possible (check Metamath), where you work with wff and rewrite rules. It gets as tricky as programming.

Anyway, it is important to go through the exercises. Every concept is properly introduced before the exercises. The chapter names make it obvious what is introduced: propositional and predicate logic, proof strategies, mathematical induction, and parts of set theory: relations (ordering relations, closures, equivalence relations), Cartesian tuples and functions.

Highly recommend this book.

Goal form	Given	Use
$P \to Q$	Assume $P$ and prove $Q$	If $P$ is given, conclude $Q$
$\lnot P$	Assume $P$ and arrive at a contradiction	If $P$ can be proven, conclude a contradiction
$P_1 \land \ldots \land P_n$	Prove each of $P_1, \ldots, P_n$	Treat $P_1, \ldots, P_n$ as given
$P_1 \lor \ldots \lor P_n$	Prove that at least one of $P_1, \ldots, P_n$	Use proof by cases, in each case assume one of $P_1, \ldots, P_n$
$P \leftrightarrow Q$	Prove $P \to Q$ and $Q \to P$	Conclude $P \to Q$ and $Q \to P$
$\forall x, P(x)$	Assume $x$ is an arbitrary object and prove $P(x)$	For any $x$ , conclude $P(x)$
$\exists x, P(x)$	Find an $x$ such that $P(x)$	Introduce a new variable, say $x_0$ so that $P(x_0)$

$\top \land \top = \top$ , and $\bot \lor \bot = \bot$ with $\top \to \bot = \bot$ (remaining are $\top$ ).

For example, to prove $A \land B \to A \lor B$ , we assume $A \land B$ (otherwise, it’s vacuously true) and use proof by cases. Since we’re given $A \land B$ , we are given $A$ . Similarly, we are also given $B$ . Thus, $A \lor B$