3.1 Propositions

3.1   Definition (Proposition.) A proposition is a statement that is either true or false. I will sometimes write a proposition inside of quotes (`` ''), when I want to emphasize where the proposition begins and ends.

3.2   Examples.

If $P_1 = \lq\lq 1+1=2$'', then $P_1$ is a true proposition.

If $P_2 = \lq\lq 1+1=3$'', then $P_2$ is a false proposition.

If $P_3 = \lq\lq 2 \mbox{ is an even number}$'', then $P_3$ is a true proposition.

If $P_4 = \lq\lq 7 \mbox{ is a lucky number}$'', then I will not consider $P_4$ to be a proposition (unless lucky number has been defined.)

3.3   Definition (And, or, not.) Suppose that $P$ and $Q$ are propositions. Then we can form new propositions denoted by ``$P$ and $Q$'', ``$P$ or $Q$'', and ``not $P$''.

``$P$ and $Q$'' is true if and only if both of $P,Q$ are true.

``$P$ or $Q$'' is true if and only if at least one of $P,Q$ is true.

``not $P$'' is true if and only if $P$ is false.

Observe that in mathematics, ``or'' is always assumed to be inclusive or: If ``$P$'' and ``$Q$'' are both true, then ``$P$ or $Q$'' is true.

3.4   Examples.

``$1 +1=2$ and $1+1=3$'' is false.

``$1 +1=2$ or $1+1=3$'' is true.

``$1 +1=2$ or $2+2=4$'' is true.

``not(not $P$)'' is true if and only if $P$ is true.

For each element $x$ of Q let $R(x)$ be the proposition
`` $x^2 + 5 x + 6 = 0$''. Thus $R(-3)$ = `` $(-3)^2 + 5 \cdot (-3) + 6 = 0$'', so $R(-3)$ is true, while $R(0)$ = `` $0^2 + 5 \cdot 0 + 6 = 0$'', so $R(0)$ is false. Here I consider $R$ to be a rule which assigns to each element $x$ of Q a proposition $R(x).$

3.5   Definition (Proposition form.) Let $S$ be a set. A rule $P$ that assigns to each element $x$ of $S$ a unique proposition $P(x)$ is called a proposition form over $S$.

Thus the rule $R$ defined in the previous paragraph is a proposition form over Q. Note that a proposition form is neither true nor false, i.e. a proposition form is not a proposition.

3.6   Definition ( $\mbox{$\Longleftrightarrow$}$, Equivalent propositions.) Let $P,Q$ be two propositions. We say that ``$P$ is equivalent to $Q$'' if either ($P,Q$ are both true) or ($P,Q$ are both false). Thus every proposition is equivalent either to ``$1 +1=2$'' or to ``$1+1=3.$ '' We write `` $P \Longleftrightarrow Q$'' as an abbreviation for ``$P$ is equivalent to $Q.$'' If $P,Q$ are propositions, then `` $P \Longleftrightarrow Q$'' is a proposition, and

`` $P \Longleftrightarrow Q$'' is true if and only if (($P,Q$ are both true) or ($P,Q$ are both false)).

Ordinarily one would not make a statement like

`` $(1 + 1 = 2) \Longleftrightarrow ( 4421 \mbox{ is a prime number}$)''

even though this is a true proposition. One writes `` $P \mbox{$\Longleftrightarrow$} Q$'' in an argument, only when the person reading the argument can be expected to see the equivalence of the two statements $P$ and $Q$.

If $P,Q,R$ and $S$ are propositions,then

$$P \mbox{$\Longleftrightarrow$} Q \mbox{$\Longleftrightarrow$} R \mbox{$\Longleftrightarrow$} S$$ (3.7)

is an abbreviation for

$$((P \mbox{$\Longleftrightarrow$} Q) \mbox{ and } (Q \mbox{$... ...arrow$} R)) \mbox{ and } (R \mbox{$\Longleftrightarrow$} S).$$

Thus if we know that (3.7) is true, then we can conclude that $P \mbox{$\Longleftrightarrow$} S$ is true. The statement `` $P \mbox{$\Longleftrightarrow$} Q$'' is sometimes read as `` $P$ if and only if $Q$''.

