MAT 3343, APPLIED ALGEBRA, FALL 2003

Handout 1: What is a proof?

This handout summarizes some basic techniques used in “everyday” proofs. We use the usual logical notations P ∧Q for “P and Q”, P ∨Q for “P or Q”, P ⇒ Q for “P implies Q”, ¬P for “not P ”, ∀x ∈ A.P (x) for “for all x ∈ A, P (x)”, ∃x ∈ A.P (x) for “there exists an x ∈ A such that P (x)”.,

There are certain patterns that occur over and over in mathematical proofs; for instance, to prove a statement of the form ∀x ∈ A.P (x), we have to take an arbitrary x ∈ A and then prove P (x). To prove P ⇒ Q, we assume P and then prove Q. The following table summarizes some phrases and formulations that are commonly used in proofs. The parts in [brackets] must be filled in.

To prove:  you might write the following:

P ⇒ Q Assume P. [Prove Q]. Since we assumed P, this proves P ⇒ Q.

Or: Assume ¬Q. [Prove ¬P]. We have proved ¬Q ⇒ ¬P, which, by taking the contrapositive, implies P ⇒ Q.

P ∧ Q First we prove P. [Prove P]. Then we prove Q. [Prove Q].

∀x ∈ A.P (x)

Take an arbitrary x ∈ A. [Prove P (x)]. Since x was arbitrary, this proves ∀x ∈ A.P (x).

¬P Assume P. [Derive a contradiction]. The assumption P led to a contradiction, therefore we have shown ¬P.

∃x ∈ A.P (x)  [Construct an object a]. [Prove P (a)].
P ∨ Q  [Prove P]. This implies P ∨ Q.
Or: [Prove Q]. This implies P ∨ Q.

Or: By contradiction: Assume neither P nor Q holds. [Derive a contradiction]. Therefore, either P or Q must be true.

Or: If P holds, we are done. So assume ¬P. [Prove Q]. Therefore P ∨ Q.

(continued on the next page)

To prove:  you might write the following:

P (by contradiction)

Assume ¬P. [Derive a contradiction]. The assumption ¬P led to a contradiction, thus we have proved P.

P (by case distinction)

(Here, Q is some statement). We distinguish two cases. Case 1: Q holds. [Prove P]. Case 2: ¬Q holds. [Prove P]. In either case, we have proved P.

(to divide a long proof)

We will first show P. [Show P]. We have shown P. (etc.)

Another question is how you can use assumptions, hypotheses, axioms, and previously proved statements.

The statement:  can be used as follows:
P ⇒ Q  If you know P, you may conclude Q.
P ∧ Q  You may use P. You many also use Q.
∀x ∈ A.P (x)  If you know x ∈ A, you may conclude P (x).

¬P ∧ P This is a contradiction. Use it to conclude that the most recent assumption was false.

∃x ∈ A.P (x)

You may conclude P (b), for some unknown element b ∈ A. (You cannot choose b).

P ∨ Q You can use this in a case distinction. Suppose you are in the process of proving some statement C. Case 1: Assume P. [Prove C]. Case 2: Assume Q. [Prove C]. Then you know C is true.

a = b  If you know P (a), you may conclude P (b).

Here are a few more useful patterns, some from set theory.

To prove:  you have to show:
P ⇔ Q  P ⇒ Q and Q ⇒ P.
A ⊆ B  For all x ∈ A, we must show that x ∈ B.
A = B (for sets)  A ⊆ B and B ⊆ A.
x ∈ A ∩ B  x ∈ A and x ∈ B.
x ∈ A ∪ B  x ∈ A or x ∈ B.