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.")?
Can we use Peano's axioms to prove that integer = prime + integer?
-
2I'm a bit confused; are you wanting something like $1+n=1+(3+(n-3))=3+(n-2)=3+((n+1)-3)$? – 2011-09-23
-
12Why does it have to be *some* prime number? Can't we just say that $n = (n - 3) + 3$ ? – 2011-09-23
-
0@aengle,no, I wrote random examples...it can be any combination of $n,p,m$ that satisfy conditions of statement – 2011-09-23
3 Answers
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).
-
0,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... – 2011-09-23
-
0,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... – 2011-09-23
-
0@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$. – 2011-09-23
-
0,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... – 2011-09-23
-
0@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. – 2011-09-23
-
0@ArturoMagidin,http://www.ms.uky.edu/~lee/ma502/notes2/node7.html..look at axiom $1$, it isn't same as in wikipedia version..so I don't know what version of the first axiom to use... – 2011-09-23
-
0@AsafKaragila,http://www.ms.uky.edu/~lee/ma502/notes2/node7.html – 2011-09-23
-
0@pedja: Sigh. If to you "natural number" means "positive integer", and to me "natural number" means "nonnegative integer", then **what is the problem**? You asked for a proof using Peano's axioms that every natural greater than 2 is the sum of a prime and a nonnegative integer. Take my proof, and wherever you see "natural number" replace it with "nonnegative integer". You are getting stuck on a triviality. – 2011-09-23
-
0@pedja: Perhaps you might want to confuse yourself with your own words: you say "the sixth axiom". The notes you now gleefully point to have no "sixth axiom". – 2011-09-23
-
0@ArturoMagidin,If $0$ isn't element of $S$ than $3$ can not be represented neither as $2+1$ neither as $3+0$...which means that number $3$ is an exception.. – 2011-09-23
-
0@ArturoMagidin,I didn't notice at first glance that wiki version of axioms includes $0$ – 2011-09-23
-
0@pedja: Do me a favor: read carefully and think about it before objecting. $S$ is the set of all natural numbers greater than 3 that satisfy the condition you want, with $1$ and $2$ (and possibly $0$) thrown in for good measure. When we say "$n$ can be expressed as the sum of a prime greater than 2 and a nonnegative integer", we are **not** saying "the sum of a prime greater than 2 and an element of $S$" (that would not be a valid definition of $S$!). We don't take $0$ from the set $S$, we take it from, wait for it... *the set of nonnegative integer*, exactly what the definition of $S$ says. – 2011-09-23
-
0@ArturoMagidin,Thank you for explanation... – 2011-09-23
HINT $\ $ For nonempty $\rm\ S\subset \mathbb N\ $ show $\rm\ S\:+\:\mathbb N\ =\: \min(S)\: +\: \mathbb N\:.\ $ Your case is $\rm\:S =\:$ odd primes.
Yes we can use the Peano's axiom to prove that integer = prime + integer. Think of $0 + a = a$.
-
3$0$ is not a prime. – 2011-09-23
-
8"Without loss of generality, assume that $0$ is prime..." $$$$ :) – 2011-09-23
-
0I 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$. – 2011-09-23
-
0@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? – 2011-09-23
-
0@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. – 2011-09-23