Register to reply

Natural Numbers Proof?

by Bipolarity
Tags: natural, numbers, proof
Share this thread:
Bipolarity
#1
Apr6-12, 01:51 PM
P: 783
If 'n' is a natural number such that n>1, prove that there exists a natural number k such that n-k=1.

It raises the question: What is the definition of a natural number?

Could you say that because n is natural, n-1 must be natural so that if k = n-1, n-k = 1?

BiP
Phys.Org News Partner Science news on Phys.org
What lit up the universe?
Sheepdogs use just two simple rules to round up large herds of sheep
Animals first flex their muscles
Robert1986
#2
Apr6-12, 02:09 PM
P: 828
That seems like a good argument, just mention that n-1 > 0 since n > 1.

As for the definition of "natural number", they simply the positive integers. So, n-1 is natural because a)n is natural so n-1 is an integer and b)b>1 so n-1 >0
micromass
#3
Apr6-12, 02:24 PM
Mentor
micromass's Avatar
P: 18,277
This is actually a surprisingly difficult question. Of course, it's very easy on the first glance. But if you want to work it out fully from the very definition of natural numbers, then it can be difficult.

There are two common definitions of natural numbers.

1) The Peano-axioms.
Natural numbers are a triple (N,s,0) with N a set,[itex]s:N\rightarrow N[/itex] a function (intuitively s(n)=n+1) and 0 an element of N such that
- there exists no x in N such that s(x)=0
- if s(x)=s(y) then x=y
- induction: if [itex]A\subseteq N[/itex] is a set such that [itex]0\in A[/itex] and such that if [itex]x\in A[/itex] than [itex]s(x)\in A[/itex], then A=N

From these axioms, you can reconstruct the theory of natural numbers. In particular you can prove the question in the OP. It is not that easy, however.

2) The set-theoretic definition.
We define
[itex]0=\emptyset[/itex]
[itex]1=\{0\}[/itex]
[itex]2=\{0,1\}[/itex]
[itex]3=\{0,1,2\}[/itex]
[itex]4=\{0,1,2,3\}[/itex]
and so on. (this needs to be made rigorous)

The set of all such sets is called the natural numbers. This satisfied the Peano-axioms with [itex]s(n)=n\cup \{n\}[/itex]. The advantage here is that there is a unique set of natural numbers. In the first approach, there could be many such sets (which are homeomorphic). Another advantage is that induction is no longer an axiom, but can be proven from the set theoretic axioms. This might be preferable as induction might not be so intuitive to be taken an axiom.

HallsofIvy
#4
Apr6-12, 02:36 PM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,533
Natural Numbers Proof?

If you want a proof from basic definitions, that's a long proof!

One way to define the "natural numbers" is to use the Peano axioms:

The natural numbers consist of a set N, together with a function, s (called the "successor function") from N to N such that
1) There exist a unique member of N, called "1" such that s is a one-to-one function from N to N-{1}. (In other words, every natural number has a successor, every natural number except 1 is the successor of some natural number.)
2) If X is a set of natural numbers such that 1 is in X and, whenever n is in X so is s(n), then X is the set of all natural numbers. (This is the "induction axiom.)

We can define ">" by "m> n if and only if there exist a natural number x such that x+ n= m.

From there we can define "m+ n", for m and n natural numbers, by
1) 1+ n= s(n).
2) if [itex]m\ne 1[/itex], then there exist x such that m= s(x) and we define
m+ n= s(x+ n).

One needs to show that is "well defined". That is, that given any m,n in N, there exist a unique member of N equal to m+n.

Once we have that, we can define n- m as the unique number, x, such that m+ x= n.

Now, if n> 1, by definition of ">", there exist k such that k+1= n and therefore, n- k= 1.

(micromass got in ahead of me again!)
AdrianZ
#5
Apr7-12, 08:00 AM
P: 320
Quote Quote by micromass View Post
Another advantage is that induction is no longer an axiom, but can be proven from the set theoretic axioms. This might be preferable as induction might not be so intuitive to be taken an axiom.
How can we prove induction from the set theoretic axioms? sounds very interesting.
DonAntonio
#6
Apr7-12, 08:09 AM
P: 606
Quote Quote by AdrianZ View Post
How can we prove induction from the set theoretic axioms? sounds very interesting.


What "set theoretic axioms"?? The Principle of Induction is equivalent, under the usual axioms of arithmetic, to the well (natural) ordering of the set of the natural numbers...is this what you meant?

DonAntonio


Register to reply

Related Discussions
Proof: Applications of the Universal Property of Natural Numbers Calculus & Beyond Homework 4
Proof with natural numbers and sequences of functions Calculus & Beyond Homework 4
Cardinality of Natural even numbers and Natural numbers Set Theory, Logic, Probability, Statistics 19
Natural numbers proof help Calculus & Beyond Homework 2
Proof for k natural numbers Set Theory, Logic, Probability, Statistics 22