next up previous index
Next: 1.3 Equality Up: 1. Notation, Undefined Concepts Previous: 1.1 Sets   Index

1.2 Propositions

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

1.12   Examples. Both




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

\begin{displaymath}13 \mbox{ is a prime number } \end{displaymath}

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

\begin{displaymath}13 \mbox{ is an unlucky number } \end{displaymath}

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

The proposition

\begin{displaymath}\{1\}\subset \mbox{{\bf N}}\end{displaymath}

is true, and the proposition

\begin{displaymath}\mbox{{\bf N}}\in \mbox{{\bf N}}\end{displaymath}

is false, but

\begin{displaymath}1\subset \mbox{{\bf N}}\end{displaymath}

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

\begin{displaymath}{1\over 0}=5\end{displaymath}

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

\begin{displaymath}P \mbox{ or } Q \qquad P \mbox{ and } Q \qquad \mbox{ not } P\end{displaymath}

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.

(1+1=2) &\rm {and}& (2+2=4), \\
(1+1=2) &\rm {or}& (1+1=3), \\
(1+1=2) &\rm {or}& (2+2=4),

are all true propositions.

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

\begin{displaymath}\mbox{ not } (a=b) \mbox{ by } a\not= b,\end{displaymath}

and we abbreviate

\begin{displaymath}\mbox{ not } (a\in A) \mbox{ by } a\notin A.\end{displaymath}

1.16   Notation ( $\mbox{$\Longrightarrow$}$) If $P$ and $Q$ are propositions, we write
\end{displaymath} (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:
$\displaystyle (x=y)$ $\textstyle \mbox{$\Longrightarrow$}$ $\displaystyle (z\cdot x=z\cdot y).$ (1.19)
$\displaystyle (x=y)$ $\textstyle \mbox{$\Longrightarrow$}$ $\displaystyle (x+z=y+z).$ (1.20)
$\displaystyle (x\not= y)$ $\textstyle \mbox{$\Longrightarrow$}$ $\displaystyle \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:

  $\textstyle $ $\displaystyle \mbox{If $P$\ is true, and $(P\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}Q)$\ is true, then $Q$\ is true}.\mbox{{}}$  
  $\textstyle $ $\displaystyle \mbox{If $(P\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}Q)$\ is true and $Q$\ is false, then $P$\ is false.}\mbox{{}}$  
  $\textstyle $ $\displaystyle \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
\end{displaymath} (1.24)

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

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

``Proof'' of (1.24):

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


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

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

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

``Proof'' of (1.25):

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


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


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

The previous example is supposed to motivate the following assumption:

A false proposition implies everything,
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


is true. Hence all three of the statements below are true:
$\displaystyle 2=2$ $\textstyle \mbox{$\Longrightarrow$}$ $\displaystyle 2^2=4,$ (1.27)
$\displaystyle -2=2$ $\textstyle \mbox{$\Longrightarrow$}$ $\displaystyle (-2)^2=4,$ (1.28)
$\displaystyle 3=2$ $\textstyle \mbox{$\Longrightarrow$}$ $\displaystyle 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;


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
\end{displaymath} (1.31)

is an abbreviation for

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

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

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

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


(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)
\end{displaymath} (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.

next up previous index
Next: 1.3 Equality Up: 1. Notation, Undefined Concepts Previous: 1.1 Sets   Index