|
|
Introduction to Logic
|
Tools for Thought
|
|
Peano Arithmetic differs from Modular Arithmetic (axiomatized in Lesson 7.8) in that it applies to all natural numbers (0, 1, 2, 3, ...). Since there are infinitely many such numbers, we need infinitely many terms.
As mentioned in the introduction, we can get infinitely many terms by expanding our vocabulary with infinitely many object constants. Unfortunately, this makes the job of axiomatizing arithmetic effectively impossible, as we would have to write out infinitely many sentences.
An alternative approach is to represent numbers using a single object constant (e.g. 0) and a single unary function constant (e.g. s). We can then represent every number n by applying the function constant to 0 exactly n times. In this encoding, s(0) represents 1; s(s(0)) represents 2; and so forth. With this encoding, we automatically get an infinite universe of terms, and we can write axioms defining addition and multiplication as simple variations on the axioms of Modular Arithmetic.
|
Unfortunately, even with this representation, axiomatizing Peano Arithmetic is more challenging than axiomatizing Modular Arithmetic. We cannot just write out ground relational sentences to characterize our relations, because there are infinitely many cases to consider. For Peano Arithmetic, we must rely on logical sentences and quantified sentences, not just because they are more economical but because they are the only way we can characterize our relations in finite space.
|
Let's look at the same relation first. The axioms shown here define the same relation in terms of 0 and s.
∀x.same(x,x) |
∀x.(¬same(0,s(x)) ∧ ¬same(s(x),0)) |
∀x.∀y.(¬same(x,y) ⇒ ¬same(s(x),s(y))) |
|
It is easy to see that these axioms completely characterize the same relation. By the first axiom, the same relation holds of every term and itself.
same(0,0) |
same(s(0),s(0)) |
same(s(s(0)),s(s(0))) |
... |
|
The other two axioms tell us what is not true. The second axiom tells us that 0 is not the same as any composite term. The same holds true with the arguments reversed.
¬same(0,s(0)) | | ¬same(s(0),0) |
¬same(0,s(s(0))) | | ¬same(s(s(0)),0) |
¬same(0,s(s(s(0)))) | | ¬same(s(s(s(0))),0) |
... | | ... |
|
The third axiom builds on these results to show that non-identical composite terms of arbitrary complexity do not satisfy the same relation. Viewed the other way around, to see that two non-identical terms are not the same, we just strip away occurrences of s from each term till one of the two terms becomes 0 and the other one is not 0. By the second axiom, these are not the same, and so the original terms are not the same.
¬same(s(0),s(s(0))) | | ¬same(s(s(0)),s(0)) |
¬same(s(0),s(s(s(0)))) | | ¬same(s(s(s(0))),s(0)) |
¬same(s(0),s(s(s(s(0))))) | | ¬same(s(s(s(s(0)))),s(0)) |
... | | ... |
|
Once we have the same relation, we can define the other relations in our arithmetic. The following axioms define the plus relation in terms of 0, s, and same. Adding 0 to any number results in that number. If adding a number x to a number y produces a number z, then adding the successor of x to y produces the successor of z. Finally, we have a functionality axiom for plus.
∀y.plus(0,y,y) |
∀x.∀y.∀z.(plus(x,y,z) ⇒ plus(s(x),y,s(z))) |
∀x.∀y.∀z.∀w.(plus(x,y,z) ∧ ¬same(z,w) ⇒ ¬plus(x,y,w)) |
|
The axiomatization of multiplication is analogous. Multiplying any number by 0 produces 0. If a number z is the product of x and y and w is the sum of y and z, then w is the product of the successor of x and y. As before, we have a functionality axiom.
∀y.times(0,y,0) |
∀x.∀y.∀z.∀w.(times(x,y,z) ∧ plus(y,z,w) ⇒ times(s(x),y,w)) |
∀x.∀y.∀z.∀w.(times(x,y,z) ∧ ¬same(z,w) ⇒ ¬times(x,y,w)) |
That's all we need - just three axioms for same and three axioms for each arithmetic function.
|
Before we leave our discussion of Peano arithmetic, it is worthwhile to look at the concept of Diophantine equations. A polynomial equation is a sentence composed using only addition, multiplication, and exponentiation with fixed exponents (that is numbers not variables). For example, the expression shown below in traditional math notation is a polynomial equation.
x2 + 2y = 4z
|
A natural Diophantine equation is a polynomial equation in which the variables are restricted to the natural numbers. For example, the polynomial equation here is also a Diophantine equation and happens to have a solution in the natural numbers, viz. x=4 and y=8 and z=8.
Diophantine equations can be readily expressed as sentences in Peano Arithmetic. For example, we can represent the Diophantine equation above with the sentence shown below.
∃x.∃y.∃z.∀u.∀v.∀w.(times(x,x,u) ∧ times(2,y,v) ∧ plus(u,v,w) ⇒ times(4,z,w))
This is a little messy, but it is doable. And we can always clean things up by adding a little syntactic sugar to our notation to make it look like traditional math notation.
|
Once this mapping is done, we can use the tools of logic to work with these sentences. In some cases, we can find solutions; and, in some cases, we can prove that solutions do not exist. This has practical value in some situations, but it also has significant theoretical value in establishing important properties of Herbrand Logic, a topic that we discuss in a later section.
|
Use the arrow keys to navigate.
Press the escape key to toggle all / one.
|
|