All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Information Report

Category:
## Documents

Published:

Views: 13 | Pages: 31

Extension: PDF | Download: 0

Share

Related documents

Description

Peano Axioms

Tags

Transcript

CHAPTER 1: THE PEANO AXIOMS
MATH 378, CSUSM. SPRING 2009. AITKEN
1.
Introduction
We begin our exploration of number systems with the most basic numbersystem: the natural numbers
N
. Informally, natural numbers are just the or-dinary whole numbers 0
,
1
,
2
,...
starting with 0 and continuing indeﬁnitely.
1
For a formal description, see the axiom system presented in the next section.Throughout your life you have acquired a substantial amount of knowl-edge about these numbers, but do you know the reasons behind your knowl-edge? Why is addition commutative? Why is multiplication associative?Why does the distributive law hold? Why is it that when you count a ﬁniteset you get the same answer regardless of the order in which you count theelements? In this and following chapters we will systematically prove basicfacts about the natural numbers in an eﬀort to answer these kinds of ques-tions. Sometimes we will encounter more than one answer, each yieldingits own insights. You might see an informal explanation and then a for-mal explanation, or perhaps you will see more than one formal explanation.For instance, there will be a proof for the commutative law of addition inChapter 1 using induction, and then a more insightful proof in Chapter 2involving the counting of ﬁnite sets.We will use the axiomatic method where we start with a few axiomsand build up the theory of the number systems by proving that each newresult follows from earlier results. In the ﬁrst few chapters of these notesthere will be a strong temptation to use unproved facts about arithmeticand numbers that are so familiar to us that they are practically part of ourmental DNA. Resist this temptation! In the context of a formal proof, takethe attitude that such familiar facts are not certain until they are proved.So they cannot be used in a formal proof until after they have been proved.A similar thing can be said of deﬁnitions: pretend that your intuitive ideasof even basic things such as + and
<
are inaccessible until you can havea formal deﬁnition. In the beginning, the only terms that can be used areterms from logic and set theory, explained in Chapter 0, and the primitiveterms. The only facts that can be used are the axioms together with facts
Date
: May 19, 2009.
1
Warning: some authors do not include 0 in the set of natural numbers. This will bediscussed in the next section.
1
2 MATH 378, CSUSM. SPRING 2009. AITKEN
from logic and set theory as summarized in Chapter 0, including generalfacts about equality, functions, and relations.
2
The system of axioms we use here is a famous system called the
Dedekind-Peano axioms
(Section 2), or the
Peano axioms
for short. We will add to thisan axiom about iterating functions (Section 3), but in an optional section(Section 12) to this chapter, we will see that this iteration axiom is notnecessary since it can actually be proved from Peano’s axioms. Thus it isstrictly speaking a convenient “temporary” axiom: one could replace theiteration axiom by a theorem that says the same thing. We take it as atemporary axiom in these notes since the proof of the iteration axiom is abit subtle, and is at a higher level than most of the other theorems of theChapter. I do not want to start oﬀ the chapter by scaring away readers.
Remark
1
.
Although we will be strict about not using unproved assertions inthe formal development, you do not need to be so shy about using your priorknowledge in the
informal
exercises. Such prior knowledge is also useful fortemporarily guiding your thinking until a ﬁrmer foundation is laid down inthe formal development.This distinction between formal and informal is especially important inthe many exercises that will arise in these notes. The informal exercises willbe labeled as such. The rest are considered to be formal exercises.The formal exercises may require you to ﬁll in details of sketchy proofsor even to write complete proofs for theorems whose proofs are not toohard or are similar to earlier proofs. These constitute part of the oﬃcialdevelopment of the number systems, and the facts established in them canbe used in future proofs. On the other hand, the informal exercises aredesigned to help familiarize you with facts or deﬁnitions, or to lead you ininteresting but tangential directions. These do not have to be solved witha formal proof, and can appeal to prior knowledge. They are considered tobe outside the logical development of the number systems, and so cannot becited in a later formal proof.For example, suppose an informal exercise asks for an example of anassociative binary operation that his not commutative. Suppose you knowabout matrix multiplication from a linear algebra course. Then you canuse your knowledge of linear algebra to help solve the problem. On theother hand, you cannot use matrix multiplication in a formal exercise sincematrices are not developed in this course.
Remark
2
.
In the above discussion, the term
theorem
refers to any resultthat has a proof. Keep in mind that other terms for theorems are commonlyused including
proposition
,
lemma
, and
corollary
. The term
lemma
is used
2
In these notes, we start almost at the very beginning of mathematics, but you should beaware that there are other approaches that start with less and begin by proving theoremsabout set theory ﬁrst before developing the number systems. For example, set theoriststypically start with the Zermelo-Fraenkel axioms for set theory, and from there developset theory, the number systems, and (most of) the rest of mathematics.
CHAPTER 1: THE PEANO AXIOMS 3
for a theorem that is only important as a stepping stone in proving othertheorems, and a
corollary
is a theorem that follows fairly easily, for exampleas an interesting special case, from a previous theorem. Some authors alsomake a distinction between the terms
theorem
and
proposition
, using thelabel
proposition
for more ordinary theorems and using
theorem
only forthe more important theorems. These are informal guidelines: one can ﬁndexceptions.
Remark
3
.
As mentioned above, in the formal development of the naturalnumbers we begin by assuming that everything about the natural numbersis as yet unknown territory. On the other hand, we do allow logic as ex-pressed in everyday, but careful, language. This leads to a point that needsto be clariﬁed: even though we are developing the natural numbers fromscratch, we will allow ourselves to use a few number-related terms such as“pair”, “unique”, “ﬁrst”, “second”, and so on. We do so because we cansafely treat such basic terms as forming part of our
logical
vocabulary.
3
Wewill also use numerals for the labeling of sections, theorems, exercises, andsuch. These labels have no arithmetic content, and could have just as easilybeen any string of symbols. They are being used informally to help keep thechapter organized. On the other hand, we will not take any truly mathe-matical or arithmetic fact for granted, for example facts about addition andmultiplication. These all must be proved.2.
The Axioms
Forget everything you think you know about the natural numbers, evensomething as basic as 1+1 = 2. Pretend you don’t even know the deﬁnitionof addition. In what follows, we will recreate all this knowledge on a solidlogical foundation by
proving
all the elementary theorems and
deﬁnining
allthe basic ideas. (Of course this self-imposed forgetting should be conﬁnedto the oﬃcial formal development of the natural numbers, and the formalproofs. Your past knowledge will come in handy for thinking up strategiesfor proofs, for helping you mentally digest deﬁnitions, and for warning youwhen you are about to make an error.)At this point, the only thing that you are oﬃcially allowed to know con-cerning the natural numbers is what is expressed in the following axioms.They function partially as descriptions of the primitive terms, and partiallyas a list of facts that we can use in later proofs. These axioms are called
3
For example, the statement “the set
S
has at least two elements” does not reallyrequire the number 2. It can be translated easily into basic logic as follows:
∃
x
∃
y
“
(
x
∈
S
)
∧
(
y
∈
S
)
∧
(
x
=
y
)
”
.
4 MATH 378, CSUSM. SPRING 2009. AITKEN
the
Dedekind-Peano axioms
since they are based on the axioms of the Ger-man mathematician Richard Dedekind (1831 – 1916) and the the Italianmathematician Giuseppe Peano (1858 – 1932).
4
We begin with the primitive terms described in the axioms. They arecalled
primitive
because they do not have to be formally deﬁned, but insteadare described in the axioms. All other terms, such as + or
<
must be deﬁned.Such deﬁnitions can build on primitive terms, notions from Chapter 0, orany previously deﬁned term.
Primitive Terms.
The three primitive terms are
N
,
0
, and
σ
.
Axiom 1.
(i)
N
is a set, (ii)
0
is an element of
N
, and (iii)
σ
is a function
σ
:
N
→
N
with domain and codomain equal to
N
.
We call
N
the “set of natural numbers”, and we call its elements “naturalnumbers”. We call 0 the “zero element”, or just “zero”. We call
σ
the“successor function”. If
n
∈
N
we call
σn
the “successor of
n
.” Informally,the successor of
n
is the next number following
n
. This is informal since wehave not yet deﬁned an order
<
on
N
.
Axiom 2.
The image of
σ
:
N
→
N
does not contain
0
:
¬
∃
n
∈
N
. σn
= 0
In other words,
0
is not the successor of a natural number.
Axiom 3.
The function
σ
:
N
→
N
is injective.
5
In other words, distinct natural numbers have distinct successors.
∀
x,y
∈
N
. x
=
y
=
⇒
σx
=
σy
or equivalently
∀
x,y
∈
N
. σx
=
σy
=
⇒
x
=
y.
Axiom 4
(
Induction
)
.
Suppose
S
is a subset of
N
such that
(i)
0
∈
S
,and
(ii)
n
∈
S
implies
σn
∈
S
for arbitrary
n
∈
N
. Then
S
=
N
.
S
⊆
N
∧
0
∈
S
∧
∀
n
(
n
∈
S
⇒
σn
∈
S
)
=
⇒
S
=
N
4
There are several variations of these axioms. We use a version of what is sometimescalled the
second-order Peano axioms
which allows the notion of subsets of
N
. Thereis another, more elementary system called the
ﬁrst-order
Peano axioms which does notquantify over sets of natural numbers. If you encounter the Peano axioms outside thesenotes, you might see the ﬁrst order version with axioms that refer directly to addition andmultiplication. In our second-order version the operations of addition and multiplicationare not mentioned in the axioms, but must be deﬁned in terms of the successor function.
5
The reader is expected to be familiar with the term
injective
, or the equivalentterm
one-to-one
. These terms describe functions
f
that map distinct elements to dis-tinct images.

Recommended

Related Search

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks