Theorem About Binary Operations - Introductory Analysis

  • #1

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 fp:ℕ→ℕ such that fp(1)=s(p) and fp(s(n)) = s(fp(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
 

Answers and Replies

  • #2
andrewkirk
Science Advisor
Homework Helper
Insights Author
Gold Member
3,886
1,454
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.
 
  • #3
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
 
  • #4
andrewkirk
Science Advisor
Homework Helper
Insights Author
Gold Member
3,886
1,454
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.
 
  • #5
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 G1 such that it does not follow this axiom and a set G2 that does follow the axiom,G1 ≠ G2 = ℕ → G1 ≠ ℕ. 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
 
  • #6
22,089
3,296
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}##.
 
  • #7
Thank you,

I understand now. It kind of odd that I haven't had problems before with this misunderstanding.
 
  • #8
1,095
289
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.
 

Related Threads on Theorem About Binary Operations - Introductory Analysis

  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
16
Views
497
Replies
2
Views
2K
  • Last Post
Replies
1
Views
4K
Top