3
$\begingroup$

I have to give a talk which mentions the Peano Axioms for Arithmetic. I want to make sure when i am explaining them in English I am describing them correctly.

(PA1) $(\forall x_1)( \neg s(x_1) = 0)$ $\ \ $

(PA2) $(\forall x_1) (\forall x_2) (s(x_1) = s(x_2) \to x_1 = x_2)$

(PA3) $(\forall x_1) x_1 + 0 = x_1$

(PA4) $(\forall x_1) (\forall x_2) x_1 + s(x_2) = s(x_1 + x_2)$

(PA5) $(\forall x_1) x_1 * 0 = 0$

(PA6) $(\forall x_1) (\forall x_2) x_1 s(x_2) = x_1 * x_2+x_1$

(PA7) $\phi (0) \to ((\forall x_1) (\phi (x_1) \to \phi(s(x_1))) \to (\forall x_1)\phi(x_1)$

(PA1) says 0 is not the succesor of any number.

(PA2) says Two numbers of which the successors are equal are themselves equal

PA3 says that additive identity exists

PA4 says successor function ()

PA5 says there exists a multiplicative identity

PA6 says

PA7 is the induction axiom and says If a set of numbers contains zero and also the successor of every number in the set, then every number is in the set.

Any help will be appreciated

$\endgroup$
  • 1
    $\begingroup$ You dropped the index on PA1. 2 seems right, 3 seems right, but also additive identity is that particular number which is not the successor of another (0 specifically). $\endgroup$ – mathreadler Mar 25 '17 at 22:15
  • 1
    $\begingroup$ PA5 is not right. 0 is not multiplicative identity. 1 is. 0 is a number which if multiplied with any number becomes itself. $\endgroup$ – mathreadler Mar 25 '17 at 22:20
  • 1
    $\begingroup$ I think PA6 is that multiplication distributes over addition. $x_1(x_2+1)$ allowed to "expand" parenthesis to $x_1x_2 + x_1$ $\endgroup$ – mathreadler Mar 25 '17 at 22:23
2
$\begingroup$

You have PA1 and PA2 right (though the equivalent reading of PA2, that different numbers have different successors, is perhaps even easier to motivate).

PA3 obviously tells us both less and more than that there is an additive identity. Less, because it only tells us about adding zero on the right. And more because it tells us what that right-hand identity is. But why try to complicate things? It just generalises the familiar arithmetical truth that $n + 0 = n$.

PA4 just generalises the familiar truth that $m + (n + 1) = (m + n) + 1$ (since taking successors is the same as adding $1$, i.e. adding $s0$, by PA3 and a special case of PA4: $s(n) = s(n + 0) = n + s0$).

PA5 does not give us multiplicative identity (that identity is $1$, i.e. $s0$, not $0$). It just tells us that multiplying by zero gives us zero.

PA6 generalises the familiar $m(n + 1) = mn + m$

PA7 (presented like that) has nothing to do with sets. It's an axiom template or schema. And every instance that we get when we fill in the $\phi( )$ with a open sentence of Peano Arithmetic is an axiom. Suppose a particular filling for $\phi( )$ expresses the property $P$ -- then the instance of the axiom says, in effect, that if (i) $0$ has $P$ and (ii) $P$ is always passed from a number to its successor, then (iii) all numbers have $P$.

It is crucial to be clear that PA7 as a schema gives us a quite different theory ("First-order Peano Arithmetic") from a theory with a stronger axiom which talks about sets of numbers ("Second-order Peano Arithmetic").

You might find bits of my Introduction to Gödel's Theorems helpful -- in the second edition, Ch 13 on what first-order PA is (you'll need some sections from the previous three chapters) and Ch 29 on second-order PA.

$\endgroup$
  • $\begingroup$ Thank you so much. My talk is about Godel's Incompleteness Theorem. $\endgroup$ – HypestHype Mar 25 '17 at 23:00
  • 1
    $\begingroup$ Then I should have mentioned too the much brisker introduction to my Introduction -- Gödel Without Tears, which you can download from here: logicmatters.net/igt/godel-without-tears $\endgroup$ – Peter Smith Mar 25 '17 at 23:11
1
$\begingroup$

After presenting the axioms individually, I think it is useful to present how some of these axioms work in pairs:

PA1 and PA2 will force any model of those two axioms to contain an infinite chain of objects with 0 being the 'first' object, $s(0)$ (which of course we typically refer to as '1') being the 'next', $s(s(0))$ ('2') the one after that, etc. And since no two different objects can ever have the same successor, the successor of each is different from any of the earlier ones, thus forcing this infinite chain isomorph to the structure of the natural numbers as we know them.

You can present PA3 and PA4 together as a recursive definition of addition, where the right 'addend' is recursively added to the left 'addend' one by one. That is, to add n to m, I repeatedly add 1 to n, until I have done that n times. PA3 is the recursive base, and PA4 the recursive step.

Similarly, PA5 and PA6 form a recursive definition of multiplication, where multiplication is defined as repeated addition. That is, to multiply m by n we start with 0, and repeatedly add m to that, n times. PA5 is the recursive base, and PA6 is the recursive step.

(If you have computer scientists in your audience, they will certainly appreciate this reference to recursion ... And it's hard to avoid some notion of recursion anyway when talking about the Godel results, even at a high level)

Oh, and PA7 is of course the schema of weak mathematical induction, that exploits the very recursive nature of the natural numbers (that is, since 0 is a natural number (base) and since the successor $s(n)$ of any natural number $n$ is a natural number itself, and since there are no other natural numbers than those you get through this recursive process, then if you can prove that 0 has some property, and if the successor $s(n)$ of any natural number $n$ has that property assuming $n$ has that property, then every natural number has that property)

$\endgroup$
  • $\begingroup$ I will make sure to do this as well thank you. I am not sure if there are going to be any computer scientists though as my campus doesn't have a Computer Science degree. It is at the main campus. $\endgroup$ – HypestHype Mar 26 '17 at 22:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.