## Proof: Applications of the Universal Property of Natural Numbers

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.

 PhysOrg.com science news on PhysOrg.com >> Front-row seats to climate change>> Attacking MRSA with metals from antibacterial clays>> New formula invented for microscope viewing, substitutes for federally controlled drug

Mentor
 Quote by icestone111 1. The problem statement, all variables and given/known data N refers to the set of all natural numbers. Part 1: There are two different parts I'm having trouble with: Let S be a set and let f : S → S be a function. Show that for any n ε N, there exists a function denoted by f^n : S → S such that f^1 = f and f^σ(n) = f ° fn.
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.
 Quote by icestone111 Part 2: From the previous problem, we have σ^n : N → N for all n ε N. Show that for any n ε N, σ^(n+1) of (N) is a subset of σ^n of (N), where we have used n + 1 for σ(n) as we defined in class. 2. The attempt at a solution Part 1: For my reasoning, we have to prove the two given statements, f^1 = f and f^σ(n) = f ° f^n. So f^1 is clearly equivalent to f. After, the only thing I could think of doing is letting σ(n) = n+1, using the property of commutativity of addition, to have f^(n+1)= f ° f^n => f^(1+n) = f° f^n => f ° f^n = f ° f^n, though I feel as if this is not valid reasoning. Beforehand, I proved this for an element, say x ε N, but can construct functions to navigate around the elements. How do I do this for functions? For Part 2, I believe the goal would be to prove that given any x ε σ^(n+1) of (N), that x ε σ^n of (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).

 Ah, sorry about that. f^σ(n) means fσ(n) and fn was meant to be fn

Mentor

## Proof: Applications of the Universal Property of Natural Numbers

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.

 Quote by Mark44 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.
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!