Theorem About Binary Operations - Introductory Analysis

[Ethan Godden]

Homework Statement

This theorem comes from the book "The Real Numbers and Real Analysis" by Bloch. I am having a hard time understanding a particular part of the proof given in the book.

Prove the following theorem:

There is a unique binary operation +:ℕ×ℕ→ℕ that satisfies the following two properties for all n,m ∈ ℕ.
1) n+1=s(n)
2)n+s(m)=s(n+m)

Homework Equations

The following is info that can be used to prove the theorem
.
Definition: Let S be a set. A binary operation on S is a function S×S→S.
Axiom: There exists a set ℕ with an element 1 ∈ ℕ and a function s:ℕ→ℕ that satisfy the following three properties
1) There is no n ∈ ℕ such that s(n) = 1
2) The function s is injective (one-to-one)
3)Let G⊆ℕ be a set. Suppose 1 ∈ G, and that if g ∈ G then s(g) ∈ G. Then G = ℕ
Lemma: Let a ∈ ℕ. Suppose a ≠ 1. Then there is a unique b ∈ ℕ such that a = s(b)
Theorem (Defintion by Recursion): Let H be a set, let e ∈ H and let k: H→H be a function. Then there is a unique function f: ℕ→H such that f(1)=e, and f(s(n))=k(f(n))

The Attempt at a Solution

The following is the proof given in the book for existence of such an operation . The underlined bolded part is what I am having trouble understanding.

Suppose p ∈ ℕ. We can apply the theorem above to the set ℕ, the element s(p) ∈ ℕ and the function s: ℕ→ℕ to deduce that there is a unique function f_p:ℕ→ℕ such that f_p(1)=s(p) and f_p(s(n)) = s(f_p(n))...

Why is s(p) ∈ ℕ? I do realize the function s is defined as s:ℕ→ℕ, so the output of the function s (if it exists) must be in ℕ, but how do we know s(p) is defined from the above info or from the definition, axiom, or theorem above. The only reason I can think of is we can assume for any p that s(p) is defined, but I am not conviced because that axiom only says the function is injective, not bijective,

Any help would be appreciated,

Thank you,

Ethan

 

[andrewkirk]

Why is s(p) ∈ ℕ? I do realize the function s is defined as s:ℕ→ℕ, so the output of the function s (if it exists) must be in ℕ, but how do we know s(p) is defined from the above info or from the definition, axiom, or theorem above.

These propositions are asserted by the axiom. Note that it is an Axiom, not a Definition. An axiom asserts a proposition, that is thenceforth to be accepted as true. A definition specifies a property and attaches a label to that property. It does not assert that there is necessarily anything satisfying that property. For that, an axiom or a proof is needed.

By accepting the axiom, we are accepting that there exists a function s with the required properties, including that its image lies in ##\mathbb N##. Note, by the way that the axiom does not assert that ##s## is the only function from ##\mathbb N## to ##\mathbb N## that satisfies those properties. It remains to be proved (should we wish to do so (and it is possible to do so)) that s is the only such function.

 

[Ethan Godden]

By accepting the axiom, we are accepting that there exists a function s with the required properties, including that its image lies in NN\mathbb N.

I understand that if s(p) exists, its image lies in ℕ by the axiom, but isn't it possible that s(p) is not defined at p? After all, doesn't the axiom say that the function s is injective. Wouldn't it need to be bijective or surjective in order for s(p) to be defined for all possible p ∈ ℕ? I hope I am not bypassing anything you said in the first paragraph that explains this.I still do not quite understand how I can deduce s(p) is defined for all p from the axiom.

Thank You,

Ethan

 

[andrewkirk]

isn't it possible that s(p) is not defined at p?

No. The statement that ##s:\mathbb N\to\mathbb N## means, amongst other things, that ##s(p)## is defined for every natural number ##p##. In other words, its domain is ##\mathbb N##.

Wouldn't it need to be bijective or surjective in order for s(p) to be defined for all possible p ∈ ℕ?

No. The function ##n\mapsto 2n## is defined on all natural numbers but it is not surjective: its image is only the even numbers.

 

[Ethan Godden]

No. The statement that s:N→Ns:N→Ns:\mathbb N\to\mathbb N means, amongst other things, that s(p)s(p)s(p) is defined for every natural number ppp. In other words, its domain is NN\mathbb N.

Ok, what about a function f:ℝ→ℝ such that f(x)=√x? This would mean its not defined for x<0, but how could we deduce that from "f: ℝ→ℝ" only like in this question?

I think I found a reason for why s(p) is defined for every p. I believe part 3 of the axiom implies s∈ℕ→s(p)∈ℕ because given a set G₁ such that it does not follow this axiom and a set G₂ that does follow the axiom,G₁ ≠ G₂ = ℕ → G₁ ≠ ℕ. It can't equal ℕ because of the definition of set equality. Is this correct reasoning?

What I originally thought was part 3 was a simple implication where a→b, but that does not mean b→a. The b→a is the p∈ℕ→s(p)∈ℕ in axiom 3.

Thank You,

Ethan

 

[micromass]

Ok, what about a function f:ℝ→ℝ such that f(x)=√x? This would mean its not defined for x<0, but how could we deduce that from "f: ℝ→ℝ" only like in this question?

The simple reason is that ##f:\mathbb{R}\rightarrow \mathbb{R}:x\rightarrow \sqrt{x}## is dead wrong. That ##f## is not a function. One of the requirements of a function says exactly that every element in the domain has an image. This is not true with the square root. However, we could write ##f:\mathbb{R}^+\rightarrow \mathbb{R}:x\rightarrow \sqrt{x}##.

So the answer to your OP is clear: ##s:\mathbb{N}\rightarrow \mathbb{N}## is defined to be a function, so ##s(p)## exists for all ##p\in \mathbb{N}##.

 

[Ethan Godden]

Thank you,

I understand now. It kind of odd that I haven't had problems before with this misunderstanding.

 

[MidgetDwarf]

I know this is an old thread, but this is in regards to book, Bloch: Real Numbers and Real Analysis. It was confusing for a bit to me, it took me like 3 days to understand.

We apply the Definition of Recursion to the Peano Postulates. We know by definition of the set of Natural Numbers, it's existence is given by parts a,b,c of the Peano Postulates.