Next: 1.3 Equality
Up: 1. Notation, Undefined Concepts
Previous: 1.1 Sets
  Index
1.11
Definition (Proposition.)
A
proposition is a statement that is either true or false.
1.12
Examples.
Both
and
are propositions. The first is true and the second is false. I will consider
to be a proposition, because I expect that you know what a prime number is. However,
I will not consider
to be a proposition (unless I provide you with a definition for
unlucky number).
The proposition
is true, and the proposition
is false, but
is not a
proposition but rather a meaningless statement (cf (
1.8)).
Observe that ``
![$x\subset y$](img84.gif)
'' makes sense whenever
![$x$](img85.gif)
and
![$y$](img86.gif)
are sets,
and ``
![$x \in y$](img87.gif)
'' makes sense when
![$y$](img86.gif)
is a set, and
![$x$](img85.gif)
is any object.
Similarly
is meaningless rather than false, since division by zero is not defined., i.e.
I do not consider
![${1 \over 0}$](img89.gif)
to be a name for any object.
1.13
Definition (and, or, not.)
If
![$P$](img90.gif)
and
![$Q$](img91.gif)
are propositions, then
are propositions, and (
![$P$](img90.gif)
or
![$Q$](img91.gif)
) is true if and only if at least one of
![$P,Q$](img93.gif)
is
true; (
![$P$](img90.gif)
and
![$Q$](img91.gif)
) is true if and only if both of
![$P,Q$](img93.gif)
are true; (not
![$P$](img90.gif)
) is true
if and only if
![$P$](img90.gif)
is false.
1.14
Example.
are all true propositions.
1.15
Notation (
.)
We abbreviate
and we abbreviate
1.16
Notation (
)
If
![$P$](img90.gif)
and
![$Q$](img91.gif)
are propositions, we write
![\begin{displaymath}
P\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}Q
\end{displaymath}](img99.gif) |
(1.17) |
to denote the proposition ``
![$P$](img90.gif)
implies
![$Q$](img91.gif)
".
1.18
Example.
If
![$x,y,z$](img100.gif)
are integers then all of the following are true:
The three main properties of implication that we will use are:
We denote property (1.22) by saying that
is transitive.
1.23
Example.
The meaning of a statement like
![\begin{displaymath}
(1=2)\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}(5=7)
\end{displaymath}](img111.gif) |
(1.24) |
or
![\begin{displaymath}
(1=2)\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}(5\not= 7)
\end{displaymath}](img112.gif) |
(1.25) |
may not be obvious. I claim that both (
1.24) and (
1.25) should be true.
``Proof'' of (1.24):
and
so by transitivity of
![$\mbox{$\Longrightarrow$}$](img98.gif)
,
``Proof'' of (1.25):
so
so
The previous example is supposed to motivate the following assumption:
A false proposition implies everything,
i.e.
If
![$P$](img90.gif)
is false, then
![$(P\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}Q)$](img119.gif)
is true for all propositions
![$Q$](img91.gif)
.
1.26
Example.
For every
![$x\in\mbox{{\bf Z}}$](img120.gif)
, the proposition
is true. Hence all three of the statements below are true:
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$](img91.gif)
is true then
![$(P\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}Q)$](img119.gif)
is true for all propositions
![$P$](img90.gif)
.
The following table shows the conditions under which
is true.
![$P$](img90.gif) |
![$Q$](img91.gif) |
![$P\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}Q$](img128.gif) |
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 (
.)
Let
![$P$](img90.gif)
,
![$Q$](img91.gif)
,
![$R$](img130.gif)
,
![$S$](img131.gif)
be propositions. Then
![\begin{displaymath}
P\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}Q\mbox{$\hs...
...space{1ex}$}R\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}S
\end{displaymath}](img132.gif) |
(1.31) |
is an abbreviation for
It follows from transitivity of
![$\mbox{$\Longrightarrow$}$](img98.gif)
that if (
1.31) is true,
then
![$P\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}S$](img134.gif)
is true.
Note that (1.31) is not an abbreviation for
i.e., when I write (1.31), I do not assume that
is true.
1.32
Definition (Equivalence of propositions,
.)
Let
![$P,Q$](img93.gif)
be propositions. We say that
![$P$](img90.gif)
and
![$Q$](img91.gif)
are
equivalent and write
(read this ``
![$P$](img90.gif)
is equivalent to
![$Q$](img91.gif)
" or ``
![$P$](img90.gif)
if and only if
![$Q$](img91.gif)
") to mean
![\begin{displaymath}
(P\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}Q) \mbox{ and } (Q\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}P)
\end{displaymath}](img138.gif) |
(1.33) |
If either (
are both true) or (
are both false), then
is
true. If one of
is false, and the other is true,
then one of
,
has the form
true
false
, and hence in this case
is false. Thus
![$(P\hspace{1ex}\Longleftrightarrow\hspace{1ex}Q)$](img139.gif)
is true if and only if
![$P,Q$](img93.gif)
are both true or both false.
Next: 1.3 Equality
Up: 1. Notation, Undefined Concepts
Previous: 1.1 Sets
  Index