A: Some Rules of Logic

Constructing mathematical proofs is an art that is best learned by seeing many examples of proofs and by trying to imitate these examples when constructing one’s own proofs. Nevertheless, there are a few rules of logic and language that it is useful to be aware of. Most of these are very natural and will be used without comment. Their full understanding only comes with experience. We begin with some basic assumptions concerning equality.

1. \(x =x\) holds for all \(x\). [ Reflexivity.]
2. If \(x= y\) then \(y=x\). [Symmetry.]
3. If \(x=y\) and \(y=z\) then \(x=z\). [Transitivity.]

For example, if we are able to prove \(x=y\), \(y=z\), \(z=w\) and \(w=r\), then we may conclude by transitivity of equality that \(x=r\). Reflexivity and symmetry of equality are also very useful. It is not necessary to quote these rules everytime they are used, but it is good to be aware of them (in case someone asks).

Implications are crucial to the development of mathematics. An implication is a statement of the form

\[\begin{align} \mbox{ If $P$ then $Q$} \label{A1}\end{align}\] where \(P\) and \(Q\) are statements. Instead of (A.1) we will sometimes write

\[\begin{align} P \Longrightarrow Q . \label{A2} \end{align}\] The statement (A.2) is read,“\(P\) implies \(Q\)”. We call \(P\) the hypothesis and, \(Q\) the conclusion of the implication (A.2). Students should be careful when using this notation. For example, do not write \[\nonumber {\mbox{If} \ P \Longrightarrow Q}\] when you mean

\[\begin{align} \label{implication} P \Longrightarrow Q \end{align}\]

To prove the implication \(P \Longrightarrow Q\), start by assuming that \(P\) is true and use this assumption to establish the validity of \(Q\). It is sometimes easier to prove the equivalent statement \[\begin{align} \label{contrapositive} \mbox{$Q$ is false} \Longrightarrow \mbox{$P$ is false} \end{align}\] This is called the contrapositive of the implication (A.3).

We write

\[\begin{align} P \Longleftrightarrow Q \label{A3} \end{align}\] as an abbreviation for the two statements \[P \Longrightarrow Q \quad \mbox{ and } \quad Q \Longrightarrow P\] So, for example, if you need to prove \(P \Longleftrightarrow Q\) you really have two things to prove: both \(P \Longrightarrow Q\) and \(Q \Longrightarrow P\). The statement (A.5) is read \[\mbox{``$P$ is equivalent to $Q$''},\] or \[\mbox{``$P$ holds if and only if $Q$ holds.''}\] And sometimes we use the abbreviation “iff” for “if and only if”. So an acceptable alternative to (A.5) is \[\mbox{$P$ \ iff \ $Q$}\].

We assume that implication satisfies the following rules:

1. \(P \Longrightarrow P\) holds for all \(P\). [ Reflexivity.]
2. If \(P \Longrightarrow Q\) and \(Q \Longrightarrow R\) then \(P \Longrightarrow R\). [Transitivity.]

We assume that equivalence satisfies the following rules.

1. \(P \Longleftrightarrow P\) holds for all \(P\). [ Reflexivity.]
2. If \(P \Longleftrightarrow Q\) then \(Q \Longleftrightarrow P\). [Symmetry.]
3. If \(P \Longleftrightarrow Q\) and \(Q \Longleftrightarrow R\) then \(P \Longleftrightarrow R\). [Transitivity.]

We will often use these rules for implication and equivalence without comment.

Convention In definitions the word if means if and only if. Compare, for example, Definition 2.2.

Important Phrases In addition to looking for implications and equivalences, students should pay close attention to the following words and phrases:

1. there exists
2. there is
3. there are
4. for all
5. for each
6. for every
7. for some
8. unique
9. one and only one
10. at most one
11. at least one
12. the
13. a, an
14. such that
15. implies
16. hence
17. therefore

The use of these phrases and words will be clarified if necessary as the course progresses. Some techniques of proof such as proof by contradiction and proof by induction are best understood by examples of which we shall see many as the course progresses.