Mixing
How do I prove whether this formula is valid or satisfiable? $exists xy[P(x,y) rightarrow forall xy P(x,y)]$
$begingroup$
By valid/satisfiable I mean in the context of propositional logic. The following formula is:
$$exists xy[P(x,y) rightarrow forall xy P(x,y)]$$
I understand that P is considered to be a predicate symbol, by P(x,y) is a formula that should evaluate to true or false. However, how do I go about solving this kind of problems if I don't have information on what x and y are?
logic
edited Jan 30 at 4:39
Blue
49.3k870157
asked Jan 30 at 1:41
oldselflearner1959oldselflearner1959
432112
$endgroup$
|
show 1 more comment
$begingroup$
By valid/satisfiable I mean in the context of propositional logic. The following formula is:
$$exists xy[P(x,y) rightarrow forall xy P(x,y)]$$
I understand that P is considered to be a predicate symbol, by P(x,y) is a formula that should evaluate to true or false. However, how do I go about solving this kind of problems if I don't have information on what x and y are?
logic
edited Jan 30 at 4:39
Blue
49.3k870157
asked Jan 30 at 1:41
oldselflearner1959oldselflearner1959
432112
$endgroup$
1
$begingroup$
This is called the drinkers paradox. Either $exists xy .Pxy$ or $lnot exists xy .Pxy$
$endgroup$
– DanielV
Jan 30 at 2:10
$begingroup$
Thanks for pointing this out. Is the proof meant to be in natural language form or is there a mathematical proof for this?
$endgroup$
– oldselflearner1959
Jan 30 at 2:16
$begingroup$
That is for you to decide.
$endgroup$
– DanielV
Jan 30 at 2:17
1
$begingroup$
If I were asked whether a given first-order sentence is valid and whether it is satisfiable, I might start by considering a particular structure and checking whether the sentence is true in that structure. Being lazy, I'd choose the structure to be very simple, perhaps just one element. If the formula is true in that one structure, I at least know it's satisfiable. If the formula is false in that structure, I at least know it isn't valid. So one of the two questions, "valid?" or "satisfiable?" is immediately answered.
$endgroup$
– Andreas Blass
Jan 30 at 3:24
$begingroup$
To answer the other question, I'd need to check whether some other structure gives the opposite truth value for the given sentence. That can be hard work, but in the present case it's not too bad.Think about what would have to happen in a structure to produce the opposite truth value, and try to design a structure like that. If you can't design one, look for the reason why you can't, i.e., a proof that there's no such structure.
$endgroup$
– Andreas Blass
Jan 30 at 3:28
|
show 1 more comment
$begingroup$
By valid/satisfiable I mean in the context of propositional logic. The following formula is:
$$exists xy[P(x,y) rightarrow forall xy P(x,y)]$$
I understand that P is considered to be a predicate symbol, by P(x,y) is a formula that should evaluate to true or false. However, how do I go about solving this kind of problems if I don't have information on what x and y are?
logic
edited Jan 30 at 4:39
Blue
49.3k870157
asked Jan 30 at 1:41
oldselflearner1959oldselflearner1959
432112
$endgroup$
By valid/satisfiable I mean in the context of propositional logic. The following formula is:
$$exists xy[P(x,y) rightarrow forall xy P(x,y)]$$
I understand that P is considered to be a predicate symbol, by P(x,y) is a formula that should evaluate to true or false. However, how do I go about solving this kind of problems if I don't have information on what x and y are?
logic
logic
edited Jan 30 at 4:39
Blue
49.3k870157
asked Jan 30 at 1:41
oldselflearner1959oldselflearner1959
432112
edited Jan 30 at 4:39
Blue
49.3k870157
asked Jan 30 at 1:41
oldselflearner1959oldselflearner1959
432112
edited Jan 30 at 4:39
Blue
49.3k870157
edited Jan 30 at 4:39
Blue
49.3k870157
edited Jan 30 at 4:39
Blue
49.3k870157
49.3k870157
asked Jan 30 at 1:41
oldselflearner1959oldselflearner1959
432112
asked Jan 30 at 1:41
oldselflearner1959oldselflearner1959
432112
asked Jan 30 at 1:41
oldselflearner1959oldselflearner1959
432112
432112
1
$begingroup$
This is called the drinkers paradox. Either $exists xy .Pxy$ or $lnot exists xy .Pxy$
$endgroup$
– DanielV
Jan 30 at 2:10
$begingroup$
Thanks for pointing this out. Is the proof meant to be in natural language form or is there a mathematical proof for this?
$endgroup$
– oldselflearner1959
Jan 30 at 2:16
$begingroup$
That is for you to decide.
$endgroup$
– DanielV
Jan 30 at 2:17
1
$begingroup$
If I were asked whether a given first-order sentence is valid and whether it is satisfiable, I might start by considering a particular structure and checking whether the sentence is true in that structure. Being lazy, I'd choose the structure to be very simple, perhaps just one element. If the formula is true in that one structure, I at least know it's satisfiable. If the formula is false in that structure, I at least know it isn't valid. So one of the two questions, "valid?" or "satisfiable?" is immediately answered.
$endgroup$
– Andreas Blass
Jan 30 at 3:24
$begingroup$
To answer the other question, I'd need to check whether some other structure gives the opposite truth value for the given sentence. That can be hard work, but in the present case it's not too bad.Think about what would have to happen in a structure to produce the opposite truth value, and try to design a structure like that. If you can't design one, look for the reason why you can't, i.e., a proof that there's no such structure.
$endgroup$
– Andreas Blass
Jan 30 at 3:28
|
show 1 more comment
1
$begingroup$
This is called the drinkers paradox. Either $exists xy .Pxy$ or $lnot exists xy .Pxy$
$endgroup$
– DanielV
Jan 30 at 2:10
$begingroup$
Thanks for pointing this out. Is the proof meant to be in natural language form or is there a mathematical proof for this?
$endgroup$
– oldselflearner1959
Jan 30 at 2:16
$begingroup$
That is for you to decide.
$endgroup$
– DanielV
Jan 30 at 2:17
1
$begingroup$
If I were asked whether a given first-order sentence is valid and whether it is satisfiable, I might start by considering a particular structure and checking whether the sentence is true in that structure. Being lazy, I'd choose the structure to be very simple, perhaps just one element. If the formula is true in that one structure, I at least know it's satisfiable. If the formula is false in that structure, I at least know it isn't valid. So one of the two questions, "valid?" or "satisfiable?" is immediately answered.
$endgroup$
– Andreas Blass
Jan 30 at 3:24
$begingroup$
To answer the other question, I'd need to check whether some other structure gives the opposite truth value for the given sentence. That can be hard work, but in the present case it's not too bad.Think about what would have to happen in a structure to produce the opposite truth value, and try to design a structure like that. If you can't design one, look for the reason why you can't, i.e., a proof that there's no such structure.
$endgroup$
– Andreas Blass
Jan 30 at 3:28
1
1
$begingroup$
This is called the drinkers paradox. Either $exists xy .Pxy$ or $lnot exists xy .Pxy$
$endgroup$
– DanielV
Jan 30 at 2:10
$begingroup$
This is called the drinkers paradox. Either $exists xy .Pxy$ or $lnot exists xy .Pxy$
$endgroup$
– DanielV
Jan 30 at 2:10
$begingroup$
Thanks for pointing this out. Is the proof meant to be in natural language form or is there a mathematical proof for this?
$endgroup$
– oldselflearner1959
Jan 30 at 2:16
$begingroup$
Thanks for pointing this out. Is the proof meant to be in natural language form or is there a mathematical proof for this?
$endgroup$
– oldselflearner1959
Jan 30 at 2:16
$begingroup$
That is for you to decide.
$endgroup$
– DanielV
Jan 30 at 2:17
$begingroup$
That is for you to decide.
$endgroup$
– DanielV
Jan 30 at 2:17
1
1
$begingroup$
If I were asked whether a given first-order sentence is valid and whether it is satisfiable, I might start by considering a particular structure and checking whether the sentence is true in that structure. Being lazy, I'd choose the structure to be very simple, perhaps just one element. If the formula is true in that one structure, I at least know it's satisfiable. If the formula is false in that structure, I at least know it isn't valid. So one of the two questions, "valid?" or "satisfiable?" is immediately answered.
$endgroup$
– Andreas Blass
Jan 30 at 3:24
$begingroup$
If I were asked whether a given first-order sentence is valid and whether it is satisfiable, I might start by considering a particular structure and checking whether the sentence is true in that structure. Being lazy, I'd choose the structure to be very simple, perhaps just one element. If the formula is true in that one structure, I at least know it's satisfiable. If the formula is false in that structure, I at least know it isn't valid. So one of the two questions, "valid?" or "satisfiable?" is immediately answered.
$endgroup$
– Andreas Blass
Jan 30 at 3:24
$begingroup$
To answer the other question, I'd need to check whether some other structure gives the opposite truth value for the given sentence. That can be hard work, but in the present case it's not too bad.Think about what would have to happen in a structure to produce the opposite truth value, and try to design a structure like that. If you can't design one, look for the reason why you can't, i.e., a proof that there's no such structure.
$endgroup$
– Andreas Blass
Jan 30 at 3:28
$begingroup$
To answer the other question, I'd need to check whether some other structure gives the opposite truth value for the given sentence. That can be hard work, but in the present case it's not too bad.Think about what would have to happen in a structure to produce the opposite truth value, and try to design a structure like that. If you can't design one, look for the reason why you can't, i.e., a proof that there's no such structure.
$endgroup$
– Andreas Blass
Jan 30 at 3:28
|
show 1 more comment
1 Answer
1
active
oldest
votes
$begingroup$
By the rules I learned the sentence is not well formed, so it is neither valid nor satisfiable. The square brackets mean the existential quantifier applies to everything inside, so you can't requantify over them with the universal quantifier. It would be legal to write $exists xy P(x,y) implies forall xy P(x,y)$ but this still creates an opportunity for confusion because of the reuse of $x,y$. I find it better to write
$$exists xy P(x,y) implies forall wz P(w,z)$$
where the scope of the quantifiers is obvious. I have seen authors who specifically allow reuse of variables, but they have to be very careful about the rules for substitution. Some comments have said the rules they are used to accept your sentence, but it is equivalent to the one I set in display mode.
This makes it easier to see that the sentence is satisfiable but not valid. If $forall wz P(w,z)$ is true the implication is true as well. If $P(x,y)$ is true sometimes and false sometimes the implication is false. We could easily construct a model for each of the previous sentences to prove our claim.
answered Jan 30 at 5:12
Ross MillikanRoss Millikan
301k24200375
$endgroup$
2
$begingroup$
I slightly disagree with you there. The square bracket means: the quantifier applies to every FREE variable inside the bracket. That is, the scope of a quantifier preceding a parenthesis or a bracket does not range over variables bound by other quantifiers. You might want to change that. I hope that was useful, cheers!
$endgroup$
– Bertrand Wittgenstein's Ghost
Jan 30 at 5:20
$begingroup$
@BertrandWittgenstein'sGhost: that depends on the syntax rules you are working with. The first set I worked with forced a set of parentheses just after the quantifier to show the range of the quantifier. This would demand $exists xy (P(x,y)) implies forall wz( P(w,z))$. It seems a little clumsy, but there is good sense in it.
$endgroup$
– Ross Millikan
Jan 30 at 5:26
3
$begingroup$
I agree with @BertrandWittgenstein'sGhost -- I happened to cover this exact material in class today, and the professor allowed nested quantifiers with the innermost quantifier having precedence (equivalently, the outer quantifier only applies to free variables).
$endgroup$
– Elliot Gorokhovsky
Jan 30 at 5:29
$begingroup$
@RossMillikan I agree with your correction, but notice: $forall x,y,z[exists x_1[P(x_1,y) rightarrow P(x,z,x_1) ]]$ in this case if we separate each atomic formula into one which has its own independent quantifier, then it would not hold the same meaning.
$endgroup$
– Bertrand Wittgenstein's Ghost
Jan 30 at 5:33
1
$begingroup$
$$exists xy[P(x,y)toforall xy P(x,y)]$$ has the same meaning as $$exists xy[P(x,y)toforall uv P(u,v)]$$ or $$exists xyforall uv[P(x,y)to P(u,v)].$$
$endgroup$
– bof
Jan 30 at 8:05
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%2f3092993%2fhow-do-i-prove-whether-this-formula-is-valid-or-satisfiable-exists-xypx-y%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$
By the rules I learned the sentence is not well formed, so it is neither valid nor satisfiable. The square brackets mean the existential quantifier applies to everything inside, so you can't requantify over them with the universal quantifier. It would be legal to write $exists xy P(x,y) implies forall xy P(x,y)$ but this still creates an opportunity for confusion because of the reuse of $x,y$. I find it better to write
$$exists xy P(x,y) implies forall wz P(w,z)$$
where the scope of the quantifiers is obvious. I have seen authors who specifically allow reuse of variables, but they have to be very careful about the rules for substitution. Some comments have said the rules they are used to accept your sentence, but it is equivalent to the one I set in display mode.
This makes it easier to see that the sentence is satisfiable but not valid. If $forall wz P(w,z)$ is true the implication is true as well. If $P(x,y)$ is true sometimes and false sometimes the implication is false. We could easily construct a model for each of the previous sentences to prove our claim.
answered Jan 30 at 5:12
Ross MillikanRoss Millikan
301k24200375
$endgroup$
2
$begingroup$
I slightly disagree with you there. The square bracket means: the quantifier applies to every FREE variable inside the bracket. That is, the scope of a quantifier preceding a parenthesis or a bracket does not range over variables bound by other quantifiers. You might want to change that. I hope that was useful, cheers!
$endgroup$
– Bertrand Wittgenstein's Ghost
Jan 30 at 5:20
$begingroup$
@BertrandWittgenstein'sGhost: that depends on the syntax rules you are working with. The first set I worked with forced a set of parentheses just after the quantifier to show the range of the quantifier. This would demand $exists xy (P(x,y)) implies forall wz( P(w,z))$. It seems a little clumsy, but there is good sense in it.
$endgroup$
– Ross Millikan
Jan 30 at 5:26
3
$begingroup$
I agree with @BertrandWittgenstein'sGhost -- I happened to cover this exact material in class today, and the professor allowed nested quantifiers with the innermost quantifier having precedence (equivalently, the outer quantifier only applies to free variables).
$endgroup$
– Elliot Gorokhovsky
Jan 30 at 5:29
$begingroup$
@RossMillikan I agree with your correction, but notice: $forall x,y,z[exists x_1[P(x_1,y) rightarrow P(x,z,x_1) ]]$ in this case if we separate each atomic formula into one which has its own independent quantifier, then it would not hold the same meaning.
$endgroup$
– Bertrand Wittgenstein's Ghost
Jan 30 at 5:33
1
$begingroup$
$$exists xy[P(x,y)toforall xy P(x,y)]$$ has the same meaning as $$exists xy[P(x,y)toforall uv P(u,v)]$$ or $$exists xyforall uv[P(x,y)to P(u,v)].$$
$endgroup$
– bof
Jan 30 at 8:05
add a comment |
$begingroup$
By the rules I learned the sentence is not well formed, so it is neither valid nor satisfiable. The square brackets mean the existential quantifier applies to everything inside, so you can't requantify over them with the universal quantifier. It would be legal to write $exists xy P(x,y) implies forall xy P(x,y)$ but this still creates an opportunity for confusion because of the reuse of $x,y$. I find it better to write
$$exists xy P(x,y) implies forall wz P(w,z)$$
where the scope of the quantifiers is obvious. I have seen authors who specifically allow reuse of variables, but they have to be very careful about the rules for substitution. Some comments have said the rules they are used to accept your sentence, but it is equivalent to the one I set in display mode.
This makes it easier to see that the sentence is satisfiable but not valid. If $forall wz P(w,z)$ is true the implication is true as well. If $P(x,y)$ is true sometimes and false sometimes the implication is false. We could easily construct a model for each of the previous sentences to prove our claim.
answered Jan 30 at 5:12
Ross MillikanRoss Millikan
301k24200375
$endgroup$
2
$begingroup$
I slightly disagree with you there. The square bracket means: the quantifier applies to every FREE variable inside the bracket. That is, the scope of a quantifier preceding a parenthesis or a bracket does not range over variables bound by other quantifiers. You might want to change that. I hope that was useful, cheers!
$endgroup$
– Bertrand Wittgenstein's Ghost
Jan 30 at 5:20
$begingroup$
@BertrandWittgenstein'sGhost: that depends on the syntax rules you are working with. The first set I worked with forced a set of parentheses just after the quantifier to show the range of the quantifier. This would demand $exists xy (P(x,y)) implies forall wz( P(w,z))$. It seems a little clumsy, but there is good sense in it.
$endgroup$
– Ross Millikan
Jan 30 at 5:26
3
$begingroup$
I agree with @BertrandWittgenstein'sGhost -- I happened to cover this exact material in class today, and the professor allowed nested quantifiers with the innermost quantifier having precedence (equivalently, the outer quantifier only applies to free variables).
$endgroup$
– Elliot Gorokhovsky
Jan 30 at 5:29
$begingroup$
@RossMillikan I agree with your correction, but notice: $forall x,y,z[exists x_1[P(x_1,y) rightarrow P(x,z,x_1) ]]$ in this case if we separate each atomic formula into one which has its own independent quantifier, then it would not hold the same meaning.
$endgroup$
– Bertrand Wittgenstein's Ghost
Jan 30 at 5:33
1
$begingroup$
$$exists xy[P(x,y)toforall xy P(x,y)]$$ has the same meaning as $$exists xy[P(x,y)toforall uv P(u,v)]$$ or $$exists xyforall uv[P(x,y)to P(u,v)].$$
$endgroup$
– bof
Jan 30 at 8:05
add a comment |
$begingroup$
By the rules I learned the sentence is not well formed, so it is neither valid nor satisfiable. The square brackets mean the existential quantifier applies to everything inside, so you can't requantify over them with the universal quantifier. It would be legal to write $exists xy P(x,y) implies forall xy P(x,y)$ but this still creates an opportunity for confusion because of the reuse of $x,y$. I find it better to write
$$exists xy P(x,y) implies forall wz P(w,z)$$
where the scope of the quantifiers is obvious. I have seen authors who specifically allow reuse of variables, but they have to be very careful about the rules for substitution. Some comments have said the rules they are used to accept your sentence, but it is equivalent to the one I set in display mode.
This makes it easier to see that the sentence is satisfiable but not valid. If $forall wz P(w,z)$ is true the implication is true as well. If $P(x,y)$ is true sometimes and false sometimes the implication is false. We could easily construct a model for each of the previous sentences to prove our claim.
answered Jan 30 at 5:12
Ross MillikanRoss Millikan
301k24200375
$endgroup$
By the rules I learned the sentence is not well formed, so it is neither valid nor satisfiable. The square brackets mean the existential quantifier applies to everything inside, so you can't requantify over them with the universal quantifier. It would be legal to write $exists xy P(x,y) implies forall xy P(x,y)$ but this still creates an opportunity for confusion because of the reuse of $x,y$. I find it better to write
$$exists xy P(x,y) implies forall wz P(w,z)$$
where the scope of the quantifiers is obvious. I have seen authors who specifically allow reuse of variables, but they have to be very careful about the rules for substitution. Some comments have said the rules they are used to accept your sentence, but it is equivalent to the one I set in display mode.
This makes it easier to see that the sentence is satisfiable but not valid. If $forall wz P(w,z)$ is true the implication is true as well. If $P(x,y)$ is true sometimes and false sometimes the implication is false. We could easily construct a model for each of the previous sentences to prove our claim.
answered Jan 30 at 5:12
Ross MillikanRoss Millikan
301k24200375
edited Jan 30 at 5:34
answered Jan 30 at 5:12
Ross MillikanRoss Millikan
301k24200375
answered Jan 30 at 5:12
Ross MillikanRoss Millikan
301k24200375
answered Jan 30 at 5:12
Ross MillikanRoss Millikan
301k24200375
301k24200375
2
$begingroup$
I slightly disagree with you there. The square bracket means: the quantifier applies to every FREE variable inside the bracket. That is, the scope of a quantifier preceding a parenthesis or a bracket does not range over variables bound by other quantifiers. You might want to change that. I hope that was useful, cheers!
$endgroup$
– Bertrand Wittgenstein's Ghost
Jan 30 at 5:20
$begingroup$
@BertrandWittgenstein'sGhost: that depends on the syntax rules you are working with. The first set I worked with forced a set of parentheses just after the quantifier to show the range of the quantifier. This would demand $exists xy (P(x,y)) implies forall wz( P(w,z))$. It seems a little clumsy, but there is good sense in it.
$endgroup$
– Ross Millikan
Jan 30 at 5:26
3
$begingroup$
I agree with @BertrandWittgenstein'sGhost -- I happened to cover this exact material in class today, and the professor allowed nested quantifiers with the innermost quantifier having precedence (equivalently, the outer quantifier only applies to free variables).
$endgroup$
– Elliot Gorokhovsky
Jan 30 at 5:29
$begingroup$
@RossMillikan I agree with your correction, but notice: $forall x,y,z[exists x_1[P(x_1,y) rightarrow P(x,z,x_1) ]]$ in this case if we separate each atomic formula into one which has its own independent quantifier, then it would not hold the same meaning.
$endgroup$
– Bertrand Wittgenstein's Ghost
Jan 30 at 5:33
1
$begingroup$
$$exists xy[P(x,y)toforall xy P(x,y)]$$ has the same meaning as $$exists xy[P(x,y)toforall uv P(u,v)]$$ or $$exists xyforall uv[P(x,y)to P(u,v)].$$
$endgroup$
– bof
Jan 30 at 8:05
add a comment |
2
$begingroup$
I slightly disagree with you there. The square bracket means: the quantifier applies to every FREE variable inside the bracket. That is, the scope of a quantifier preceding a parenthesis or a bracket does not range over variables bound by other quantifiers. You might want to change that. I hope that was useful, cheers!
$endgroup$
– Bertrand Wittgenstein's Ghost
Jan 30 at 5:20
$begingroup$
@BertrandWittgenstein'sGhost: that depends on the syntax rules you are working with. The first set I worked with forced a set of parentheses just after the quantifier to show the range of the quantifier. This would demand $exists xy (P(x,y)) implies forall wz( P(w,z))$. It seems a little clumsy, but there is good sense in it.
$endgroup$
– Ross Millikan
Jan 30 at 5:26
3
$begingroup$
I agree with @BertrandWittgenstein'sGhost -- I happened to cover this exact material in class today, and the professor allowed nested quantifiers with the innermost quantifier having precedence (equivalently, the outer quantifier only applies to free variables).
$endgroup$
– Elliot Gorokhovsky
Jan 30 at 5:29
$begingroup$
@RossMillikan I agree with your correction, but notice: $forall x,y,z[exists x_1[P(x_1,y) rightarrow P(x,z,x_1) ]]$ in this case if we separate each atomic formula into one which has its own independent quantifier, then it would not hold the same meaning.
$endgroup$
– Bertrand Wittgenstein's Ghost
Jan 30 at 5:33
1
$begingroup$
$$exists xy[P(x,y)toforall xy P(x,y)]$$ has the same meaning as $$exists xy[P(x,y)toforall uv P(u,v)]$$ or $$exists xyforall uv[P(x,y)to P(u,v)].$$
$endgroup$
– bof
Jan 30 at 8:05
2
2
$begingroup$
I slightly disagree with you there. The square bracket means: the quantifier applies to every FREE variable inside the bracket. That is, the scope of a quantifier preceding a parenthesis or a bracket does not range over variables bound by other quantifiers. You might want to change that. I hope that was useful, cheers!
$endgroup$
– Bertrand Wittgenstein's Ghost
Jan 30 at 5:20
$begingroup$
I slightly disagree with you there. The square bracket means: the quantifier applies to every FREE variable inside the bracket. That is, the scope of a quantifier preceding a parenthesis or a bracket does not range over variables bound by other quantifiers. You might want to change that. I hope that was useful, cheers!
$endgroup$
– Bertrand Wittgenstein's Ghost
Jan 30 at 5:20
$begingroup$
@BertrandWittgenstein'sGhost: that depends on the syntax rules you are working with. The first set I worked with forced a set of parentheses just after the quantifier to show the range of the quantifier. This would demand $exists xy (P(x,y)) implies forall wz( P(w,z))$. It seems a little clumsy, but there is good sense in it.
$endgroup$
– Ross Millikan
Jan 30 at 5:26
$begingroup$
@BertrandWittgenstein'sGhost: that depends on the syntax rules you are working with. The first set I worked with forced a set of parentheses just after the quantifier to show the range of the quantifier. This would demand $exists xy (P(x,y)) implies forall wz( P(w,z))$. It seems a little clumsy, but there is good sense in it.
$endgroup$
– Ross Millikan
Jan 30 at 5:26
3
3
$begingroup$
I agree with @BertrandWittgenstein'sGhost -- I happened to cover this exact material in class today, and the professor allowed nested quantifiers with the innermost quantifier having precedence (equivalently, the outer quantifier only applies to free variables).
$endgroup$
– Elliot Gorokhovsky
Jan 30 at 5:29
$begingroup$
I agree with @BertrandWittgenstein'sGhost -- I happened to cover this exact material in class today, and the professor allowed nested quantifiers with the innermost quantifier having precedence (equivalently, the outer quantifier only applies to free variables).
$endgroup$
– Elliot Gorokhovsky
Jan 30 at 5:29
$begingroup$
@RossMillikan I agree with your correction, but notice: $forall x,y,z[exists x_1[P(x_1,y) rightarrow P(x,z,x_1) ]]$ in this case if we separate each atomic formula into one which has its own independent quantifier, then it would not hold the same meaning.
$endgroup$
– Bertrand Wittgenstein's Ghost
Jan 30 at 5:33
$begingroup$
@RossMillikan I agree with your correction, but notice: $forall x,y,z[exists x_1[P(x_1,y) rightarrow P(x,z,x_1) ]]$ in this case if we separate each atomic formula into one which has its own independent quantifier, then it would not hold the same meaning.
$endgroup$
– Bertrand Wittgenstein's Ghost
Jan 30 at 5:33
1
1
$begingroup$
$$exists xy[P(x,y)toforall xy P(x,y)]$$ has the same meaning as $$exists xy[P(x,y)toforall uv P(u,v)]$$ or $$exists xyforall uv[P(x,y)to P(u,v)].$$
$endgroup$
– bof
Jan 30 at 8:05
$begingroup$
$$exists xy[P(x,y)toforall xy P(x,y)]$$ has the same meaning as $$exists xy[P(x,y)toforall uv P(u,v)]$$ or $$exists xyforall uv[P(x,y)to P(u,v)].$$
$endgroup$
– bof
Jan 30 at 8:05
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%2f3092993%2fhow-do-i-prove-whether-this-formula-is-valid-or-satisfiable-exists-xypx-y%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
$begingroup$
This is called the drinkers paradox. Either $exists xy .Pxy$ or $lnot exists xy .Pxy$
$endgroup$
– DanielV
Jan 30 at 2:10
$begingroup$
Thanks for pointing this out. Is the proof meant to be in natural language form or is there a mathematical proof for this?
$endgroup$
– oldselflearner1959
Jan 30 at 2:16
$begingroup$
That is for you to decide.
$endgroup$
– DanielV
Jan 30 at 2:17
1
$begingroup$
If I were asked whether a given first-order sentence is valid and whether it is satisfiable, I might start by considering a particular structure and checking whether the sentence is true in that structure. Being lazy, I'd choose the structure to be very simple, perhaps just one element. If the formula is true in that one structure, I at least know it's satisfiable. If the formula is false in that structure, I at least know it isn't valid. So one of the two questions, "valid?" or "satisfiable?" is immediately answered.
$endgroup$
– Andreas Blass
Jan 30 at 3:24
$begingroup$
To answer the other question, I'd need to check whether some other structure gives the opposite truth value for the given sentence. That can be hard work, but in the present case it's not too bad.Think about what would have to happen in a structure to produce the opposite truth value, and try to design a structure like that. If you can't design one, look for the reason why you can't, i.e., a proof that there's no such structure.
$endgroup$
– Andreas Blass
Jan 30 at 3:28