Proof Strategies

[UNDER CONSTRUCTION]

Daniel J. Velleman’s popular handbook [1] on proving technique’s is simply fantastic. Below I offer some snippets.

Definitions

• hypothesis: the antecedent (if component) of a conditional statement; in this context, hypotheses (also called premises) are treated as assumptions
• conclusion: the consequent (then component) of a conditional statement; in this context, conclusions are the elements, which, if proven false, render the statement under consideration incorrect
• theorem: a statement that says if certain hypotheses are true, then some conclusion must also be true (and, thus, the statement has been proven)

Symbols

• $P,Q,...$ statements: as individual letters, each is used as a shorthand to represent a given statement (also known as a proposition or a operand), which, known or unknown, may be TRUE or FALSE (e.g., let $P$ stand for $2 + 2 = 4$; $P$, in this case, is TRUE)
• $\neg$ negation/complement: the NOT truth function, a unary connective, also known as an operator, that returns the inverted truth value of the connected statement; for example, if $P$ is TRUE, $\neg P$ is FALSE
• $\vee$ inclusive disjunction: the OR truth function, is a binary connective that returns the value TRUE if at least one of the connected statements is TRUE
• $\wedge$ conjunction: the AND truth function, is a binary connective that returns the value TRUE if both connected statements are TRUE

Truth Tables (T = TRUE, F = FALSE)

Format

A logical argument may take the form:

Let $P$ stand for the statement $(3 < \pi)$.
Let $Q$ stand for the statement $(3 = \pi)$.

Then $P \vee Q$ stands for $(3 \leq \pi)$.
Then $\neg Q$ means $(3 \neq \pi)$.

Assuming $P \vee Q$.
Given $\neg Q$.

Therefore, $P$.

To prove a conclusion of the form $P \rightarrow Q$, assume $P$ is TRUE and then prove $Q$. If $P$ is assumed, it may then be used as any other hypothesis.

REFERENCES

[1] D. Velleman, How to Prove It: A Structured Approach. Cambridge: Cambridge University Press, 2006.