Prove that there is a $Delta_1$-set $E$ which satisfies $S_0 setminus S_1 subset E subset S_0$
$begingroup$
I'd appreciate some help for the following exercise. $Sigma_1, Pi_1$ and $Delta_1$ are defined here: https://en.wikipedia.org/wiki/Arithmetical_hierarchy
I think I can prove 2. when I have 1. - can someone give me hint, how to start with the proof? I already know that all $Sigma_1$-sets are r.e. and all $Pi_1$-sets are co-r.e. and all $Delta_1$-sets are recursive.
Assume $S_0, S_1 subset mathbb{N}$ are $Sigma_1$-sets which satisfy $S_0 cup S_1 = mathbb{N}$. Prove that there is a $Delta_1$-set $E$ such that $S_0 setminus S_1 subset E subset S_0$ is satisfied.
Assume $Q_0, Q_1 subset mathbb{N}$ are $Pi_1$-sets which satisfy $S_0 cap S_1 = emptyset$. Prove that there is a $Delta_1$-set $E$ such that $Q_0 subset E$ and $Q_1 subset mathbb{N} setminus E$ are satisfied.
EDIT:
I'm trying to construct $Pi_1$ and $Sigma_1$ formulas for $E$:
$exists k varphi_0(k,n),exists k varphi_1(k,n)$ are $Sigma_1$ formulas which define $S_0$ and $S_1$.
$S_0={nin mathbb{N}: mathbb{N}vDash exists k ~ varphi_0(k,n)}$
$S_1={nin mathbb{N}: mathbb{N}vDash exists k ~ varphi_1(k,n)}$
$S_0setminus S_1={nin mathbb{N}: mathbb{N}vDash exists k ~ varphi_0(k,n) land forall l ~ lnot varphi_1(l,n)}$
$E={nin mathbb{N}: mathbb{N}vDash exists k ~ varphi_0(k,n) land exists l ~ lnot varphi_1(l,n)}$
$exists k ~ varphi_0(k,n) land exists l ~ lnot varphi_1(l,n)$ is equivalent to a $Sigma_1$ formula. Now I need a $Sigma_1$ formula for $mathbb{N} setminus E$ or a $Pi_1$ formula for $E$. Can someone give me a hint how to find it?
logic first-order-logic predicate-logic recursion computability
asked Jan 5 at 22:55
thehardyreaderthehardyreader
21829
$endgroup$
add a comment |
$begingroup$
I'd appreciate some help for the following exercise. $Sigma_1, Pi_1$ and $Delta_1$ are defined here: https://en.wikipedia.org/wiki/Arithmetical_hierarchy
I think I can prove 2. when I have 1. - can someone give me hint, how to start with the proof? I already know that all $Sigma_1$-sets are r.e. and all $Pi_1$-sets are co-r.e. and all $Delta_1$-sets are recursive.
Assume $S_0, S_1 subset mathbb{N}$ are $Sigma_1$-sets which satisfy $S_0 cup S_1 = mathbb{N}$. Prove that there is a $Delta_1$-set $E$ such that $S_0 setminus S_1 subset E subset S_0$ is satisfied.
Assume $Q_0, Q_1 subset mathbb{N}$ are $Pi_1$-sets which satisfy $S_0 cap S_1 = emptyset$. Prove that there is a $Delta_1$-set $E$ such that $Q_0 subset E$ and $Q_1 subset mathbb{N} setminus E$ are satisfied.
EDIT:
I'm trying to construct $Pi_1$ and $Sigma_1$ formulas for $E$:
$exists k varphi_0(k,n),exists k varphi_1(k,n)$ are $Sigma_1$ formulas which define $S_0$ and $S_1$.
$S_0={nin mathbb{N}: mathbb{N}vDash exists k ~ varphi_0(k,n)}$
$S_1={nin mathbb{N}: mathbb{N}vDash exists k ~ varphi_1(k,n)}$
$S_0setminus S_1={nin mathbb{N}: mathbb{N}vDash exists k ~ varphi_0(k,n) land forall l ~ lnot varphi_1(l,n)}$
$E={nin mathbb{N}: mathbb{N}vDash exists k ~ varphi_0(k,n) land exists l ~ lnot varphi_1(l,n)}$
$exists k ~ varphi_0(k,n) land exists l ~ lnot varphi_1(l,n)$ is equivalent to a $Sigma_1$ formula. Now I need a $Sigma_1$ formula for $mathbb{N} setminus E$ or a $Pi_1$ formula for $E$. Can someone give me a hint how to find it?
logic first-order-logic predicate-logic recursion computability
asked Jan 5 at 22:55
thehardyreaderthehardyreader
21829
$endgroup$
add a comment |
$begingroup$
I'd appreciate some help for the following exercise. $Sigma_1, Pi_1$ and $Delta_1$ are defined here: https://en.wikipedia.org/wiki/Arithmetical_hierarchy
I think I can prove 2. when I have 1. - can someone give me hint, how to start with the proof? I already know that all $Sigma_1$-sets are r.e. and all $Pi_1$-sets are co-r.e. and all $Delta_1$-sets are recursive.
Assume $S_0, S_1 subset mathbb{N}$ are $Sigma_1$-sets which satisfy $S_0 cup S_1 = mathbb{N}$. Prove that there is a $Delta_1$-set $E$ such that $S_0 setminus S_1 subset E subset S_0$ is satisfied.
Assume $Q_0, Q_1 subset mathbb{N}$ are $Pi_1$-sets which satisfy $S_0 cap S_1 = emptyset$. Prove that there is a $Delta_1$-set $E$ such that $Q_0 subset E$ and $Q_1 subset mathbb{N} setminus E$ are satisfied.
EDIT:
I'm trying to construct $Pi_1$ and $Sigma_1$ formulas for $E$:
$exists k varphi_0(k,n),exists k varphi_1(k,n)$ are $Sigma_1$ formulas which define $S_0$ and $S_1$.
$S_0={nin mathbb{N}: mathbb{N}vDash exists k ~ varphi_0(k,n)}$
$S_1={nin mathbb{N}: mathbb{N}vDash exists k ~ varphi_1(k,n)}$
$S_0setminus S_1={nin mathbb{N}: mathbb{N}vDash exists k ~ varphi_0(k,n) land forall l ~ lnot varphi_1(l,n)}$
$E={nin mathbb{N}: mathbb{N}vDash exists k ~ varphi_0(k,n) land exists l ~ lnot varphi_1(l,n)}$
$exists k ~ varphi_0(k,n) land exists l ~ lnot varphi_1(l,n)$ is equivalent to a $Sigma_1$ formula. Now I need a $Sigma_1$ formula for $mathbb{N} setminus E$ or a $Pi_1$ formula for $E$. Can someone give me a hint how to find it?
logic first-order-logic predicate-logic recursion computability
asked Jan 5 at 22:55
thehardyreaderthehardyreader
21829
$endgroup$
I'd appreciate some help for the following exercise. $Sigma_1, Pi_1$ and $Delta_1$ are defined here: https://en.wikipedia.org/wiki/Arithmetical_hierarchy
I think I can prove 2. when I have 1. - can someone give me hint, how to start with the proof? I already know that all $Sigma_1$-sets are r.e. and all $Pi_1$-sets are co-r.e. and all $Delta_1$-sets are recursive.
Assume $S_0, S_1 subset mathbb{N}$ are $Sigma_1$-sets which satisfy $S_0 cup S_1 = mathbb{N}$. Prove that there is a $Delta_1$-set $E$ such that $S_0 setminus S_1 subset E subset S_0$ is satisfied.
Assume $Q_0, Q_1 subset mathbb{N}$ are $Pi_1$-sets which satisfy $S_0 cap S_1 = emptyset$. Prove that there is a $Delta_1$-set $E$ such that $Q_0 subset E$ and $Q_1 subset mathbb{N} setminus E$ are satisfied.
EDIT:
I'm trying to construct $Pi_1$ and $Sigma_1$ formulas for $E$:
$exists k varphi_0(k,n),exists k varphi_1(k,n)$ are $Sigma_1$ formulas which define $S_0$ and $S_1$.
$S_0={nin mathbb{N}: mathbb{N}vDash exists k ~ varphi_0(k,n)}$
$S_1={nin mathbb{N}: mathbb{N}vDash exists k ~ varphi_1(k,n)}$
$S_0setminus S_1={nin mathbb{N}: mathbb{N}vDash exists k ~ varphi_0(k,n) land forall l ~ lnot varphi_1(l,n)}$
$E={nin mathbb{N}: mathbb{N}vDash exists k ~ varphi_0(k,n) land exists l ~ lnot varphi_1(l,n)}$
$exists k ~ varphi_0(k,n) land exists l ~ lnot varphi_1(l,n)$ is equivalent to a $Sigma_1$ formula. Now I need a $Sigma_1$ formula for $mathbb{N} setminus E$ or a $Pi_1$ formula for $E$. Can someone give me a hint how to find it?
logic first-order-logic predicate-logic recursion computability
logic first-order-logic predicate-logic recursion computability
asked Jan 5 at 22:55
thehardyreaderthehardyreader
21829
asked Jan 5 at 22:55
thehardyreaderthehardyreader
21829
edited Jan 6 at 21:29
thehardyreader
asked Jan 5 at 22:55
thehardyreaderthehardyreader
21829
asked Jan 5 at 22:55
thehardyreaderthehardyreader
21829
asked Jan 5 at 22:55
thehardyreaderthehardyreader
21829
21829
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Here is the intuition: We know any natural number is in $S_0$ or in $S_1.$ So given $ninmathbb N,$ recursively enumerate $S_0$ and $S_1$ side by side. If $n$ appears first in the $S_1$ enumeration, $nnotin E,$ whereas if it appears first in the $S_0$ enumeration, $nin E.$ (And break ties however.)
answered Jan 5 at 23:45
spaceisdarkgreenspaceisdarkgreen
32.8k21753
$endgroup$
$begingroup$
Thanks for your answer! So I can basically give a recursive characteristic function $chi_E$ for $E$: $chi_E(x)=1$ if $x in S_0$ or $x in S_0 cap S_1$ $chi_E(x)=0$ else. This function is recursive because there is an algorithm which holds in finite time if $x in S_0$or $x in S_1$. Hence $E$ is a $Delta_1$-set which also satisfies the condition $S_0 setminus S_1 subset E subset S_0$.
$endgroup$
– thehardyreader
Jan 6 at 11:07
$begingroup$
Do you have suggestions how to formalize what I wrote?
$endgroup$
– thehardyreader
Jan 6 at 11:22
$begingroup$
No, $E$ probably only contains some of $S_0cap S_1$ (whichever happen to appear in the enumeration of $S_0$ before they appear in the enumeration of $S_1$). Yes, $E$ is defined in terms of some fixed recursive enumerations of the two sets, and the definition is in the form of an algorithm that decides membership in $E$ based on these, so $E$ is recursive. Not sure how formal you have to be here. If you wish, you can avoid arguments about recursiveness and use the idea I gave to write down a $Delta_1$ formula based on the $Sigma_1$ formulas defining $S_0$ and $S_1.$
$endgroup$
– spaceisdarkgreen
Jan 6 at 18:00
$begingroup$
Okay, I see what's wrong in my comment above. What do you mean by $Delta_1$ formula? For a $Delta_1$-set there is a $Sigma_1$-formula and $Pi_1$-formula which defines it, or am I mistaken? But maybe I can do just that, writing down both for $E$.
$endgroup$
– thehardyreader
Jan 6 at 19:04
1
$begingroup$
It doesn't seem like you're grasping what $E$ is. The logic above suggests that $E$ should be defined by something like $exists k (varphi_0(k,n)land forall (l< k)lnotvarphi_1(l,n))$ (i.e. it appears in $S_0$ before (or same time as) it appears in $S_1$). And the complement of $E$ can be defined something like $exists k(varphi_1(k,n)land forall (lle k) lnot varphi_0(l,n)$ (i.e. it appears in $S_1$ before it appears in $S_0$). That the former is equivalent to the negation of the latter will require the fact that $forall n(exists k varphi_0(k,n)lor exists k varphi_1(k,n))$
$endgroup$
– spaceisdarkgreen
Jan 6 at 22:50
|
show 2 more comments
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%2f3063292%2fprove-that-there-is-a-delta-1-set-e-which-satisfies-s-0-setminus-s-1-sub%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$
Here is the intuition: We know any natural number is in $S_0$ or in $S_1.$ So given $ninmathbb N,$ recursively enumerate $S_0$ and $S_1$ side by side. If $n$ appears first in the $S_1$ enumeration, $nnotin E,$ whereas if it appears first in the $S_0$ enumeration, $nin E.$ (And break ties however.)
answered Jan 5 at 23:45
spaceisdarkgreenspaceisdarkgreen
32.8k21753
$endgroup$
$begingroup$
Thanks for your answer! So I can basically give a recursive characteristic function $chi_E$ for $E$: $chi_E(x)=1$ if $x in S_0$ or $x in S_0 cap S_1$ $chi_E(x)=0$ else. This function is recursive because there is an algorithm which holds in finite time if $x in S_0$or $x in S_1$. Hence $E$ is a $Delta_1$-set which also satisfies the condition $S_0 setminus S_1 subset E subset S_0$.
$endgroup$
– thehardyreader
Jan 6 at 11:07
$begingroup$
Do you have suggestions how to formalize what I wrote?
$endgroup$
– thehardyreader
Jan 6 at 11:22
$begingroup$
No, $E$ probably only contains some of $S_0cap S_1$ (whichever happen to appear in the enumeration of $S_0$ before they appear in the enumeration of $S_1$). Yes, $E$ is defined in terms of some fixed recursive enumerations of the two sets, and the definition is in the form of an algorithm that decides membership in $E$ based on these, so $E$ is recursive. Not sure how formal you have to be here. If you wish, you can avoid arguments about recursiveness and use the idea I gave to write down a $Delta_1$ formula based on the $Sigma_1$ formulas defining $S_0$ and $S_1.$
$endgroup$
– spaceisdarkgreen
Jan 6 at 18:00
$begingroup$
Okay, I see what's wrong in my comment above. What do you mean by $Delta_1$ formula? For a $Delta_1$-set there is a $Sigma_1$-formula and $Pi_1$-formula which defines it, or am I mistaken? But maybe I can do just that, writing down both for $E$.
$endgroup$
– thehardyreader
Jan 6 at 19:04
1
$begingroup$
It doesn't seem like you're grasping what $E$ is. The logic above suggests that $E$ should be defined by something like $exists k (varphi_0(k,n)land forall (l< k)lnotvarphi_1(l,n))$ (i.e. it appears in $S_0$ before (or same time as) it appears in $S_1$). And the complement of $E$ can be defined something like $exists k(varphi_1(k,n)land forall (lle k) lnot varphi_0(l,n)$ (i.e. it appears in $S_1$ before it appears in $S_0$). That the former is equivalent to the negation of the latter will require the fact that $forall n(exists k varphi_0(k,n)lor exists k varphi_1(k,n))$
$endgroup$
– spaceisdarkgreen
Jan 6 at 22:50
|
show 2 more comments
$begingroup$
Here is the intuition: We know any natural number is in $S_0$ or in $S_1.$ So given $ninmathbb N,$ recursively enumerate $S_0$ and $S_1$ side by side. If $n$ appears first in the $S_1$ enumeration, $nnotin E,$ whereas if it appears first in the $S_0$ enumeration, $nin E.$ (And break ties however.)
answered Jan 5 at 23:45
spaceisdarkgreenspaceisdarkgreen
32.8k21753
$endgroup$
$begingroup$
Thanks for your answer! So I can basically give a recursive characteristic function $chi_E$ for $E$: $chi_E(x)=1$ if $x in S_0$ or $x in S_0 cap S_1$ $chi_E(x)=0$ else. This function is recursive because there is an algorithm which holds in finite time if $x in S_0$or $x in S_1$. Hence $E$ is a $Delta_1$-set which also satisfies the condition $S_0 setminus S_1 subset E subset S_0$.
$endgroup$
– thehardyreader
Jan 6 at 11:07
$begingroup$
Do you have suggestions how to formalize what I wrote?
$endgroup$
– thehardyreader
Jan 6 at 11:22
$begingroup$
No, $E$ probably only contains some of $S_0cap S_1$ (whichever happen to appear in the enumeration of $S_0$ before they appear in the enumeration of $S_1$). Yes, $E$ is defined in terms of some fixed recursive enumerations of the two sets, and the definition is in the form of an algorithm that decides membership in $E$ based on these, so $E$ is recursive. Not sure how formal you have to be here. If you wish, you can avoid arguments about recursiveness and use the idea I gave to write down a $Delta_1$ formula based on the $Sigma_1$ formulas defining $S_0$ and $S_1.$
$endgroup$
– spaceisdarkgreen
Jan 6 at 18:00
$begingroup$
Okay, I see what's wrong in my comment above. What do you mean by $Delta_1$ formula? For a $Delta_1$-set there is a $Sigma_1$-formula and $Pi_1$-formula which defines it, or am I mistaken? But maybe I can do just that, writing down both for $E$.
$endgroup$
– thehardyreader
Jan 6 at 19:04
1
$begingroup$
It doesn't seem like you're grasping what $E$ is. The logic above suggests that $E$ should be defined by something like $exists k (varphi_0(k,n)land forall (l< k)lnotvarphi_1(l,n))$ (i.e. it appears in $S_0$ before (or same time as) it appears in $S_1$). And the complement of $E$ can be defined something like $exists k(varphi_1(k,n)land forall (lle k) lnot varphi_0(l,n)$ (i.e. it appears in $S_1$ before it appears in $S_0$). That the former is equivalent to the negation of the latter will require the fact that $forall n(exists k varphi_0(k,n)lor exists k varphi_1(k,n))$
$endgroup$
– spaceisdarkgreen
Jan 6 at 22:50
|
show 2 more comments
$begingroup$
Here is the intuition: We know any natural number is in $S_0$ or in $S_1.$ So given $ninmathbb N,$ recursively enumerate $S_0$ and $S_1$ side by side. If $n$ appears first in the $S_1$ enumeration, $nnotin E,$ whereas if it appears first in the $S_0$ enumeration, $nin E.$ (And break ties however.)
answered Jan 5 at 23:45
spaceisdarkgreenspaceisdarkgreen
32.8k21753
$endgroup$
Here is the intuition: We know any natural number is in $S_0$ or in $S_1.$ So given $ninmathbb N,$ recursively enumerate $S_0$ and $S_1$ side by side. If $n$ appears first in the $S_1$ enumeration, $nnotin E,$ whereas if it appears first in the $S_0$ enumeration, $nin E.$ (And break ties however.)
answered Jan 5 at 23:45
spaceisdarkgreenspaceisdarkgreen
32.8k21753
answered Jan 5 at 23:45
spaceisdarkgreenspaceisdarkgreen
32.8k21753
answered Jan 5 at 23:45
spaceisdarkgreenspaceisdarkgreen
32.8k21753
answered Jan 5 at 23:45
spaceisdarkgreenspaceisdarkgreen
32.8k21753
32.8k21753
$begingroup$
Thanks for your answer! So I can basically give a recursive characteristic function $chi_E$ for $E$: $chi_E(x)=1$ if $x in S_0$ or $x in S_0 cap S_1$ $chi_E(x)=0$ else. This function is recursive because there is an algorithm which holds in finite time if $x in S_0$or $x in S_1$. Hence $E$ is a $Delta_1$-set which also satisfies the condition $S_0 setminus S_1 subset E subset S_0$.
$endgroup$
– thehardyreader
Jan 6 at 11:07
$begingroup$
Do you have suggestions how to formalize what I wrote?
$endgroup$
– thehardyreader
Jan 6 at 11:22
$begingroup$
No, $E$ probably only contains some of $S_0cap S_1$ (whichever happen to appear in the enumeration of $S_0$ before they appear in the enumeration of $S_1$). Yes, $E$ is defined in terms of some fixed recursive enumerations of the two sets, and the definition is in the form of an algorithm that decides membership in $E$ based on these, so $E$ is recursive. Not sure how formal you have to be here. If you wish, you can avoid arguments about recursiveness and use the idea I gave to write down a $Delta_1$ formula based on the $Sigma_1$ formulas defining $S_0$ and $S_1.$
$endgroup$
– spaceisdarkgreen
Jan 6 at 18:00
$begingroup$
Okay, I see what's wrong in my comment above. What do you mean by $Delta_1$ formula? For a $Delta_1$-set there is a $Sigma_1$-formula and $Pi_1$-formula which defines it, or am I mistaken? But maybe I can do just that, writing down both for $E$.
$endgroup$
– thehardyreader
Jan 6 at 19:04
1
$begingroup$
It doesn't seem like you're grasping what $E$ is. The logic above suggests that $E$ should be defined by something like $exists k (varphi_0(k,n)land forall (l< k)lnotvarphi_1(l,n))$ (i.e. it appears in $S_0$ before (or same time as) it appears in $S_1$). And the complement of $E$ can be defined something like $exists k(varphi_1(k,n)land forall (lle k) lnot varphi_0(l,n)$ (i.e. it appears in $S_1$ before it appears in $S_0$). That the former is equivalent to the negation of the latter will require the fact that $forall n(exists k varphi_0(k,n)lor exists k varphi_1(k,n))$
$endgroup$
– spaceisdarkgreen
Jan 6 at 22:50
|
show 2 more comments
$begingroup$
Thanks for your answer! So I can basically give a recursive characteristic function $chi_E$ for $E$: $chi_E(x)=1$ if $x in S_0$ or $x in S_0 cap S_1$ $chi_E(x)=0$ else. This function is recursive because there is an algorithm which holds in finite time if $x in S_0$or $x in S_1$. Hence $E$ is a $Delta_1$-set which also satisfies the condition $S_0 setminus S_1 subset E subset S_0$.
$endgroup$
– thehardyreader
Jan 6 at 11:07
$begingroup$
Do you have suggestions how to formalize what I wrote?
$endgroup$
– thehardyreader
Jan 6 at 11:22
$begingroup$
No, $E$ probably only contains some of $S_0cap S_1$ (whichever happen to appear in the enumeration of $S_0$ before they appear in the enumeration of $S_1$). Yes, $E$ is defined in terms of some fixed recursive enumerations of the two sets, and the definition is in the form of an algorithm that decides membership in $E$ based on these, so $E$ is recursive. Not sure how formal you have to be here. If you wish, you can avoid arguments about recursiveness and use the idea I gave to write down a $Delta_1$ formula based on the $Sigma_1$ formulas defining $S_0$ and $S_1.$
$endgroup$
– spaceisdarkgreen
Jan 6 at 18:00
$begingroup$
Okay, I see what's wrong in my comment above. What do you mean by $Delta_1$ formula? For a $Delta_1$-set there is a $Sigma_1$-formula and $Pi_1$-formula which defines it, or am I mistaken? But maybe I can do just that, writing down both for $E$.
$endgroup$
– thehardyreader
Jan 6 at 19:04
1
$begingroup$
It doesn't seem like you're grasping what $E$ is. The logic above suggests that $E$ should be defined by something like $exists k (varphi_0(k,n)land forall (l< k)lnotvarphi_1(l,n))$ (i.e. it appears in $S_0$ before (or same time as) it appears in $S_1$). And the complement of $E$ can be defined something like $exists k(varphi_1(k,n)land forall (lle k) lnot varphi_0(l,n)$ (i.e. it appears in $S_1$ before it appears in $S_0$). That the former is equivalent to the negation of the latter will require the fact that $forall n(exists k varphi_0(k,n)lor exists k varphi_1(k,n))$
$endgroup$
– spaceisdarkgreen
Jan 6 at 22:50
$begingroup$
Thanks for your answer! So I can basically give a recursive characteristic function $chi_E$ for $E$: $chi_E(x)=1$ if $x in S_0$ or $x in S_0 cap S_1$ $chi_E(x)=0$ else. This function is recursive because there is an algorithm which holds in finite time if $x in S_0$or $x in S_1$. Hence $E$ is a $Delta_1$-set which also satisfies the condition $S_0 setminus S_1 subset E subset S_0$.
$endgroup$
– thehardyreader
Jan 6 at 11:07
$begingroup$
Thanks for your answer! So I can basically give a recursive characteristic function $chi_E$ for $E$: $chi_E(x)=1$ if $x in S_0$ or $x in S_0 cap S_1$ $chi_E(x)=0$ else. This function is recursive because there is an algorithm which holds in finite time if $x in S_0$or $x in S_1$. Hence $E$ is a $Delta_1$-set which also satisfies the condition $S_0 setminus S_1 subset E subset S_0$.
$endgroup$
– thehardyreader
Jan 6 at 11:07
$begingroup$
Do you have suggestions how to formalize what I wrote?
$endgroup$
– thehardyreader
Jan 6 at 11:22
$begingroup$
Do you have suggestions how to formalize what I wrote?
$endgroup$
– thehardyreader
Jan 6 at 11:22
$begingroup$
No, $E$ probably only contains some of $S_0cap S_1$ (whichever happen to appear in the enumeration of $S_0$ before they appear in the enumeration of $S_1$). Yes, $E$ is defined in terms of some fixed recursive enumerations of the two sets, and the definition is in the form of an algorithm that decides membership in $E$ based on these, so $E$ is recursive. Not sure how formal you have to be here. If you wish, you can avoid arguments about recursiveness and use the idea I gave to write down a $Delta_1$ formula based on the $Sigma_1$ formulas defining $S_0$ and $S_1.$
$endgroup$
– spaceisdarkgreen
Jan 6 at 18:00
$begingroup$
No, $E$ probably only contains some of $S_0cap S_1$ (whichever happen to appear in the enumeration of $S_0$ before they appear in the enumeration of $S_1$). Yes, $E$ is defined in terms of some fixed recursive enumerations of the two sets, and the definition is in the form of an algorithm that decides membership in $E$ based on these, so $E$ is recursive. Not sure how formal you have to be here. If you wish, you can avoid arguments about recursiveness and use the idea I gave to write down a $Delta_1$ formula based on the $Sigma_1$ formulas defining $S_0$ and $S_1.$
$endgroup$
– spaceisdarkgreen
Jan 6 at 18:00
$begingroup$
Okay, I see what's wrong in my comment above. What do you mean by $Delta_1$ formula? For a $Delta_1$-set there is a $Sigma_1$-formula and $Pi_1$-formula which defines it, or am I mistaken? But maybe I can do just that, writing down both for $E$.
$endgroup$
– thehardyreader
Jan 6 at 19:04
$begingroup$
Okay, I see what's wrong in my comment above. What do you mean by $Delta_1$ formula? For a $Delta_1$-set there is a $Sigma_1$-formula and $Pi_1$-formula which defines it, or am I mistaken? But maybe I can do just that, writing down both for $E$.
$endgroup$
– thehardyreader
Jan 6 at 19:04
1
1
$begingroup$
It doesn't seem like you're grasping what $E$ is. The logic above suggests that $E$ should be defined by something like $exists k (varphi_0(k,n)land forall (l< k)lnotvarphi_1(l,n))$ (i.e. it appears in $S_0$ before (or same time as) it appears in $S_1$). And the complement of $E$ can be defined something like $exists k(varphi_1(k,n)land forall (lle k) lnot varphi_0(l,n)$ (i.e. it appears in $S_1$ before it appears in $S_0$). That the former is equivalent to the negation of the latter will require the fact that $forall n(exists k varphi_0(k,n)lor exists k varphi_1(k,n))$
$endgroup$
– spaceisdarkgreen
Jan 6 at 22:50
$begingroup$
It doesn't seem like you're grasping what $E$ is. The logic above suggests that $E$ should be defined by something like $exists k (varphi_0(k,n)land forall (l< k)lnotvarphi_1(l,n))$ (i.e. it appears in $S_0$ before (or same time as) it appears in $S_1$). And the complement of $E$ can be defined something like $exists k(varphi_1(k,n)land forall (lle k) lnot varphi_0(l,n)$ (i.e. it appears in $S_1$ before it appears in $S_0$). That the former is equivalent to the negation of the latter will require the fact that $forall n(exists k varphi_0(k,n)lor exists k varphi_1(k,n))$
$endgroup$
– spaceisdarkgreen
Jan 6 at 22:50
|
show 2 more comments
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%2f3063292%2fprove-that-there-is-a-delta-1-set-e-which-satisfies-s-0-setminus-s-1-sub%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
