Why is $F(a,b) = G(a,b, bar F (a,b) )$ unique if $bar F (a,b)$ is a sequence number applied to each element...
I was reading these notes and on page 88 (of the paper version) it said:
however it wasn't clear to me why the function would be unique (or why it mattered). It seems entirely possible depending on the definition of $G$ that it might not be unique. Also, how does the explanation of making the explicit point by point what $F$ is explain anything? I think that is the key point I don't understand.
functions logic computability
asked Nov 24 at 18:21
Pinocchio
1,88021754
add a comment |
I was reading these notes and on page 88 (of the paper version) it said:
however it wasn't clear to me why the function would be unique (or why it mattered). It seems entirely possible depending on the definition of $G$ that it might not be unique. Also, how does the explanation of making the explicit point by point what $F$ is explain anything? I think that is the key point I don't understand.
functions logic computability
asked Nov 24 at 18:21
Pinocchio
1,88021754
I still don't know why uniqueness is obvious.
– Pinocchio
Nov 28 at 5:00
add a comment |
I was reading these notes and on page 88 (of the paper version) it said:
however it wasn't clear to me why the function would be unique (or why it mattered). It seems entirely possible depending on the definition of $G$ that it might not be unique. Also, how does the explanation of making the explicit point by point what $F$ is explain anything? I think that is the key point I don't understand.
functions logic computability
asked Nov 24 at 18:21
Pinocchio
1,88021754
I was reading these notes and on page 88 (of the paper version) it said:
however it wasn't clear to me why the function would be unique (or why it mattered). It seems entirely possible depending on the definition of $G$ that it might not be unique. Also, how does the explanation of making the explicit point by point what $F$ is explain anything? I think that is the key point I don't understand.
functions logic computability
functions logic computability
asked Nov 24 at 18:21
Pinocchio
1,88021754
asked Nov 24 at 18:21
Pinocchio
1,88021754
asked Nov 24 at 18:21
Pinocchio
1,88021754
asked Nov 24 at 18:21
Pinocchio
1,88021754
asked Nov 24 at 18:21
Pinocchio
1,88021754
1,88021754
I still don't know why uniqueness is obvious.
– Pinocchio
Nov 28 at 5:00
add a comment |
I still don't know why uniqueness is obvious.
– Pinocchio
Nov 28 at 5:00
I still don't know why uniqueness is obvious.
– Pinocchio
Nov 28 at 5:00
I still don't know why uniqueness is obvious.
– Pinocchio
Nov 28 at 5:00
add a comment |
1 Answer
1
active
oldest
votes
It should be pretty intuitively clear why $F$ is uniquely defined. If you want to know what $F(a,b)$ is for any $a$ and $b$, you simply apply the $F(a,b+1)$ equation repeatedly until $b=0$ and then you apply the $F(a,0)$ equation. This will unfold $F(a,b)$ out into a $b$-deep nested applications of $G$ to itself. Now, we'll still have occurrences of $F$ in this unfolded expression, but since they are always applied to smaller values of $b$ we can use strong induction to show that they too can be rewritten in terms of $G$ only. The end result is that $F(a,b)$ is defined as an expression solely in terms of $G$, $a$, and $b$. If you do the proof, you'll find that strong induction fits extremely nicely. This is no surprise as this is the computational analogue of strong induction (with parameters) itself.
answered Nov 24 at 19:36
Derek Elkins
16.1k11337
why is uniqueness obvious? Thats usually requires proof.
– Pinocchio
Nov 26 at 21:04
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%2f3011890%2fwhy-is-fa-b-ga-b-bar-f-a-b-unique-if-bar-f-a-b-is-a-sequence-n%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
It should be pretty intuitively clear why $F$ is uniquely defined. If you want to know what $F(a,b)$ is for any $a$ and $b$, you simply apply the $F(a,b+1)$ equation repeatedly until $b=0$ and then you apply the $F(a,0)$ equation. This will unfold $F(a,b)$ out into a $b$-deep nested applications of $G$ to itself. Now, we'll still have occurrences of $F$ in this unfolded expression, but since they are always applied to smaller values of $b$ we can use strong induction to show that they too can be rewritten in terms of $G$ only. The end result is that $F(a,b)$ is defined as an expression solely in terms of $G$, $a$, and $b$. If you do the proof, you'll find that strong induction fits extremely nicely. This is no surprise as this is the computational analogue of strong induction (with parameters) itself.
answered Nov 24 at 19:36
Derek Elkins
16.1k11337
why is uniqueness obvious? Thats usually requires proof.
– Pinocchio
Nov 26 at 21:04
add a comment |
It should be pretty intuitively clear why $F$ is uniquely defined. If you want to know what $F(a,b)$ is for any $a$ and $b$, you simply apply the $F(a,b+1)$ equation repeatedly until $b=0$ and then you apply the $F(a,0)$ equation. This will unfold $F(a,b)$ out into a $b$-deep nested applications of $G$ to itself. Now, we'll still have occurrences of $F$ in this unfolded expression, but since they are always applied to smaller values of $b$ we can use strong induction to show that they too can be rewritten in terms of $G$ only. The end result is that $F(a,b)$ is defined as an expression solely in terms of $G$, $a$, and $b$. If you do the proof, you'll find that strong induction fits extremely nicely. This is no surprise as this is the computational analogue of strong induction (with parameters) itself.
answered Nov 24 at 19:36
Derek Elkins
16.1k11337
why is uniqueness obvious? Thats usually requires proof.
– Pinocchio
Nov 26 at 21:04
add a comment |
It should be pretty intuitively clear why $F$ is uniquely defined. If you want to know what $F(a,b)$ is for any $a$ and $b$, you simply apply the $F(a,b+1)$ equation repeatedly until $b=0$ and then you apply the $F(a,0)$ equation. This will unfold $F(a,b)$ out into a $b$-deep nested applications of $G$ to itself. Now, we'll still have occurrences of $F$ in this unfolded expression, but since they are always applied to smaller values of $b$ we can use strong induction to show that they too can be rewritten in terms of $G$ only. The end result is that $F(a,b)$ is defined as an expression solely in terms of $G$, $a$, and $b$. If you do the proof, you'll find that strong induction fits extremely nicely. This is no surprise as this is the computational analogue of strong induction (with parameters) itself.
answered Nov 24 at 19:36
Derek Elkins
16.1k11337
It should be pretty intuitively clear why $F$ is uniquely defined. If you want to know what $F(a,b)$ is for any $a$ and $b$, you simply apply the $F(a,b+1)$ equation repeatedly until $b=0$ and then you apply the $F(a,0)$ equation. This will unfold $F(a,b)$ out into a $b$-deep nested applications of $G$ to itself. Now, we'll still have occurrences of $F$ in this unfolded expression, but since they are always applied to smaller values of $b$ we can use strong induction to show that they too can be rewritten in terms of $G$ only. The end result is that $F(a,b)$ is defined as an expression solely in terms of $G$, $a$, and $b$. If you do the proof, you'll find that strong induction fits extremely nicely. This is no surprise as this is the computational analogue of strong induction (with parameters) itself.
answered Nov 24 at 19:36
Derek Elkins
16.1k11337
answered Nov 24 at 19:36
Derek Elkins
16.1k11337
answered Nov 24 at 19:36
Derek Elkins
16.1k11337
answered Nov 24 at 19:36
Derek Elkins
16.1k11337
16.1k11337
why is uniqueness obvious? Thats usually requires proof.
– Pinocchio
Nov 26 at 21:04
add a comment |
why is uniqueness obvious? Thats usually requires proof.
– Pinocchio
Nov 26 at 21:04
why is uniqueness obvious? Thats usually requires proof.
– Pinocchio
Nov 26 at 21:04
why is uniqueness obvious? Thats usually requires proof.
– Pinocchio
Nov 26 at 21:04
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3011890%2fwhy-is-fa-b-ga-b-bar-f-a-b-unique-if-bar-f-a-b-is-a-sequence-n%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
I still don't know why uniqueness is obvious.
– Pinocchio
Nov 28 at 5:00