3.8   Example. Find all real numbers $x$ such that

$$x^2-5x+6=0.$$ (3.9)

Let $x$ be an arbitrary real number. Then

$$\begin{eqnarray*} x^2 -5x +6 = 0 & \mbox{$\Longleftrightarrow$}& (x-2)(x-3) = 0 ... ...0 )\\ & \mbox{$\Longleftrightarrow$}& (x= 2) \mbox{ or }(x=3). \end{eqnarray*}$$

Thus the set of all numbers that satisfy equation (3.9) is {2,3}. $\diamondsuit$

3.10   Definition ( $\mbox{$\Longrightarrow$}$, Implication.) If $P$ and $Q$ are propositions then we say ``$P$ implies $Q$'' and write `` $P \mbox{$\Longrightarrow$}Q$'', if the truth of $Q$ follows from the truth of $P$. We make the convention that if $P$ is false then $(P \mbox{$\Longrightarrow$}Q)$ is true for all propositions $Q$, and in fact that

$$(P \mbox{$\Longrightarrow$} Q) \mbox{ is true {\em unless} ($P$ is true and $Q$ is false)}.$$ (3.11)

Hence for all propositions $P$ and $Q$

$$(P \mbox{$\Longrightarrow$} Q) \hspace{1ex}\Longleftrightarrow\hspace{1ex} (Q \mbox{ or } \mbox{ not}(P)).$$ (3.12)

3.13   Example. For every element $x$ in Q

$$x = 2 \mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$} x^2 = 4.$$ (3.14)

In particular, the following statements are all true.

$$2 = 2 \mbox{$\Longrightarrow$} 2^2 = 4.$$ (3.15)

$$-2 = 2 \mbox{$\Longrightarrow$} (-2)^2 = 4.$$ (3.16)

$$3 = 2 \mbox{$\Longrightarrow$} 3^2 = 4.$$ (3.17)

In proposition 3.16, $P$ is false, $Q$ is true, and $P \mbox{$\Longrightarrow$}Q$ is true.

In proposition 3.17, $P$ is false, $Q$ is false, and $P \mbox{$\Longrightarrow$}Q$ is true.

The usual way to prove $P \mbox{$\Longrightarrow$}Q$ is to assume that $P$ is true and show that then $Q$ must be true. This is sufficient by our convention in (3.11).

If $P$ and $Q$ are propositions, then `` $P \mbox{$\Longrightarrow$}Q$'' is also a proposition, and

$$(P \mbox{$\Longleftrightarrow$} Q) \mbox{ is equivalent to ... ...ngrightarrow$} Q \mbox{ and } Q \mbox{$\Longrightarrow$} P)$$ (3.18)

(the right side of (3.18) is true if and only if $P,Q$ are both true or both false.) An alternate way of writing `` $P \mbox{$\Longrightarrow$}Q$'' is ``if $P$ then $Q$''.

We will not make much use of the idea of two propositions being equal. Roughly, two propositions are equal if and only if they are word for word the same. Thus ``$1 +1=2$'' and ``$2=1+1$'' are not equal propositions, although they are equivalent. The only time I will use an ``$=$'' sign between propositions is in definitions. For example, I might define a proposition form $P$ over N by saying

for all $n \in \mbox{{\bf N}},$ $P(n) =$``$n+1=2$'',

or

for all $n \in \mbox{{\bf N}},$ $P(n) = [n+1= 2]$.

The definition we have given for ``implies'' is a matter of convention, and there is a school of contemporary mathematicians (called constructivists) who define $P \mbox{$\Longrightarrow$}Q$ to be true only if a ``constructive'' argument can be given that the truth of $Q$ follows from the truth of $P$. For the constructivists, some of the propositions of the sort we use are neither true nor false, and some of the theorems we prove are not provable (or disprovable). A very readable description of the constructivist point of view can be found in the article Schizophrenia in Contemporary Mathematics[10, pages 1-10].

3.19   Exercise.

a) Give examples of propositions $P,Q$ such that `` $P \mbox{$\Longrightarrow$}Q$'' and `` $Q \mbox{$\Longrightarrow$} P$'' are both true, or else explain why no such examples exist.

