Mixing
Question about the proof of the Recursion Theorem
$begingroup$
I have been studying the book, Introduction to Set Theory written by Hrbacek and Jech.
In this book the Recursion Theorem is stated as follows:
For any set $A$, any $ain A$, and any function $g: A times mathbb{N} rightarrow A$, there exists a unique infinite sequence $f: mathbb{N} rightarrow A$ such that
(a)$f_0=a$;
(b)$f_{n+1} = g(f_n , n)$ for all $nin mathbb{N}$.
Then the proof begins with defining $m$-step computation.
A function $t:(m+1) rightarrow A$ is called an $m$-step computation based on $a$ and $g$ if $t_0 =a$, and, for all $k$ such that $0 leq k < m$,
$t_{k+1} = g(t_k, k)$.
And then, by using $m$-step computations, $f$ is defined, and the proof proceeds.
It is my question. Is $m$-step computation $t$ really a function?
I think $t$ is also defined recursively.
It means that the way to define either $f$ or $t$ is really similar.
Thus I have got some confusion,
"Why isn't $f$ directly a function, and is $t$ (obviously) a function?"
Please help me.
set-theory proof-explanation
asked Jan 7 at 11:18
Doyun NamDoyun Nam
41819
$endgroup$
add a comment |
$begingroup$
I have been studying the book, Introduction to Set Theory written by Hrbacek and Jech.
In this book the Recursion Theorem is stated as follows:
For any set $A$, any $ain A$, and any function $g: A times mathbb{N} rightarrow A$, there exists a unique infinite sequence $f: mathbb{N} rightarrow A$ such that
(a)$f_0=a$;
(b)$f_{n+1} = g(f_n , n)$ for all $nin mathbb{N}$.
Then the proof begins with defining $m$-step computation.
A function $t:(m+1) rightarrow A$ is called an $m$-step computation based on $a$ and $g$ if $t_0 =a$, and, for all $k$ such that $0 leq k < m$,
$t_{k+1} = g(t_k, k)$.
And then, by using $m$-step computations, $f$ is defined, and the proof proceeds.
It is my question. Is $m$-step computation $t$ really a function?
I think $t$ is also defined recursively.
It means that the way to define either $f$ or $t$ is really similar.
Thus I have got some confusion,
"Why isn't $f$ directly a function, and is $t$ (obviously) a function?"
Please help me.
set-theory proof-explanation
asked Jan 7 at 11:18
Doyun NamDoyun Nam
41819
$endgroup$
2
$begingroup$
By definition, $t$ is obviously a function. The point of the result is not that $f$ is a function. The point is that it exists
$endgroup$
– Andrés E. Caicedo
Jan 7 at 16:10
add a comment |
$begingroup$
I have been studying the book, Introduction to Set Theory written by Hrbacek and Jech.
In this book the Recursion Theorem is stated as follows:
For any set $A$, any $ain A$, and any function $g: A times mathbb{N} rightarrow A$, there exists a unique infinite sequence $f: mathbb{N} rightarrow A$ such that
(a)$f_0=a$;
(b)$f_{n+1} = g(f_n , n)$ for all $nin mathbb{N}$.
Then the proof begins with defining $m$-step computation.
A function $t:(m+1) rightarrow A$ is called an $m$-step computation based on $a$ and $g$ if $t_0 =a$, and, for all $k$ such that $0 leq k < m$,
$t_{k+1} = g(t_k, k)$.
And then, by using $m$-step computations, $f$ is defined, and the proof proceeds.
It is my question. Is $m$-step computation $t$ really a function?
I think $t$ is also defined recursively.
It means that the way to define either $f$ or $t$ is really similar.
Thus I have got some confusion,
"Why isn't $f$ directly a function, and is $t$ (obviously) a function?"
Please help me.
set-theory proof-explanation
asked Jan 7 at 11:18
Doyun NamDoyun Nam
41819
$endgroup$
I have been studying the book, Introduction to Set Theory written by Hrbacek and Jech.
In this book the Recursion Theorem is stated as follows:
For any set $A$, any $ain A$, and any function $g: A times mathbb{N} rightarrow A$, there exists a unique infinite sequence $f: mathbb{N} rightarrow A$ such that
(a)$f_0=a$;
(b)$f_{n+1} = g(f_n , n)$ for all $nin mathbb{N}$.
Then the proof begins with defining $m$-step computation.
A function $t:(m+1) rightarrow A$ is called an $m$-step computation based on $a$ and $g$ if $t_0 =a$, and, for all $k$ such that $0 leq k < m$,
$t_{k+1} = g(t_k, k)$.
And then, by using $m$-step computations, $f$ is defined, and the proof proceeds.
It is my question. Is $m$-step computation $t$ really a function?
I think $t$ is also defined recursively.
It means that the way to define either $f$ or $t$ is really similar.
Thus I have got some confusion,
"Why isn't $f$ directly a function, and is $t$ (obviously) a function?"
Please help me.
set-theory proof-explanation
set-theory proof-explanation
asked Jan 7 at 11:18
Doyun NamDoyun Nam
41819
asked Jan 7 at 11:18
Doyun NamDoyun Nam
41819
asked Jan 7 at 11:18
Doyun NamDoyun Nam
41819
asked Jan 7 at 11:18
Doyun NamDoyun Nam
41819
asked Jan 7 at 11:18
Doyun NamDoyun Nam
41819
41819
2
$begingroup$
By definition, $t$ is obviously a function. The point of the result is not that $f$ is a function. The point is that it exists
$endgroup$
– Andrés E. Caicedo
Jan 7 at 16:10
add a comment |
2
$begingroup$
By definition, $t$ is obviously a function. The point of the result is not that $f$ is a function. The point is that it exists
$endgroup$
– Andrés E. Caicedo
Jan 7 at 16:10
2
2
$begingroup$
By definition, $t$ is obviously a function. The point of the result is not that $f$ is a function. The point is that it exists
$endgroup$
– Andrés E. Caicedo
Jan 7 at 16:10
$begingroup$
By definition, $t$ is obviously a function. The point of the result is not that $f$ is a function. The point is that it exists
$endgroup$
– Andrés E. Caicedo
Jan 7 at 16:10
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Recall a set $f$ is a function if it is a set of ordered pairs that has the property that if $langle m,nrangle$ and $langle m,n'rangle$ are in $f,$ then $n=n'.$
So, a priori, (a) and (b) do not constitute the definition of a function since they do not directly specify some set with the above property. Instead, (a) and (b) are merely some properties a function might have. The point of this theorem is to show that there is a unique function with these two properties. Once we have done so, then we may say henceforth that (a) and (b) define a function.
(Part of the confusion here is that it is fairly obvious from our intuition for recursion that such a function exists and is unique. The point of this theorem is to turn this intuition into a formal ZF proof. Then once we've done so, we know ZF is powerful enough to prove what we knew all along about recursion, and we can feel free to appeal to the principle.)
An $m$-step computation is defined to be a function with certain properties. Thus an $m$-step computation is a function by definition. What requires proof is the fact that for any $m,$ there is exactly one unique $m$-step computation. This can be proved by induction: There is exactly one $0$-step computation, ${langle 0, arangle},$ and if there is exactly one $m$-step computation $t^m,$ then there is exactly one $m+1$-step computation $t^{m+1}=t^mcup{langle m+1, g(t^m(m), m)rangle}.$ Again, it is important to emphasize we are not “defining functions by recursion” here. We are proving a sequence of functions with certain properties exists by induction.
Finally, we define $f = {langle m, t^m(m)rangle :minmathbb N},$ where $t^m$ is the unique $m$-step computation. Then, we can prove that $f$ is a function with properties (a) and (b). That a function satisfying (a) and (b) must be unique can be proven by induction.
answered Jan 8 at 3:19
spaceisdarkgreenspaceisdarkgreen
32.8k21753
$endgroup$
$begingroup$
Thank you. I understand your explanation. However, I also have some questions. I think that the existence of a function $f$ satisfying (a) and (b) is proved by induction, using the similar way that you define $t^{m+1}$. And then, the uniqueness is also proved by induction as you said. Then, why is $m$-step computation needed? Is my opinion that the existence of $f$ is proved by induction false?
$endgroup$
– Doyun Nam
Jan 9 at 11:28
1
$begingroup$
@DoyunNam The whole point of the $m$-step computations is to “prove the existence of $f$ by induction.” How do you propose to do it without? Here’s what is probably your error: you say “we’re going to prove the existence of $f$,” but what is $f$? Have you defined it?
$endgroup$
– spaceisdarkgreen
Jan 9 at 15:24
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3064890%2fquestion-about-the-proof-of-the-recursion-theorem%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Recall a set $f$ is a function if it is a set of ordered pairs that has the property that if $langle m,nrangle$ and $langle m,n'rangle$ are in $f,$ then $n=n'.$
So, a priori, (a) and (b) do not constitute the definition of a function since they do not directly specify some set with the above property. Instead, (a) and (b) are merely some properties a function might have. The point of this theorem is to show that there is a unique function with these two properties. Once we have done so, then we may say henceforth that (a) and (b) define a function.
(Part of the confusion here is that it is fairly obvious from our intuition for recursion that such a function exists and is unique. The point of this theorem is to turn this intuition into a formal ZF proof. Then once we've done so, we know ZF is powerful enough to prove what we knew all along about recursion, and we can feel free to appeal to the principle.)
An $m$-step computation is defined to be a function with certain properties. Thus an $m$-step computation is a function by definition. What requires proof is the fact that for any $m,$ there is exactly one unique $m$-step computation. This can be proved by induction: There is exactly one $0$-step computation, ${langle 0, arangle},$ and if there is exactly one $m$-step computation $t^m,$ then there is exactly one $m+1$-step computation $t^{m+1}=t^mcup{langle m+1, g(t^m(m), m)rangle}.$ Again, it is important to emphasize we are not “defining functions by recursion” here. We are proving a sequence of functions with certain properties exists by induction.
Finally, we define $f = {langle m, t^m(m)rangle :minmathbb N},$ where $t^m$ is the unique $m$-step computation. Then, we can prove that $f$ is a function with properties (a) and (b). That a function satisfying (a) and (b) must be unique can be proven by induction.
answered Jan 8 at 3:19
spaceisdarkgreenspaceisdarkgreen
32.8k21753
$endgroup$
$begingroup$
Thank you. I understand your explanation. However, I also have some questions. I think that the existence of a function $f$ satisfying (a) and (b) is proved by induction, using the similar way that you define $t^{m+1}$. And then, the uniqueness is also proved by induction as you said. Then, why is $m$-step computation needed? Is my opinion that the existence of $f$ is proved by induction false?
$endgroup$
– Doyun Nam
Jan 9 at 11:28
1
$begingroup$
@DoyunNam The whole point of the $m$-step computations is to “prove the existence of $f$ by induction.” How do you propose to do it without? Here’s what is probably your error: you say “we’re going to prove the existence of $f$,” but what is $f$? Have you defined it?
$endgroup$
– spaceisdarkgreen
Jan 9 at 15:24
add a comment |
$begingroup$
Recall a set $f$ is a function if it is a set of ordered pairs that has the property that if $langle m,nrangle$ and $langle m,n'rangle$ are in $f,$ then $n=n'.$
So, a priori, (a) and (b) do not constitute the definition of a function since they do not directly specify some set with the above property. Instead, (a) and (b) are merely some properties a function might have. The point of this theorem is to show that there is a unique function with these two properties. Once we have done so, then we may say henceforth that (a) and (b) define a function.
(Part of the confusion here is that it is fairly obvious from our intuition for recursion that such a function exists and is unique. The point of this theorem is to turn this intuition into a formal ZF proof. Then once we've done so, we know ZF is powerful enough to prove what we knew all along about recursion, and we can feel free to appeal to the principle.)
An $m$-step computation is defined to be a function with certain properties. Thus an $m$-step computation is a function by definition. What requires proof is the fact that for any $m,$ there is exactly one unique $m$-step computation. This can be proved by induction: There is exactly one $0$-step computation, ${langle 0, arangle},$ and if there is exactly one $m$-step computation $t^m,$ then there is exactly one $m+1$-step computation $t^{m+1}=t^mcup{langle m+1, g(t^m(m), m)rangle}.$ Again, it is important to emphasize we are not “defining functions by recursion” here. We are proving a sequence of functions with certain properties exists by induction.
Finally, we define $f = {langle m, t^m(m)rangle :minmathbb N},$ where $t^m$ is the unique $m$-step computation. Then, we can prove that $f$ is a function with properties (a) and (b). That a function satisfying (a) and (b) must be unique can be proven by induction.
answered Jan 8 at 3:19
spaceisdarkgreenspaceisdarkgreen
32.8k21753
$endgroup$
$begingroup$
Thank you. I understand your explanation. However, I also have some questions. I think that the existence of a function $f$ satisfying (a) and (b) is proved by induction, using the similar way that you define $t^{m+1}$. And then, the uniqueness is also proved by induction as you said. Then, why is $m$-step computation needed? Is my opinion that the existence of $f$ is proved by induction false?
$endgroup$
– Doyun Nam
Jan 9 at 11:28
1
$begingroup$
@DoyunNam The whole point of the $m$-step computations is to “prove the existence of $f$ by induction.” How do you propose to do it without? Here’s what is probably your error: you say “we’re going to prove the existence of $f$,” but what is $f$? Have you defined it?
$endgroup$
– spaceisdarkgreen
Jan 9 at 15:24
add a comment |
$begingroup$
Recall a set $f$ is a function if it is a set of ordered pairs that has the property that if $langle m,nrangle$ and $langle m,n'rangle$ are in $f,$ then $n=n'.$
So, a priori, (a) and (b) do not constitute the definition of a function since they do not directly specify some set with the above property. Instead, (a) and (b) are merely some properties a function might have. The point of this theorem is to show that there is a unique function with these two properties. Once we have done so, then we may say henceforth that (a) and (b) define a function.
(Part of the confusion here is that it is fairly obvious from our intuition for recursion that such a function exists and is unique. The point of this theorem is to turn this intuition into a formal ZF proof. Then once we've done so, we know ZF is powerful enough to prove what we knew all along about recursion, and we can feel free to appeal to the principle.)
An $m$-step computation is defined to be a function with certain properties. Thus an $m$-step computation is a function by definition. What requires proof is the fact that for any $m,$ there is exactly one unique $m$-step computation. This can be proved by induction: There is exactly one $0$-step computation, ${langle 0, arangle},$ and if there is exactly one $m$-step computation $t^m,$ then there is exactly one $m+1$-step computation $t^{m+1}=t^mcup{langle m+1, g(t^m(m), m)rangle}.$ Again, it is important to emphasize we are not “defining functions by recursion” here. We are proving a sequence of functions with certain properties exists by induction.
Finally, we define $f = {langle m, t^m(m)rangle :minmathbb N},$ where $t^m$ is the unique $m$-step computation. Then, we can prove that $f$ is a function with properties (a) and (b). That a function satisfying (a) and (b) must be unique can be proven by induction.
answered Jan 8 at 3:19
spaceisdarkgreenspaceisdarkgreen
32.8k21753
$endgroup$
Recall a set $f$ is a function if it is a set of ordered pairs that has the property that if $langle m,nrangle$ and $langle m,n'rangle$ are in $f,$ then $n=n'.$
So, a priori, (a) and (b) do not constitute the definition of a function since they do not directly specify some set with the above property. Instead, (a) and (b) are merely some properties a function might have. The point of this theorem is to show that there is a unique function with these two properties. Once we have done so, then we may say henceforth that (a) and (b) define a function.
(Part of the confusion here is that it is fairly obvious from our intuition for recursion that such a function exists and is unique. The point of this theorem is to turn this intuition into a formal ZF proof. Then once we've done so, we know ZF is powerful enough to prove what we knew all along about recursion, and we can feel free to appeal to the principle.)
An $m$-step computation is defined to be a function with certain properties. Thus an $m$-step computation is a function by definition. What requires proof is the fact that for any $m,$ there is exactly one unique $m$-step computation. This can be proved by induction: There is exactly one $0$-step computation, ${langle 0, arangle},$ and if there is exactly one $m$-step computation $t^m,$ then there is exactly one $m+1$-step computation $t^{m+1}=t^mcup{langle m+1, g(t^m(m), m)rangle}.$ Again, it is important to emphasize we are not “defining functions by recursion” here. We are proving a sequence of functions with certain properties exists by induction.
Finally, we define $f = {langle m, t^m(m)rangle :minmathbb N},$ where $t^m$ is the unique $m$-step computation. Then, we can prove that $f$ is a function with properties (a) and (b). That a function satisfying (a) and (b) must be unique can be proven by induction.
answered Jan 8 at 3:19
spaceisdarkgreenspaceisdarkgreen
32.8k21753
edited Jan 8 at 16:20
answered Jan 8 at 3:19
spaceisdarkgreenspaceisdarkgreen
32.8k21753
answered Jan 8 at 3:19
spaceisdarkgreenspaceisdarkgreen
32.8k21753
answered Jan 8 at 3:19
spaceisdarkgreenspaceisdarkgreen
32.8k21753
32.8k21753
$begingroup$
Thank you. I understand your explanation. However, I also have some questions. I think that the existence of a function $f$ satisfying (a) and (b) is proved by induction, using the similar way that you define $t^{m+1}$. And then, the uniqueness is also proved by induction as you said. Then, why is $m$-step computation needed? Is my opinion that the existence of $f$ is proved by induction false?
$endgroup$
– Doyun Nam
Jan 9 at 11:28
1
$begingroup$
@DoyunNam The whole point of the $m$-step computations is to “prove the existence of $f$ by induction.” How do you propose to do it without? Here’s what is probably your error: you say “we’re going to prove the existence of $f$,” but what is $f$? Have you defined it?
$endgroup$
– spaceisdarkgreen
Jan 9 at 15:24
add a comment |
$begingroup$
Thank you. I understand your explanation. However, I also have some questions. I think that the existence of a function $f$ satisfying (a) and (b) is proved by induction, using the similar way that you define $t^{m+1}$. And then, the uniqueness is also proved by induction as you said. Then, why is $m$-step computation needed? Is my opinion that the existence of $f$ is proved by induction false?
$endgroup$
– Doyun Nam
Jan 9 at 11:28
1
$begingroup$
@DoyunNam The whole point of the $m$-step computations is to “prove the existence of $f$ by induction.” How do you propose to do it without? Here’s what is probably your error: you say “we’re going to prove the existence of $f$,” but what is $f$? Have you defined it?
$endgroup$
– spaceisdarkgreen
Jan 9 at 15:24
$begingroup$
Thank you. I understand your explanation. However, I also have some questions. I think that the existence of a function $f$ satisfying (a) and (b) is proved by induction, using the similar way that you define $t^{m+1}$. And then, the uniqueness is also proved by induction as you said. Then, why is $m$-step computation needed? Is my opinion that the existence of $f$ is proved by induction false?
$endgroup$
– Doyun Nam
Jan 9 at 11:28
$begingroup$
Thank you. I understand your explanation. However, I also have some questions. I think that the existence of a function $f$ satisfying (a) and (b) is proved by induction, using the similar way that you define $t^{m+1}$. And then, the uniqueness is also proved by induction as you said. Then, why is $m$-step computation needed? Is my opinion that the existence of $f$ is proved by induction false?
$endgroup$
– Doyun Nam
Jan 9 at 11:28
1
1
$begingroup$
@DoyunNam The whole point of the $m$-step computations is to “prove the existence of $f$ by induction.” How do you propose to do it without? Here’s what is probably your error: you say “we’re going to prove the existence of $f$,” but what is $f$? Have you defined it?
$endgroup$
– spaceisdarkgreen
Jan 9 at 15:24
$begingroup$
@DoyunNam The whole point of the $m$-step computations is to “prove the existence of $f$ by induction.” How do you propose to do it without? Here’s what is probably your error: you say “we’re going to prove the existence of $f$,” but what is $f$? Have you defined it?
$endgroup$
– spaceisdarkgreen
Jan 9 at 15:24
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3064890%2fquestion-about-the-proof-of-the-recursion-theorem%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
$begingroup$
By definition, $t$ is obviously a function. The point of the result is not that $f$ is a function. The point is that it exists
$endgroup$
– Andrés E. Caicedo
Jan 7 at 16:10