1.2 Propositions

1.11   Definition (Proposition.) A proposition is a statement that is either true or false.

1.12   Examples. Both

$$1+1=2$$

and

$$1+1=3$$

are propositions. The first is true and the second is false. I will consider

$$13 \mbox{ is a prime number }$$

to be a proposition, because I expect that you know what a prime number is. However, I will not consider

$$13 \mbox{ is an unlucky number }$$

to be a proposition (unless I provide you with a definition for unlucky number).

The proposition

$$\{1\}\subset \mbox{{\bf N}}$$

is true, and the proposition

$$\mbox{{\bf N}}\in \mbox{{\bf N}}$$

is false, but

$$1\subset \mbox{{\bf N}}$$

is not a proposition but rather a meaningless statement (cf (1.8)). Observe that ``$x\subset y$'' makes sense whenever $x$ and $y$ are sets, and `` $x \in y$'' makes sense when $y$ is a set, and $x$ is any object. Similarly

$${1\over 0}=5$$

is meaningless rather than false, since division by zero is not defined., i.e. I do not consider ${1 \over 0}$ to be a name for any object.

1.13   Definition (and, or, not.) If $P$ and $Q$ are propositions, then

$$P \mbox{ or } Q \qquad P \mbox{ and } Q \qquad \mbox{ not } P$$

are propositions, and ($P$ or $Q$) is true if and only if at least one of $P,Q$ is true; ($P$ and $Q$) is true if and only if both of $P,Q$ are true; (not $P$) is true if and only if $P$ is false.

1.14   Example.

$$\begin{eqnarray*} (1+1=2) &\rm {and}& (2+2=4), \\ (1+1=2) &\rm {or}& (1+1=3), \\ (1+1=2) &\rm {or}& (2+2=4), \end{eqnarray*}$$

are all true propositions.

1.15   Notation ( $\not=, \not\in$.) We abbreviate

$$\mbox{ not } (a=b) \mbox{ by } a\not= b,$$

and we abbreviate

$$\mbox{ not } (a\in A) \mbox{ by } a\notin A.$$

1.16   Notation ( $\mbox{$\Longrightarrow$}$) If $P$ and $Q$ are propositions, we write

$$P\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}Q$$ (1.17)

to denote the proposition `` $P$ implies $Q$".

1.18   Example. If $x,y,z$ are integers then all of the following are true:

$$(x=y) \mbox{$\Longrightarrow$} (z\cdot x=z\cdot y).$$ (1.19)

$$(x=y) \mbox{$\Longrightarrow$} (x+z=y+z).$$ (1.20)

$$(x\not= y) \mbox{$\Longrightarrow$} \left( (z=x)\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}(z\not= y)\right).$$ (1.21)

The three main properties of implication that we will use are:

$$ \mbox{If $P$\ is true, and $(P\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}Q)$\ is true, then $Q$\ is true}.\mbox{{}}$$

$$ \mbox{If $(P\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}Q)$\ is true and $Q$\ is false, then $P$\ is false.}\mbox{{}}$$

$$ \mbox{If $(P\mbox{$\Longrightarrow$}Q)$\ is true and $(Q\mbox{$\Longrightarrow$}R)$\ is true, then $(P\mbox{$\Longrightarrow$}R)$\ is true.}$$ (1.22)

We denote property (1.22) by saying that $\mbox{$\Longrightarrow$}$ is transitive.

1.23   Example. The meaning of a statement like

$$(1=2)\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}(5=7)$$ (1.24)

or

$$(1=2)\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}(5\not= 7)$$ (1.25)

may not be obvious. I claim that both (1.24) and (1.25) should be true.

``Proof'' of (1.24):

$$\begin{eqnarray*} % latex2html id marker 1010(1=2)&\mbox{$\Longrightarrow$}&(2... ...tarrow$}& (2\cdot 1+3=2\cdot 2+3) \mbox{ (by } (\ref{reason2})), \end{eqnarray*}$$

