• Support PF! Buy your school textbooks, materials and every day products Here!

Proof: Applications of the Universal Property of Natural Numbers

  • #1

Homework Statement


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:

Answers and Replies

  • #2
33,262
4,963

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 fn?

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).
 
  • #3
Ah, sorry about that. f^σ(n) means fσ(n) and fn was meant to be fn
 
  • #4
33,262
4,963
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.
 
  • #5
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!
 

Related Threads on Proof: Applications of the Universal Property of Natural Numbers

  • Last Post
Replies
9
Views
3K
  • Last Post
Replies
1
Views
1K
Replies
4
Views
2K
Replies
5
Views
1K
  • Last Post
Replies
2
Views
5K
Replies
3
Views
295
Replies
3
Views
946
  • Last Post
Replies
10
Views
4K
  • Last Post
Replies
4
Views
880
  • Last Post
Replies
2
Views
4K
Top