Commutative quantifiersWrite statements using quantifiersQuestion About Notation Nested Quantifiers.Understanding Scope of QuantifiersSwapping first- and second-order quantifiersEliminating any subset of quantifiers by Skolemization: no constants, please!Proofs involving multiple quantifiers?Order of three or more quantifiersHow are quantifiers managed in truth tables?How to express propositional functions with multiple quantifiers using “AND” and "OR'?Determining if propositions with quantifiers are the same
Light propagating through a sound wave
What does Deadpool mean by "left the house in that shirt"?
How can an organ that provides biological immortality be unable to regenerate?
Can you move over difficult terrain with only 5 feet of movement?
Should I use acronyms in dialogues before telling the readers what it stands for in fiction?
Does multi-classing into Fighter give you heavy armor proficiency?
Generic TVP tradeoffs?
Suggestions on how to spend Shaabath (constructively) alone
Is there a term for accumulated dirt on the outside of your hands and feet?
Probably overheated black color SMD pads
Help rendering a complicated sum/product formula
Why didn't Héctor fade away after this character died in the movie Coco?
Turning a hard to access nut?
How to terminate ping <dest> &
Print a physical multiplication table
Bash - pair each line of file
Variable completely messes up echoed string
How do hiring committees for research positions view getting "scooped"?
Are dual Irish/British citizens bound by the 90/180 day rule when travelling in the EU after Brexit?
In what cases must I use 了 and in what cases not?
Differential and Linear trail propagation in Noekeon
Does the attack bonus from a Masterwork weapon stack with the attack bonus from Masterwork ammunition?
Does .bashrc contain syntax errors?
Is it possible to stack the damage done by the Absorb Elements spell?
Commutative quantifiers
Write statements using quantifiersQuestion About Notation Nested Quantifiers.Understanding Scope of QuantifiersSwapping first- and second-order quantifiersEliminating any subset of quantifiers by Skolemization: no constants, please!Proofs involving multiple quantifiers?Order of three or more quantifiersHow are quantifiers managed in truth tables?How to express propositional functions with multiple quantifiers using “AND” and "OR'?Determining if propositions with quantifiers are the same
$begingroup$
If I have a proposition of the form $$(forall x in X) (exists y in Y) (forall r in R) , P(x,y,r)$$ where at least any number of $X$, $Y$ and $R$ can be the same. Is that logically equivalent to the following?
$$(forall r in R) (forall x in X) (exists y in Y) , P(x,y,r)$$
where $P(x,y,r)$ is any proposition (possibly an implication). How would I prove it, if it's possible? Properties of quantifiers can't be proven through truth tables, so how would I start to approach this sort of problem?
logic predicate-logic quantifiers
edited Mar 13 at 18:50
Rodrigo de Azevedo
13.1k41960
asked Mar 12 at 19:49
topologicalmagiciantopologicalmagician
1019
$endgroup$
add a comment |
$begingroup$
If I have a proposition of the form $$(forall x in X) (exists y in Y) (forall r in R) , P(x,y,r)$$ where at least any number of $X$, $Y$ and $R$ can be the same. Is that logically equivalent to the following?
$$(forall r in R) (forall x in X) (exists y in Y) , P(x,y,r)$$
where $P(x,y,r)$ is any proposition (possibly an implication). How would I prove it, if it's possible? Properties of quantifiers can't be proven through truth tables, so how would I start to approach this sort of problem?
logic predicate-logic quantifiers
edited Mar 13 at 18:50
Rodrigo de Azevedo
13.1k41960
asked Mar 12 at 19:49
topologicalmagiciantopologicalmagician
1019
$endgroup$
1
$begingroup$
I love this question! Seems intuitive that the two statements are logically equivalent, but how to prove it using the axioms?
$endgroup$
– Mark Fischler
Mar 12 at 19:59
$begingroup$
@MarkFischler correct, that's what i'm curious about. Im not sure how to prove it if its true. If its not true, I would like to know under what conditions is it true.
$endgroup$
– topologicalmagician
Mar 12 at 20:04
add a comment |
$begingroup$
If I have a proposition of the form $$(forall x in X) (exists y in Y) (forall r in R) , P(x,y,r)$$ where at least any number of $X$, $Y$ and $R$ can be the same. Is that logically equivalent to the following?
$$(forall r in R) (forall x in X) (exists y in Y) , P(x,y,r)$$
where $P(x,y,r)$ is any proposition (possibly an implication). How would I prove it, if it's possible? Properties of quantifiers can't be proven through truth tables, so how would I start to approach this sort of problem?
logic predicate-logic quantifiers
edited Mar 13 at 18:50
Rodrigo de Azevedo
13.1k41960
asked Mar 12 at 19:49
topologicalmagiciantopologicalmagician
1019
$endgroup$
If I have a proposition of the form $$(forall x in X) (exists y in Y) (forall r in R) , P(x,y,r)$$ where at least any number of $X$, $Y$ and $R$ can be the same. Is that logically equivalent to the following?
$$(forall r in R) (forall x in X) (exists y in Y) , P(x,y,r)$$
where $P(x,y,r)$ is any proposition (possibly an implication). How would I prove it, if it's possible? Properties of quantifiers can't be proven through truth tables, so how would I start to approach this sort of problem?
logic predicate-logic quantifiers
logic predicate-logic quantifiers
edited Mar 13 at 18:50
Rodrigo de Azevedo
13.1k41960
asked Mar 12 at 19:49
topologicalmagiciantopologicalmagician
1019
edited Mar 13 at 18:50
Rodrigo de Azevedo
13.1k41960
asked Mar 12 at 19:49
topologicalmagiciantopologicalmagician
1019
edited Mar 13 at 18:50
Rodrigo de Azevedo
13.1k41960
edited Mar 13 at 18:50
Rodrigo de Azevedo
13.1k41960
edited Mar 13 at 18:50
Rodrigo de Azevedo
13.1k41960
13.1k41960
asked Mar 12 at 19:49
topologicalmagiciantopologicalmagician
1019
asked Mar 12 at 19:49
topologicalmagiciantopologicalmagician
1019
asked Mar 12 at 19:49
topologicalmagiciantopologicalmagician
1019
1019
1
$begingroup$
I love this question! Seems intuitive that the two statements are logically equivalent, but how to prove it using the axioms?
$endgroup$
– Mark Fischler
Mar 12 at 19:59
$begingroup$
@MarkFischler correct, that's what i'm curious about. Im not sure how to prove it if its true. If its not true, I would like to know under what conditions is it true.
$endgroup$
– topologicalmagician
Mar 12 at 20:04
add a comment |
1
$begingroup$
I love this question! Seems intuitive that the two statements are logically equivalent, but how to prove it using the axioms?
$endgroup$
– Mark Fischler
Mar 12 at 19:59
$begingroup$
@MarkFischler correct, that's what i'm curious about. Im not sure how to prove it if its true. If its not true, I would like to know under what conditions is it true.
$endgroup$
– topologicalmagician
Mar 12 at 20:04
1
1
$begingroup$
I love this question! Seems intuitive that the two statements are logically equivalent, but how to prove it using the axioms?
$endgroup$
– Mark Fischler
Mar 12 at 19:59
$begingroup$
I love this question! Seems intuitive that the two statements are logically equivalent, but how to prove it using the axioms?
$endgroup$
– Mark Fischler
Mar 12 at 19:59
$begingroup$
@MarkFischler correct, that's what i'm curious about. Im not sure how to prove it if its true. If its not true, I would like to know under what conditions is it true.
$endgroup$
– topologicalmagician
Mar 12 at 20:04
$begingroup$
@MarkFischler correct, that's what i'm curious about. Im not sure how to prove it if its true. If its not true, I would like to know under what conditions is it true.
$endgroup$
– topologicalmagician
Mar 12 at 20:04
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
No, the statements are not equivalent. In general, quantifiers of the same type are commutative ($forall x forall y phi equiv forall y forall x phi$; $exists x exists y phi equiv exists y exists x phi$), but quantifiers of two different types are not ($forall x exists y not equiv exists y forall x$).
To illustrate this, consider the simple example:
For all tupperware boxes there is a lid that fits it.
This can be formalized as
(1) $forall x (box(x) to exists y (lid(y) land fit(y,x)))$
Or, using the abbreviations you made use of in your formula$^1$,
$forall x in box exists y in lid, fit(y,x)$
Unfortunately, from this we can not conclude that there is a magical lid that fits all tupperware boxes:
(2) $not vDash exists y forall x (box(x) to (lid(y) land fit(y,x)))$
(Usually, the case is rather that there are alwyays somehow more lids than tupperware boxes, but still you can't find a suitable lid for all your boxes...)
So $forall x exists y phi not vDash exists y forall x phi$. This can be shown by providing a simple model that satisfies that first but not the second formula.
The reverse direction does hold: If there were a magical lid that is compatible with all tupperware boxes, then of course every tupperware box would have a matching lid.
So $exists y forall x phi vDash forall x exists y phi$. You can prove this by making an argument about about how quantified formulas are satisfied semantically, or by a formal proof in some system like natural deduction for predicate logic, employing soundness of this system.
That (1) $not vDash$ (2) but (2) $vDash$ (1) means that (2) is a stronger statement: Any situation in which (2) holds is one where (1) is also true, but there are situations in which (1) is true but (2) is not, because (2) is a stronger constraint on the valid models.
The same reasoning now applies to your formula that involves three quantifications: While it is okay to swap the order of $forall x$ and $forall r$, moving $forall r$ in front of $exists y$ is not. This makes for a weaker statement: Saying that for all $r in R$ we can find some $y in Y$ that satisfies $P(x,y,r)$ is a less strict requirement and will hence have models that don't satisfy the original stronger claim that there must be a particular $y in Y$ that works for all $r in R$.
Since $forall r in R forall x in X exists y in Y ,P(x,y,r) not models forall x in X exists y in Y forall r in R ,P(x,y,r)$ but $forall x in X exists y in Y forall r in R ,P(x,y,r) models forall r in R forall x in X exists y in Y ,P(x,y,r)$, if you are convinced that your second formulation does the job, you can use this one, and all the models that were compatible with your first formalization will also be permitted by your second formalization. But they are not logically equivalent: Depending on what you want to describe/to which models you want to restrict yourself to with your proposition, your second formalization might be too weak, in that it in addition permits models that would contradict the first formalization - at least it is in the general case. (I would have to get a better understanding of your predicate to be able to tell whether your second, weaker version is still strong enough for what you want to express).
To show that the two formulas are not equivalent, consider a simple model:
$$mathfrakA = langle mathcalA, mathcalI rangle$$ with
$$mathcalA = x1, y1, y2, r1, r2$$
$$mathcalI(X) = x1;\
mathcalI(Y) = y1, y2;\
mathcalI(R) = r1, r2;\
mathcalI(P) = langle x1, y1, r1 rangle, langle x1, y2, r2 rangle$$
$mathfrakA models forall r in R forall x in X exists y in Y P(x,y,r)$ (your second formalization): For each r and for each thing in x (there is just one, to make things simpler) we can find find some element y that goes in the triple: For $r1$, we have $y1$, and for $r2$, we find $y2$.
But $mathfrakA not models forall x in X exists y in Y forall r in R P(x,y,r)$ (your first formalization), because for our one $x$, there is no thing in $Y$ that works for all the $r$.
Since there is a model that satisfies the second but not the first formula, they are not equivalent.
$^1$ Technically, $forall x in X exists y in Y phi$ is not a syntactically valid first-order formula, but it's a very common abbrevation for $forall x (x in X to exists y (y in Y land phi))$. I'm using this latter explicit syntax to hopefully give a better understanding of why a formula is or is not satisfied by a model.
answered Mar 12 at 21:04
lemontreelemontree
1,177622
$endgroup$
$begingroup$
Comments are not for extended discussion; this conversation has been moved to chat.
$endgroup$
– Pedro Tamaroff♦
Mar 13 at 10:52
add a comment |
$begingroup$
If I have a proposition of the form $forall x in X exists y in Y forall r in R P(x,y,r)$ where at least any number of Y,X and R can be the same. Is that logically equivalent to $forall r in R forall x in X exists y in Y P(x,y,r)$ ?
No. The former implies the latter but is not equivalent to it.
You have $forall xinmathrm X~~exists yinmathrm Y~~forall rinmathrm R~~P(x,y,r)$ where $P$ is a generic relation.
Now $exists y~forall r~phi$ entails $forall r~exists y~phi$. If something holds for every $r$ of a particular $y$, then something holds for some $y$ of any $r$.
- "There is a column where every row contains a letter", entails that "Every row has a column which contains a letter."
However, the converse is not so.
- "Every row has a column which contains a letter," does not logically entail "There is a column where every row contains a letter." For instance, when every row may have a distinct column containing its letter, then the first statement is satisfied while the second is not.
So $forall xinmathrm X~~forall rinmathrm R~~exists yinmathrm Y~~P(x,y,r)$ is entailed by the original sentence, but is not equivalent to it.
This can be broken into two steps.
$forall x ~forall r~phi$ entails and is entailed by $forall r~forall x~phi$. So the previous statement is equivalent to the desired result. However the original statement only entails them. $$forall xinmathrm X~~exists yinmathrm Y~~forall rinmathrm R~~P(x,y,r)\Downarrow\forall xinmathrm X~~forall rinmathrm R~~exists yinmathrm Y~~P(x,y,r)\Updownarrow\forall rinmathrm R~~forall xinmathrm X~~exists yinmathrm Y~~P(x,y,r)$$
answered Mar 12 at 23:48
Graham KempGraham Kemp
86.8k43579
$endgroup$
add a comment |
$begingroup$
ADDED LAST
The final word is that lemontree's answer was right and mine was wrong; I have left the original in place below.
A good example of the in-equivalence, is to let the domains of discourse
$X$, $Y$, and $R$ be the reals, and consider the proposition $P(x,y,z)$ to be
$$ (x=0) vee
((y in Bbb Q) wedge (|y-sqrt2| lt |x|) wedge (|ry-rsqrt2| lt |rx|))
$$
Then the first statement $forall xleft( exists y forall r P(x,y,r) right)$
reads in English as "for any given real non-zero $x$ there exists some rational $y$ such that for all real $r$ the absolute difference between $y$ and $sqrt2$ is less than $|x|$ (and when both sides of that inequality are multiplied by $R$ it still holds). This is obviously true, since arbitrarily good rational approximations to $sqrt2$ can be found.
But the second statement $forall rleft( exists y forall x P(x,y,r) right)$
reads "for every real $r$, there exists some rational $y$ such that for any arbitrary non-zero $x$ the absolute difference between $y$ and $sqrt2$ is less than $|x|$ (and another clause)." That is obviously not true, because there is no rational approximation to $sqrt2$ that is closer than any arbitrarly chosen $x$.
Thus the two statements are not logically equivalent.
ORIGINAL ANSWER
In a logic system that allows Skolemization, you can apply this second-order equivalence (see https://en.wikipedia.org/wiki/Skolem_normal_form):
$$
forall xleft( R(g(x)) vee exists yR(x,y)right) Longleftrightarrow exists fforall x left( R(g(x)) vee R(x,f(x))right)
$$
where $f(x)$ is a function that maps $x$ to $y$.
Our application of this is a specialization which is a considerable simplification: Let
$R(g(x)) = F$ (False) and $F(x,f(x)$ be $forall r P(x,f(x),r)$. Then the equivalence reads
$$
forall xleft( exists y forall r P(x,y,r) right) Longleftrightarrow exists fforall x left( forall r P(x,f(x),r)right)
$$
Here I have omitted the domain designations, that is, $forall x$ means $forall x in X$ and $exists y$ means $exists y in Y$.
And now we can commute $forall x forall r$ because an axiom says that
$forall x forall r, P$ is identical to $forall r forall x, P$, thus
$$exists fforall x forall r P(x,f(x),r) Longleftrightarrow
exists fforall r forall x P(x,f(x),r) Longleftrightarrow
forall rleft( exists y forall x P(x,y,r) right)
$$
Added later:
OMG, I didn't have to go into this detail, because (assuming the Skolem_normal_form page is correct) they give an example that is precisely the case in the problem! To quote:
As an example, the formula $forall x exists y forall z P(x,y,z)$ is not in Skolem normal form because it contains the existential quatifier $exists y$.
Skolemization replaces $y$ with $f(x) ldots$ and removes the quantification over $y$. The resulting formula is $forall x forall z P(x,f(x),z)$. $ldots$ The formula obtained by this transformation is satisfiable if and only if the original formula is.
(Emphasis mine). So we can now go over to $forall x forall z P(x,f(x),z)
equiv forall z forall x P(x,f(x),z)$ and from there, use the "if and only if" property to go to the equivalent $forall z exists y forall x P(x,y,z)$
The use of the function $f(x)$ might imply that this reasoning depends on having the axiom of choice.
To extend/use the @lemontree example:
Let $P(x,y,r)$ be "lid $r$ fits every tupperware that is in the same house ($x$) as this tupperware box $y$.
Then the question becomes whether these statements are identical:
- For all houses, there is some lid that fits every tupperware in the house.
- For every tupperware, there exists some lid that fits (it and) every tupperware in the same house.
I claim they are logically equivalent.
answered Mar 12 at 21:04
Mark FischlerMark Fischler
33.5k12452
$endgroup$
2
$begingroup$
Skolemization preserves satisfiability (If $phi$ is satisfiable, then its skolem normal form is), but the skolemized formula is in the general case not logically equivalent to the original formula, which is what OP asked for.
$endgroup$
– lemontree
Mar 12 at 21:08
2
$begingroup$
The equivalence you are probably referring to is a second-order equivalence: It is an equivalence relation between properties of first-order formula - namely that that the Skolem normal form is satisfiable iff the original formula is satisfiable. This is not the same as logical equivalence between formulas of first-order logic. The Wikipedia article actually states that "The resulting formula is not necessarily equivalent to the original one, but is equisatisfiable with it".
$endgroup$
– lemontree
Mar 12 at 21:20
3
$begingroup$
I'm sorry, but still no, @both Mark Fischler und topologicalmagician, they are not equivalent. They are only equisatisfiable. This is not the same. There might well be some models/interpretations of P under which they have the same truth value, like in the interpretation you provided in your edit, but this is is no proof that they are logically equivalent, which by definition means true in all the same models/interpretations of the predicate symbols.
$endgroup$
– lemontree
Mar 12 at 22:29
2
$begingroup$
There are models/interpretations in which the one holds while the other one doesn't, like the simple model for the P predicate I edited into my post, and if there is at least model that satisfies the one but not the other formula, then - by the definition of logical equivalence - the two formulas are not equivalent. Providing one counter-model is proof enough that a logical equivalence (a universal quantification) does not hold. On the other hand, providing one interpretation of P is not an appropriate means to prove that a logical equivalence does hold.
$endgroup$
– lemontree
Mar 12 at 22:30
2
$begingroup$
@lemontree Your patience is admirable!
$endgroup$
– Alex Kruckman
Mar 12 at 23:32
|
show 6 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%2f3145588%2fcommutative-quantifiers%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
No, the statements are not equivalent. In general, quantifiers of the same type are commutative ($forall x forall y phi equiv forall y forall x phi$; $exists x exists y phi equiv exists y exists x phi$), but quantifiers of two different types are not ($forall x exists y not equiv exists y forall x$).
To illustrate this, consider the simple example:
For all tupperware boxes there is a lid that fits it.
This can be formalized as
(1) $forall x (box(x) to exists y (lid(y) land fit(y,x)))$
Or, using the abbreviations you made use of in your formula$^1$,
$forall x in box exists y in lid, fit(y,x)$
Unfortunately, from this we can not conclude that there is a magical lid that fits all tupperware boxes:
(2) $not vDash exists y forall x (box(x) to (lid(y) land fit(y,x)))$
(Usually, the case is rather that there are alwyays somehow more lids than tupperware boxes, but still you can't find a suitable lid for all your boxes...)
So $forall x exists y phi not vDash exists y forall x phi$. This can be shown by providing a simple model that satisfies that first but not the second formula.
The reverse direction does hold: If there were a magical lid that is compatible with all tupperware boxes, then of course every tupperware box would have a matching lid.
So $exists y forall x phi vDash forall x exists y phi$. You can prove this by making an argument about about how quantified formulas are satisfied semantically, or by a formal proof in some system like natural deduction for predicate logic, employing soundness of this system.
That (1) $not vDash$ (2) but (2) $vDash$ (1) means that (2) is a stronger statement: Any situation in which (2) holds is one where (1) is also true, but there are situations in which (1) is true but (2) is not, because (2) is a stronger constraint on the valid models.
The same reasoning now applies to your formula that involves three quantifications: While it is okay to swap the order of $forall x$ and $forall r$, moving $forall r$ in front of $exists y$ is not. This makes for a weaker statement: Saying that for all $r in R$ we can find some $y in Y$ that satisfies $P(x,y,r)$ is a less strict requirement and will hence have models that don't satisfy the original stronger claim that there must be a particular $y in Y$ that works for all $r in R$.
Since $forall r in R forall x in X exists y in Y ,P(x,y,r) not models forall x in X exists y in Y forall r in R ,P(x,y,r)$ but $forall x in X exists y in Y forall r in R ,P(x,y,r) models forall r in R forall x in X exists y in Y ,P(x,y,r)$, if you are convinced that your second formulation does the job, you can use this one, and all the models that were compatible with your first formalization will also be permitted by your second formalization. But they are not logically equivalent: Depending on what you want to describe/to which models you want to restrict yourself to with your proposition, your second formalization might be too weak, in that it in addition permits models that would contradict the first formalization - at least it is in the general case. (I would have to get a better understanding of your predicate to be able to tell whether your second, weaker version is still strong enough for what you want to express).
To show that the two formulas are not equivalent, consider a simple model:
$$mathfrakA = langle mathcalA, mathcalI rangle$$ with
$$mathcalA = x1, y1, y2, r1, r2$$
$$mathcalI(X) = x1;\
mathcalI(Y) = y1, y2;\
mathcalI(R) = r1, r2;\
mathcalI(P) = langle x1, y1, r1 rangle, langle x1, y2, r2 rangle$$
$mathfrakA models forall r in R forall x in X exists y in Y P(x,y,r)$ (your second formalization): For each r and for each thing in x (there is just one, to make things simpler) we can find find some element y that goes in the triple: For $r1$, we have $y1$, and for $r2$, we find $y2$.
But $mathfrakA not models forall x in X exists y in Y forall r in R P(x,y,r)$ (your first formalization), because for our one $x$, there is no thing in $Y$ that works for all the $r$.
Since there is a model that satisfies the second but not the first formula, they are not equivalent.
$^1$ Technically, $forall x in X exists y in Y phi$ is not a syntactically valid first-order formula, but it's a very common abbrevation for $forall x (x in X to exists y (y in Y land phi))$. I'm using this latter explicit syntax to hopefully give a better understanding of why a formula is or is not satisfied by a model.
answered Mar 12 at 21:04
lemontreelemontree
1,177622
$endgroup$
$begingroup$
Comments are not for extended discussion; this conversation has been moved to chat.
$endgroup$
– Pedro Tamaroff♦
Mar 13 at 10:52
add a comment |
$begingroup$
No, the statements are not equivalent. In general, quantifiers of the same type are commutative ($forall x forall y phi equiv forall y forall x phi$; $exists x exists y phi equiv exists y exists x phi$), but quantifiers of two different types are not ($forall x exists y not equiv exists y forall x$).
To illustrate this, consider the simple example:
For all tupperware boxes there is a lid that fits it.
This can be formalized as
(1) $forall x (box(x) to exists y (lid(y) land fit(y,x)))$
Or, using the abbreviations you made use of in your formula$^1$,
$forall x in box exists y in lid, fit(y,x)$
Unfortunately, from this we can not conclude that there is a magical lid that fits all tupperware boxes:
(2) $not vDash exists y forall x (box(x) to (lid(y) land fit(y,x)))$
(Usually, the case is rather that there are alwyays somehow more lids than tupperware boxes, but still you can't find a suitable lid for all your boxes...)
So $forall x exists y phi not vDash exists y forall x phi$. This can be shown by providing a simple model that satisfies that first but not the second formula.
The reverse direction does hold: If there were a magical lid that is compatible with all tupperware boxes, then of course every tupperware box would have a matching lid.
So $exists y forall x phi vDash forall x exists y phi$. You can prove this by making an argument about about how quantified formulas are satisfied semantically, or by a formal proof in some system like natural deduction for predicate logic, employing soundness of this system.
That (1) $not vDash$ (2) but (2) $vDash$ (1) means that (2) is a stronger statement: Any situation in which (2) holds is one where (1) is also true, but there are situations in which (1) is true but (2) is not, because (2) is a stronger constraint on the valid models.
The same reasoning now applies to your formula that involves three quantifications: While it is okay to swap the order of $forall x$ and $forall r$, moving $forall r$ in front of $exists y$ is not. This makes for a weaker statement: Saying that for all $r in R$ we can find some $y in Y$ that satisfies $P(x,y,r)$ is a less strict requirement and will hence have models that don't satisfy the original stronger claim that there must be a particular $y in Y$ that works for all $r in R$.
Since $forall r in R forall x in X exists y in Y ,P(x,y,r) not models forall x in X exists y in Y forall r in R ,P(x,y,r)$ but $forall x in X exists y in Y forall r in R ,P(x,y,r) models forall r in R forall x in X exists y in Y ,P(x,y,r)$, if you are convinced that your second formulation does the job, you can use this one, and all the models that were compatible with your first formalization will also be permitted by your second formalization. But they are not logically equivalent: Depending on what you want to describe/to which models you want to restrict yourself to with your proposition, your second formalization might be too weak, in that it in addition permits models that would contradict the first formalization - at least it is in the general case. (I would have to get a better understanding of your predicate to be able to tell whether your second, weaker version is still strong enough for what you want to express).
To show that the two formulas are not equivalent, consider a simple model:
$$mathfrakA = langle mathcalA, mathcalI rangle$$ with
$$mathcalA = x1, y1, y2, r1, r2$$
$$mathcalI(X) = x1;\
mathcalI(Y) = y1, y2;\
mathcalI(R) = r1, r2;\
mathcalI(P) = langle x1, y1, r1 rangle, langle x1, y2, r2 rangle$$
$mathfrakA models forall r in R forall x in X exists y in Y P(x,y,r)$ (your second formalization): For each r and for each thing in x (there is just one, to make things simpler) we can find find some element y that goes in the triple: For $r1$, we have $y1$, and for $r2$, we find $y2$.
But $mathfrakA not models forall x in X exists y in Y forall r in R P(x,y,r)$ (your first formalization), because for our one $x$, there is no thing in $Y$ that works for all the $r$.
Since there is a model that satisfies the second but not the first formula, they are not equivalent.
$^1$ Technically, $forall x in X exists y in Y phi$ is not a syntactically valid first-order formula, but it's a very common abbrevation for $forall x (x in X to exists y (y in Y land phi))$. I'm using this latter explicit syntax to hopefully give a better understanding of why a formula is or is not satisfied by a model.
answered Mar 12 at 21:04
lemontreelemontree
1,177622
$endgroup$
$begingroup$
Comments are not for extended discussion; this conversation has been moved to chat.
$endgroup$
– Pedro Tamaroff♦
Mar 13 at 10:52
add a comment |
$begingroup$
No, the statements are not equivalent. In general, quantifiers of the same type are commutative ($forall x forall y phi equiv forall y forall x phi$; $exists x exists y phi equiv exists y exists x phi$), but quantifiers of two different types are not ($forall x exists y not equiv exists y forall x$).
To illustrate this, consider the simple example:
For all tupperware boxes there is a lid that fits it.
This can be formalized as
(1) $forall x (box(x) to exists y (lid(y) land fit(y,x)))$
Or, using the abbreviations you made use of in your formula$^1$,
$forall x in box exists y in lid, fit(y,x)$
Unfortunately, from this we can not conclude that there is a magical lid that fits all tupperware boxes:
(2) $not vDash exists y forall x (box(x) to (lid(y) land fit(y,x)))$
(Usually, the case is rather that there are alwyays somehow more lids than tupperware boxes, but still you can't find a suitable lid for all your boxes...)
So $forall x exists y phi not vDash exists y forall x phi$. This can be shown by providing a simple model that satisfies that first but not the second formula.
The reverse direction does hold: If there were a magical lid that is compatible with all tupperware boxes, then of course every tupperware box would have a matching lid.
So $exists y forall x phi vDash forall x exists y phi$. You can prove this by making an argument about about how quantified formulas are satisfied semantically, or by a formal proof in some system like natural deduction for predicate logic, employing soundness of this system.
That (1) $not vDash$ (2) but (2) $vDash$ (1) means that (2) is a stronger statement: Any situation in which (2) holds is one where (1) is also true, but there are situations in which (1) is true but (2) is not, because (2) is a stronger constraint on the valid models.
The same reasoning now applies to your formula that involves three quantifications: While it is okay to swap the order of $forall x$ and $forall r$, moving $forall r$ in front of $exists y$ is not. This makes for a weaker statement: Saying that for all $r in R$ we can find some $y in Y$ that satisfies $P(x,y,r)$ is a less strict requirement and will hence have models that don't satisfy the original stronger claim that there must be a particular $y in Y$ that works for all $r in R$.
Since $forall r in R forall x in X exists y in Y ,P(x,y,r) not models forall x in X exists y in Y forall r in R ,P(x,y,r)$ but $forall x in X exists y in Y forall r in R ,P(x,y,r) models forall r in R forall x in X exists y in Y ,P(x,y,r)$, if you are convinced that your second formulation does the job, you can use this one, and all the models that were compatible with your first formalization will also be permitted by your second formalization. But they are not logically equivalent: Depending on what you want to describe/to which models you want to restrict yourself to with your proposition, your second formalization might be too weak, in that it in addition permits models that would contradict the first formalization - at least it is in the general case. (I would have to get a better understanding of your predicate to be able to tell whether your second, weaker version is still strong enough for what you want to express).
To show that the two formulas are not equivalent, consider a simple model:
$$mathfrakA = langle mathcalA, mathcalI rangle$$ with
$$mathcalA = x1, y1, y2, r1, r2$$
$$mathcalI(X) = x1;\
mathcalI(Y) = y1, y2;\
mathcalI(R) = r1, r2;\
mathcalI(P) = langle x1, y1, r1 rangle, langle x1, y2, r2 rangle$$
$mathfrakA models forall r in R forall x in X exists y in Y P(x,y,r)$ (your second formalization): For each r and for each thing in x (there is just one, to make things simpler) we can find find some element y that goes in the triple: For $r1$, we have $y1$, and for $r2$, we find $y2$.
But $mathfrakA not models forall x in X exists y in Y forall r in R P(x,y,r)$ (your first formalization), because for our one $x$, there is no thing in $Y$ that works for all the $r$.
Since there is a model that satisfies the second but not the first formula, they are not equivalent.
$^1$ Technically, $forall x in X exists y in Y phi$ is not a syntactically valid first-order formula, but it's a very common abbrevation for $forall x (x in X to exists y (y in Y land phi))$. I'm using this latter explicit syntax to hopefully give a better understanding of why a formula is or is not satisfied by a model.
answered Mar 12 at 21:04
lemontreelemontree
1,177622
$endgroup$
No, the statements are not equivalent. In general, quantifiers of the same type are commutative ($forall x forall y phi equiv forall y forall x phi$; $exists x exists y phi equiv exists y exists x phi$), but quantifiers of two different types are not ($forall x exists y not equiv exists y forall x$).
To illustrate this, consider the simple example:
For all tupperware boxes there is a lid that fits it.
This can be formalized as
(1) $forall x (box(x) to exists y (lid(y) land fit(y,x)))$
Or, using the abbreviations you made use of in your formula$^1$,
$forall x in box exists y in lid, fit(y,x)$
Unfortunately, from this we can not conclude that there is a magical lid that fits all tupperware boxes:
(2) $not vDash exists y forall x (box(x) to (lid(y) land fit(y,x)))$
(Usually, the case is rather that there are alwyays somehow more lids than tupperware boxes, but still you can't find a suitable lid for all your boxes...)
So $forall x exists y phi not vDash exists y forall x phi$. This can be shown by providing a simple model that satisfies that first but not the second formula.
The reverse direction does hold: If there were a magical lid that is compatible with all tupperware boxes, then of course every tupperware box would have a matching lid.
So $exists y forall x phi vDash forall x exists y phi$. You can prove this by making an argument about about how quantified formulas are satisfied semantically, or by a formal proof in some system like natural deduction for predicate logic, employing soundness of this system.
That (1) $not vDash$ (2) but (2) $vDash$ (1) means that (2) is a stronger statement: Any situation in which (2) holds is one where (1) is also true, but there are situations in which (1) is true but (2) is not, because (2) is a stronger constraint on the valid models.
The same reasoning now applies to your formula that involves three quantifications: While it is okay to swap the order of $forall x$ and $forall r$, moving $forall r$ in front of $exists y$ is not. This makes for a weaker statement: Saying that for all $r in R$ we can find some $y in Y$ that satisfies $P(x,y,r)$ is a less strict requirement and will hence have models that don't satisfy the original stronger claim that there must be a particular $y in Y$ that works for all $r in R$.
Since $forall r in R forall x in X exists y in Y ,P(x,y,r) not models forall x in X exists y in Y forall r in R ,P(x,y,r)$ but $forall x in X exists y in Y forall r in R ,P(x,y,r) models forall r in R forall x in X exists y in Y ,P(x,y,r)$, if you are convinced that your second formulation does the job, you can use this one, and all the models that were compatible with your first formalization will also be permitted by your second formalization. But they are not logically equivalent: Depending on what you want to describe/to which models you want to restrict yourself to with your proposition, your second formalization might be too weak, in that it in addition permits models that would contradict the first formalization - at least it is in the general case. (I would have to get a better understanding of your predicate to be able to tell whether your second, weaker version is still strong enough for what you want to express).
To show that the two formulas are not equivalent, consider a simple model:
$$mathfrakA = langle mathcalA, mathcalI rangle$$ with
$$mathcalA = x1, y1, y2, r1, r2$$
$$mathcalI(X) = x1;\
mathcalI(Y) = y1, y2;\
mathcalI(R) = r1, r2;\
mathcalI(P) = langle x1, y1, r1 rangle, langle x1, y2, r2 rangle$$
$mathfrakA models forall r in R forall x in X exists y in Y P(x,y,r)$ (your second formalization): For each r and for each thing in x (there is just one, to make things simpler) we can find find some element y that goes in the triple: For $r1$, we have $y1$, and for $r2$, we find $y2$.
But $mathfrakA not models forall x in X exists y in Y forall r in R P(x,y,r)$ (your first formalization), because for our one $x$, there is no thing in $Y$ that works for all the $r$.
Since there is a model that satisfies the second but not the first formula, they are not equivalent.
$^1$ Technically, $forall x in X exists y in Y phi$ is not a syntactically valid first-order formula, but it's a very common abbrevation for $forall x (x in X to exists y (y in Y land phi))$. I'm using this latter explicit syntax to hopefully give a better understanding of why a formula is or is not satisfied by a model.
answered Mar 12 at 21:04
lemontreelemontree
1,177622
edited Mar 12 at 23:40
answered Mar 12 at 21:04
lemontreelemontree
1,177622
answered Mar 12 at 21:04
lemontreelemontree
1,177622
answered Mar 12 at 21:04
lemontreelemontree
1,177622
1,177622
$begingroup$
Comments are not for extended discussion; this conversation has been moved to chat.
$endgroup$
– Pedro Tamaroff♦
Mar 13 at 10:52
add a comment |
$begingroup$
Comments are not for extended discussion; this conversation has been moved to chat.
$endgroup$
– Pedro Tamaroff♦
Mar 13 at 10:52
$begingroup$
Comments are not for extended discussion; this conversation has been moved to chat.
$endgroup$
– Pedro Tamaroff♦
Mar 13 at 10:52
$begingroup$
Comments are not for extended discussion; this conversation has been moved to chat.
$endgroup$
– Pedro Tamaroff♦
Mar 13 at 10:52
add a comment |
$begingroup$
If I have a proposition of the form $forall x in X exists y in Y forall r in R P(x,y,r)$ where at least any number of Y,X and R can be the same. Is that logically equivalent to $forall r in R forall x in X exists y in Y P(x,y,r)$ ?
No. The former implies the latter but is not equivalent to it.
You have $forall xinmathrm X~~exists yinmathrm Y~~forall rinmathrm R~~P(x,y,r)$ where $P$ is a generic relation.
Now $exists y~forall r~phi$ entails $forall r~exists y~phi$. If something holds for every $r$ of a particular $y$, then something holds for some $y$ of any $r$.
- "There is a column where every row contains a letter", entails that "Every row has a column which contains a letter."
However, the converse is not so.
- "Every row has a column which contains a letter," does not logically entail "There is a column where every row contains a letter." For instance, when every row may have a distinct column containing its letter, then the first statement is satisfied while the second is not.
So $forall xinmathrm X~~forall rinmathrm R~~exists yinmathrm Y~~P(x,y,r)$ is entailed by the original sentence, but is not equivalent to it.
This can be broken into two steps.
$forall x ~forall r~phi$ entails and is entailed by $forall r~forall x~phi$. So the previous statement is equivalent to the desired result. However the original statement only entails them. $$forall xinmathrm X~~exists yinmathrm Y~~forall rinmathrm R~~P(x,y,r)\Downarrow\forall xinmathrm X~~forall rinmathrm R~~exists yinmathrm Y~~P(x,y,r)\Updownarrow\forall rinmathrm R~~forall xinmathrm X~~exists yinmathrm Y~~P(x,y,r)$$
answered Mar 12 at 23:48
Graham KempGraham Kemp
86.8k43579
$endgroup$
add a comment |
$begingroup$
If I have a proposition of the form $forall x in X exists y in Y forall r in R P(x,y,r)$ where at least any number of Y,X and R can be the same. Is that logically equivalent to $forall r in R forall x in X exists y in Y P(x,y,r)$ ?
No. The former implies the latter but is not equivalent to it.
You have $forall xinmathrm X~~exists yinmathrm Y~~forall rinmathrm R~~P(x,y,r)$ where $P$ is a generic relation.
Now $exists y~forall r~phi$ entails $forall r~exists y~phi$. If something holds for every $r$ of a particular $y$, then something holds for some $y$ of any $r$.
- "There is a column where every row contains a letter", entails that "Every row has a column which contains a letter."
However, the converse is not so.
- "Every row has a column which contains a letter," does not logically entail "There is a column where every row contains a letter." For instance, when every row may have a distinct column containing its letter, then the first statement is satisfied while the second is not.
So $forall xinmathrm X~~forall rinmathrm R~~exists yinmathrm Y~~P(x,y,r)$ is entailed by the original sentence, but is not equivalent to it.
This can be broken into two steps.
$forall x ~forall r~phi$ entails and is entailed by $forall r~forall x~phi$. So the previous statement is equivalent to the desired result. However the original statement only entails them. $$forall xinmathrm X~~exists yinmathrm Y~~forall rinmathrm R~~P(x,y,r)\Downarrow\forall xinmathrm X~~forall rinmathrm R~~exists yinmathrm Y~~P(x,y,r)\Updownarrow\forall rinmathrm R~~forall xinmathrm X~~exists yinmathrm Y~~P(x,y,r)$$
answered Mar 12 at 23:48
Graham KempGraham Kemp
86.8k43579
$endgroup$
add a comment |
$begingroup$
If I have a proposition of the form $forall x in X exists y in Y forall r in R P(x,y,r)$ where at least any number of Y,X and R can be the same. Is that logically equivalent to $forall r in R forall x in X exists y in Y P(x,y,r)$ ?
No. The former implies the latter but is not equivalent to it.
You have $forall xinmathrm X~~exists yinmathrm Y~~forall rinmathrm R~~P(x,y,r)$ where $P$ is a generic relation.
Now $exists y~forall r~phi$ entails $forall r~exists y~phi$. If something holds for every $r$ of a particular $y$, then something holds for some $y$ of any $r$.
- "There is a column where every row contains a letter", entails that "Every row has a column which contains a letter."
However, the converse is not so.
- "Every row has a column which contains a letter," does not logically entail "There is a column where every row contains a letter." For instance, when every row may have a distinct column containing its letter, then the first statement is satisfied while the second is not.
So $forall xinmathrm X~~forall rinmathrm R~~exists yinmathrm Y~~P(x,y,r)$ is entailed by the original sentence, but is not equivalent to it.
This can be broken into two steps.
$forall x ~forall r~phi$ entails and is entailed by $forall r~forall x~phi$. So the previous statement is equivalent to the desired result. However the original statement only entails them. $$forall xinmathrm X~~exists yinmathrm Y~~forall rinmathrm R~~P(x,y,r)\Downarrow\forall xinmathrm X~~forall rinmathrm R~~exists yinmathrm Y~~P(x,y,r)\Updownarrow\forall rinmathrm R~~forall xinmathrm X~~exists yinmathrm Y~~P(x,y,r)$$
answered Mar 12 at 23:48
Graham KempGraham Kemp
86.8k43579
$endgroup$
If I have a proposition of the form $forall x in X exists y in Y forall r in R P(x,y,r)$ where at least any number of Y,X and R can be the same. Is that logically equivalent to $forall r in R forall x in X exists y in Y P(x,y,r)$ ?
No. The former implies the latter but is not equivalent to it.
You have $forall xinmathrm X~~exists yinmathrm Y~~forall rinmathrm R~~P(x,y,r)$ where $P$ is a generic relation.
Now $exists y~forall r~phi$ entails $forall r~exists y~phi$. If something holds for every $r$ of a particular $y$, then something holds for some $y$ of any $r$.
- "There is a column where every row contains a letter", entails that "Every row has a column which contains a letter."
However, the converse is not so.
- "Every row has a column which contains a letter," does not logically entail "There is a column where every row contains a letter." For instance, when every row may have a distinct column containing its letter, then the first statement is satisfied while the second is not.
So $forall xinmathrm X~~forall rinmathrm R~~exists yinmathrm Y~~P(x,y,r)$ is entailed by the original sentence, but is not equivalent to it.
This can be broken into two steps.
$forall x ~forall r~phi$ entails and is entailed by $forall r~forall x~phi$. So the previous statement is equivalent to the desired result. However the original statement only entails them. $$forall xinmathrm X~~exists yinmathrm Y~~forall rinmathrm R~~P(x,y,r)\Downarrow\forall xinmathrm X~~forall rinmathrm R~~exists yinmathrm Y~~P(x,y,r)\Updownarrow\forall rinmathrm R~~forall xinmathrm X~~exists yinmathrm Y~~P(x,y,r)$$
answered Mar 12 at 23:48
Graham KempGraham Kemp
86.8k43579
edited Mar 12 at 23:54
answered Mar 12 at 23:48
Graham KempGraham Kemp
86.8k43579
answered Mar 12 at 23:48
Graham KempGraham Kemp
86.8k43579
answered Mar 12 at 23:48
Graham KempGraham Kemp
86.8k43579
86.8k43579
add a comment |
add a comment |
$begingroup$
ADDED LAST
The final word is that lemontree's answer was right and mine was wrong; I have left the original in place below.
A good example of the in-equivalence, is to let the domains of discourse
$X$, $Y$, and $R$ be the reals, and consider the proposition $P(x,y,z)$ to be
$$ (x=0) vee
((y in Bbb Q) wedge (|y-sqrt2| lt |x|) wedge (|ry-rsqrt2| lt |rx|))
$$
Then the first statement $forall xleft( exists y forall r P(x,y,r) right)$
reads in English as "for any given real non-zero $x$ there exists some rational $y$ such that for all real $r$ the absolute difference between $y$ and $sqrt2$ is less than $|x|$ (and when both sides of that inequality are multiplied by $R$ it still holds). This is obviously true, since arbitrarily good rational approximations to $sqrt2$ can be found.
But the second statement $forall rleft( exists y forall x P(x,y,r) right)$
reads "for every real $r$, there exists some rational $y$ such that for any arbitrary non-zero $x$ the absolute difference between $y$ and $sqrt2$ is less than $|x|$ (and another clause)." That is obviously not true, because there is no rational approximation to $sqrt2$ that is closer than any arbitrarly chosen $x$.
Thus the two statements are not logically equivalent.
ORIGINAL ANSWER
In a logic system that allows Skolemization, you can apply this second-order equivalence (see https://en.wikipedia.org/wiki/Skolem_normal_form):
$$
forall xleft( R(g(x)) vee exists yR(x,y)right) Longleftrightarrow exists fforall x left( R(g(x)) vee R(x,f(x))right)
$$
where $f(x)$ is a function that maps $x$ to $y$.
Our application of this is a specialization which is a considerable simplification: Let
$R(g(x)) = F$ (False) and $F(x,f(x)$ be $forall r P(x,f(x),r)$. Then the equivalence reads
$$
forall xleft( exists y forall r P(x,y,r) right) Longleftrightarrow exists fforall x left( forall r P(x,f(x),r)right)
$$
Here I have omitted the domain designations, that is, $forall x$ means $forall x in X$ and $exists y$ means $exists y in Y$.
And now we can commute $forall x forall r$ because an axiom says that
$forall x forall r, P$ is identical to $forall r forall x, P$, thus
$$exists fforall x forall r P(x,f(x),r) Longleftrightarrow
exists fforall r forall x P(x,f(x),r) Longleftrightarrow
forall rleft( exists y forall x P(x,y,r) right)
$$
Added later:
OMG, I didn't have to go into this detail, because (assuming the Skolem_normal_form page is correct) they give an example that is precisely the case in the problem! To quote:
As an example, the formula $forall x exists y forall z P(x,y,z)$ is not in Skolem normal form because it contains the existential quatifier $exists y$.
Skolemization replaces $y$ with $f(x) ldots$ and removes the quantification over $y$. The resulting formula is $forall x forall z P(x,f(x),z)$. $ldots$ The formula obtained by this transformation is satisfiable if and only if the original formula is.
(Emphasis mine). So we can now go over to $forall x forall z P(x,f(x),z)
equiv forall z forall x P(x,f(x),z)$ and from there, use the "if and only if" property to go to the equivalent $forall z exists y forall x P(x,y,z)$
The use of the function $f(x)$ might imply that this reasoning depends on having the axiom of choice.
To extend/use the @lemontree example:
Let $P(x,y,r)$ be "lid $r$ fits every tupperware that is in the same house ($x$) as this tupperware box $y$.
Then the question becomes whether these statements are identical:
- For all houses, there is some lid that fits every tupperware in the house.
- For every tupperware, there exists some lid that fits (it and) every tupperware in the same house.
I claim they are logically equivalent.
answered Mar 12 at 21:04
Mark FischlerMark Fischler
33.5k12452
$endgroup$
2
$begingroup$
Skolemization preserves satisfiability (If $phi$ is satisfiable, then its skolem normal form is), but the skolemized formula is in the general case not logically equivalent to the original formula, which is what OP asked for.
$endgroup$
– lemontree
Mar 12 at 21:08
2
$begingroup$
The equivalence you are probably referring to is a second-order equivalence: It is an equivalence relation between properties of first-order formula - namely that that the Skolem normal form is satisfiable iff the original formula is satisfiable. This is not the same as logical equivalence between formulas of first-order logic. The Wikipedia article actually states that "The resulting formula is not necessarily equivalent to the original one, but is equisatisfiable with it".
$endgroup$
– lemontree
Mar 12 at 21:20
3
$begingroup$
I'm sorry, but still no, @both Mark Fischler und topologicalmagician, they are not equivalent. They are only equisatisfiable. This is not the same. There might well be some models/interpretations of P under which they have the same truth value, like in the interpretation you provided in your edit, but this is is no proof that they are logically equivalent, which by definition means true in all the same models/interpretations of the predicate symbols.
$endgroup$
– lemontree
Mar 12 at 22:29
2
$begingroup$
There are models/interpretations in which the one holds while the other one doesn't, like the simple model for the P predicate I edited into my post, and if there is at least model that satisfies the one but not the other formula, then - by the definition of logical equivalence - the two formulas are not equivalent. Providing one counter-model is proof enough that a logical equivalence (a universal quantification) does not hold. On the other hand, providing one interpretation of P is not an appropriate means to prove that a logical equivalence does hold.
$endgroup$
– lemontree
Mar 12 at 22:30
2
$begingroup$
@lemontree Your patience is admirable!
$endgroup$
– Alex Kruckman
Mar 12 at 23:32
|
show 6 more comments
$begingroup$
ADDED LAST
The final word is that lemontree's answer was right and mine was wrong; I have left the original in place below.
A good example of the in-equivalence, is to let the domains of discourse
$X$, $Y$, and $R$ be the reals, and consider the proposition $P(x,y,z)$ to be
$$ (x=0) vee
((y in Bbb Q) wedge (|y-sqrt2| lt |x|) wedge (|ry-rsqrt2| lt |rx|))
$$
Then the first statement $forall xleft( exists y forall r P(x,y,r) right)$
reads in English as "for any given real non-zero $x$ there exists some rational $y$ such that for all real $r$ the absolute difference between $y$ and $sqrt2$ is less than $|x|$ (and when both sides of that inequality are multiplied by $R$ it still holds). This is obviously true, since arbitrarily good rational approximations to $sqrt2$ can be found.
But the second statement $forall rleft( exists y forall x P(x,y,r) right)$
reads "for every real $r$, there exists some rational $y$ such that for any arbitrary non-zero $x$ the absolute difference between $y$ and $sqrt2$ is less than $|x|$ (and another clause)." That is obviously not true, because there is no rational approximation to $sqrt2$ that is closer than any arbitrarly chosen $x$.
Thus the two statements are not logically equivalent.
ORIGINAL ANSWER
In a logic system that allows Skolemization, you can apply this second-order equivalence (see https://en.wikipedia.org/wiki/Skolem_normal_form):
$$
forall xleft( R(g(x)) vee exists yR(x,y)right) Longleftrightarrow exists fforall x left( R(g(x)) vee R(x,f(x))right)
$$
where $f(x)$ is a function that maps $x$ to $y$.
Our application of this is a specialization which is a considerable simplification: Let
$R(g(x)) = F$ (False) and $F(x,f(x)$ be $forall r P(x,f(x),r)$. Then the equivalence reads
$$
forall xleft( exists y forall r P(x,y,r) right) Longleftrightarrow exists fforall x left( forall r P(x,f(x),r)right)
$$
Here I have omitted the domain designations, that is, $forall x$ means $forall x in X$ and $exists y$ means $exists y in Y$.
And now we can commute $forall x forall r$ because an axiom says that
$forall x forall r, P$ is identical to $forall r forall x, P$, thus
$$exists fforall x forall r P(x,f(x),r) Longleftrightarrow
exists fforall r forall x P(x,f(x),r) Longleftrightarrow
forall rleft( exists y forall x P(x,y,r) right)
$$
Added later:
OMG, I didn't have to go into this detail, because (assuming the Skolem_normal_form page is correct) they give an example that is precisely the case in the problem! To quote:
As an example, the formula $forall x exists y forall z P(x,y,z)$ is not in Skolem normal form because it contains the existential quatifier $exists y$.
Skolemization replaces $y$ with $f(x) ldots$ and removes the quantification over $y$. The resulting formula is $forall x forall z P(x,f(x),z)$. $ldots$ The formula obtained by this transformation is satisfiable if and only if the original formula is.
(Emphasis mine). So we can now go over to $forall x forall z P(x,f(x),z)
equiv forall z forall x P(x,f(x),z)$ and from there, use the "if and only if" property to go to the equivalent $forall z exists y forall x P(x,y,z)$
The use of the function $f(x)$ might imply that this reasoning depends on having the axiom of choice.
To extend/use the @lemontree example:
Let $P(x,y,r)$ be "lid $r$ fits every tupperware that is in the same house ($x$) as this tupperware box $y$.
Then the question becomes whether these statements are identical:
- For all houses, there is some lid that fits every tupperware in the house.
- For every tupperware, there exists some lid that fits (it and) every tupperware in the same house.
I claim they are logically equivalent.
answered Mar 12 at 21:04
Mark FischlerMark Fischler
33.5k12452
$endgroup$
2
$begingroup$
Skolemization preserves satisfiability (If $phi$ is satisfiable, then its skolem normal form is), but the skolemized formula is in the general case not logically equivalent to the original formula, which is what OP asked for.
$endgroup$
– lemontree
Mar 12 at 21:08
2
$begingroup$
The equivalence you are probably referring to is a second-order equivalence: It is an equivalence relation between properties of first-order formula - namely that that the Skolem normal form is satisfiable iff the original formula is satisfiable. This is not the same as logical equivalence between formulas of first-order logic. The Wikipedia article actually states that "The resulting formula is not necessarily equivalent to the original one, but is equisatisfiable with it".
$endgroup$
– lemontree
Mar 12 at 21:20
3
$begingroup$
I'm sorry, but still no, @both Mark Fischler und topologicalmagician, they are not equivalent. They are only equisatisfiable. This is not the same. There might well be some models/interpretations of P under which they have the same truth value, like in the interpretation you provided in your edit, but this is is no proof that they are logically equivalent, which by definition means true in all the same models/interpretations of the predicate symbols.
$endgroup$
– lemontree
Mar 12 at 22:29
2
$begingroup$
There are models/interpretations in which the one holds while the other one doesn't, like the simple model for the P predicate I edited into my post, and if there is at least model that satisfies the one but not the other formula, then - by the definition of logical equivalence - the two formulas are not equivalent. Providing one counter-model is proof enough that a logical equivalence (a universal quantification) does not hold. On the other hand, providing one interpretation of P is not an appropriate means to prove that a logical equivalence does hold.
$endgroup$
– lemontree
Mar 12 at 22:30
2
$begingroup$
@lemontree Your patience is admirable!
$endgroup$
– Alex Kruckman
Mar 12 at 23:32
|
show 6 more comments
$begingroup$
ADDED LAST
The final word is that lemontree's answer was right and mine was wrong; I have left the original in place below.
A good example of the in-equivalence, is to let the domains of discourse
$X$, $Y$, and $R$ be the reals, and consider the proposition $P(x,y,z)$ to be
$$ (x=0) vee
((y in Bbb Q) wedge (|y-sqrt2| lt |x|) wedge (|ry-rsqrt2| lt |rx|))
$$
Then the first statement $forall xleft( exists y forall r P(x,y,r) right)$
reads in English as "for any given real non-zero $x$ there exists some rational $y$ such that for all real $r$ the absolute difference between $y$ and $sqrt2$ is less than $|x|$ (and when both sides of that inequality are multiplied by $R$ it still holds). This is obviously true, since arbitrarily good rational approximations to $sqrt2$ can be found.
But the second statement $forall rleft( exists y forall x P(x,y,r) right)$
reads "for every real $r$, there exists some rational $y$ such that for any arbitrary non-zero $x$ the absolute difference between $y$ and $sqrt2$ is less than $|x|$ (and another clause)." That is obviously not true, because there is no rational approximation to $sqrt2$ that is closer than any arbitrarly chosen $x$.
Thus the two statements are not logically equivalent.
ORIGINAL ANSWER
In a logic system that allows Skolemization, you can apply this second-order equivalence (see https://en.wikipedia.org/wiki/Skolem_normal_form):
$$
forall xleft( R(g(x)) vee exists yR(x,y)right) Longleftrightarrow exists fforall x left( R(g(x)) vee R(x,f(x))right)
$$
where $f(x)$ is a function that maps $x$ to $y$.
Our application of this is a specialization which is a considerable simplification: Let
$R(g(x)) = F$ (False) and $F(x,f(x)$ be $forall r P(x,f(x),r)$. Then the equivalence reads
$$
forall xleft( exists y forall r P(x,y,r) right) Longleftrightarrow exists fforall x left( forall r P(x,f(x),r)right)
$$
Here I have omitted the domain designations, that is, $forall x$ means $forall x in X$ and $exists y$ means $exists y in Y$.
And now we can commute $forall x forall r$ because an axiom says that
$forall x forall r, P$ is identical to $forall r forall x, P$, thus
$$exists fforall x forall r P(x,f(x),r) Longleftrightarrow
exists fforall r forall x P(x,f(x),r) Longleftrightarrow
forall rleft( exists y forall x P(x,y,r) right)
$$
Added later:
OMG, I didn't have to go into this detail, because (assuming the Skolem_normal_form page is correct) they give an example that is precisely the case in the problem! To quote:
As an example, the formula $forall x exists y forall z P(x,y,z)$ is not in Skolem normal form because it contains the existential quatifier $exists y$.
Skolemization replaces $y$ with $f(x) ldots$ and removes the quantification over $y$. The resulting formula is $forall x forall z P(x,f(x),z)$. $ldots$ The formula obtained by this transformation is satisfiable if and only if the original formula is.
(Emphasis mine). So we can now go over to $forall x forall z P(x,f(x),z)
equiv forall z forall x P(x,f(x),z)$ and from there, use the "if and only if" property to go to the equivalent $forall z exists y forall x P(x,y,z)$
The use of the function $f(x)$ might imply that this reasoning depends on having the axiom of choice.
To extend/use the @lemontree example:
Let $P(x,y,r)$ be "lid $r$ fits every tupperware that is in the same house ($x$) as this tupperware box $y$.
Then the question becomes whether these statements are identical:
- For all houses, there is some lid that fits every tupperware in the house.
- For every tupperware, there exists some lid that fits (it and) every tupperware in the same house.
I claim they are logically equivalent.
answered Mar 12 at 21:04
Mark FischlerMark Fischler
33.5k12452
$endgroup$
ADDED LAST
The final word is that lemontree's answer was right and mine was wrong; I have left the original in place below.
A good example of the in-equivalence, is to let the domains of discourse
$X$, $Y$, and $R$ be the reals, and consider the proposition $P(x,y,z)$ to be
$$ (x=0) vee
((y in Bbb Q) wedge (|y-sqrt2| lt |x|) wedge (|ry-rsqrt2| lt |rx|))
$$
Then the first statement $forall xleft( exists y forall r P(x,y,r) right)$
reads in English as "for any given real non-zero $x$ there exists some rational $y$ such that for all real $r$ the absolute difference between $y$ and $sqrt2$ is less than $|x|$ (and when both sides of that inequality are multiplied by $R$ it still holds). This is obviously true, since arbitrarily good rational approximations to $sqrt2$ can be found.
But the second statement $forall rleft( exists y forall x P(x,y,r) right)$
reads "for every real $r$, there exists some rational $y$ such that for any arbitrary non-zero $x$ the absolute difference between $y$ and $sqrt2$ is less than $|x|$ (and another clause)." That is obviously not true, because there is no rational approximation to $sqrt2$ that is closer than any arbitrarly chosen $x$.
Thus the two statements are not logically equivalent.
ORIGINAL ANSWER
In a logic system that allows Skolemization, you can apply this second-order equivalence (see https://en.wikipedia.org/wiki/Skolem_normal_form):
$$
forall xleft( R(g(x)) vee exists yR(x,y)right) Longleftrightarrow exists fforall x left( R(g(x)) vee R(x,f(x))right)
$$
where $f(x)$ is a function that maps $x$ to $y$.
Our application of this is a specialization which is a considerable simplification: Let
$R(g(x)) = F$ (False) and $F(x,f(x)$ be $forall r P(x,f(x),r)$. Then the equivalence reads
$$
forall xleft( exists y forall r P(x,y,r) right) Longleftrightarrow exists fforall x left( forall r P(x,f(x),r)right)
$$
Here I have omitted the domain designations, that is, $forall x$ means $forall x in X$ and $exists y$ means $exists y in Y$.
And now we can commute $forall x forall r$ because an axiom says that
$forall x forall r, P$ is identical to $forall r forall x, P$, thus
$$exists fforall x forall r P(x,f(x),r) Longleftrightarrow
exists fforall r forall x P(x,f(x),r) Longleftrightarrow
forall rleft( exists y forall x P(x,y,r) right)
$$
Added later:
OMG, I didn't have to go into this detail, because (assuming the Skolem_normal_form page is correct) they give an example that is precisely the case in the problem! To quote:
As an example, the formula $forall x exists y forall z P(x,y,z)$ is not in Skolem normal form because it contains the existential quatifier $exists y$.
Skolemization replaces $y$ with $f(x) ldots$ and removes the quantification over $y$. The resulting formula is $forall x forall z P(x,f(x),z)$. $ldots$ The formula obtained by this transformation is satisfiable if and only if the original formula is.
(Emphasis mine). So we can now go over to $forall x forall z P(x,f(x),z)
equiv forall z forall x P(x,f(x),z)$ and from there, use the "if and only if" property to go to the equivalent $forall z exists y forall x P(x,y,z)$
The use of the function $f(x)$ might imply that this reasoning depends on having the axiom of choice.
To extend/use the @lemontree example:
Let $P(x,y,r)$ be "lid $r$ fits every tupperware that is in the same house ($x$) as this tupperware box $y$.
Then the question becomes whether these statements are identical:
- For all houses, there is some lid that fits every tupperware in the house.
- For every tupperware, there exists some lid that fits (it and) every tupperware in the same house.
I claim they are logically equivalent.
answered Mar 12 at 21:04
Mark FischlerMark Fischler
33.5k12452
edited Mar 13 at 18:33
answered Mar 12 at 21:04
Mark FischlerMark Fischler
33.5k12452
answered Mar 12 at 21:04
Mark FischlerMark Fischler
33.5k12452
answered Mar 12 at 21:04
Mark FischlerMark Fischler
33.5k12452
33.5k12452
2
$begingroup$
Skolemization preserves satisfiability (If $phi$ is satisfiable, then its skolem normal form is), but the skolemized formula is in the general case not logically equivalent to the original formula, which is what OP asked for.
$endgroup$
– lemontree
Mar 12 at 21:08
2
$begingroup$
The equivalence you are probably referring to is a second-order equivalence: It is an equivalence relation between properties of first-order formula - namely that that the Skolem normal form is satisfiable iff the original formula is satisfiable. This is not the same as logical equivalence between formulas of first-order logic. The Wikipedia article actually states that "The resulting formula is not necessarily equivalent to the original one, but is equisatisfiable with it".
$endgroup$
– lemontree
Mar 12 at 21:20
3
$begingroup$
I'm sorry, but still no, @both Mark Fischler und topologicalmagician, they are not equivalent. They are only equisatisfiable. This is not the same. There might well be some models/interpretations of P under which they have the same truth value, like in the interpretation you provided in your edit, but this is is no proof that they are logically equivalent, which by definition means true in all the same models/interpretations of the predicate symbols.
$endgroup$
– lemontree
Mar 12 at 22:29
2
$begingroup$
There are models/interpretations in which the one holds while the other one doesn't, like the simple model for the P predicate I edited into my post, and if there is at least model that satisfies the one but not the other formula, then - by the definition of logical equivalence - the two formulas are not equivalent. Providing one counter-model is proof enough that a logical equivalence (a universal quantification) does not hold. On the other hand, providing one interpretation of P is not an appropriate means to prove that a logical equivalence does hold.
$endgroup$
– lemontree
Mar 12 at 22:30
2
$begingroup$
@lemontree Your patience is admirable!
$endgroup$
– Alex Kruckman
Mar 12 at 23:32
|
show 6 more comments
2
$begingroup$
Skolemization preserves satisfiability (If $phi$ is satisfiable, then its skolem normal form is), but the skolemized formula is in the general case not logically equivalent to the original formula, which is what OP asked for.
$endgroup$
– lemontree
Mar 12 at 21:08
2
$begingroup$
The equivalence you are probably referring to is a second-order equivalence: It is an equivalence relation between properties of first-order formula - namely that that the Skolem normal form is satisfiable iff the original formula is satisfiable. This is not the same as logical equivalence between formulas of first-order logic. The Wikipedia article actually states that "The resulting formula is not necessarily equivalent to the original one, but is equisatisfiable with it".
$endgroup$
– lemontree
Mar 12 at 21:20
3
$begingroup$
I'm sorry, but still no, @both Mark Fischler und topologicalmagician, they are not equivalent. They are only equisatisfiable. This is not the same. There might well be some models/interpretations of P under which they have the same truth value, like in the interpretation you provided in your edit, but this is is no proof that they are logically equivalent, which by definition means true in all the same models/interpretations of the predicate symbols.
$endgroup$
– lemontree
Mar 12 at 22:29
2
$begingroup$
There are models/interpretations in which the one holds while the other one doesn't, like the simple model for the P predicate I edited into my post, and if there is at least model that satisfies the one but not the other formula, then - by the definition of logical equivalence - the two formulas are not equivalent. Providing one counter-model is proof enough that a logical equivalence (a universal quantification) does not hold. On the other hand, providing one interpretation of P is not an appropriate means to prove that a logical equivalence does hold.
$endgroup$
– lemontree
Mar 12 at 22:30
2
$begingroup$
@lemontree Your patience is admirable!
$endgroup$
– Alex Kruckman
Mar 12 at 23:32
2
2
$begingroup$
Skolemization preserves satisfiability (If $phi$ is satisfiable, then its skolem normal form is), but the skolemized formula is in the general case not logically equivalent to the original formula, which is what OP asked for.
$endgroup$
– lemontree
Mar 12 at 21:08
$begingroup$
Skolemization preserves satisfiability (If $phi$ is satisfiable, then its skolem normal form is), but the skolemized formula is in the general case not logically equivalent to the original formula, which is what OP asked for.
$endgroup$
– lemontree
Mar 12 at 21:08
2
2
$begingroup$
The equivalence you are probably referring to is a second-order equivalence: It is an equivalence relation between properties of first-order formula - namely that that the Skolem normal form is satisfiable iff the original formula is satisfiable. This is not the same as logical equivalence between formulas of first-order logic. The Wikipedia article actually states that "The resulting formula is not necessarily equivalent to the original one, but is equisatisfiable with it".
$endgroup$
– lemontree
Mar 12 at 21:20
$begingroup$
The equivalence you are probably referring to is a second-order equivalence: It is an equivalence relation between properties of first-order formula - namely that that the Skolem normal form is satisfiable iff the original formula is satisfiable. This is not the same as logical equivalence between formulas of first-order logic. The Wikipedia article actually states that "The resulting formula is not necessarily equivalent to the original one, but is equisatisfiable with it".
$endgroup$
– lemontree
Mar 12 at 21:20
3
3
$begingroup$
I'm sorry, but still no, @both Mark Fischler und topologicalmagician, they are not equivalent. They are only equisatisfiable. This is not the same. There might well be some models/interpretations of P under which they have the same truth value, like in the interpretation you provided in your edit, but this is is no proof that they are logically equivalent, which by definition means true in all the same models/interpretations of the predicate symbols.
$endgroup$
– lemontree
Mar 12 at 22:29
$begingroup$
I'm sorry, but still no, @both Mark Fischler und topologicalmagician, they are not equivalent. They are only equisatisfiable. This is not the same. There might well be some models/interpretations of P under which they have the same truth value, like in the interpretation you provided in your edit, but this is is no proof that they are logically equivalent, which by definition means true in all the same models/interpretations of the predicate symbols.
$endgroup$
– lemontree
Mar 12 at 22:29
2
2
$begingroup$
There are models/interpretations in which the one holds while the other one doesn't, like the simple model for the P predicate I edited into my post, and if there is at least model that satisfies the one but not the other formula, then - by the definition of logical equivalence - the two formulas are not equivalent. Providing one counter-model is proof enough that a logical equivalence (a universal quantification) does not hold. On the other hand, providing one interpretation of P is not an appropriate means to prove that a logical equivalence does hold.
$endgroup$
– lemontree
Mar 12 at 22:30
$begingroup$
There are models/interpretations in which the one holds while the other one doesn't, like the simple model for the P predicate I edited into my post, and if there is at least model that satisfies the one but not the other formula, then - by the definition of logical equivalence - the two formulas are not equivalent. Providing one counter-model is proof enough that a logical equivalence (a universal quantification) does not hold. On the other hand, providing one interpretation of P is not an appropriate means to prove that a logical equivalence does hold.
$endgroup$
– lemontree
Mar 12 at 22:30
2
2
$begingroup$
@lemontree Your patience is admirable!
$endgroup$
– Alex Kruckman
Mar 12 at 23:32
$begingroup$
@lemontree Your patience is admirable!
$endgroup$
– Alex Kruckman
Mar 12 at 23:32
|
show 6 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%2f3145588%2fcommutative-quantifiers%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$
I love this question! Seems intuitive that the two statements are logically equivalent, but how to prove it using the axioms?
$endgroup$
– Mark Fischler
Mar 12 at 19:59
$begingroup$
@MarkFischler correct, that's what i'm curious about. Im not sure how to prove it if its true. If its not true, I would like to know under what conditions is it true.
$endgroup$
– topologicalmagician
Mar 12 at 20:04