Order of quantifiers in first-order logic

[Joestar]

Hello.

According to this lecture(somewhere around 5:20) shifting order of quantifiers in first-order logic can create a formula which isn't equivalent to the preceding one.

So, Ax Ey P(x,y) would not be the same as Ey Ax P(x,y).

I don't understand why is that so and the lecture doesn't mention it much. Can anyone here explain why?

[prime1999]

The second is stronger than the first, since for the first, it does not need the y to be the same in the P(x,y) for all x.

P(x,y):
  y
 010
x001
 100

1 - true
0 - false

The above can satisfy [for all x, there exists y where P(x,y)], but cannot satisfy [There exists y where for all x, P(x,y)].

[Rashakil Fol]

So, Ax Ey P(x,y) would not be the same as Ey Ax P(x,y).

I don't understand why is that so and the lecture doesn't mention it much. Can anyone here explain why?

Read the sentences. "For all x, there exists y such that P(x,y)." "There exists y such that for all x, P(x,y)." They obviously have different meanings.

[geezus]

Hello.

According to this lecture(somewhere around 5:20) shifting order of quantifiers in first-order logic can create a formula which isn't equivalent to the preceding one.

So, Ax Ey P(x,y) would not be the same as Ey Ax P(x,y).

I don't understand why is that so and the lecture doesn't mention it much. Can anyone here explain why?

so one somewhat subtle thing to keep in mind, first off, is that quantifications don't occur in parallel or simultaneously, so to speak; one is applied to the result of applying the other.

less obtusely, \exists{x} \forall{y} P(x,y) is actually shorthand for \exists{x}(\forall{y}(P(x,y))), & similarly with your other statement.

this is not entirely dissimilar to the composition of functions: g(f(x)) is not necessarily equal to f(g(x)) - in fact even saying this is a bit sloppy, as the composed functions may not even be over the same domain.

so here's what the two statements mean, respectively:

in spoken mathematics the association implied by the parentheses as in the above would normally be read as "such that"... bear with me...

\exists{x} \forall{y} P(x,y) is read "there exists some x, such that for all y, P(x,y) [ is true ]".

again, we're kind of glossing over the issue of domain here... for now let's just assume that x & y are both real numbers, & thus both elements of the same set [ of real numbers ]... to see why this matters google "russell's paradox".

this is an assertion of the existence of exactly one real number, call it x, for which P(x,y) is true for every real number y. there could very well be some other real number, call it z, such that P(z,y) is also true for every real number y - or not. this statement makes no assertion one way or the other on the uniqueness of x. oftentimes in mathematics simply proving the existence of exactly one object satisfying some set of conditions can give you a lot to work with.

also note that if y ranges over every element of the reals, that P(x, x) is true, since x is a real itself, after all. i'm not sure if that's obvious or not.

take P(x,y) to be defined as x \times y = 0, where the cross just represents the ordinary multiplication of reals. then in this case, the statement is true because there does exists one real number x - that being 0 - such that P holds. in this case there's exactly one such real but in general, for arbitrary statements, this need not be the case.

actually, i'll stop here for now... let me know if this makes sense & if it does we can go over the other statement if need be; if not we can drill down into this one more.

[Allan Joshua]

Ax Ey P(x,y) would not be the same as Ey Ax P(x,y).

P is a relation. Try to replace this abstract relation to some thing which is more specific and that would help understand.

Replace P with Loves.

so AxEy Loves(x,y) means
Everybody loves some body.
which means
Jack loves jill or jack loves rose or jack loves jeniffer .... and so on
mike loves maureen or mike loves yasmene or ..........
....
which means every one loves some one else

wheras
EyAx loves (x,y) means There exists someone whom every one loves

Say this Y is allan

Every one loves allan

jeniffer loves allan
yasmene loves allan
person x loves allan
person y loves allan
so on and so forth.

Hope this helps.