1
$\begingroup$

Every integer greater than 2 can be expressed as sum of some prime number greater than 2 and some nonegative integer....$n=p+m$. Since 3=3+0; 4=3+1; 5=3+2 or 5=5+0...etc it is obvious that statement is true.My question is: Can we use Peano's axioms to prove this statement (especially sixth axiom which states "For every natural number $n$, $S(n)$ is a natural number.")?

$\endgroup$
3
  • 2
    $\begingroup$ I'm a bit confused; are you wanting something like $1+n=1+(3+(n-3))=3+(n-2)=3+((n+1)-3)$? $\endgroup$ Sep 23, 2011 at 5:56
  • 13
    $\begingroup$ Why does it have to be some prime number? Can't we just say that $n = (n - 3) + 3$ ? $\endgroup$ Sep 23, 2011 at 5:59
  • $\begingroup$ @aengle,no, I wrote random examples...it can be any combination of $n,p,m$ that satisfy conditions of statement $\endgroup$
    – Pedja
    Sep 23, 2011 at 6:03

3 Answers 3

5
$\begingroup$

Note: My usual definition of $\mathbb{N}$ includes $0$, as for example in Halmos's Naive Set Theory. This does not matter here. The proposed result asks for an expression of natural numbers greater than $2$ (which means it doesn't matter if you consider $0$ a natural number or not) as a sum of a prime greater than 2 and a nonnegative integer; the proof below shows that every nonnegative integer (in particular, every "natural number if you don't include $0$") is the sum of a prime greater than two and a "natural-number-including-zero" (that is, a "nonnegative integer").

Let $S=\{n\in\mathbb{N}\mid n\leq 2\text{ or there exists a prime }p\gt 2\text{ and a natural }m\text{ such that }n=p+m\}$.

Note that $0$, $1$, and $2$ lies in $S$.

Assume that $k\in S$; we want to prove that $s(k)$, the successor of $k$, lies in $S$.

  • If $k\lt 2$, then $s(k)\leq 2$, so $s(k)\in S$.
  • If $k=2$, then $s(k) = k+1 = 2+1 = 3+0$ is the sum of a prime, $3$, and a natural number, $0$, so $s(k)\in S$.
  • If $k=p+m$ for some prime $p$ and some natural number $m$, then $$s(k) = s(p+m) = p+s(m),$$ and by Peano's postulates, since $m\in\mathbb{N}$ then $s(m)\in\mathbb{N}$. So $s(k)$ is the sum of a prime and a natural number, hence $s(k)\in S$.

By Peano's Fifth Postulate (Induction), $S=\mathbb{N}$. This proves that every natural number greater than $2$ is the sum of a prime and natural number. $\Box$


If you don't consider the natural numbers to include zero, it is very simple to translate the proof above: the definition of $S$ just has to replace the word "natural" with "nonnegative integer": $$S = \{n\in\mathbb{N}\mid n\leq 2\text{ or there exists a prime }p\gt 2\text{ and a nonnegative integer }m\text{ such that }n=p+m\}.$$

Then the first line of the proof can omit the observation that $0\in S$, and where it says "natural number" afterwards, just replace with "nonnegative integer", and the observation that if $m$ is a nonnegative integer, then it is either a natural-greater-than-1, so $s(m)$ is a natural number (under either definition), or else $m=0$ in which case "$s(m)$" denotes $1$, which is a natural number (under either definition).

$\endgroup$
13
  • $\begingroup$ ,For case $k=2$ you took for prime to be $2$, but statement refers to the primes strictly greater than 2.I agree with the rest of your proof... $\endgroup$
    – Pedja
    Sep 23, 2011 at 14:00
  • $\begingroup$ ,I am little bit confused because my question refers to the primes greater than $2$ and $m$ as nonnegativ integer and your answer refers to all primes and $m$ as natural number... $\endgroup$
    – Pedja
    Sep 23, 2011 at 15:30
  • $\begingroup$ @pedja: Simple enough to fix; if $k=2$, then $s(k)=3=3+0$, with $3$ prime and $0$ a natural number. To me, natural numbers include $0$. $\endgroup$ Sep 23, 2011 at 16:01
  • $\begingroup$ ,Peano's original formulation of the axioms used 1 instead of 0 as the "first" natural number...if it is so then $S(2)$ doesn't belong to $S$ so that's confusing me... $\endgroup$
    – Pedja
    Sep 23, 2011 at 16:12
  • $\begingroup$ @pedja: In the wikipedia link you have provided the first axiom is "$0$ is a natural number". Either accept this as an axiom, or provide an alternative link with the "correct" formulation of Peano's axioms. $\endgroup$
    – Asaf Karagila
    Sep 23, 2011 at 16:49
1
$\begingroup$

HINT $\ $ For nonempty $\rm\ S\subset \mathbb N\ $ show $\rm\ S\:+\:\mathbb N\ =\: \min(S)\: +\: \mathbb N\:.\ $ Your case is $\rm\:S =\:$ odd primes.

$\endgroup$
-2
$\begingroup$

Yes we can use the Peano's axiom to prove that integer = prime + integer. Think of $0 + a = a$.

$\endgroup$
5
  • 3
    $\begingroup$ $0$ is not a prime. $\endgroup$
    – Srivatsan
    Sep 23, 2011 at 6:07
  • 8
    $\begingroup$ "Without loss of generality, assume that $0$ is prime..." $$$$ :) $\endgroup$ Sep 23, 2011 at 6:08
  • 1
    $\begingroup$ I think The Chaz and Blake's point is that Peano's Arithmetics can prove that if $m \leq n$, then there exists a $k$ such that $m + k = n$. $\endgroup$
    – William
    Sep 23, 2011 at 6:20
  • $\begingroup$ @William Now I am confused (and that was not really my point). The question is to write a given number as a prime plus a nonnegative integer, so how is writing $a = 0+a$ useful? $\endgroup$
    – Srivatsan
    Sep 23, 2011 at 6:33
  • $\begingroup$ @Blake: All of the basic theorems of number theory, and much more, can be proved using the first-order Peano axioms. The result you are asking about has a quick informal proof, and that proof can be formalized. $\endgroup$ Sep 23, 2011 at 7:54

You must log in to answer this question.

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