# Homework Help: Theorem About Binary Operations - Introductory Analysis

1. Jul 1, 2016

### Ethan Godden

1. The problem statement, all variables and given/known data
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)

2. Relevant 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))

3. 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

2. Jul 1, 2016

### andrewkirk

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. Jul 1, 2016

### Ethan Godden

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. Jul 2, 2016

### andrewkirk

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$.
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. Jul 2, 2016

### Ethan Godden

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. Jul 2, 2016

### micromass

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. Jul 2, 2016

### Ethan Godden

Thank you,

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