-2
$\begingroup$

I am wondering if the following modifications of the Peano axioms result in a set of axioms equivalent to the Peano axioms, in the sense that any set of numbers satisfies these modified axioms if and only if they satisfy the Peano axioms:

  1. Delete the axiom of induction, namely "Let $P(n)$ be any property pertaining to a natural number $n$. Suppose that $P(0)$ is true, and suppose that whenever $P(n)$ is true, $P(S(n)$ is also true. Then $P(n)$ is true for every natural number $n$."

  2. Add the following axiom: "$n$ is a natural number only if it can be expressed as the sum of 2 natural numbers"

  3. (This may or may not be a modification) Define addition by defining $0 + 0 = 0$, and if $n+m = x$, then $S(n) + m = n+S(m) = S(x) $

where $S(n)$ is the successor of $n$.

I think this works because:

  1. We can guarantee that for any 2 numbers $n,m$ which are in a number system satisfying these axioms, that the addition of $n+m$ is defined- as because both $n$ and $m$ are, by the axiom in the second modification above, the result of addition, they are the result of repeated applications of the successor operation on $0$; therefore they are in the scope of the recursion contained in the addition definition.

  2. The principle of induction still holds: because every number in a system satisfying these axioms can be obtained by repeatedly applying the successor operations on $0$, due to how addition is defined for them as above, $P(0) $ and $P(n) \implies P(S(n))$ implies that for all $n, P(n)$.

Is this reasoning correct?

$\endgroup$
1

2 Answers 2

2
$\begingroup$

Consider the set of ordered pairs of natural numbers i.e. $\{(x,y)\mid (x,y) \in \mathbb{N}, x \leq y\}$. Let $(x,y) + (a,b) = (x+a,y+b)$ and $(x,y) \times (a,b) = (x\times a, y \times b)$. Let the succesor function be defined such that $S'((a,b)) = (a,S(b))$. Let $(x,y) \leq (a,b)$ be $x < a \vee (x = a\wedge y \leq b) $. Then the set is a totally ordered set that satisfies your axioms but does not satisfy the induction axiom.

Edit: For a counterexample that satisfies the Robinson arithmetic, see this answer

$\endgroup$
12
  • $\begingroup$ what is $S'$ here? $\endgroup$ Commented May 20 at 1:15
  • $\begingroup$ @PrincessMia it is the successor function that I chose for the given set I defined, just to differentiate it from the successor function of natural numbers. $\endgroup$
    – ioveri
    Commented May 20 at 1:35
  • 1
    $\begingroup$ @CameronBuie oh that's my mistake, I meant to say $(x,y) + (a,b) = (x+a,y+b)$ and $(x,y) \times (a,b) = (x\times a, y \times b)$ $\endgroup$
    – ioveri
    Commented May 20 at 4:02
  • 1
    $\begingroup$ @PrincessMia The point of my addition is that is it is a solution to your axioms but isn't adequate to what you want. That's why I said it "satisfies your axioms but does not satisfy the induction axiom". Your "definition" simply isn't strong enough to rule out numbers that violate induction itself. Induction axiom is simply a lot stronger than you think. $\endgroup$
    – ioveri
    Commented May 21 at 17:00
  • 1
    $\begingroup$ @PrincessMia here's a post that's related to what you might want. In short, induction is independent from other axioms of the Peano axioms, or ${PA}^-$. So it doesn't matter how you try to redefine addition or multiplication via axioms. math.stackexchange.com/questions/331733/… $\endgroup$
    – ioveri
    Commented May 21 at 17:17
1
$\begingroup$

Consider the set $\Bbb H:=\left\{\frac12 n\mid n\in \Bbb N\right\},$ where $\Bbb N$ is the usual set of natural numbers, so that $\Bbb H$ is a subset of the rational numbers that is closed under rational addition. Let $S:\Bbb H\to\Bbb H$ be given by $S(x):=x+1,$ where $+$ is the typical addition of rational numbers. This setup satisfies the following axioms:

  • $0\in\Bbb H$
  • $\forall x\in\Bbb H, S(x)\in\Bbb H$
  • $\forall x\in\Bbb H,S(x)\neq 0$
  • $\forall x\in\Bbb H,\forall y\in \Bbb H,\bigl[S(x)=S(y)\implies x=y\bigr]$

These are the Peano axioms except for the Induction Axiom. However, it does not satisfy the Induction axiom, as $\Bbb N$ is a proper subset which contains $0$ and is closed under the successor operation.

On the other hand, it satisfies the following axiom: $$\forall x\in\Bbb H,\exists y\in H:\exists z\in H:x=y+z.$$ This is true because $0+x=x$ for all $x\in\Bbb H,$ and (together with closure under addition) means that the axiom you're wanting to replace Induction with has been satisfied, so your replacement axiom won't do the job.

Added: In response to your edit, note that $\Bbb H$ also satisfies the following properties:

  • $0+0=0$
  • $\forall x\in\Bbb H,\forall y\in\Bbb H,S(x)+y=S(x+y)$
  • $\forall x\in\Bbb H,\forall y\in\Bbb H,S(x+y)=x+S(y)$
$\endgroup$
9
  • $\begingroup$ Thanks, is it not the case that because one 'modification' above was defining addition to result in only things which could be produced from repeated applications of the successor function to $0$, if we stipulate that every natural number must be the result of addition, it follows that the non-integer elements of $\mathbb{H}$ cannot actually be the result of addition, and fail the axiom with which I wanted to replace the axiom of induction? $\endgroup$ Commented May 20 at 4:17
  • 1
    $\begingroup$ @PrincessMia: there is nothing in your axiom that limits the naturals to things which you can reach from $0$ by successor. In addition, your axiom 2 is second order logic, which PA avoids. The usual second order arithmetic induction is much simpler-it basically says all the naturals can be reached by successor from $0$. Second order logic does not have the nice proof properties that first order logic has, but this is a complicated subject. $\endgroup$ Commented May 20 at 4:52
  • $\begingroup$ @RossMillikan can you tell me where exactly the error is in the following reasoning: 1. every result of addition can be reached from $0$ by a successor- as we start off with $0+0 = 0$, and every other result of addition, $n+m$, is the successor of a 'previous' version of addition- it is either $S(S^{-1}(n) + m)$ or $S(n+ S^{-1}(m))$. So there is ultimately a chain of successors from $0$ to $n+m$. 2. Because every natural number is the result of addition by axiom 2, every natural number can be reached from $0$ by a successor. $\endgroup$ Commented May 20 at 4:58
  • $\begingroup$ @PrincessMia: nothing you have said implies there are not naturals not reachable from $0$. The example with the half integers is a good one. They satisfy your axiom 2 using the usual addition function. You are hoping the only if will rule out numbers that are not the usual naturals, but we get to build a model with whatever we want as long as it satisfies the axioms. So $0+\frac 12=\frac 12$ and I have shown that $\frac 12$ is the sum of two naturals. $\endgroup$ Commented May 20 at 5:05
  • $\begingroup$ @RossMillikan isn't addition undefined for $1 \over 2$ though, according to the definition I have given above (using the successor function given in the post to which we are replying?) $\endgroup$ Commented May 20 at 5:11

Not the answer you're looking for? Browse other questions tagged .