Mixing
Why does the fixed point theorem justify the existence of the factorial function?
Clash Royale CLAN TAG#URR8PPP
up vote
5
down vote
favorite
I was learning about fixed point theorem in the context of programming language semantics. In the notes they have the following excerpt:
Many recursive definitions in mathematics and computer science are given informally, but they are more
subtle than they appear to be. The fixed-point theorem can be used to formally argue that such definitions are
indeed correct. Consider, for example, the following common definition of the factorial:
$$
f(n) =
left{
beginarrayll
1 & mboxif n = 0 \
n * f(n-1) & mboxif n > 0
endarray
right.
$$
How can we know whether such a mathematical object, i.e., a function f satisfying the above property,
actually exists and is unique, as tacitly assumed?
then it moves one to claim that somehow the fixed point theorem magically justifies this definition to be valid. Thats the part I don't understand. Why is that true?
I think they proceed to try to justify the fixed point theorem justifies it but I don't think I understand what in particular makes the fixed point theorem make this work. Any ideas?
Excerpt (from here) for more context (page 89):
computer-science computability fixed-point-theorems fixedpoints
asked 2 hours ago
Pinocchio
1,76621651
 |Â
show 4 more comments
up vote
5
down vote
favorite
I was learning about fixed point theorem in the context of programming language semantics. In the notes they have the following excerpt:
Many recursive definitions in mathematics and computer science are given informally, but they are more
subtle than they appear to be. The fixed-point theorem can be used to formally argue that such definitions are
indeed correct. Consider, for example, the following common definition of the factorial:
$$
f(n) =
left{
beginarrayll
1 & mboxif n = 0 \
n * f(n-1) & mboxif n > 0
endarray
right.
$$
How can we know whether such a mathematical object, i.e., a function f satisfying the above property,
actually exists and is unique, as tacitly assumed?
then it moves one to claim that somehow the fixed point theorem magically justifies this definition to be valid. Thats the part I don't understand. Why is that true?
I think they proceed to try to justify the fixed point theorem justifies it but I don't think I understand what in particular makes the fixed point theorem make this work. Any ideas?
Excerpt (from here) for more context (page 89):
computer-science computability fixed-point-theorems fixedpoints
asked 2 hours ago
Pinocchio
1,76621651
I would check out the well-ordering principle. This is very much related to this
– Rushabh Mehta
2 hours ago
What page is it on?
– Ovi
2 hours ago
@Ovi page 89 of the notes fsl.cs.illinois.edu/images/c/ca/…
– Pinocchio
2 hours ago
@RushabhMehta non empty sets of positive integers have least elements (I assume generalizes to well ordered sets that are countable and non empty have a least element or something of that sort). Now what? I fail to see the relation, my apology.
– Pinocchio
2 hours ago
@N.Bach I still don't get it. I could have proved the original $f(n)$ that didn't refer to fixed points existed everywhere in $mathbb N$ without referring to fixed points. What did introducing the concept of fixed points actually do?
– Pinocchio
1 hour ago
 |Â
show 4 more comments
up vote
5
down vote
favorite
up vote
5
down vote
favorite
I was learning about fixed point theorem in the context of programming language semantics. In the notes they have the following excerpt:
Many recursive definitions in mathematics and computer science are given informally, but they are more
subtle than they appear to be. The fixed-point theorem can be used to formally argue that such definitions are
indeed correct. Consider, for example, the following common definition of the factorial:
$$
f(n) =
left{
beginarrayll
1 & mboxif n = 0 \
n * f(n-1) & mboxif n > 0
endarray
right.
$$
How can we know whether such a mathematical object, i.e., a function f satisfying the above property,
actually exists and is unique, as tacitly assumed?
then it moves one to claim that somehow the fixed point theorem magically justifies this definition to be valid. Thats the part I don't understand. Why is that true?
I think they proceed to try to justify the fixed point theorem justifies it but I don't think I understand what in particular makes the fixed point theorem make this work. Any ideas?
Excerpt (from here) for more context (page 89):
computer-science computability fixed-point-theorems fixedpoints
asked 2 hours ago
Pinocchio
1,76621651
I was learning about fixed point theorem in the context of programming language semantics. In the notes they have the following excerpt:
Many recursive definitions in mathematics and computer science are given informally, but they are more
subtle than they appear to be. The fixed-point theorem can be used to formally argue that such definitions are
indeed correct. Consider, for example, the following common definition of the factorial:
$$
f(n) =
left{
beginarrayll
1 & mboxif n = 0 \
n * f(n-1) & mboxif n > 0
endarray
right.
$$
How can we know whether such a mathematical object, i.e., a function f satisfying the above property,
actually exists and is unique, as tacitly assumed?
then it moves one to claim that somehow the fixed point theorem magically justifies this definition to be valid. Thats the part I don't understand. Why is that true?
I think they proceed to try to justify the fixed point theorem justifies it but I don't think I understand what in particular makes the fixed point theorem make this work. Any ideas?
Excerpt (from here) for more context (page 89):
computer-science computability fixed-point-theorems fixedpoints
computer-science computability fixed-point-theorems fixedpoints
asked 2 hours ago
Pinocchio
1,76621651
asked 2 hours ago
Pinocchio
1,76621651
edited 2 hours ago
asked 2 hours ago
Pinocchio
1,76621651
asked 2 hours ago
Pinocchio
1,76621651
asked 2 hours ago
Pinocchio
1,76621651
1,76621651
I would check out the well-ordering principle. This is very much related to this
– Rushabh Mehta
2 hours ago
What page is it on?
– Ovi
2 hours ago
@Ovi page 89 of the notes fsl.cs.illinois.edu/images/c/ca/…
– Pinocchio
2 hours ago
@RushabhMehta non empty sets of positive integers have least elements (I assume generalizes to well ordered sets that are countable and non empty have a least element or something of that sort). Now what? I fail to see the relation, my apology.
– Pinocchio
2 hours ago
@N.Bach I still don't get it. I could have proved the original $f(n)$ that didn't refer to fixed points existed everywhere in $mathbb N$ without referring to fixed points. What did introducing the concept of fixed points actually do?
– Pinocchio
1 hour ago
 |Â
show 4 more comments
I would check out the well-ordering principle. This is very much related to this
– Rushabh Mehta
2 hours ago
What page is it on?
– Ovi
2 hours ago
@Ovi page 89 of the notes fsl.cs.illinois.edu/images/c/ca/…
– Pinocchio
2 hours ago
@RushabhMehta non empty sets of positive integers have least elements (I assume generalizes to well ordered sets that are countable and non empty have a least element or something of that sort). Now what? I fail to see the relation, my apology.
– Pinocchio
2 hours ago
@N.Bach I still don't get it. I could have proved the original $f(n)$ that didn't refer to fixed points existed everywhere in $mathbb N$ without referring to fixed points. What did introducing the concept of fixed points actually do?
– Pinocchio
1 hour ago
I would check out the well-ordering principle. This is very much related to this
– Rushabh Mehta
2 hours ago
I would check out the well-ordering principle. This is very much related to this
– Rushabh Mehta
2 hours ago
What page is it on?
– Ovi
2 hours ago
What page is it on?
– Ovi
2 hours ago
@Ovi page 89 of the notes fsl.cs.illinois.edu/images/c/ca/…
– Pinocchio
2 hours ago
@Ovi page 89 of the notes fsl.cs.illinois.edu/images/c/ca/…
– Pinocchio
2 hours ago
@RushabhMehta non empty sets of positive integers have least elements (I assume generalizes to well ordered sets that are countable and non empty have a least element or something of that sort). Now what? I fail to see the relation, my apology.
– Pinocchio
2 hours ago
@RushabhMehta non empty sets of positive integers have least elements (I assume generalizes to well ordered sets that are countable and non empty have a least element or something of that sort). Now what? I fail to see the relation, my apology.
– Pinocchio
2 hours ago
@N.Bach I still don't get it. I could have proved the original $f(n)$ that didn't refer to fixed points existed everywhere in $mathbb N$ without referring to fixed points. What did introducing the concept of fixed points actually do?
– Pinocchio
1 hour ago
@N.Bach I still don't get it. I could have proved the original $f(n)$ that didn't refer to fixed points existed everywhere in $mathbb N$ without referring to fixed points. What did introducing the concept of fixed points actually do?
– Pinocchio
1 hour ago
 |Â
show 4 more comments
2 Answers
2
active
oldest
votes
up vote
3
down vote
Why is the fixed point theorem actually important here?
Well, let's think about why we believe that there is a function $f$ satisfying [recursive description of $!$]. It comes down to the following two (quite correct) beliefs:
We can use the recursive description of $!$ to "deduce" what the value of $!$ should be on each specific natural number.
We cannot use the recursive description of $!$ to deduce two contradictory things about $!$ (e.g. we can't use it to prove that $2!$ should be $7$).
With both claims in hand, we can then define $!$ by saying "$n!$ is the unique $m$ such that "$n!=m$" is implied by the recursive description." (In fact, only the second claim is needed to justify the existence of $!$ as a partial function.) But these claims need to be justified, and while in the case of the factorial function they are pretty obvious, $(i)$ the second claim is actually not as trivial to prove as one might hope and $(ii)$ certainly in general we want a theorem that lets us handle problems like these.
The fixed point theorem is basically a machine for getting around this issue: given a recursive description of a function, the fixed point theorem can (often) construct functions which actually satisfy that description in a precise, controlled way.
How we use it here (part $1$)
We can pass from the recursive description of the factorial function to a (perfectly good) definition of an operator on (partial) functions. The fixed point theorem shows that there is a fixed point, $f$, for this operator (once we've shown that this operator is in fact continuous); we then argue by induction that in fact this $f$ actually is the factorial function.
In detail:
From our self-referential "definition" of the factorial function, we can extract a perfectly good non-self-referential definition of an operator on partial functions $mathcalF$: given a partial function $g:mathbbNrightarrowmathbbN$, $mathcalF(g)$ is the partial function given by
$$
mathcalF(g):nmapsto
left{
beginarrayll
1 & mboxif n = 0 \
n * g(n-1) & mboxif n > 0mbox and g(n-1)downarrow\
uparrow & mboxif $n>0$ and $g(n-1)uparrow$
endarray
right.
$$
where "$uparrow$" means "is undefined" and "$downarrow$" means "is defined." (Note that I've written "$mathcalF(g):nmapsto...$" instead of "$mathcalF(g)(n)=...$" for clarity, but there's no actual difference.) Intuitively, think of $mathcalF$ as taking in a "partial computation" of $!$ - say, the first seventeen bits of the factorial function - and "going a bit further." The function we want is the "limit" of this process. This is exactly what the fixed point theorem says exists.
A quick example
Suppose $g$ is the partial function which sends $3$ to $7$, sends $10$ to $2$, sends $11$ to $11$, and is otherwise undefined. Then what partial function should $mathcalF(g)$ be?
In no particular order:
$mathcalF(g)$ is certainly defined at $0$: by definition of $mathcalF$, we'll always have $mathcalF(g):0mapsto 1$ regardless of what $g$ is.
On the other hand, since $g(0)$ isn't defined, we know that $mathcalF(g)(1)$ isn't defined.
What about $11$? Well, $11>0$ and $g(11-1)$ is defined, so the second clause of the definition of $mathcalF$ tells us that $$mathcalF(g)(11)=11cdot g(11-1)=11cdot g(10)=11cdot 2=22.$$ So $mathcalF(g)(11)downarrow =2$.
Exercise: Convince yourself that in fact the domain of $mathcalF(g)$ is precisely $0,4,11,12$ and calculate the values of $mathcalF(g)(4)$ and $mathcalF(g)(12)$.
How we use it here (part $2$)
Having defined our operator $mathcalF$, we now need to use it somehow.
Claim $1$: $mathcalF$ is continuous.
The text you've quoted doesn't actually prove this, but it's not hard to check. If this is an issue, though, let me know and I'll add details.
With the continuity of $mathcalF$ in hand, we can now invoke the fixed point theorem to get a function $f$ such that $$mathcalF(f)=f.$$ In fact, the fixed point theorem gives us a least fixed point of $mathcalF$, but we don't even need that in the current situation. We now show:
Claim $2$: This $f$ is in fact the factorial function. That is, we have $(i)$ $f$ is defined on all of $mathbbN$, $(ii)$ $f(0)=1$, and $(iii)$ $f(n+1)=(n+1)f(n)$.
Parts $(i)$ and $(iii)$ are proved by induction: get a contradiction from looking at the putative first $n$ on which $f$ is undefined, and the putative first $n$ on which $f(n+1)not=(n+1)f(n)$, respectively. Part $(ii)$ doesn't require any induction, and is just a quick observation.
Specifically, here's how we prove $(i)$ and $(ii)$ (I'll leave $(iii)$ as an exercise). The key point is that the equality $$mathcalF(f)=f$$ (this is what it means for $f$ to be a fixed point of $mathcalF$) lets us prove things about $f$ by proving them about $mathcalF(f)$.
To prove $(ii)$, we know by definition of $mathcalF$ that $mathcalF(g)(0)downarrow=1$ for any partial function $g$. In particular, we have $$mathcalF(f)(0)downarrow=1.$$ But since $f$ is a fixed point for $mathcalF$ we can turn this into $$f(0)downarrow=1.$$
To prove $(i)$, we've just shown that $f(0)$ is defined. Now suppose $f(n)$ is defined. By definition of $mathcalF$, we know $mathcalF(f)(n+1)$ is defined (namely, it's $(n+1)f(n)$). But again since $f$ is a fixed point of $mathcalF$, this tells us that $f(n+1)$ is defined. So by induction, $f$ is total.
answered 1 hour ago
Noah Schweber
114k9143268
is taking in a....seems you missed out a part of your sentence.
– Pinocchio
1 hour ago
my previous comment is important because I am failing to understand how continuity holds. $mathcal F$ maps partial functions $g(n)$ to either the partial constant function 1, or $n*g(n-1)$ or undefined. So $mathcal F$ itself is a partial function because it maps partial functions to undefined? I'm really confused...
– Pinocchio
1 hour ago
@Pinocchio Good catch, I've fixed that bit. Re: your second comment: no, $mathcalF$ is total as an operator on partial functions: it takes in partial functions and outputs partial functions. Saying that $mathcalF$ is total is to say that $mathcalF(g)$ is always a well-defined partial function whenever $g$ is a partial function, not that $mathcalF(g)$ is always a total function whenever $g$ is a partial function. (Unfortunately the phrase "$mathcalF(g)$ is always defined" may indeed suggest the latter!)
– Noah Schweber
1 hour ago
sorry to be a complainer but it makes it harder to read, usually $bot$ i.e. bottom means undefined. So seeing arrows going up instead of down for undefined is confusing me. I'm trying to parse your answer. I still don't get it :(
– Pinocchio
1 hour ago
Why is $mathcal F$ continuous?
– Pinocchio
1 hour ago
 |Â
show 4 more comments
up vote
2
down vote
As the function $f$ is defined in terms of itself, you have a priori no guarantee that it is defined at all or uniquely defined.
Now the function $mathcal F$ is such that it extends the known values of $f(n)$ (from a given subset of naturals) by applying the definition.
Then the fixed-point theorem guarantees that $mathcal F$ has a fixed-point, which corresponds to $f$ defined over the whole of $mathbb N$. Uniqueness of the fixed-point guarantees that $f$ is uniquely defined.
answered 1 hour ago
Yves Daoust
116k667211
I'm failing to appreciate what the role of $mathcal F$ is. $mathcal F(g(n))$ is equal to the definition of factorial function plus a condition of undefined when the funciton is undefined. Conceptually $mathcal F$ is just the same as $g(n)$. So I don't see what role its suppose to be playing.
– Pinocchio
1 hour ago
like we could have done induction on the original definition of $f(n)$ that didn't refer to any fixed points to show it was defined everywhere...what did $mathcal F $ contribute?
– Pinocchio
1 hour ago
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
Why is the fixed point theorem actually important here?
Well, let's think about why we believe that there is a function $f$ satisfying [recursive description of $!$]. It comes down to the following two (quite correct) beliefs:
We can use the recursive description of $!$ to "deduce" what the value of $!$ should be on each specific natural number.
We cannot use the recursive description of $!$ to deduce two contradictory things about $!$ (e.g. we can't use it to prove that $2!$ should be $7$).
With both claims in hand, we can then define $!$ by saying "$n!$ is the unique $m$ such that "$n!=m$" is implied by the recursive description." (In fact, only the second claim is needed to justify the existence of $!$ as a partial function.) But these claims need to be justified, and while in the case of the factorial function they are pretty obvious, $(i)$ the second claim is actually not as trivial to prove as one might hope and $(ii)$ certainly in general we want a theorem that lets us handle problems like these.
The fixed point theorem is basically a machine for getting around this issue: given a recursive description of a function, the fixed point theorem can (often) construct functions which actually satisfy that description in a precise, controlled way.
How we use it here (part $1$)
We can pass from the recursive description of the factorial function to a (perfectly good) definition of an operator on (partial) functions. The fixed point theorem shows that there is a fixed point, $f$, for this operator (once we've shown that this operator is in fact continuous); we then argue by induction that in fact this $f$ actually is the factorial function.
In detail:
From our self-referential "definition" of the factorial function, we can extract a perfectly good non-self-referential definition of an operator on partial functions $mathcalF$: given a partial function $g:mathbbNrightarrowmathbbN$, $mathcalF(g)$ is the partial function given by
$$
mathcalF(g):nmapsto
left{
beginarrayll
1 & mboxif n = 0 \
n * g(n-1) & mboxif n > 0mbox and g(n-1)downarrow\
uparrow & mboxif $n>0$ and $g(n-1)uparrow$
endarray
right.
$$
where "$uparrow$" means "is undefined" and "$downarrow$" means "is defined." (Note that I've written "$mathcalF(g):nmapsto...$" instead of "$mathcalF(g)(n)=...$" for clarity, but there's no actual difference.) Intuitively, think of $mathcalF$ as taking in a "partial computation" of $!$ - say, the first seventeen bits of the factorial function - and "going a bit further." The function we want is the "limit" of this process. This is exactly what the fixed point theorem says exists.
A quick example
Suppose $g$ is the partial function which sends $3$ to $7$, sends $10$ to $2$, sends $11$ to $11$, and is otherwise undefined. Then what partial function should $mathcalF(g)$ be?
In no particular order:
$mathcalF(g)$ is certainly defined at $0$: by definition of $mathcalF$, we'll always have $mathcalF(g):0mapsto 1$ regardless of what $g$ is.
On the other hand, since $g(0)$ isn't defined, we know that $mathcalF(g)(1)$ isn't defined.
What about $11$? Well, $11>0$ and $g(11-1)$ is defined, so the second clause of the definition of $mathcalF$ tells us that $$mathcalF(g)(11)=11cdot g(11-1)=11cdot g(10)=11cdot 2=22.$$ So $mathcalF(g)(11)downarrow =2$.
Exercise: Convince yourself that in fact the domain of $mathcalF(g)$ is precisely $0,4,11,12$ and calculate the values of $mathcalF(g)(4)$ and $mathcalF(g)(12)$.
How we use it here (part $2$)
Having defined our operator $mathcalF$, we now need to use it somehow.
Claim $1$: $mathcalF$ is continuous.
The text you've quoted doesn't actually prove this, but it's not hard to check. If this is an issue, though, let me know and I'll add details.
With the continuity of $mathcalF$ in hand, we can now invoke the fixed point theorem to get a function $f$ such that $$mathcalF(f)=f.$$ In fact, the fixed point theorem gives us a least fixed point of $mathcalF$, but we don't even need that in the current situation. We now show:
Claim $2$: This $f$ is in fact the factorial function. That is, we have $(i)$ $f$ is defined on all of $mathbbN$, $(ii)$ $f(0)=1$, and $(iii)$ $f(n+1)=(n+1)f(n)$.
Parts $(i)$ and $(iii)$ are proved by induction: get a contradiction from looking at the putative first $n$ on which $f$ is undefined, and the putative first $n$ on which $f(n+1)not=(n+1)f(n)$, respectively. Part $(ii)$ doesn't require any induction, and is just a quick observation.
Specifically, here's how we prove $(i)$ and $(ii)$ (I'll leave $(iii)$ as an exercise). The key point is that the equality $$mathcalF(f)=f$$ (this is what it means for $f$ to be a fixed point of $mathcalF$) lets us prove things about $f$ by proving them about $mathcalF(f)$.
To prove $(ii)$, we know by definition of $mathcalF$ that $mathcalF(g)(0)downarrow=1$ for any partial function $g$. In particular, we have $$mathcalF(f)(0)downarrow=1.$$ But since $f$ is a fixed point for $mathcalF$ we can turn this into $$f(0)downarrow=1.$$
To prove $(i)$, we've just shown that $f(0)$ is defined. Now suppose $f(n)$ is defined. By definition of $mathcalF$, we know $mathcalF(f)(n+1)$ is defined (namely, it's $(n+1)f(n)$). But again since $f$ is a fixed point of $mathcalF$, this tells us that $f(n+1)$ is defined. So by induction, $f$ is total.
answered 1 hour ago
Noah Schweber
114k9143268
is taking in a....seems you missed out a part of your sentence.
– Pinocchio
1 hour ago
my previous comment is important because I am failing to understand how continuity holds. $mathcal F$ maps partial functions $g(n)$ to either the partial constant function 1, or $n*g(n-1)$ or undefined. So $mathcal F$ itself is a partial function because it maps partial functions to undefined? I'm really confused...
– Pinocchio
1 hour ago
@Pinocchio Good catch, I've fixed that bit. Re: your second comment: no, $mathcalF$ is total as an operator on partial functions: it takes in partial functions and outputs partial functions. Saying that $mathcalF$ is total is to say that $mathcalF(g)$ is always a well-defined partial function whenever $g$ is a partial function, not that $mathcalF(g)$ is always a total function whenever $g$ is a partial function. (Unfortunately the phrase "$mathcalF(g)$ is always defined" may indeed suggest the latter!)
– Noah Schweber
1 hour ago
sorry to be a complainer but it makes it harder to read, usually $bot$ i.e. bottom means undefined. So seeing arrows going up instead of down for undefined is confusing me. I'm trying to parse your answer. I still don't get it :(
– Pinocchio
1 hour ago
Why is $mathcal F$ continuous?
– Pinocchio
1 hour ago
 |Â
show 4 more comments
up vote
3
down vote
Why is the fixed point theorem actually important here?
Well, let's think about why we believe that there is a function $f$ satisfying [recursive description of $!$]. It comes down to the following two (quite correct) beliefs:
We can use the recursive description of $!$ to "deduce" what the value of $!$ should be on each specific natural number.
We cannot use the recursive description of $!$ to deduce two contradictory things about $!$ (e.g. we can't use it to prove that $2!$ should be $7$).
With both claims in hand, we can then define $!$ by saying "$n!$ is the unique $m$ such that "$n!=m$" is implied by the recursive description." (In fact, only the second claim is needed to justify the existence of $!$ as a partial function.) But these claims need to be justified, and while in the case of the factorial function they are pretty obvious, $(i)$ the second claim is actually not as trivial to prove as one might hope and $(ii)$ certainly in general we want a theorem that lets us handle problems like these.
The fixed point theorem is basically a machine for getting around this issue: given a recursive description of a function, the fixed point theorem can (often) construct functions which actually satisfy that description in a precise, controlled way.
How we use it here (part $1$)
We can pass from the recursive description of the factorial function to a (perfectly good) definition of an operator on (partial) functions. The fixed point theorem shows that there is a fixed point, $f$, for this operator (once we've shown that this operator is in fact continuous); we then argue by induction that in fact this $f$ actually is the factorial function.
In detail:
From our self-referential "definition" of the factorial function, we can extract a perfectly good non-self-referential definition of an operator on partial functions $mathcalF$: given a partial function $g:mathbbNrightarrowmathbbN$, $mathcalF(g)$ is the partial function given by
$$
mathcalF(g):nmapsto
left{
beginarrayll
1 & mboxif n = 0 \
n * g(n-1) & mboxif n > 0mbox and g(n-1)downarrow\
uparrow & mboxif $n>0$ and $g(n-1)uparrow$
endarray
right.
$$
where "$uparrow$" means "is undefined" and "$downarrow$" means "is defined." (Note that I've written "$mathcalF(g):nmapsto...$" instead of "$mathcalF(g)(n)=...$" for clarity, but there's no actual difference.) Intuitively, think of $mathcalF$ as taking in a "partial computation" of $!$ - say, the first seventeen bits of the factorial function - and "going a bit further." The function we want is the "limit" of this process. This is exactly what the fixed point theorem says exists.
A quick example
Suppose $g$ is the partial function which sends $3$ to $7$, sends $10$ to $2$, sends $11$ to $11$, and is otherwise undefined. Then what partial function should $mathcalF(g)$ be?
In no particular order:
$mathcalF(g)$ is certainly defined at $0$: by definition of $mathcalF$, we'll always have $mathcalF(g):0mapsto 1$ regardless of what $g$ is.
On the other hand, since $g(0)$ isn't defined, we know that $mathcalF(g)(1)$ isn't defined.
What about $11$? Well, $11>0$ and $g(11-1)$ is defined, so the second clause of the definition of $mathcalF$ tells us that $$mathcalF(g)(11)=11cdot g(11-1)=11cdot g(10)=11cdot 2=22.$$ So $mathcalF(g)(11)downarrow =2$.
Exercise: Convince yourself that in fact the domain of $mathcalF(g)$ is precisely $0,4,11,12$ and calculate the values of $mathcalF(g)(4)$ and $mathcalF(g)(12)$.
How we use it here (part $2$)
Having defined our operator $mathcalF$, we now need to use it somehow.
Claim $1$: $mathcalF$ is continuous.
The text you've quoted doesn't actually prove this, but it's not hard to check. If this is an issue, though, let me know and I'll add details.
With the continuity of $mathcalF$ in hand, we can now invoke the fixed point theorem to get a function $f$ such that $$mathcalF(f)=f.$$ In fact, the fixed point theorem gives us a least fixed point of $mathcalF$, but we don't even need that in the current situation. We now show:
Claim $2$: This $f$ is in fact the factorial function. That is, we have $(i)$ $f$ is defined on all of $mathbbN$, $(ii)$ $f(0)=1$, and $(iii)$ $f(n+1)=(n+1)f(n)$.
Parts $(i)$ and $(iii)$ are proved by induction: get a contradiction from looking at the putative first $n$ on which $f$ is undefined, and the putative first $n$ on which $f(n+1)not=(n+1)f(n)$, respectively. Part $(ii)$ doesn't require any induction, and is just a quick observation.
Specifically, here's how we prove $(i)$ and $(ii)$ (I'll leave $(iii)$ as an exercise). The key point is that the equality $$mathcalF(f)=f$$ (this is what it means for $f$ to be a fixed point of $mathcalF$) lets us prove things about $f$ by proving them about $mathcalF(f)$.
To prove $(ii)$, we know by definition of $mathcalF$ that $mathcalF(g)(0)downarrow=1$ for any partial function $g$. In particular, we have $$mathcalF(f)(0)downarrow=1.$$ But since $f$ is a fixed point for $mathcalF$ we can turn this into $$f(0)downarrow=1.$$
To prove $(i)$, we've just shown that $f(0)$ is defined. Now suppose $f(n)$ is defined. By definition of $mathcalF$, we know $mathcalF(f)(n+1)$ is defined (namely, it's $(n+1)f(n)$). But again since $f$ is a fixed point of $mathcalF$, this tells us that $f(n+1)$ is defined. So by induction, $f$ is total.
answered 1 hour ago
Noah Schweber
114k9143268
is taking in a....seems you missed out a part of your sentence.
– Pinocchio
1 hour ago
my previous comment is important because I am failing to understand how continuity holds. $mathcal F$ maps partial functions $g(n)$ to either the partial constant function 1, or $n*g(n-1)$ or undefined. So $mathcal F$ itself is a partial function because it maps partial functions to undefined? I'm really confused...
– Pinocchio
1 hour ago
@Pinocchio Good catch, I've fixed that bit. Re: your second comment: no, $mathcalF$ is total as an operator on partial functions: it takes in partial functions and outputs partial functions. Saying that $mathcalF$ is total is to say that $mathcalF(g)$ is always a well-defined partial function whenever $g$ is a partial function, not that $mathcalF(g)$ is always a total function whenever $g$ is a partial function. (Unfortunately the phrase "$mathcalF(g)$ is always defined" may indeed suggest the latter!)
– Noah Schweber
1 hour ago
sorry to be a complainer but it makes it harder to read, usually $bot$ i.e. bottom means undefined. So seeing arrows going up instead of down for undefined is confusing me. I'm trying to parse your answer. I still don't get it :(
– Pinocchio
1 hour ago
Why is $mathcal F$ continuous?
– Pinocchio
1 hour ago
 |Â
show 4 more comments
up vote
3
down vote
up vote
3
down vote
Why is the fixed point theorem actually important here?
Well, let's think about why we believe that there is a function $f$ satisfying [recursive description of $!$]. It comes down to the following two (quite correct) beliefs:
We can use the recursive description of $!$ to "deduce" what the value of $!$ should be on each specific natural number.
We cannot use the recursive description of $!$ to deduce two contradictory things about $!$ (e.g. we can't use it to prove that $2!$ should be $7$).
With both claims in hand, we can then define $!$ by saying "$n!$ is the unique $m$ such that "$n!=m$" is implied by the recursive description." (In fact, only the second claim is needed to justify the existence of $!$ as a partial function.) But these claims need to be justified, and while in the case of the factorial function they are pretty obvious, $(i)$ the second claim is actually not as trivial to prove as one might hope and $(ii)$ certainly in general we want a theorem that lets us handle problems like these.
The fixed point theorem is basically a machine for getting around this issue: given a recursive description of a function, the fixed point theorem can (often) construct functions which actually satisfy that description in a precise, controlled way.
How we use it here (part $1$)
We can pass from the recursive description of the factorial function to a (perfectly good) definition of an operator on (partial) functions. The fixed point theorem shows that there is a fixed point, $f$, for this operator (once we've shown that this operator is in fact continuous); we then argue by induction that in fact this $f$ actually is the factorial function.
In detail:
From our self-referential "definition" of the factorial function, we can extract a perfectly good non-self-referential definition of an operator on partial functions $mathcalF$: given a partial function $g:mathbbNrightarrowmathbbN$, $mathcalF(g)$ is the partial function given by
$$
mathcalF(g):nmapsto
left{
beginarrayll
1 & mboxif n = 0 \
n * g(n-1) & mboxif n > 0mbox and g(n-1)downarrow\
uparrow & mboxif $n>0$ and $g(n-1)uparrow$
endarray
right.
$$
where "$uparrow$" means "is undefined" and "$downarrow$" means "is defined." (Note that I've written "$mathcalF(g):nmapsto...$" instead of "$mathcalF(g)(n)=...$" for clarity, but there's no actual difference.) Intuitively, think of $mathcalF$ as taking in a "partial computation" of $!$ - say, the first seventeen bits of the factorial function - and "going a bit further." The function we want is the "limit" of this process. This is exactly what the fixed point theorem says exists.
A quick example
Suppose $g$ is the partial function which sends $3$ to $7$, sends $10$ to $2$, sends $11$ to $11$, and is otherwise undefined. Then what partial function should $mathcalF(g)$ be?
In no particular order:
$mathcalF(g)$ is certainly defined at $0$: by definition of $mathcalF$, we'll always have $mathcalF(g):0mapsto 1$ regardless of what $g$ is.
On the other hand, since $g(0)$ isn't defined, we know that $mathcalF(g)(1)$ isn't defined.
What about $11$? Well, $11>0$ and $g(11-1)$ is defined, so the second clause of the definition of $mathcalF$ tells us that $$mathcalF(g)(11)=11cdot g(11-1)=11cdot g(10)=11cdot 2=22.$$ So $mathcalF(g)(11)downarrow =2$.
Exercise: Convince yourself that in fact the domain of $mathcalF(g)$ is precisely $0,4,11,12$ and calculate the values of $mathcalF(g)(4)$ and $mathcalF(g)(12)$.
How we use it here (part $2$)
Having defined our operator $mathcalF$, we now need to use it somehow.
Claim $1$: $mathcalF$ is continuous.
The text you've quoted doesn't actually prove this, but it's not hard to check. If this is an issue, though, let me know and I'll add details.
With the continuity of $mathcalF$ in hand, we can now invoke the fixed point theorem to get a function $f$ such that $$mathcalF(f)=f.$$ In fact, the fixed point theorem gives us a least fixed point of $mathcalF$, but we don't even need that in the current situation. We now show:
Claim $2$: This $f$ is in fact the factorial function. That is, we have $(i)$ $f$ is defined on all of $mathbbN$, $(ii)$ $f(0)=1$, and $(iii)$ $f(n+1)=(n+1)f(n)$.
Parts $(i)$ and $(iii)$ are proved by induction: get a contradiction from looking at the putative first $n$ on which $f$ is undefined, and the putative first $n$ on which $f(n+1)not=(n+1)f(n)$, respectively. Part $(ii)$ doesn't require any induction, and is just a quick observation.
Specifically, here's how we prove $(i)$ and $(ii)$ (I'll leave $(iii)$ as an exercise). The key point is that the equality $$mathcalF(f)=f$$ (this is what it means for $f$ to be a fixed point of $mathcalF$) lets us prove things about $f$ by proving them about $mathcalF(f)$.
To prove $(ii)$, we know by definition of $mathcalF$ that $mathcalF(g)(0)downarrow=1$ for any partial function $g$. In particular, we have $$mathcalF(f)(0)downarrow=1.$$ But since $f$ is a fixed point for $mathcalF$ we can turn this into $$f(0)downarrow=1.$$
To prove $(i)$, we've just shown that $f(0)$ is defined. Now suppose $f(n)$ is defined. By definition of $mathcalF$, we know $mathcalF(f)(n+1)$ is defined (namely, it's $(n+1)f(n)$). But again since $f$ is a fixed point of $mathcalF$, this tells us that $f(n+1)$ is defined. So by induction, $f$ is total.
answered 1 hour ago
Noah Schweber
114k9143268
Why is the fixed point theorem actually important here?
Well, let's think about why we believe that there is a function $f$ satisfying [recursive description of $!$]. It comes down to the following two (quite correct) beliefs:
We can use the recursive description of $!$ to "deduce" what the value of $!$ should be on each specific natural number.
We cannot use the recursive description of $!$ to deduce two contradictory things about $!$ (e.g. we can't use it to prove that $2!$ should be $7$).
With both claims in hand, we can then define $!$ by saying "$n!$ is the unique $m$ such that "$n!=m$" is implied by the recursive description." (In fact, only the second claim is needed to justify the existence of $!$ as a partial function.) But these claims need to be justified, and while in the case of the factorial function they are pretty obvious, $(i)$ the second claim is actually not as trivial to prove as one might hope and $(ii)$ certainly in general we want a theorem that lets us handle problems like these.
The fixed point theorem is basically a machine for getting around this issue: given a recursive description of a function, the fixed point theorem can (often) construct functions which actually satisfy that description in a precise, controlled way.
How we use it here (part $1$)
We can pass from the recursive description of the factorial function to a (perfectly good) definition of an operator on (partial) functions. The fixed point theorem shows that there is a fixed point, $f$, for this operator (once we've shown that this operator is in fact continuous); we then argue by induction that in fact this $f$ actually is the factorial function.
In detail:
From our self-referential "definition" of the factorial function, we can extract a perfectly good non-self-referential definition of an operator on partial functions $mathcalF$: given a partial function $g:mathbbNrightarrowmathbbN$, $mathcalF(g)$ is the partial function given by
$$
mathcalF(g):nmapsto
left{
beginarrayll
1 & mboxif n = 0 \
n * g(n-1) & mboxif n > 0mbox and g(n-1)downarrow\
uparrow & mboxif $n>0$ and $g(n-1)uparrow$
endarray
right.
$$
where "$uparrow$" means "is undefined" and "$downarrow$" means "is defined." (Note that I've written "$mathcalF(g):nmapsto...$" instead of "$mathcalF(g)(n)=...$" for clarity, but there's no actual difference.) Intuitively, think of $mathcalF$ as taking in a "partial computation" of $!$ - say, the first seventeen bits of the factorial function - and "going a bit further." The function we want is the "limit" of this process. This is exactly what the fixed point theorem says exists.
A quick example
Suppose $g$ is the partial function which sends $3$ to $7$, sends $10$ to $2$, sends $11$ to $11$, and is otherwise undefined. Then what partial function should $mathcalF(g)$ be?
In no particular order:
$mathcalF(g)$ is certainly defined at $0$: by definition of $mathcalF$, we'll always have $mathcalF(g):0mapsto 1$ regardless of what $g$ is.
On the other hand, since $g(0)$ isn't defined, we know that $mathcalF(g)(1)$ isn't defined.
What about $11$? Well, $11>0$ and $g(11-1)$ is defined, so the second clause of the definition of $mathcalF$ tells us that $$mathcalF(g)(11)=11cdot g(11-1)=11cdot g(10)=11cdot 2=22.$$ So $mathcalF(g)(11)downarrow =2$.
Exercise: Convince yourself that in fact the domain of $mathcalF(g)$ is precisely $0,4,11,12$ and calculate the values of $mathcalF(g)(4)$ and $mathcalF(g)(12)$.
How we use it here (part $2$)
Having defined our operator $mathcalF$, we now need to use it somehow.
Claim $1$: $mathcalF$ is continuous.
The text you've quoted doesn't actually prove this, but it's not hard to check. If this is an issue, though, let me know and I'll add details.
With the continuity of $mathcalF$ in hand, we can now invoke the fixed point theorem to get a function $f$ such that $$mathcalF(f)=f.$$ In fact, the fixed point theorem gives us a least fixed point of $mathcalF$, but we don't even need that in the current situation. We now show:
Claim $2$: This $f$ is in fact the factorial function. That is, we have $(i)$ $f$ is defined on all of $mathbbN$, $(ii)$ $f(0)=1$, and $(iii)$ $f(n+1)=(n+1)f(n)$.
Parts $(i)$ and $(iii)$ are proved by induction: get a contradiction from looking at the putative first $n$ on which $f$ is undefined, and the putative first $n$ on which $f(n+1)not=(n+1)f(n)$, respectively. Part $(ii)$ doesn't require any induction, and is just a quick observation.
Specifically, here's how we prove $(i)$ and $(ii)$ (I'll leave $(iii)$ as an exercise). The key point is that the equality $$mathcalF(f)=f$$ (this is what it means for $f$ to be a fixed point of $mathcalF$) lets us prove things about $f$ by proving them about $mathcalF(f)$.
To prove $(ii)$, we know by definition of $mathcalF$ that $mathcalF(g)(0)downarrow=1$ for any partial function $g$. In particular, we have $$mathcalF(f)(0)downarrow=1.$$ But since $f$ is a fixed point for $mathcalF$ we can turn this into $$f(0)downarrow=1.$$
To prove $(i)$, we've just shown that $f(0)$ is defined. Now suppose $f(n)$ is defined. By definition of $mathcalF$, we know $mathcalF(f)(n+1)$ is defined (namely, it's $(n+1)f(n)$). But again since $f$ is a fixed point of $mathcalF$, this tells us that $f(n+1)$ is defined. So by induction, $f$ is total.
answered 1 hour ago
Noah Schweber
114k9143268
edited 1 hour ago
answered 1 hour ago
Noah Schweber
114k9143268
answered 1 hour ago
Noah Schweber
114k9143268
answered 1 hour ago
Noah Schweber
114k9143268
114k9143268
is taking in a....seems you missed out a part of your sentence.
– Pinocchio
1 hour ago
my previous comment is important because I am failing to understand how continuity holds. $mathcal F$ maps partial functions $g(n)$ to either the partial constant function 1, or $n*g(n-1)$ or undefined. So $mathcal F$ itself is a partial function because it maps partial functions to undefined? I'm really confused...
– Pinocchio
1 hour ago
@Pinocchio Good catch, I've fixed that bit. Re: your second comment: no, $mathcalF$ is total as an operator on partial functions: it takes in partial functions and outputs partial functions. Saying that $mathcalF$ is total is to say that $mathcalF(g)$ is always a well-defined partial function whenever $g$ is a partial function, not that $mathcalF(g)$ is always a total function whenever $g$ is a partial function. (Unfortunately the phrase "$mathcalF(g)$ is always defined" may indeed suggest the latter!)
– Noah Schweber
1 hour ago
sorry to be a complainer but it makes it harder to read, usually $bot$ i.e. bottom means undefined. So seeing arrows going up instead of down for undefined is confusing me. I'm trying to parse your answer. I still don't get it :(
– Pinocchio
1 hour ago
Why is $mathcal F$ continuous?
– Pinocchio
1 hour ago
 |Â
show 4 more comments
is taking in a....seems you missed out a part of your sentence.
– Pinocchio
1 hour ago
my previous comment is important because I am failing to understand how continuity holds. $mathcal F$ maps partial functions $g(n)$ to either the partial constant function 1, or $n*g(n-1)$ or undefined. So $mathcal F$ itself is a partial function because it maps partial functions to undefined? I'm really confused...
– Pinocchio
1 hour ago
@Pinocchio Good catch, I've fixed that bit. Re: your second comment: no, $mathcalF$ is total as an operator on partial functions: it takes in partial functions and outputs partial functions. Saying that $mathcalF$ is total is to say that $mathcalF(g)$ is always a well-defined partial function whenever $g$ is a partial function, not that $mathcalF(g)$ is always a total function whenever $g$ is a partial function. (Unfortunately the phrase "$mathcalF(g)$ is always defined" may indeed suggest the latter!)
– Noah Schweber
1 hour ago
sorry to be a complainer but it makes it harder to read, usually $bot$ i.e. bottom means undefined. So seeing arrows going up instead of down for undefined is confusing me. I'm trying to parse your answer. I still don't get it :(
– Pinocchio
1 hour ago
Why is $mathcal F$ continuous?
– Pinocchio
1 hour ago
is taking in a....seems you missed out a part of your sentence.
– Pinocchio
1 hour ago
is taking in a....seems you missed out a part of your sentence.
– Pinocchio
1 hour ago
my previous comment is important because I am failing to understand how continuity holds. $mathcal F$ maps partial functions $g(n)$ to either the partial constant function 1, or $n*g(n-1)$ or undefined. So $mathcal F$ itself is a partial function because it maps partial functions to undefined? I'm really confused...
– Pinocchio
1 hour ago
my previous comment is important because I am failing to understand how continuity holds. $mathcal F$ maps partial functions $g(n)$ to either the partial constant function 1, or $n*g(n-1)$ or undefined. So $mathcal F$ itself is a partial function because it maps partial functions to undefined? I'm really confused...
– Pinocchio
1 hour ago
@Pinocchio Good catch, I've fixed that bit. Re: your second comment: no, $mathcalF$ is total as an operator on partial functions: it takes in partial functions and outputs partial functions. Saying that $mathcalF$ is total is to say that $mathcalF(g)$ is always a well-defined partial function whenever $g$ is a partial function, not that $mathcalF(g)$ is always a total function whenever $g$ is a partial function. (Unfortunately the phrase "$mathcalF(g)$ is always defined" may indeed suggest the latter!)
– Noah Schweber
1 hour ago
@Pinocchio Good catch, I've fixed that bit. Re: your second comment: no, $mathcalF$ is total as an operator on partial functions: it takes in partial functions and outputs partial functions. Saying that $mathcalF$ is total is to say that $mathcalF(g)$ is always a well-defined partial function whenever $g$ is a partial function, not that $mathcalF(g)$ is always a total function whenever $g$ is a partial function. (Unfortunately the phrase "$mathcalF(g)$ is always defined" may indeed suggest the latter!)
– Noah Schweber
1 hour ago
sorry to be a complainer but it makes it harder to read, usually $bot$ i.e. bottom means undefined. So seeing arrows going up instead of down for undefined is confusing me. I'm trying to parse your answer. I still don't get it :(
– Pinocchio
1 hour ago
sorry to be a complainer but it makes it harder to read, usually $bot$ i.e. bottom means undefined. So seeing arrows going up instead of down for undefined is confusing me. I'm trying to parse your answer. I still don't get it :(
– Pinocchio
1 hour ago
Why is $mathcal F$ continuous?
– Pinocchio
1 hour ago
Why is $mathcal F$ continuous?
– Pinocchio
1 hour ago
 |Â
show 4 more comments
up vote
2
down vote
As the function $f$ is defined in terms of itself, you have a priori no guarantee that it is defined at all or uniquely defined.
Now the function $mathcal F$ is such that it extends the known values of $f(n)$ (from a given subset of naturals) by applying the definition.
Then the fixed-point theorem guarantees that $mathcal F$ has a fixed-point, which corresponds to $f$ defined over the whole of $mathbb N$. Uniqueness of the fixed-point guarantees that $f$ is uniquely defined.
answered 1 hour ago
Yves Daoust
116k667211
I'm failing to appreciate what the role of $mathcal F$ is. $mathcal F(g(n))$ is equal to the definition of factorial function plus a condition of undefined when the funciton is undefined. Conceptually $mathcal F$ is just the same as $g(n)$. So I don't see what role its suppose to be playing.
– Pinocchio
1 hour ago
like we could have done induction on the original definition of $f(n)$ that didn't refer to any fixed points to show it was defined everywhere...what did $mathcal F $ contribute?
– Pinocchio
1 hour ago
add a comment |Â
up vote
2
down vote
As the function $f$ is defined in terms of itself, you have a priori no guarantee that it is defined at all or uniquely defined.
Now the function $mathcal F$ is such that it extends the known values of $f(n)$ (from a given subset of naturals) by applying the definition.
Then the fixed-point theorem guarantees that $mathcal F$ has a fixed-point, which corresponds to $f$ defined over the whole of $mathbb N$. Uniqueness of the fixed-point guarantees that $f$ is uniquely defined.
answered 1 hour ago
Yves Daoust
116k667211
I'm failing to appreciate what the role of $mathcal F$ is. $mathcal F(g(n))$ is equal to the definition of factorial function plus a condition of undefined when the funciton is undefined. Conceptually $mathcal F$ is just the same as $g(n)$. So I don't see what role its suppose to be playing.
– Pinocchio
1 hour ago
like we could have done induction on the original definition of $f(n)$ that didn't refer to any fixed points to show it was defined everywhere...what did $mathcal F $ contribute?
– Pinocchio
1 hour ago
add a comment |Â
up vote
2
down vote
up vote
2
down vote
As the function $f$ is defined in terms of itself, you have a priori no guarantee that it is defined at all or uniquely defined.
Now the function $mathcal F$ is such that it extends the known values of $f(n)$ (from a given subset of naturals) by applying the definition.
Then the fixed-point theorem guarantees that $mathcal F$ has a fixed-point, which corresponds to $f$ defined over the whole of $mathbb N$. Uniqueness of the fixed-point guarantees that $f$ is uniquely defined.
answered 1 hour ago
Yves Daoust
116k667211
As the function $f$ is defined in terms of itself, you have a priori no guarantee that it is defined at all or uniquely defined.
Now the function $mathcal F$ is such that it extends the known values of $f(n)$ (from a given subset of naturals) by applying the definition.
Then the fixed-point theorem guarantees that $mathcal F$ has a fixed-point, which corresponds to $f$ defined over the whole of $mathbb N$. Uniqueness of the fixed-point guarantees that $f$ is uniquely defined.
answered 1 hour ago
Yves Daoust
116k667211
answered 1 hour ago
Yves Daoust
116k667211
answered 1 hour ago
Yves Daoust
116k667211
answered 1 hour ago
Yves Daoust
116k667211
116k667211
I'm failing to appreciate what the role of $mathcal F$ is. $mathcal F(g(n))$ is equal to the definition of factorial function plus a condition of undefined when the funciton is undefined. Conceptually $mathcal F$ is just the same as $g(n)$. So I don't see what role its suppose to be playing.
– Pinocchio
1 hour ago
like we could have done induction on the original definition of $f(n)$ that didn't refer to any fixed points to show it was defined everywhere...what did $mathcal F $ contribute?
– Pinocchio
1 hour ago
add a comment |Â
I'm failing to appreciate what the role of $mathcal F$ is. $mathcal F(g(n))$ is equal to the definition of factorial function plus a condition of undefined when the funciton is undefined. Conceptually $mathcal F$ is just the same as $g(n)$. So I don't see what role its suppose to be playing.
– Pinocchio
1 hour ago
like we could have done induction on the original definition of $f(n)$ that didn't refer to any fixed points to show it was defined everywhere...what did $mathcal F $ contribute?
– Pinocchio
1 hour ago
I'm failing to appreciate what the role of $mathcal F$ is. $mathcal F(g(n))$ is equal to the definition of factorial function plus a condition of undefined when the funciton is undefined. Conceptually $mathcal F$ is just the same as $g(n)$. So I don't see what role its suppose to be playing.
– Pinocchio
1 hour ago
I'm failing to appreciate what the role of $mathcal F$ is. $mathcal F(g(n))$ is equal to the definition of factorial function plus a condition of undefined when the funciton is undefined. Conceptually $mathcal F$ is just the same as $g(n)$. So I don't see what role its suppose to be playing.
– Pinocchio
1 hour ago
like we could have done induction on the original definition of $f(n)$ that didn't refer to any fixed points to show it was defined everywhere...what did $mathcal F $ contribute?
– Pinocchio
1 hour ago
like we could have done induction on the original definition of $f(n)$ that didn't refer to any fixed points to show it was defined everywhere...what did $mathcal F $ contribute?
– Pinocchio
1 hour ago
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2941370%2fwhy-does-the-fixed-point-theorem-justify-the-existence-of-the-factorial-function%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
I would check out the well-ordering principle. This is very much related to this
– Rushabh Mehta
2 hours ago
What page is it on?
– Ovi
2 hours ago
@Ovi page 89 of the notes fsl.cs.illinois.edu/images/c/ca/…
– Pinocchio
2 hours ago
@RushabhMehta non empty sets of positive integers have least elements (I assume generalizes to well ordered sets that are countable and non empty have a least element or something of that sort). Now what? I fail to see the relation, my apology.
– Pinocchio
2 hours ago
@N.Bach I still don't get it. I could have proved the original $f(n)$ that didn't refer to fixed points existed everywhere in $mathbb N$ without referring to fixed points. What did introducing the concept of fixed points actually do?
– Pinocchio
1 hour ago