Is there a partial recursive function mapping $e$ to the least element of $W_e$?
$begingroup$
Is there a partial recursive function $f$ that maps $e$ to the least element of $W_e$ if $W_eneq varnothing$?
Can we apply the $mu$-operator (minimization) to a partially decidable predicate to get a partial recursive function (as in defining $f(x)=mu z(zin W_e)$ if $W_eneqvarnothing$ and undefined otherwise, since $zin W_e$ is partially decidable)?
My guess was that there is no such $f$, but I wasn't sure how to show that.
Thanks in adavnce.
logic computability
asked Dec 8 '18 at 20:26
user500144user500144
645
$endgroup$
add a comment |
$begingroup$
Is there a partial recursive function $f$ that maps $e$ to the least element of $W_e$ if $W_eneq varnothing$?
Can we apply the $mu$-operator (minimization) to a partially decidable predicate to get a partial recursive function (as in defining $f(x)=mu z(zin W_e)$ if $W_eneqvarnothing$ and undefined otherwise, since $zin W_e$ is partially decidable)?
My guess was that there is no such $f$, but I wasn't sure how to show that.
Thanks in adavnce.
logic computability
asked Dec 8 '18 at 20:26
user500144user500144
645
$endgroup$
add a comment |
$begingroup$
Is there a partial recursive function $f$ that maps $e$ to the least element of $W_e$ if $W_eneq varnothing$?
Can we apply the $mu$-operator (minimization) to a partially decidable predicate to get a partial recursive function (as in defining $f(x)=mu z(zin W_e)$ if $W_eneqvarnothing$ and undefined otherwise, since $zin W_e$ is partially decidable)?
My guess was that there is no such $f$, but I wasn't sure how to show that.
Thanks in adavnce.
logic computability
asked Dec 8 '18 at 20:26
user500144user500144
645
$endgroup$
Is there a partial recursive function $f$ that maps $e$ to the least element of $W_e$ if $W_eneq varnothing$?
Can we apply the $mu$-operator (minimization) to a partially decidable predicate to get a partial recursive function (as in defining $f(x)=mu z(zin W_e)$ if $W_eneqvarnothing$ and undefined otherwise, since $zin W_e$ is partially decidable)?
My guess was that there is no such $f$, but I wasn't sure how to show that.
Thanks in adavnce.
logic computability
logic computability
asked Dec 8 '18 at 20:26
user500144user500144
645
asked Dec 8 '18 at 20:26
user500144user500144
645
asked Dec 8 '18 at 20:26
user500144user500144
645
asked Dec 8 '18 at 20:26
user500144user500144
645
asked Dec 8 '18 at 20:26
user500144user500144
645
645
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Your intuition is right: there is no such function.
We can see this in a couple different ways:
Contradiction: Suppose there were such an $f$. Then - given an arbitrary (infinite) c.e. set $A$ - we could compute the sequence $$min(A), min(Asetminus{min(A)}), min(Asetminus{min(A), min(Asetminus{min(A)})}), ...$$ by iteratively applying $f$. But this precisely enumerates $A$ in order, and so makes $A$ computable. Since there are non-computable sets, this can't happen.
Direct diagonalization: Given a computable function $f$, we can find an $e$ such that $(i)$ $2$ enters $W_e$ at stage $0$, $(ii)$ $1$ enters $W_e$ at stage $n+1$ iff $f(e)$ halts and outputs "$2$" at stage exactly $n$, and $(iii)$ no other numbers enter $W_e$ under any other circumstances. Then we get $min(W_e)=2$ iff $f(e)not=2$, so $f$ doesn't do what we want it to.
- This fits into the "game picture" of c.e. sets: I pick a computable $f$, and you start building my $W_e$. You put $2$ into it, which forces me to eventually decide what $f(e)$ is; as soon as I do, if I say "$2$" then you put $1$ into my set, and if I say anything other than "$2$" you do nothing. Either way, you've defeated my purported $f$.
I haven't provided full details of either case, but the idea should be clear. Filling in the details (of the first one, especially) is a good exercise.
answered Dec 8 '18 at 20:36
Noah SchweberNoah Schweber
127k10151290
$endgroup$
$begingroup$
I haven't seen much of the "game" arguments, so could you explain what you mean by we "build $W_e$"? Isn't $W_e$ already determined for each $e$? Also, what do you mean by we can "find" $e$ such that 2 enters $W_e$ at stage 0... and so on?
$endgroup$
– user500144
Dec 8 '18 at 21:02
$begingroup$
@user500144 The two key ingredients here are Church's thesis and, more subtly, the recursion theorem. It's the latter which lets us seemingly "define $e$ while knowing already $e$."
$endgroup$
– Noah Schweber
Dec 8 '18 at 21:05
$begingroup$
Specifically, the argument has two pieces. Suppose $f$ has the property proposed. We begin with a Church's thesis argument: there is a total computable $h$ such that, for each $e$, we have $W_{h(e)}={1,2}$ if $f(e)downarrow=2$ and $W_{h(e)}={2}$ otherwise.
$endgroup$
– Noah Schweber
Dec 8 '18 at 21:16
$begingroup$
(cont'd) The interesting step is applying the Recursion Theorem. Since $h$ is total computable, it has a fixed point - some $c$ such that $W_c=W_{h(c)}$. But then we have $W_{c}={1,2}$ if $f(c)downarrow=2$ and $W_c={2}$ otherwise - contradicting the assumption on $f$.
$endgroup$
– Noah Schweber
Dec 8 '18 at 21:17
$begingroup$
(contd) The recursion theorem aside (it is genuinely a technical result), all of this stuff becomes more intuitive once you think of c.e. sets as sets you can "enumerate effectively." E.g. intuitively we can effectively enumerate the theorems of a given (computably axiomatizable) theory: just search through all possible proofs and put sentences into the set we're building when we see them proved. This corresponds to the fact that the set of (Godel numbers of) theorems of a (computably axiomatizable) theory is c.e. So it's a useful intuitive device: if you can build it, it's $W_e$ for some $e$.
$endgroup$
– Noah Schweber
Dec 8 '18 at 21:19
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%2f3031600%2fis-there-a-partial-recursive-function-mapping-e-to-the-least-element-of-w-e%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$
Your intuition is right: there is no such function.
We can see this in a couple different ways:
Contradiction: Suppose there were such an $f$. Then - given an arbitrary (infinite) c.e. set $A$ - we could compute the sequence $$min(A), min(Asetminus{min(A)}), min(Asetminus{min(A), min(Asetminus{min(A)})}), ...$$ by iteratively applying $f$. But this precisely enumerates $A$ in order, and so makes $A$ computable. Since there are non-computable sets, this can't happen.
Direct diagonalization: Given a computable function $f$, we can find an $e$ such that $(i)$ $2$ enters $W_e$ at stage $0$, $(ii)$ $1$ enters $W_e$ at stage $n+1$ iff $f(e)$ halts and outputs "$2$" at stage exactly $n$, and $(iii)$ no other numbers enter $W_e$ under any other circumstances. Then we get $min(W_e)=2$ iff $f(e)not=2$, so $f$ doesn't do what we want it to.
- This fits into the "game picture" of c.e. sets: I pick a computable $f$, and you start building my $W_e$. You put $2$ into it, which forces me to eventually decide what $f(e)$ is; as soon as I do, if I say "$2$" then you put $1$ into my set, and if I say anything other than "$2$" you do nothing. Either way, you've defeated my purported $f$.
I haven't provided full details of either case, but the idea should be clear. Filling in the details (of the first one, especially) is a good exercise.
answered Dec 8 '18 at 20:36
Noah SchweberNoah Schweber
127k10151290
$endgroup$
$begingroup$
I haven't seen much of the "game" arguments, so could you explain what you mean by we "build $W_e$"? Isn't $W_e$ already determined for each $e$? Also, what do you mean by we can "find" $e$ such that 2 enters $W_e$ at stage 0... and so on?
$endgroup$
– user500144
Dec 8 '18 at 21:02
$begingroup$
@user500144 The two key ingredients here are Church's thesis and, more subtly, the recursion theorem. It's the latter which lets us seemingly "define $e$ while knowing already $e$."
$endgroup$
– Noah Schweber
Dec 8 '18 at 21:05
$begingroup$
Specifically, the argument has two pieces. Suppose $f$ has the property proposed. We begin with a Church's thesis argument: there is a total computable $h$ such that, for each $e$, we have $W_{h(e)}={1,2}$ if $f(e)downarrow=2$ and $W_{h(e)}={2}$ otherwise.
$endgroup$
– Noah Schweber
Dec 8 '18 at 21:16
$begingroup$
(cont'd) The interesting step is applying the Recursion Theorem. Since $h$ is total computable, it has a fixed point - some $c$ such that $W_c=W_{h(c)}$. But then we have $W_{c}={1,2}$ if $f(c)downarrow=2$ and $W_c={2}$ otherwise - contradicting the assumption on $f$.
$endgroup$
– Noah Schweber
Dec 8 '18 at 21:17
$begingroup$
(contd) The recursion theorem aside (it is genuinely a technical result), all of this stuff becomes more intuitive once you think of c.e. sets as sets you can "enumerate effectively." E.g. intuitively we can effectively enumerate the theorems of a given (computably axiomatizable) theory: just search through all possible proofs and put sentences into the set we're building when we see them proved. This corresponds to the fact that the set of (Godel numbers of) theorems of a (computably axiomatizable) theory is c.e. So it's a useful intuitive device: if you can build it, it's $W_e$ for some $e$.
$endgroup$
– Noah Schweber
Dec 8 '18 at 21:19
add a comment |
$begingroup$
Your intuition is right: there is no such function.
We can see this in a couple different ways:
Contradiction: Suppose there were such an $f$. Then - given an arbitrary (infinite) c.e. set $A$ - we could compute the sequence $$min(A), min(Asetminus{min(A)}), min(Asetminus{min(A), min(Asetminus{min(A)})}), ...$$ by iteratively applying $f$. But this precisely enumerates $A$ in order, and so makes $A$ computable. Since there are non-computable sets, this can't happen.
Direct diagonalization: Given a computable function $f$, we can find an $e$ such that $(i)$ $2$ enters $W_e$ at stage $0$, $(ii)$ $1$ enters $W_e$ at stage $n+1$ iff $f(e)$ halts and outputs "$2$" at stage exactly $n$, and $(iii)$ no other numbers enter $W_e$ under any other circumstances. Then we get $min(W_e)=2$ iff $f(e)not=2$, so $f$ doesn't do what we want it to.
- This fits into the "game picture" of c.e. sets: I pick a computable $f$, and you start building my $W_e$. You put $2$ into it, which forces me to eventually decide what $f(e)$ is; as soon as I do, if I say "$2$" then you put $1$ into my set, and if I say anything other than "$2$" you do nothing. Either way, you've defeated my purported $f$.
I haven't provided full details of either case, but the idea should be clear. Filling in the details (of the first one, especially) is a good exercise.
answered Dec 8 '18 at 20:36
Noah SchweberNoah Schweber
127k10151290
$endgroup$
$begingroup$
I haven't seen much of the "game" arguments, so could you explain what you mean by we "build $W_e$"? Isn't $W_e$ already determined for each $e$? Also, what do you mean by we can "find" $e$ such that 2 enters $W_e$ at stage 0... and so on?
$endgroup$
– user500144
Dec 8 '18 at 21:02
$begingroup$
@user500144 The two key ingredients here are Church's thesis and, more subtly, the recursion theorem. It's the latter which lets us seemingly "define $e$ while knowing already $e$."
$endgroup$
– Noah Schweber
Dec 8 '18 at 21:05
$begingroup$
Specifically, the argument has two pieces. Suppose $f$ has the property proposed. We begin with a Church's thesis argument: there is a total computable $h$ such that, for each $e$, we have $W_{h(e)}={1,2}$ if $f(e)downarrow=2$ and $W_{h(e)}={2}$ otherwise.
$endgroup$
– Noah Schweber
Dec 8 '18 at 21:16
$begingroup$
(cont'd) The interesting step is applying the Recursion Theorem. Since $h$ is total computable, it has a fixed point - some $c$ such that $W_c=W_{h(c)}$. But then we have $W_{c}={1,2}$ if $f(c)downarrow=2$ and $W_c={2}$ otherwise - contradicting the assumption on $f$.
$endgroup$
– Noah Schweber
Dec 8 '18 at 21:17
$begingroup$
(contd) The recursion theorem aside (it is genuinely a technical result), all of this stuff becomes more intuitive once you think of c.e. sets as sets you can "enumerate effectively." E.g. intuitively we can effectively enumerate the theorems of a given (computably axiomatizable) theory: just search through all possible proofs and put sentences into the set we're building when we see them proved. This corresponds to the fact that the set of (Godel numbers of) theorems of a (computably axiomatizable) theory is c.e. So it's a useful intuitive device: if you can build it, it's $W_e$ for some $e$.
$endgroup$
– Noah Schweber
Dec 8 '18 at 21:19
add a comment |
$begingroup$
Your intuition is right: there is no such function.
We can see this in a couple different ways:
Contradiction: Suppose there were such an $f$. Then - given an arbitrary (infinite) c.e. set $A$ - we could compute the sequence $$min(A), min(Asetminus{min(A)}), min(Asetminus{min(A), min(Asetminus{min(A)})}), ...$$ by iteratively applying $f$. But this precisely enumerates $A$ in order, and so makes $A$ computable. Since there are non-computable sets, this can't happen.
Direct diagonalization: Given a computable function $f$, we can find an $e$ such that $(i)$ $2$ enters $W_e$ at stage $0$, $(ii)$ $1$ enters $W_e$ at stage $n+1$ iff $f(e)$ halts and outputs "$2$" at stage exactly $n$, and $(iii)$ no other numbers enter $W_e$ under any other circumstances. Then we get $min(W_e)=2$ iff $f(e)not=2$, so $f$ doesn't do what we want it to.
- This fits into the "game picture" of c.e. sets: I pick a computable $f$, and you start building my $W_e$. You put $2$ into it, which forces me to eventually decide what $f(e)$ is; as soon as I do, if I say "$2$" then you put $1$ into my set, and if I say anything other than "$2$" you do nothing. Either way, you've defeated my purported $f$.
I haven't provided full details of either case, but the idea should be clear. Filling in the details (of the first one, especially) is a good exercise.
answered Dec 8 '18 at 20:36
Noah SchweberNoah Schweber
127k10151290
$endgroup$
Your intuition is right: there is no such function.
We can see this in a couple different ways:
Contradiction: Suppose there were such an $f$. Then - given an arbitrary (infinite) c.e. set $A$ - we could compute the sequence $$min(A), min(Asetminus{min(A)}), min(Asetminus{min(A), min(Asetminus{min(A)})}), ...$$ by iteratively applying $f$. But this precisely enumerates $A$ in order, and so makes $A$ computable. Since there are non-computable sets, this can't happen.
Direct diagonalization: Given a computable function $f$, we can find an $e$ such that $(i)$ $2$ enters $W_e$ at stage $0$, $(ii)$ $1$ enters $W_e$ at stage $n+1$ iff $f(e)$ halts and outputs "$2$" at stage exactly $n$, and $(iii)$ no other numbers enter $W_e$ under any other circumstances. Then we get $min(W_e)=2$ iff $f(e)not=2$, so $f$ doesn't do what we want it to.
- This fits into the "game picture" of c.e. sets: I pick a computable $f$, and you start building my $W_e$. You put $2$ into it, which forces me to eventually decide what $f(e)$ is; as soon as I do, if I say "$2$" then you put $1$ into my set, and if I say anything other than "$2$" you do nothing. Either way, you've defeated my purported $f$.
I haven't provided full details of either case, but the idea should be clear. Filling in the details (of the first one, especially) is a good exercise.
answered Dec 8 '18 at 20:36
Noah SchweberNoah Schweber
127k10151290
answered Dec 8 '18 at 20:36
Noah SchweberNoah Schweber
127k10151290
answered Dec 8 '18 at 20:36
Noah SchweberNoah Schweber
127k10151290
answered Dec 8 '18 at 20:36
Noah SchweberNoah Schweber
127k10151290
127k10151290
$begingroup$
I haven't seen much of the "game" arguments, so could you explain what you mean by we "build $W_e$"? Isn't $W_e$ already determined for each $e$? Also, what do you mean by we can "find" $e$ such that 2 enters $W_e$ at stage 0... and so on?
$endgroup$
– user500144
Dec 8 '18 at 21:02
$begingroup$
@user500144 The two key ingredients here are Church's thesis and, more subtly, the recursion theorem. It's the latter which lets us seemingly "define $e$ while knowing already $e$."
$endgroup$
– Noah Schweber
Dec 8 '18 at 21:05
$begingroup$
Specifically, the argument has two pieces. Suppose $f$ has the property proposed. We begin with a Church's thesis argument: there is a total computable $h$ such that, for each $e$, we have $W_{h(e)}={1,2}$ if $f(e)downarrow=2$ and $W_{h(e)}={2}$ otherwise.
$endgroup$
– Noah Schweber
Dec 8 '18 at 21:16
$begingroup$
(cont'd) The interesting step is applying the Recursion Theorem. Since $h$ is total computable, it has a fixed point - some $c$ such that $W_c=W_{h(c)}$. But then we have $W_{c}={1,2}$ if $f(c)downarrow=2$ and $W_c={2}$ otherwise - contradicting the assumption on $f$.
$endgroup$
– Noah Schweber
Dec 8 '18 at 21:17
$begingroup$
(contd) The recursion theorem aside (it is genuinely a technical result), all of this stuff becomes more intuitive once you think of c.e. sets as sets you can "enumerate effectively." E.g. intuitively we can effectively enumerate the theorems of a given (computably axiomatizable) theory: just search through all possible proofs and put sentences into the set we're building when we see them proved. This corresponds to the fact that the set of (Godel numbers of) theorems of a (computably axiomatizable) theory is c.e. So it's a useful intuitive device: if you can build it, it's $W_e$ for some $e$.
$endgroup$
– Noah Schweber
Dec 8 '18 at 21:19
add a comment |
$begingroup$
I haven't seen much of the "game" arguments, so could you explain what you mean by we "build $W_e$"? Isn't $W_e$ already determined for each $e$? Also, what do you mean by we can "find" $e$ such that 2 enters $W_e$ at stage 0... and so on?
$endgroup$
– user500144
Dec 8 '18 at 21:02
$begingroup$
@user500144 The two key ingredients here are Church's thesis and, more subtly, the recursion theorem. It's the latter which lets us seemingly "define $e$ while knowing already $e$."
$endgroup$
– Noah Schweber
Dec 8 '18 at 21:05
$begingroup$
Specifically, the argument has two pieces. Suppose $f$ has the property proposed. We begin with a Church's thesis argument: there is a total computable $h$ such that, for each $e$, we have $W_{h(e)}={1,2}$ if $f(e)downarrow=2$ and $W_{h(e)}={2}$ otherwise.
$endgroup$
– Noah Schweber
Dec 8 '18 at 21:16
$begingroup$
(cont'd) The interesting step is applying the Recursion Theorem. Since $h$ is total computable, it has a fixed point - some $c$ such that $W_c=W_{h(c)}$. But then we have $W_{c}={1,2}$ if $f(c)downarrow=2$ and $W_c={2}$ otherwise - contradicting the assumption on $f$.
$endgroup$
– Noah Schweber
Dec 8 '18 at 21:17
$begingroup$
(contd) The recursion theorem aside (it is genuinely a technical result), all of this stuff becomes more intuitive once you think of c.e. sets as sets you can "enumerate effectively." E.g. intuitively we can effectively enumerate the theorems of a given (computably axiomatizable) theory: just search through all possible proofs and put sentences into the set we're building when we see them proved. This corresponds to the fact that the set of (Godel numbers of) theorems of a (computably axiomatizable) theory is c.e. So it's a useful intuitive device: if you can build it, it's $W_e$ for some $e$.
$endgroup$
– Noah Schweber
Dec 8 '18 at 21:19
$begingroup$
I haven't seen much of the "game" arguments, so could you explain what you mean by we "build $W_e$"? Isn't $W_e$ already determined for each $e$? Also, what do you mean by we can "find" $e$ such that 2 enters $W_e$ at stage 0... and so on?
$endgroup$
– user500144
Dec 8 '18 at 21:02
$begingroup$
I haven't seen much of the "game" arguments, so could you explain what you mean by we "build $W_e$"? Isn't $W_e$ already determined for each $e$? Also, what do you mean by we can "find" $e$ such that 2 enters $W_e$ at stage 0... and so on?
$endgroup$
– user500144
Dec 8 '18 at 21:02
$begingroup$
@user500144 The two key ingredients here are Church's thesis and, more subtly, the recursion theorem. It's the latter which lets us seemingly "define $e$ while knowing already $e$."
$endgroup$
– Noah Schweber
Dec 8 '18 at 21:05
$begingroup$
@user500144 The two key ingredients here are Church's thesis and, more subtly, the recursion theorem. It's the latter which lets us seemingly "define $e$ while knowing already $e$."
$endgroup$
– Noah Schweber
Dec 8 '18 at 21:05
$begingroup$
Specifically, the argument has two pieces. Suppose $f$ has the property proposed. We begin with a Church's thesis argument: there is a total computable $h$ such that, for each $e$, we have $W_{h(e)}={1,2}$ if $f(e)downarrow=2$ and $W_{h(e)}={2}$ otherwise.
$endgroup$
– Noah Schweber
Dec 8 '18 at 21:16
$begingroup$
Specifically, the argument has two pieces. Suppose $f$ has the property proposed. We begin with a Church's thesis argument: there is a total computable $h$ such that, for each $e$, we have $W_{h(e)}={1,2}$ if $f(e)downarrow=2$ and $W_{h(e)}={2}$ otherwise.
$endgroup$
– Noah Schweber
Dec 8 '18 at 21:16
$begingroup$
(cont'd) The interesting step is applying the Recursion Theorem. Since $h$ is total computable, it has a fixed point - some $c$ such that $W_c=W_{h(c)}$. But then we have $W_{c}={1,2}$ if $f(c)downarrow=2$ and $W_c={2}$ otherwise - contradicting the assumption on $f$.
$endgroup$
– Noah Schweber
Dec 8 '18 at 21:17
$begingroup$
(cont'd) The interesting step is applying the Recursion Theorem. Since $h$ is total computable, it has a fixed point - some $c$ such that $W_c=W_{h(c)}$. But then we have $W_{c}={1,2}$ if $f(c)downarrow=2$ and $W_c={2}$ otherwise - contradicting the assumption on $f$.
$endgroup$
– Noah Schweber
Dec 8 '18 at 21:17
$begingroup$
(contd) The recursion theorem aside (it is genuinely a technical result), all of this stuff becomes more intuitive once you think of c.e. sets as sets you can "enumerate effectively." E.g. intuitively we can effectively enumerate the theorems of a given (computably axiomatizable) theory: just search through all possible proofs and put sentences into the set we're building when we see them proved. This corresponds to the fact that the set of (Godel numbers of) theorems of a (computably axiomatizable) theory is c.e. So it's a useful intuitive device: if you can build it, it's $W_e$ for some $e$.
$endgroup$
– Noah Schweber
Dec 8 '18 at 21:19
$begingroup$
(contd) The recursion theorem aside (it is genuinely a technical result), all of this stuff becomes more intuitive once you think of c.e. sets as sets you can "enumerate effectively." E.g. intuitively we can effectively enumerate the theorems of a given (computably axiomatizable) theory: just search through all possible proofs and put sentences into the set we're building when we see them proved. This corresponds to the fact that the set of (Godel numbers of) theorems of a (computably axiomatizable) theory is c.e. So it's a useful intuitive device: if you can build it, it's $W_e$ for some $e$.
$endgroup$
– Noah Schweber
Dec 8 '18 at 21:19
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%2f3031600%2fis-there-a-partial-recursive-function-mapping-e-to-the-least-element-of-w-e%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