and

$$(2\cdot 1+3=2\cdot 2 + 3)\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}(5=7),$$

so by transitivity of $\mbox{$\Longrightarrow$}$,

$$(1=2)\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}(5=7).\mbox{ $\mid\!\mid\!\mid$}$$

``Proof'' of (1.25):

$$% latex2html id marker 2098 (1=2)\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}(1+4=2+4) \mbox{ (by } (\ref{reason2}))$$

so

$$\begin{eqnarray*} % latex2html id marker 1019(1=2)&\mbox{$\Longrightarrow$}& (... ...5\not=7) \mbox{ (by } (\ref{reason3}), \mbox{ since } 6\not= 7), \end{eqnarray*}$$

so

$$(1=2)\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}(5\not= ... ...tivity of } \mbox{$\Longrightarrow$}.\mbox{ $\mid\!\mid\!\mid$}$$

The previous example is supposed to motivate the following assumption:

A false proposition implies everything,

i.e.

If $P$ is false, then $(P\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}Q)$ is true for all propositions $Q$.

1.26   Example. For every $x\in\mbox{{\bf Z}}$, the proposition

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

is true. Hence all three of the statements below are true:

$$2=2 \mbox{$\Longrightarrow$} 2^2=4,$$ (1.27)

$$-2=2 \mbox{$\Longrightarrow$} (-2)^2=4,$$ (1.28)

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

Proposition (1.28) is an example of a false statement implying a true one, and proposition (1.29) is an example of a false statement implying a false one. Equations (1.27) and (1.28) together provide motivation for the assumption.

Every statement implies a true statement;

i.e.

If $Q$ is true then $(P\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}Q)$ is true for all propositions $P$.

The following table shows the conditions under which $(P\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}Q)$ is true.

$P$	$Q$	$P\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}Q$
true	true	true
true	false	false
false	true	true
false	false	true

Thus a true statement does not imply a false one. All other sorts of implications are valid.

1.30   Notation ( $P\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}Q\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}R\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}S$.) Let $P$, $Q$, $R$ ,$S$ be propositions. Then

$$P\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}Q\mbox{$\hs... ...space{1ex}$}R\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}S$$ (1.31)

is an abbreviation for

$$\left( (P\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}Q) \... ...ox{ and } (R\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}S).$$

It follows from transitivity of $\mbox{$\Longrightarrow$}$ that if (1.31) is true, then $P\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}S$ is true.

Note that (1.31) is not an abbreviation for

$$\left((P \mbox{ and } (P\mbox{$\hspace{1ex}\Longrightarrow\hs... ...ox{ and } (R\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}S);$$

i.e., when I write (1.31), I do not assume that $P$ is true.

1.32   Definition (Equivalence of propositions, $\mbox{$\Longleftrightarrow$}$.) Let $P,Q$ be propositions. We say that $P$ and $Q$ are equivalent and write

$$P\hspace{1ex}\Longleftrightarrow\hspace{1ex}Q$$

(read this ``$P$ is equivalent to $Q$" or ``$P$ if and only if $Q$") to mean

$$(P\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}Q) \mbox{ and } (Q\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}P)$$ (1.33)

If either ($P,Q$ are both true) or ($P,Q$ are both false), then $(P\hspace{1ex}\Longleftrightarrow\hspace{1ex}Q)$ is true. If one of $P,Q$ is false, and the other is true, then one of $(P\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}Q)$, $(Q\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}P)$ has the form $\langle$true$\rangle$ $\mbox{$\Longrightarrow$}$ $\langle$false$\rangle$, and hence in this case $(P\hspace{1ex}\Longleftrightarrow\hspace{1ex}Q)$ is false. Thus

$(P\hspace{1ex}\Longleftrightarrow\hspace{1ex}Q)$ is true if and only if $P,Q$ are both true or both false.