b) Give examples of propositions $R,S$ such that `` $R \mbox{$\Longrightarrow$} S$'' and `` $S \mbox{$\Longrightarrow$} R$'' are both false, or explain why no such examples exist.

c) Give examples of propositions $T,V$ such that `` $T \mbox{$\Longrightarrow$} V$'' is true but `` $V \mbox{$\Longrightarrow$} T$'' is false, or explain why no such examples exist.

3.20   Exercise. A Let $P,Q$ be two propositions. Show that the propositions `` $P \mbox{$\Longrightarrow$}Q$'' and `` $\mbox{ not}Q \mbox{$\Longrightarrow$} \mbox{ not}P$'' are equivalent. (`` $\mbox{ not}Q \mbox{$\Longrightarrow$} \mbox{ not}P$'' is called the contrapositive of the statement `` $P \mbox{$\Longrightarrow$}Q$''.)

3.21   Exercise. Which of the proposition forms below are true for all real numbers $x$? If a proposition form is not true for all real numbers $x$, give a number for which it is false.

a)

$x = 1 \mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}x^2 = 1$.

b)

$x^2 = 1 \mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}x = 1$.

c)

$x < {1\over 2} \mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}2x < 1$.

d)

$2 < {1\over x} \hspace{1ex}\Longleftrightarrow\hspace{1ex}2x < 1$. (Here assume $x \not = 0$.)

e)

$x < 1 \mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}x+1 < 3$.

f)

$x < 1 \hspace{1ex}\Longleftrightarrow\hspace{1ex}x + 1 < 3$.

g)

$x \leq 1 \mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}x < 1$.

h)

$x < 1 \mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}x \leq 1$.

3.22   Exercise. Both of the arguments A and B given below are faulty, although one of them leads to a correct conclusion. Criticize both arguments, and correct one of them.

Problem: Let $S$ be the set of all real numbers $x$ such that $x \not= -2$. Describe the set of all elements $x \in S$ such that

$$\frac{12}{x+2} < 4.$$ (3.23)

Note that if $x \in S$ then $\frac{12}{x+2}$ is defined.

ARGUMENT A: Let $x$ be an arbitrary element of $S$. Then

$$\frac{12}{x+2} < 4 \mbox{$\Longleftrightarrow$} 12 < 4x + 8$$

$$\mbox{$\Longleftrightarrow$} 0 < 4x-4$$

$$\mbox{$\Longleftrightarrow$} 0 < 4(x-1)$$

$$\mbox{$\Longleftrightarrow$} 0 < x-1$$

$$\mbox{$\Longleftrightarrow$} 1 < x.$$

Hence the set of all real numbers that satisfy inequality (3.23) is the set of all real numbers $x$ such that $1 < x$. $\diamondsuit$

ARGUMENT B: Let $x$ be an arbitrary element of $S$. Then

$$\frac{12}{x+2} < 4 \mbox{$\Longrightarrow$} 0 < 4 - \frac{12}{x+2}$$

$$\mbox{$\Longrightarrow$} 0 < \frac{4x + 8 -12}{x+2}$$

$$\mbox{$\Longrightarrow$} 0 < \frac{4x-4}{x+2}$$

$$\mbox{$\Longrightarrow$} 0 < \frac{4(x-1)}{x+2}$$

$$\mbox{$\Longrightarrow$} 0 < \frac{x-1}{x+2}.$$

Now

$$0 < \frac{x-1}{x+2} \mbox{$\Longleftrightarrow$} (0 < x-1 \mbox{ and } 0 < x+2 ) \mbox{ or }\ (0 > x-1 \mbox{ and } 0 >x+2 )$$

$$\mbox{$\Longleftrightarrow$} (1<x \mbox{ and } -2<x) \mbox{ or } (1>x \mbox{ and } -2 > x)$$

$$\mbox{$\Longleftrightarrow$} 1<x \mbox{ or } -2 > x.$$

Hence the set of all real numbers that satisfy inequality (3.23) is the set of all $x \in \mbox{{\bf R}}$ such that either $x < -2$ or $x > 1$. $\diamondsuit$