MATH 582, INTRODUCTION TO SET THEORY, WINTER 1999

What is a proof?

Mathematics is a dual activity. We think in terms of intuitions and visualizations, but we prove things from axioms and definitions via logical reasoning. But what exactly are proofs? How do we know our reasoning is logical? Proofs can be defined very precisely and in a formal way; this is done in a logic course. In this set theory course, we have been precise about what formulas are, but we will be somewhat more informal about proofs. Still, there are certain patterns that occur over and over in mathematical proofs; for instance, to prove a statement of the form ∀x.P (x), we take an arbitrary x and then prove P (x). To prove P ⇒ Q, we assume P and then prove Q. The following table summarizes some expressions that are commonly used in proofs. The parts in [brackets] must be filled in.

To prove:  you might do 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  [Prove P]. [Prove Q]. Therefore P ∧ Q.

∀x.P (x)

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

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

∃x.P (x)  [Construct an object a]. [Prove P (a)]. We have shown P (a), hence ∃x.P (x).
P ∨ Q  [Prove P]. Therefore we have P ∨ Q.
Or: [Prove Q]. Therefore we have P ∨ Q.

Or: Case distinction: If P, we are done proving P ∨ Q. Assume that, on the contrary, ¬P. [Prove Q]. In either case, we have shown P ∨ Q.

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 formula). 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, and axioms, as well as statements that you have previously proved:

The statement:  can be used as follows:
P ⇒ Q  If you know P, you may conclude Q.
P ∧ Q  You may conclude P. You may also conclude Q.
∀x.P (x)  You may conclude P (a), for any a of your choosing.
¬P  If you also know P, you may derive a contradiction.
∃x.P (x)  You may introduce a new name b for some set that satisfies P (b).

P ∨ Q You may prove any formula C by a case distinction as follows: Assume P. [Prove C]. Now assume Q. [Prove C]. In either case, we have proved C.

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

The only primitive concepts in set theory are that of set and element. All other concepts are defined, i.e. they have been introduced as abbreviations. If you are proving something about such a defined concept, then you have to use the definition. For instance:

To prove:  you have to show:
a ⊆ b  ∀x(x ∈ a ⇒ x ∈ b).
a = b (for sets)  ∀x(x ∈ a ⇒ x ∈ b) and ∀x(x ∈ b ⇒ x ∈ a) (by extensionality).
x ∈ a ∩ b  x ∈ a and x ∈ b.
x ∈ ⋃ A  ∃z(x ∈ z ∧ z ∈ A).
x ∈ PA  x ⊆ A.

and so on. Of course, you may also use any lemmas that you have previously proved, that have been proved in class, etc.

Notice the difference between (1) a hypothetical assumption, and (2) using something that you already know. For example, if you want to prove x ∈ A ⇒ x ∈ B, then you assume x ∈ A and proceed to show x ∈ B. At this point, you do not need to be concerned about whether such an x ∈ A actually exists; you are simply proving something about a hypothetical x ∈ A. On the other hand, suppose you already know (or you have previously assumed) that a certain set A is non-empty. In this case, you are allowed to pick some b ∈ A and use that element b in your further proof. Here, the assumption that b ∈ A is not hypothetical; you are simply giving the name “b” to something that you already know exists. But to be allowed to do this, you need to know ahead of time that A is non-empty.

As an example, let us consider a proof of the simple statement

∀A∀x(x ∈ A ⇒ x ⊆ ⋃ A).

If you want to be extremely verbose, you could write the following proof.

We want to show ∀A∀x(x ∈ A ⇒ x ⊆ ⋃ A). Consider an arbitrary A.

(*)  We will prove ∀x(x ∈ A ⇒ x ⊆ ⋃ A).

Consider an arbitrary x.

(*)  We will prove x ∈ A ⇒ x ⊆ ⋃ A.

Assume x ∈ A.

(*)  We will prove x ⊆ ⋃ A.
(*)  By definition of ⊆, we have to show ∀z(z ∈ x ⇒ z ∈ ⋃ A).

Consider an arbitrary z.

(*)  We will prove z ∈ x ⇒ z ∈ ⋃ A.

Assume z ∈ x.

(*)  We will prove z ∈ ⋃ A.
(*)  By definition of ⋃ A, we have to show ∃b(z ∈ b ∧ b ∈ A).

We know that z ∈ x and x ∈ A.

(*)  Thus, taking b = x, we have proved ∃b(z ∈ b ∧ b ∈ A).

Thus, we have proved z ∈ ⋃ A.

(*)  Since we assumed z ∈ x, we have proved z ∈ x ⇒ z ∈ ⋃ A.

Since z was arbitrary, (*) we have proved ∀z(z ∈ x ⇒ z ∈ ⋃ A). This shows x ⊆ ⋃ A.

(*)  Since we have assumed x ∈ A, we have proved x ∈ A ⇒ x ⊆ ⋃ A.
(*)  Since x was arbitrary, this proves ∀x(x ∈ A ⇒ x ⊆ ⋃ A).
(*)  Since A was arbitrary, this proves ∀A∀x(x ∈ A ⇒ x ⊆ ⋃ A).

So we are done.

Obviously, this proof is very redundant and tedious. Since your proofs will probably be read by people, and not by computers, you can leave some things implicit. For instance, if we omit all the parts marked (*), we get a much more readable proof.

We want to show ∀A∀x(x ∈ A ⇒ x ⊆ ⋃ A). Consider arbitrary A and x such that x ∈ A. Consider an arbitrary z ∈ x. We know that z ∈ x and x ∈ A. Thus, by definition of ⋃ A, we have proved z ∈ ⋃ A. Since z was arbitrary, this shows x ⊆ ⋃ A, by definition of ⊆. We are done.

Usually, one will be even more concise and write, for instance:

We want to show ∀A∀x(x ∈ A ⇒ x ⊆ ⋃ A). So let x ∈ A. Then for any z ∈ x, by definition of union, we have z ∈ ⋃ A. Thus, by definition of subset, x ⊆ ⋃ A, and we are done.

For another discussion of logic and proofs, see the Appendix in Enderton (p.263ff).