By b) the definitions (l)-C) are independent of the representatives of
the equivalence classes. Show that in D) and E) the definitions are
independent of the choice of the propositional variable p.
(d) If the number of propositional variables is finite, then the Boolean
algebra is also finite. If n is the number of variables, then the
number of elements in the Boolean algebra is 2^".
Bibliography
For Boolean algebra, see Goodstein [1].
10. Axiomatization of the Natural Numbers
10.1. Preliminary Remarks
The theory of natural numbers occupies an especially important place
in studies in the foundations of mathematics. In the first place, the
arithmetic of natural numbers offers a simple and important example of
a theory with an infinite domain of individuals, in which the problems
connected with the concept of infinity can be studied. Secondly, it has
turned out that many other interesting metamathematical questions can
be reduced to arithmetic (cf. the arithmetization in §5.4). Finally, the
results of Godel on arithmetical algorithms have had a lasting influence
on the whole program of metamathematics. Let us discuss these remarks
in greater detail.
The "leap to infinity" involved in recognizing the domain of the natural
numbers is already adequate for all the ontological needs of the predicate
logic (cf. §3); this is the meaning of the fundamental theorem of Lowenheim
and Skolem, which essentially states that in order to investigate the
concept of a consequence there is no need to use any domain of individuals
other than the natural numbers.
Since in a system of axioms S the means of expression (variables,
logical symbols, and so forth), are obviously countable, it is clear that the
obtainable expressions are also countable. Thus the expressions can be
"numbered" constructively (see §5.4). For every expression the resulting
index is computable and, conversely, for every number we can decide
whether or not it is the index of an expression; if it is, then the expression
can be recovered. As a result, certain metamathematical properties
like ...is an expression, ...is the conjunction of... and is true are
transformed into number-theoretical properties. Thus all questions of
decidability can be translated into the corresponding questions for
arithmetic. Moreover, if the system S includes an arithmetical system of
axioms, many of the metamathematical propositions about S can be
72 PART A FOUNDATIONS OF MATHEMATICS
formulated in S itself, and in this way it is possible to obtain extremely
general theorems about mathematical systems of axioms (cf. §10.5).
For a long time the concept of the (infinite!) totality of natural numbers
was held to be intuitively clear, and indeed quite self-evident [cf. the similar
situation for the concept of a set (§7.1)]. It was Frege A884) who first
pointed out the necessity for an exact definition of a natural number.
In his attempt to reduce arithmetic to logic he defined the number 1,
for example, as the totality of all one-place predicates that hold for
exactly one individual. This definition is closely related to the set-
theoretical introduction of the natural numbers and leads to the same kind
of difficulties as the naive theory of sets (§7.3). Thus we naturally seek,
as in that theory, to characterize the natural numbers by a system of
axioms. The best-known system of axioms for the natural numbers is due
to Dedekind A888) but is named after Peano A889). In §10.3 we shall
discuss a somewhat modified system, formulated in the language of
predicate logic. The question of axiomatizing the whole of arithmetic
(§10.4) then leads us to the well-known Incompleteness Theorem of Godel
(§10.5). The present section closes with some remarks on the operational
construction of arithmetic recently proposed by Lorenzen.
10.2. The Peano Axioms
The Peano axioms (with unimportant changes):
(a) 0 is a natural number.^^
(b) If n is a natural number, then so is ri.
(c) Ifm' = «', then m = n.
(d) There is no number nfor which n' = 0.
(e) Axiom of complete induction:
If a property P of the natural numbers satisfies the following two
conditions, then P holds for every natural number:
A) P holds for 0. -
B) For every natural number n, if P holds for n, then P holds for n'.
These axioms can be stated in a formal language consisting, as before, of
formulas or rows of symbols, but now, in view of the fact that the axiom (e)
speaks of an arbitrary property, we must make use of a generalized
predicate variable; that is, a predicate variable bound by the universal
quantifier. Expressions with quantified predicate variables are regarded
as belonging to logic of the second order, or to the extended predicate logic.
Expressions in which only subject variables are quantified are said to