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$.

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).

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).

## 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.