A proof is a sequence of statements. These statements come in two forms: givens and deductions. The following are the most important types of "givens.''
Hypotheses: Usually the theorem we are trying to prove is of the form $$P_1\land\ldots\land P_n \Rightarrow Q.$$ The $P$s are the hypotheses of the theorem. We can assume that the hypotheses are true, because if one of the $P_i$ is false, then the implication is true.
Known results: In addition to any stated hypotheses, it is always valid in a proof to write down a theorem that has already been established, or an unstated hypothesis (which is usually understood from context).
Definitions: If a term is defined by some formula it is always legitimate in a proof to replace the term by the formula or the formula by the term.
We turn now to the most important ways a statement can appear as a consequence of (or deduction from) other statements:
Tautology: If $P$ is a statement in a proof and $Q$ is logically equivalent to $P$, we can then write down $Q$.
Modus Ponens: If the formula $P$ has occurred in a proof and $P\Rightarrow Q$ is a theorem or an earlier statement in the proof, we can write down the formula $Q$. Modus ponens is used frequently, though sometimes in a disguised form; for example, most algebraic manipulations are examples of modus ponens.
Specialization: If we know "$\forall x\,P(x)$,'' then we can write down "$P(x_0)$'' whenever $x_0$ is a particular value. Similarly, if "$P(x_0)$'' has appeared in a proof, it is valid to continue with "$\exists x\,P(x)$''. Frequently, choosing a useful special case of a general proposition is the key step in an argument.
When you read or write a proof you should always be very clear exactly why each statement is valid. You should always be able to identify how it follows from earlier statements.
A direct proof is a sequence of statements which are either givens or deductions from previous statements, and whose last statement is the conclusion to be proved.
Variables: The proper use of variables in an argument is critical. Their improper use results in unclear and even incorrect arguments. Every variable in a proof has a quantifier associated with it, so there are two types of variables: those that are universally quantified and those that are existentially quantified. We may fail to mention explicitly how a variable is quantified when this information is clear from the context, but every variable has an associated quantifier.
A universally quantified variable is introduced when trying to prove a statement of the form $\forall x (P(x)\Rightarrow Q(x))$. The language typically employed is "Suppose $x$ satisfies $P(x)$,'' "Assume $P(x)$,'' or "Let $P(x)$.''
When we introduce an existentially quantified variable, it is usually defined in terms of other things that have been introduced previously in the argument. In other words, it depends on the previously mentioned quantities in the proof.
Definition 2.1.1 We say the integer $n$ is even if there is an integer $k$ such that $n=2k$. We say $n$ is odd if there is a $k$ such that $n=2k-1$. $\square$
Example 2.1.2 If $n$ is even, so is $n^2$.
Proof. Assume $n$ is an even number ($n$ is a universally quantified variable which appears in the statement we are trying to prove). Because $n$ is even, $n=2k$ for some $k$ ($k$ is existentially quantified, defined in terms of $n$, which appears previously). Now $n^2=4k^2=2(2k^2)$ (these algebraic manipulations are examples of modus ponens). Let $j=2k^2$ ($j$ is existentially quantified, defined in terms of $k$); then $n^2=2j$, so $n$ is even (by definition).$\qed$
Example 2.1.3 The sum of two odd numbers is even.
Proof. Assume $m$ and $n$ are odd numbers (introducing two universally quantified variables to stand for the quantities mentioned in the statement). Because $m$ and $n$ are odd there are integers $j$ and $k$ such that $m=2j-1$ and $n=2k-1$ (introducing existentially quantified variables, defined in terms of quantities already mentioned). Now $m+n=(2j-1)+(2k-1)=2(j+k-1)$ (modus ponens). Let $i=j+k-1$ (existentially quantified); then $m+n=2i$ is even (by definition).$\qed$
Exercises 2.1
In 1-4, write proofs for the given statements, inserting parenthetic remarks to explain the rationale behind each step (as in the examples).
Ex 2.1.1 The sum of two even numbers is even.
Ex 2.1.2 The sum of an even number and an odd number is odd.
Ex 2.1.3 The product of two odd numbers is odd.
Ex 2.1.4 The product of an even number and any other number is even.
Ex 2.1.5 Suppose in the definitions of even and odd the universe of discourse is assumed to be the real numbers, $\R$, instead of the integers. What happens? What if the universe is the natural numbers, $\N$? (When we say the universe is $U$ we mean that both $n$ and $k$ in the definition are from $U$.)
Ex 2.1.6 Prove that $x$ is odd if and only if $|x|$ is odd.
Ex 2.1.7 If $x$ and $y$ are integers and $x^2+y^2$ is even, prove that $x+y$ is even.