Proof: Applications of the Universal Property of Natural Numbers

[icestone111]

Homework Statement

N refers to the set of all natural numbers.
Part 2: From the previous problem, we have σⁿ : N → N for all n ε N.
Show that for any n ε N, σ⁽ⁿ⁺¹⁾(N) is a subset of σⁿ(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), that x ε σⁿ(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 σⁿ of (N) help (if so, how is this defined/how do I work with this?)?

Figured out part 1.

 

[Mark44]

Homework Statement

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 fⁿ?

I have a suspicion that this is about proofs by mathematical induction.

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

 

[icestone111]

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

 

[Mark44]

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 = f², 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.

 

[icestone111]

I'm having trouble understanding this notation.

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

Also, what is fn? Do you mean fⁿ?

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!