What is the meaning of ∀x∃x?
up vote
1
down vote
favorite
Say we are in first-order logic, $x$ is a variable and its values are from a set of values, doesn't matter what.
$∀x∃x$ means for every $x$ (from the set of values) there exist at least one x (from the set of values). Since we took all $x$s from the set, of course each one itself does exist for itself because $x$ is $x$. Hence this should actually shorten to $∀x$ am I right?
The same reasoning for $∃x∀x$: there exist at least one $x*$ such that every $x$ from those $*$ is $x$. Well of course, since $x$ is $x$. So it shortens to $∃x$. Am I correct?
Conclusion
Thank you for all the answers. I was wrong, it is the other way around. I think the gist of it is that the innermost quantifier matters only when quantifying the same variable for the same formula, and the outer quantifiers (of the same variable & formula) become null quantifiers since there is nothing to quantify anymore. This is, analog to computer programs, similar to variable shadowing, which is when you over-declare/define a variable, here we are over-defining quantifiers in an expression like the above.
logic first-order-logic quantifiers
asked Nov 21 at 12:53
Najib
83
add a comment |
up vote
1
down vote
favorite
Say we are in first-order logic, $x$ is a variable and its values are from a set of values, doesn't matter what.
$∀x∃x$ means for every $x$ (from the set of values) there exist at least one x (from the set of values). Since we took all $x$s from the set, of course each one itself does exist for itself because $x$ is $x$. Hence this should actually shorten to $∀x$ am I right?
The same reasoning for $∃x∀x$: there exist at least one $x*$ such that every $x$ from those $*$ is $x$. Well of course, since $x$ is $x$. So it shortens to $∃x$. Am I correct?
Conclusion
Thank you for all the answers. I was wrong, it is the other way around. I think the gist of it is that the innermost quantifier matters only when quantifying the same variable for the same formula, and the outer quantifiers (of the same variable & formula) become null quantifiers since there is nothing to quantify anymore. This is, analog to computer programs, similar to variable shadowing, which is when you over-declare/define a variable, here we are over-defining quantifiers in an expression like the above.
logic first-order-logic quantifiers
asked Nov 21 at 12:53
Najib
83
In general, if $x$ is not free in $phi$, both $forall x phi$ and $exists x phi$ are equivalent to $phi$.
– Mauro ALLEGRANZA
Nov 21 at 12:56
@MauroALLEGRANZA Thank you Mauro!
– Najib
Nov 21 at 22:52
Of course, in practice, it would be best to avoid such expressions (ask any CS student about "variable shadowing" for an explanation of why).
– Daniel Schepler
Nov 21 at 23:28
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Say we are in first-order logic, $x$ is a variable and its values are from a set of values, doesn't matter what.
$∀x∃x$ means for every $x$ (from the set of values) there exist at least one x (from the set of values). Since we took all $x$s from the set, of course each one itself does exist for itself because $x$ is $x$. Hence this should actually shorten to $∀x$ am I right?
The same reasoning for $∃x∀x$: there exist at least one $x*$ such that every $x$ from those $*$ is $x$. Well of course, since $x$ is $x$. So it shortens to $∃x$. Am I correct?
Conclusion
Thank you for all the answers. I was wrong, it is the other way around. I think the gist of it is that the innermost quantifier matters only when quantifying the same variable for the same formula, and the outer quantifiers (of the same variable & formula) become null quantifiers since there is nothing to quantify anymore. This is, analog to computer programs, similar to variable shadowing, which is when you over-declare/define a variable, here we are over-defining quantifiers in an expression like the above.
logic first-order-logic quantifiers
asked Nov 21 at 12:53
Najib
83
Say we are in first-order logic, $x$ is a variable and its values are from a set of values, doesn't matter what.
$∀x∃x$ means for every $x$ (from the set of values) there exist at least one x (from the set of values). Since we took all $x$s from the set, of course each one itself does exist for itself because $x$ is $x$. Hence this should actually shorten to $∀x$ am I right?
The same reasoning for $∃x∀x$: there exist at least one $x*$ such that every $x$ from those $*$ is $x$. Well of course, since $x$ is $x$. So it shortens to $∃x$. Am I correct?
Conclusion
Thank you for all the answers. I was wrong, it is the other way around. I think the gist of it is that the innermost quantifier matters only when quantifying the same variable for the same formula, and the outer quantifiers (of the same variable & formula) become null quantifiers since there is nothing to quantify anymore. This is, analog to computer programs, similar to variable shadowing, which is when you over-declare/define a variable, here we are over-defining quantifiers in an expression like the above.
logic first-order-logic quantifiers
logic first-order-logic quantifiers
asked Nov 21 at 12:53
Najib
83
asked Nov 21 at 12:53
Najib
83
edited Nov 22 at 10:32
asked Nov 21 at 12:53
Najib
83
asked Nov 21 at 12:53
Najib
83
asked Nov 21 at 12:53
Najib
83
83
In general, if $x$ is not free in $phi$, both $forall x phi$ and $exists x phi$ are equivalent to $phi$.
– Mauro ALLEGRANZA
Nov 21 at 12:56
@MauroALLEGRANZA Thank you Mauro!
– Najib
Nov 21 at 22:52
Of course, in practice, it would be best to avoid such expressions (ask any CS student about "variable shadowing" for an explanation of why).
– Daniel Schepler
Nov 21 at 23:28
add a comment |
In general, if $x$ is not free in $phi$, both $forall x phi$ and $exists x phi$ are equivalent to $phi$.
– Mauro ALLEGRANZA
Nov 21 at 12:56
@MauroALLEGRANZA Thank you Mauro!
– Najib
Nov 21 at 22:52
Of course, in practice, it would be best to avoid such expressions (ask any CS student about "variable shadowing" for an explanation of why).
– Daniel Schepler
Nov 21 at 23:28
In general, if $x$ is not free in $phi$, both $forall x phi$ and $exists x phi$ are equivalent to $phi$.
– Mauro ALLEGRANZA
Nov 21 at 12:56
In general, if $x$ is not free in $phi$, both $forall x phi$ and $exists x phi$ are equivalent to $phi$.
– Mauro ALLEGRANZA
Nov 21 at 12:56
@MauroALLEGRANZA Thank you Mauro!
– Najib
Nov 21 at 22:52
@MauroALLEGRANZA Thank you Mauro!
– Najib
Nov 21 at 22:52
Of course, in practice, it would be best to avoid such expressions (ask any CS student about "variable shadowing" for an explanation of why).
– Daniel Schepler
Nov 21 at 23:28
Of course, in practice, it would be best to avoid such expressions (ask any CS student about "variable shadowing" for an explanation of why).
– Daniel Schepler
Nov 21 at 23:28
add a comment |
2 Answers
2
active
oldest
votes
up vote
1
down vote
accepted
You are right that with multiple quantifiers that are next to each other and that quantify the same variable, you can reduce it to just one quantifier, as the others effectively end up not doing any interesting work at all; they are what are called 'null quantifiers'.
However, you got it just the other way around. As it turns out, the quantifier that stays is the most inside quantifier, and the ones outside of it become the null quantifiers.
That is, a statement like $forall x exists x P(x)$ is the same as $exists x P(x)$
And $exists x forall x P(x)$ is equivalent to $forall x P(x)$
To explain:
Take $forall x exists x P(x)$ . Now, suppose that there is at least one object $x$ such that it has property $P$. Then $exists x P(x)$ is true, and notice that that statement has no free variables $x$. So, when you 'quantify' that expression by putting a $forall x$ in front of it, then that quantifier does not quantify anything and is therefore a null quantifier, and can be removed without changing the truth-conditions of the sentence
answered Nov 21 at 12:54
Bram28
58.8k44185
I should have used a relation symbol you are right. But I don't get it. Does the evaluation order matter? I evaluate from left to right i.e. from the outside. Is that the problem and instead I should look at it from the left from P(x)?
– Najib
Nov 21 at 12:57
Such that ∀x ∃x P(x) should be read like "P(x) is true for some x-s (and for all of those some)"?
– Najib
Nov 21 at 13:00
Okay. I am replying to each edit. So that means that the one quantifier that matters for the predicate is the one before it. So things should be read from right to left of the predicate the quantifier chain quantifies, right?
– Najib
Nov 21 at 13:05
@NajibGhadri Yes, because that is how you build up the sentence suntactically as well.
– Bram28
Nov 21 at 13:09
Thank you, it is all clear!
– Najib
Nov 21 at 13:10
|
show 3 more comments
up vote
0
down vote
A more succinct explanation: it's obvious that $exists x P(x)$ is equivalent to $exists y P(y)$. You can't change the truth value of a statement merely by renaming some entities.
So $forall x [exists x P(x)]$ should be equivalent to $forall x [exists y P(y)]$ - if you're queasy about this, step through it explicitly by setting $phi := exists x P(x)$.
But that is manifestly equivalent to $exists y P(y)$ (assuming as usual that the domain of discourse is not empty), which is just $exists x P(x)$.
edited Nov 21 at 23:41
Graham Kemp
84.6k43378
answered Nov 21 at 22:58
Patrick Stevens
28.2k52874
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
You are right that with multiple quantifiers that are next to each other and that quantify the same variable, you can reduce it to just one quantifier, as the others effectively end up not doing any interesting work at all; they are what are called 'null quantifiers'.
However, you got it just the other way around. As it turns out, the quantifier that stays is the most inside quantifier, and the ones outside of it become the null quantifiers.
That is, a statement like $forall x exists x P(x)$ is the same as $exists x P(x)$
And $exists x forall x P(x)$ is equivalent to $forall x P(x)$
To explain:
Take $forall x exists x P(x)$ . Now, suppose that there is at least one object $x$ such that it has property $P$. Then $exists x P(x)$ is true, and notice that that statement has no free variables $x$. So, when you 'quantify' that expression by putting a $forall x$ in front of it, then that quantifier does not quantify anything and is therefore a null quantifier, and can be removed without changing the truth-conditions of the sentence
answered Nov 21 at 12:54
Bram28
58.8k44185
I should have used a relation symbol you are right. But I don't get it. Does the evaluation order matter? I evaluate from left to right i.e. from the outside. Is that the problem and instead I should look at it from the left from P(x)?
– Najib
Nov 21 at 12:57
Such that ∀x ∃x P(x) should be read like "P(x) is true for some x-s (and for all of those some)"?
– Najib
Nov 21 at 13:00
Okay. I am replying to each edit. So that means that the one quantifier that matters for the predicate is the one before it. So things should be read from right to left of the predicate the quantifier chain quantifies, right?
– Najib
Nov 21 at 13:05
@NajibGhadri Yes, because that is how you build up the sentence suntactically as well.
– Bram28
Nov 21 at 13:09
Thank you, it is all clear!
– Najib
Nov 21 at 13:10
|
show 3 more comments
up vote
1
down vote
accepted
You are right that with multiple quantifiers that are next to each other and that quantify the same variable, you can reduce it to just one quantifier, as the others effectively end up not doing any interesting work at all; they are what are called 'null quantifiers'.
However, you got it just the other way around. As it turns out, the quantifier that stays is the most inside quantifier, and the ones outside of it become the null quantifiers.
That is, a statement like $forall x exists x P(x)$ is the same as $exists x P(x)$
And $exists x forall x P(x)$ is equivalent to $forall x P(x)$
To explain:
Take $forall x exists x P(x)$ . Now, suppose that there is at least one object $x$ such that it has property $P$. Then $exists x P(x)$ is true, and notice that that statement has no free variables $x$. So, when you 'quantify' that expression by putting a $forall x$ in front of it, then that quantifier does not quantify anything and is therefore a null quantifier, and can be removed without changing the truth-conditions of the sentence
answered Nov 21 at 12:54
Bram28
58.8k44185
I should have used a relation symbol you are right. But I don't get it. Does the evaluation order matter? I evaluate from left to right i.e. from the outside. Is that the problem and instead I should look at it from the left from P(x)?
– Najib
Nov 21 at 12:57
Such that ∀x ∃x P(x) should be read like "P(x) is true for some x-s (and for all of those some)"?
– Najib
Nov 21 at 13:00
Okay. I am replying to each edit. So that means that the one quantifier that matters for the predicate is the one before it. So things should be read from right to left of the predicate the quantifier chain quantifies, right?
– Najib
Nov 21 at 13:05
@NajibGhadri Yes, because that is how you build up the sentence suntactically as well.
– Bram28
Nov 21 at 13:09
Thank you, it is all clear!
– Najib
Nov 21 at 13:10
|
show 3 more comments
up vote
1
down vote
accepted
up vote
1
down vote
accepted
You are right that with multiple quantifiers that are next to each other and that quantify the same variable, you can reduce it to just one quantifier, as the others effectively end up not doing any interesting work at all; they are what are called 'null quantifiers'.
However, you got it just the other way around. As it turns out, the quantifier that stays is the most inside quantifier, and the ones outside of it become the null quantifiers.
That is, a statement like $forall x exists x P(x)$ is the same as $exists x P(x)$
And $exists x forall x P(x)$ is equivalent to $forall x P(x)$
To explain:
Take $forall x exists x P(x)$ . Now, suppose that there is at least one object $x$ such that it has property $P$. Then $exists x P(x)$ is true, and notice that that statement has no free variables $x$. So, when you 'quantify' that expression by putting a $forall x$ in front of it, then that quantifier does not quantify anything and is therefore a null quantifier, and can be removed without changing the truth-conditions of the sentence
answered Nov 21 at 12:54
Bram28
58.8k44185
You are right that with multiple quantifiers that are next to each other and that quantify the same variable, you can reduce it to just one quantifier, as the others effectively end up not doing any interesting work at all; they are what are called 'null quantifiers'.
However, you got it just the other way around. As it turns out, the quantifier that stays is the most inside quantifier, and the ones outside of it become the null quantifiers.
That is, a statement like $forall x exists x P(x)$ is the same as $exists x P(x)$
And $exists x forall x P(x)$ is equivalent to $forall x P(x)$
To explain:
Take $forall x exists x P(x)$ . Now, suppose that there is at least one object $x$ such that it has property $P$. Then $exists x P(x)$ is true, and notice that that statement has no free variables $x$. So, when you 'quantify' that expression by putting a $forall x$ in front of it, then that quantifier does not quantify anything and is therefore a null quantifier, and can be removed without changing the truth-conditions of the sentence
answered Nov 21 at 12:54
Bram28
58.8k44185
edited Nov 21 at 13:08
answered Nov 21 at 12:54
Bram28
58.8k44185
answered Nov 21 at 12:54
Bram28
58.8k44185
answered Nov 21 at 12:54
Bram28
58.8k44185
58.8k44185
I should have used a relation symbol you are right. But I don't get it. Does the evaluation order matter? I evaluate from left to right i.e. from the outside. Is that the problem and instead I should look at it from the left from P(x)?
– Najib
Nov 21 at 12:57
Such that ∀x ∃x P(x) should be read like "P(x) is true for some x-s (and for all of those some)"?
– Najib
Nov 21 at 13:00
Okay. I am replying to each edit. So that means that the one quantifier that matters for the predicate is the one before it. So things should be read from right to left of the predicate the quantifier chain quantifies, right?
– Najib
Nov 21 at 13:05
@NajibGhadri Yes, because that is how you build up the sentence suntactically as well.
– Bram28
Nov 21 at 13:09
Thank you, it is all clear!
– Najib
Nov 21 at 13:10
|
show 3 more comments
I should have used a relation symbol you are right. But I don't get it. Does the evaluation order matter? I evaluate from left to right i.e. from the outside. Is that the problem and instead I should look at it from the left from P(x)?
– Najib
Nov 21 at 12:57
Such that ∀x ∃x P(x) should be read like "P(x) is true for some x-s (and for all of those some)"?
– Najib
Nov 21 at 13:00
Okay. I am replying to each edit. So that means that the one quantifier that matters for the predicate is the one before it. So things should be read from right to left of the predicate the quantifier chain quantifies, right?
– Najib
Nov 21 at 13:05
@NajibGhadri Yes, because that is how you build up the sentence suntactically as well.
– Bram28
Nov 21 at 13:09
Thank you, it is all clear!
– Najib
Nov 21 at 13:10
I should have used a relation symbol you are right. But I don't get it. Does the evaluation order matter? I evaluate from left to right i.e. from the outside. Is that the problem and instead I should look at it from the left from P(x)?
– Najib
Nov 21 at 12:57
I should have used a relation symbol you are right. But I don't get it. Does the evaluation order matter? I evaluate from left to right i.e. from the outside. Is that the problem and instead I should look at it from the left from P(x)?
– Najib
Nov 21 at 12:57
Such that ∀x ∃x P(x) should be read like "P(x) is true for some x-s (and for all of those some)"?
– Najib
Nov 21 at 13:00
Such that ∀x ∃x P(x) should be read like "P(x) is true for some x-s (and for all of those some)"?
– Najib
Nov 21 at 13:00
Okay. I am replying to each edit. So that means that the one quantifier that matters for the predicate is the one before it. So things should be read from right to left of the predicate the quantifier chain quantifies, right?
– Najib
Nov 21 at 13:05
Okay. I am replying to each edit. So that means that the one quantifier that matters for the predicate is the one before it. So things should be read from right to left of the predicate the quantifier chain quantifies, right?
– Najib
Nov 21 at 13:05
@NajibGhadri Yes, because that is how you build up the sentence suntactically as well.
– Bram28
Nov 21 at 13:09
@NajibGhadri Yes, because that is how you build up the sentence suntactically as well.
– Bram28
Nov 21 at 13:09
Thank you, it is all clear!
– Najib
Nov 21 at 13:10
Thank you, it is all clear!
– Najib
Nov 21 at 13:10
|
show 3 more comments
up vote
0
down vote
A more succinct explanation: it's obvious that $exists x P(x)$ is equivalent to $exists y P(y)$. You can't change the truth value of a statement merely by renaming some entities.
So $forall x [exists x P(x)]$ should be equivalent to $forall x [exists y P(y)]$ - if you're queasy about this, step through it explicitly by setting $phi := exists x P(x)$.
But that is manifestly equivalent to $exists y P(y)$ (assuming as usual that the domain of discourse is not empty), which is just $exists x P(x)$.
edited Nov 21 at 23:41
Graham Kemp
84.6k43378
answered Nov 21 at 22:58
Patrick Stevens
28.2k52874
add a comment |
up vote
0
down vote
A more succinct explanation: it's obvious that $exists x P(x)$ is equivalent to $exists y P(y)$. You can't change the truth value of a statement merely by renaming some entities.
So $forall x [exists x P(x)]$ should be equivalent to $forall x [exists y P(y)]$ - if you're queasy about this, step through it explicitly by setting $phi := exists x P(x)$.
But that is manifestly equivalent to $exists y P(y)$ (assuming as usual that the domain of discourse is not empty), which is just $exists x P(x)$.
edited Nov 21 at 23:41
Graham Kemp
84.6k43378
answered Nov 21 at 22:58
Patrick Stevens
28.2k52874
add a comment |
up vote
0
down vote
up vote
0
down vote
A more succinct explanation: it's obvious that $exists x P(x)$ is equivalent to $exists y P(y)$. You can't change the truth value of a statement merely by renaming some entities.
So $forall x [exists x P(x)]$ should be equivalent to $forall x [exists y P(y)]$ - if you're queasy about this, step through it explicitly by setting $phi := exists x P(x)$.
But that is manifestly equivalent to $exists y P(y)$ (assuming as usual that the domain of discourse is not empty), which is just $exists x P(x)$.
edited Nov 21 at 23:41
Graham Kemp
84.6k43378
answered Nov 21 at 22:58
Patrick Stevens
28.2k52874
A more succinct explanation: it's obvious that $exists x P(x)$ is equivalent to $exists y P(y)$. You can't change the truth value of a statement merely by renaming some entities.
So $forall x [exists x P(x)]$ should be equivalent to $forall x [exists y P(y)]$ - if you're queasy about this, step through it explicitly by setting $phi := exists x P(x)$.
But that is manifestly equivalent to $exists y P(y)$ (assuming as usual that the domain of discourse is not empty), which is just $exists x P(x)$.
edited Nov 21 at 23:41
Graham Kemp
84.6k43378
answered Nov 21 at 22:58
Patrick Stevens
28.2k52874
edited Nov 21 at 23:41
Graham Kemp
84.6k43378
edited Nov 21 at 23:41
Graham Kemp
84.6k43378
edited Nov 21 at 23:41
Graham Kemp
84.6k43378
84.6k43378
answered Nov 21 at 22:58
Patrick Stevens
28.2k52874
answered Nov 21 at 22:58
Patrick Stevens
28.2k52874
answered Nov 21 at 22:58
Patrick Stevens
28.2k52874
28.2k52874
add a comment |
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3007693%2fwhat-is-the-meaning-of-%25e2%2588%2580x%25e2%2588%2583x%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
In general, if $x$ is not free in $phi$, both $forall x phi$ and $exists x phi$ are equivalent to $phi$.
– Mauro ALLEGRANZA
Nov 21 at 12:56
@MauroALLEGRANZA Thank you Mauro!
– Najib
Nov 21 at 22:52
Of course, in practice, it would be best to avoid such expressions (ask any CS student about "variable shadowing" for an explanation of why).
– Daniel Schepler
Nov 21 at 23:28