Recursion Theory/Incompleteness Theorems: Computability of sets of formulas in first order logic
up vote
3
down vote
favorite
I am struggling with the following two problems:
Suppose that $M$ is a structure with finite universe and finite alphabet. Show that the set of formulas ${varphi$ $mid$ for every $M$-assignment $nu$ of the variables, $(M,nu) models varphi}$ is computable.
Give an example of a finite language such that the set of formulas ${varphi$ $mid$ for every finite structure $M$ which interprets that language and every $M$-assignment $nu$ of the variables, $(M,nu) models varphi}$ is not computable.
Note that in the above problems, "$(M,nu) models varphi$" is to be read as "$varphi$ holds in $M$ when the variables of $varphi$ are evaluated in $M$ according to $nu$."
Now let $V:= {varphi mid varphi$ is a validity $}$, where "A formula $varphi$ is a validity" means "For all $(M,nu)$, if $(M,nu)$ interprets all the nonlogical symbols of $varphi$, then $(M,nu) models varphi$." I know that $V geq_m H$ and therefore $V$ is not computable. The example sought by the second problem would seem to involve this theorem.
Unfortunately I can't see much further beyond this. Would anyone be so kind to share any hints or remarks that would help me begin to understand how to work towards a solution of these?
Thank you so much!
logic first-order-logic computability incompleteness decidability
asked Nov 17 at 20:31
Rebecca Bonham
15310
|
show 7 more comments
up vote
3
down vote
favorite
I am struggling with the following two problems:
Suppose that $M$ is a structure with finite universe and finite alphabet. Show that the set of formulas ${varphi$ $mid$ for every $M$-assignment $nu$ of the variables, $(M,nu) models varphi}$ is computable.
Give an example of a finite language such that the set of formulas ${varphi$ $mid$ for every finite structure $M$ which interprets that language and every $M$-assignment $nu$ of the variables, $(M,nu) models varphi}$ is not computable.
Note that in the above problems, "$(M,nu) models varphi$" is to be read as "$varphi$ holds in $M$ when the variables of $varphi$ are evaluated in $M$ according to $nu$."
Now let $V:= {varphi mid varphi$ is a validity $}$, where "A formula $varphi$ is a validity" means "For all $(M,nu)$, if $(M,nu)$ interprets all the nonlogical symbols of $varphi$, then $(M,nu) models varphi$." I know that $V geq_m H$ and therefore $V$ is not computable. The example sought by the second problem would seem to involve this theorem.
Unfortunately I can't see much further beyond this. Would anyone be so kind to share any hints or remarks that would help me begin to understand how to work towards a solution of these?
Thank you so much!
logic first-order-logic computability incompleteness decidability
asked Nov 17 at 20:31
Rebecca Bonham
15310
1
How do you define computable? Surely you can come up with an algorithm that solves 1.
– Andrés E. Caicedo
Nov 17 at 21:23
Hi, thanks for your response. The definition of a computable set is this: en.wikipedia.org/wiki/Recursive_set
– Rebecca Bonham
Nov 17 at 21:34
Intuitively, I understand the idea of algorithmically deciding whether each $varphi$ is belongs to the set defined in the first problem, but am having trouble translating that idea into a computable function, i.e. exhibiting an algorithm, if that makes sense.
– Rebecca Bonham
Nov 17 at 21:37
1
For part 1, what level of detail do you need to go into to describe the algorithm? If you are given a finite model, a formula $phi$, it is a finite task to check whether $phi$ holds under every interpretation of its free variables in $M$. (because it is a finite task to enumerate all the interpretations and then, for each interpretation it is a finite task to check whether $phi$ holds).
– Rob Arthan
Nov 17 at 23:41
1
If pressed to give more details of something like this in my own work, I would write some mathematical style pseudo-code. I can't really comment on how much explicit detail is required in your case.
– Rob Arthan
Nov 17 at 23:53
|
show 7 more comments
up vote
3
down vote
favorite
up vote
3
down vote
favorite
I am struggling with the following two problems:
Suppose that $M$ is a structure with finite universe and finite alphabet. Show that the set of formulas ${varphi$ $mid$ for every $M$-assignment $nu$ of the variables, $(M,nu) models varphi}$ is computable.
Give an example of a finite language such that the set of formulas ${varphi$ $mid$ for every finite structure $M$ which interprets that language and every $M$-assignment $nu$ of the variables, $(M,nu) models varphi}$ is not computable.
Note that in the above problems, "$(M,nu) models varphi$" is to be read as "$varphi$ holds in $M$ when the variables of $varphi$ are evaluated in $M$ according to $nu$."
Now let $V:= {varphi mid varphi$ is a validity $}$, where "A formula $varphi$ is a validity" means "For all $(M,nu)$, if $(M,nu)$ interprets all the nonlogical symbols of $varphi$, then $(M,nu) models varphi$." I know that $V geq_m H$ and therefore $V$ is not computable. The example sought by the second problem would seem to involve this theorem.
Unfortunately I can't see much further beyond this. Would anyone be so kind to share any hints or remarks that would help me begin to understand how to work towards a solution of these?
Thank you so much!
logic first-order-logic computability incompleteness decidability
asked Nov 17 at 20:31
Rebecca Bonham
15310
I am struggling with the following two problems:
Suppose that $M$ is a structure with finite universe and finite alphabet. Show that the set of formulas ${varphi$ $mid$ for every $M$-assignment $nu$ of the variables, $(M,nu) models varphi}$ is computable.
Give an example of a finite language such that the set of formulas ${varphi$ $mid$ for every finite structure $M$ which interprets that language and every $M$-assignment $nu$ of the variables, $(M,nu) models varphi}$ is not computable.
Note that in the above problems, "$(M,nu) models varphi$" is to be read as "$varphi$ holds in $M$ when the variables of $varphi$ are evaluated in $M$ according to $nu$."
Now let $V:= {varphi mid varphi$ is a validity $}$, where "A formula $varphi$ is a validity" means "For all $(M,nu)$, if $(M,nu)$ interprets all the nonlogical symbols of $varphi$, then $(M,nu) models varphi$." I know that $V geq_m H$ and therefore $V$ is not computable. The example sought by the second problem would seem to involve this theorem.
Unfortunately I can't see much further beyond this. Would anyone be so kind to share any hints or remarks that would help me begin to understand how to work towards a solution of these?
Thank you so much!
logic first-order-logic computability incompleteness decidability
logic first-order-logic computability incompleteness decidability
asked Nov 17 at 20:31
Rebecca Bonham
15310
asked Nov 17 at 20:31
Rebecca Bonham
15310
edited Nov 18 at 16:38
asked Nov 17 at 20:31
Rebecca Bonham
15310
asked Nov 17 at 20:31
Rebecca Bonham
15310
asked Nov 17 at 20:31
Rebecca Bonham
15310
15310
1
How do you define computable? Surely you can come up with an algorithm that solves 1.
– Andrés E. Caicedo
Nov 17 at 21:23
Hi, thanks for your response. The definition of a computable set is this: en.wikipedia.org/wiki/Recursive_set
– Rebecca Bonham
Nov 17 at 21:34
Intuitively, I understand the idea of algorithmically deciding whether each $varphi$ is belongs to the set defined in the first problem, but am having trouble translating that idea into a computable function, i.e. exhibiting an algorithm, if that makes sense.
– Rebecca Bonham
Nov 17 at 21:37
1
For part 1, what level of detail do you need to go into to describe the algorithm? If you are given a finite model, a formula $phi$, it is a finite task to check whether $phi$ holds under every interpretation of its free variables in $M$. (because it is a finite task to enumerate all the interpretations and then, for each interpretation it is a finite task to check whether $phi$ holds).
– Rob Arthan
Nov 17 at 23:41
1
If pressed to give more details of something like this in my own work, I would write some mathematical style pseudo-code. I can't really comment on how much explicit detail is required in your case.
– Rob Arthan
Nov 17 at 23:53
|
show 7 more comments
1
How do you define computable? Surely you can come up with an algorithm that solves 1.
– Andrés E. Caicedo
Nov 17 at 21:23
Hi, thanks for your response. The definition of a computable set is this: en.wikipedia.org/wiki/Recursive_set
– Rebecca Bonham
Nov 17 at 21:34
Intuitively, I understand the idea of algorithmically deciding whether each $varphi$ is belongs to the set defined in the first problem, but am having trouble translating that idea into a computable function, i.e. exhibiting an algorithm, if that makes sense.
– Rebecca Bonham
Nov 17 at 21:37
1
For part 1, what level of detail do you need to go into to describe the algorithm? If you are given a finite model, a formula $phi$, it is a finite task to check whether $phi$ holds under every interpretation of its free variables in $M$. (because it is a finite task to enumerate all the interpretations and then, for each interpretation it is a finite task to check whether $phi$ holds).
– Rob Arthan
Nov 17 at 23:41
1
If pressed to give more details of something like this in my own work, I would write some mathematical style pseudo-code. I can't really comment on how much explicit detail is required in your case.
– Rob Arthan
Nov 17 at 23:53
1
1
How do you define computable? Surely you can come up with an algorithm that solves 1.
– Andrés E. Caicedo
Nov 17 at 21:23
How do you define computable? Surely you can come up with an algorithm that solves 1.
– Andrés E. Caicedo
Nov 17 at 21:23
Hi, thanks for your response. The definition of a computable set is this: en.wikipedia.org/wiki/Recursive_set
– Rebecca Bonham
Nov 17 at 21:34
Hi, thanks for your response. The definition of a computable set is this: en.wikipedia.org/wiki/Recursive_set
– Rebecca Bonham
Nov 17 at 21:34
Intuitively, I understand the idea of algorithmically deciding whether each $varphi$ is belongs to the set defined in the first problem, but am having trouble translating that idea into a computable function, i.e. exhibiting an algorithm, if that makes sense.
– Rebecca Bonham
Nov 17 at 21:37
Intuitively, I understand the idea of algorithmically deciding whether each $varphi$ is belongs to the set defined in the first problem, but am having trouble translating that idea into a computable function, i.e. exhibiting an algorithm, if that makes sense.
– Rebecca Bonham
Nov 17 at 21:37
1
1
For part 1, what level of detail do you need to go into to describe the algorithm? If you are given a finite model, a formula $phi$, it is a finite task to check whether $phi$ holds under every interpretation of its free variables in $M$. (because it is a finite task to enumerate all the interpretations and then, for each interpretation it is a finite task to check whether $phi$ holds).
– Rob Arthan
Nov 17 at 23:41
For part 1, what level of detail do you need to go into to describe the algorithm? If you are given a finite model, a formula $phi$, it is a finite task to check whether $phi$ holds under every interpretation of its free variables in $M$. (because it is a finite task to enumerate all the interpretations and then, for each interpretation it is a finite task to check whether $phi$ holds).
– Rob Arthan
Nov 17 at 23:41
1
1
If pressed to give more details of something like this in my own work, I would write some mathematical style pseudo-code. I can't really comment on how much explicit detail is required in your case.
– Rob Arthan
Nov 17 at 23:53
If pressed to give more details of something like this in my own work, I would write some mathematical style pseudo-code. I can't really comment on how much explicit detail is required in your case.
– Rob Arthan
Nov 17 at 23:53
|
show 7 more comments
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3002774%2frecursion-theory-incompleteness-theorems-computability-of-sets-of-formulas-in-f%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
1
How do you define computable? Surely you can come up with an algorithm that solves 1.
– Andrés E. Caicedo
Nov 17 at 21:23
Hi, thanks for your response. The definition of a computable set is this: en.wikipedia.org/wiki/Recursive_set
– Rebecca Bonham
Nov 17 at 21:34
Intuitively, I understand the idea of algorithmically deciding whether each $varphi$ is belongs to the set defined in the first problem, but am having trouble translating that idea into a computable function, i.e. exhibiting an algorithm, if that makes sense.
– Rebecca Bonham
Nov 17 at 21:37
1
For part 1, what level of detail do you need to go into to describe the algorithm? If you are given a finite model, a formula $phi$, it is a finite task to check whether $phi$ holds under every interpretation of its free variables in $M$. (because it is a finite task to enumerate all the interpretations and then, for each interpretation it is a finite task to check whether $phi$ holds).
– Rob Arthan
Nov 17 at 23:41
1
If pressed to give more details of something like this in my own work, I would write some mathematical style pseudo-code. I can't really comment on how much explicit detail is required in your case.
– Rob Arthan
Nov 17 at 23:53