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: Proof: Applications of the Universal Property of Natural Numbers

  1. Oct 30, 2011 #1
    1. The problem statement, all variables and given/known data
    N refers to the set of all natural numbers.
    Part 2: From the previous problem, we have σn : N → N for all n ε N.
    Show that for any n ε N, σ(n+1)(N) is a subset of σn(N), where we have
    used n + 1 for σ(n) as we defined in class.

    2. The attempt at a solution
    For Part 2, I believe the goal would be to prove that given any x ε σ(n+1)(N), that x ε σn(N) as well. For this problem, I am not sure where to start for this problem, since it seems like it would be the opposite direction (the subset would be the other way). Would knowing what the definition of σn of (N) help (if so, how is this defined/how do I work with this?)?

    Figured out part 1.
    Last edited: Oct 30, 2011
  2. jcsd
  3. Oct 30, 2011 #2


    Staff: Mentor

    I'm having trouble understanding this notation.

    Does f^σ(n) mean fσ(n) or fσ(n)?

    Also, what is fn? Do you mean fn?

    I have a suspicion that this is about proofs by mathematical induction.
  4. Oct 30, 2011 #3
    Ah, sorry about that. f^σ(n) means fσ(n) and fn was meant to be fn
  5. Oct 30, 2011 #4


    Staff: Mentor

    That σ(n) suggests "successor of n" to me, so that σ(1) = 2, σ(2) = 3, and so on. f is an arbitrary function that maps an element of set S to a possibly different element of S. Certainly you would be able to compose f with itself to get f°f = f2, and that would also be a mapping from S to S.

    I can't add much more here - it's not clear to me what you need to do.
  6. Oct 30, 2011 #5
    I'm just uncertain if my reasoning for part 1 is correct and how to move forward with part 2. I'm pretty sure you do need to prove these (at least part 1) by mathematical induction, I'm just uncertain how to do these inductive steps.

    That's fine, thanks for taking a look!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook