matical meeting. In it, he set the agenda for mathematics in the twentieth
century by describing twenty-three critical problems^2 —although, unlike
the Clay Institute, he was unable to offer financial incentives for their so-
lution. The first problem on Hilbert’s list was the continuum hypothesis,
as we have seen this was shown to be undecidable within the Zermelo-
Fraenkel formulation of set theory. Second on the list was to discover
whether the axioms of arithmetic are consistent.
Recall that an axiomatic scheme is consistent if it is impossible to obtain
contradictory results within the system; that is, if it is impossible to prove
that the same result can be both true and false. Only one proposition
need be both true and false for a scheme to be inconsistent, but it may
seem that one could never prove that a proposition that is both true and
false does not exist. After all, mustn’t one be able to prove all the results
stemming from a particular axiom scheme in order to decide whether the
scheme is consistent?
Fortunately not. One of the easiest systems of logic to analyze is proposi-
tional logic, which is the logic of true/false truth tables. This system, which
is frequently taught in Math for Liberal Arts courses, involves constructing
and analyzing compound statements that are built up from simple state-
ments (which are only allowed to be true or false) using the terms not, and,
or, and if... then. In the following truth table, P and Q are simple state-
ments; the rest of the top line represents the compound statements whose
truth values depend upon the truth values of P and Q, and how we compute
them. It is rather like an addition table where we use TRUE and FALSE
rather than numbers, and compound statements rather than sums.
Row P Q NOT P P AND Q P OR Q IF P THEN Q
(1) TRUE TRUE FALSE TRUE TRUE TRUE
(2) TRUE FALSE FALSE FALSE TRUE FALSE
(3) FALSE TRUE TRUE FALSE TRUE TRUE
(4) FALSE FALSE TRUE FALSE FALSE TRUEThe first two columns list the four possible assignments of the values
TRUE and FALSE to the statements P and Q; for example, row 3 gives the
truth values of the various statements in the top when P is FALSE and Q
is TRUE.
The truth value assigned to NOT P is just the opposite of the truth value
assigned to P. As an example, if P is the true statement The sun rises in the
east, then NOT P is the false statement The sun does not rise in the east.
Even Logic Has Limits 117