next up previous index
Next: 3.2 Sets Defined by Up: 3. Propositions and Functions Previous: 3. Propositions and Functions   Index

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

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

is an abbreviation for

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

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
\begin{displaymath}
x^2-5x+6=0.
\end{displaymath} (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
\begin{displaymath}
(P \mbox{$\Longrightarrow$} Q) \mbox{ is true {\em unless} ($P$ is true and $Q$ is false)}.
\end{displaymath} (3.11)

Hence for all propositions $P$ and $Q$
\begin{displaymath}
(P \mbox{$\Longrightarrow$} Q) \hspace{1ex}\Longleftrightarrow\hspace{1ex} (Q \mbox{ or } \mbox{ not}(P)).
\end{displaymath} (3.12)

3.13   Example. For every element $x$ in Q
\begin{displaymath}
x = 2 \mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$} x^2 = 4.
\end{displaymath} (3.14)

In particular, the following statements are all true.
$\displaystyle 2 = 2$ $\textstyle \mbox{$\Longrightarrow$} $ $\displaystyle 2^2 = 4.$ (3.15)
$\displaystyle -2 = 2$ $\textstyle \mbox{$\Longrightarrow$} $ $\displaystyle (-2)^2 = 4.$ (3.16)
$\displaystyle 3 = 2$ $\textstyle \mbox{$\Longrightarrow$} $ $\displaystyle 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

\begin{displaymath}
(P \mbox{$\Longleftrightarrow$} Q) \mbox{ is equivalent to ...
...ngrightarrow$} Q \mbox{ and } Q \mbox{$\Longrightarrow$} P)
\end{displaymath} (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

\begin{displaymath}
\frac{12}{x+2} < 4.
\end{displaymath} (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

$\displaystyle \frac{12}{x+2} < 4$ $\textstyle \mbox{$\Longleftrightarrow$} $ $\displaystyle 12 < 4x + 8$  
  $\textstyle \mbox{$\Longleftrightarrow$} $ $\displaystyle 0 < 4x-4$  
  $\textstyle \mbox{$\Longleftrightarrow$} $ $\displaystyle 0 < 4(x-1)$  
  $\textstyle \mbox{$\Longleftrightarrow$} $ $\displaystyle 0 < x-1$  
  $\textstyle \mbox{$\Longleftrightarrow$} $ $\displaystyle 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

$\displaystyle \frac{12}{x+2} < 4$ $\textstyle \mbox{$\Longrightarrow$} $ $\displaystyle 0 < 4 - \frac{12}{x+2}$  
  $\textstyle \mbox{$\Longrightarrow$} $ $\displaystyle 0 < \frac{4x + 8 -12}{x+2}$  
  $\textstyle \mbox{$\Longrightarrow$} $ $\displaystyle 0 < \frac{4x-4}{x+2}$  
  $\textstyle \mbox{$\Longrightarrow$} $ $\displaystyle 0 < \frac{4(x-1)}{x+2}$  
  $\textstyle \mbox{$\Longrightarrow$} $ $\displaystyle 0 < \frac{x-1}{x+2}.$  

Now
$\displaystyle 0 < \frac{x-1}{x+2}$ $\textstyle \mbox{$\Longleftrightarrow$} $ $\displaystyle (0 < x-1 \mbox{ and } 0 < x+2 ) \mbox{ or }\
(0 > x-1 \mbox{ and } 0 >x+2 )$  
  $\textstyle \mbox{$\Longleftrightarrow$} $ $\displaystyle (1<x \mbox{ and } -2<x) \mbox{ or } (1>x \mbox{ and } -2 > x)$  
  $\textstyle \mbox{$\Longleftrightarrow$} $ $\displaystyle 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$


next up previous index
Next: 3.2 Sets Defined by Up: 3. Propositions and Functions Previous: 3. Propositions and Functions   Index
Ray Mayer 2007-09-07