1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Theorem About Binary Operations - Introductory Analysis

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

  2. jcsd
  3. Jul 1, 2016 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

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

  5. Jul 2, 2016 #4


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

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

  7. Jul 2, 2016 #6
    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}##.
  8. Jul 2, 2016 #7
    Thank you,

    I understand now. It kind of odd that I haven't had problems before with this misunderstanding.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted