Logic - Switching quantifiers

[rokimomi]

Homework Statement

Determine whether $$\exists$$x$$\forall$$y[p(y) --> q(x)] is equivalent to $$\forall$$y$$\exists$$x[p(y) --> q(x)], justify your answer with a proof.

Homework Equations

The Attempt at a Solution

I know that when you switch quantifiers in something like P(x,y), the meaning changes and it is not equivalent but how about here where the variables are again separated. My intuition is telling me they are equivalent, or rather I should say I can't think of any proof that would falsify this.

Likewise, I can't think of how to prove this either. Would I have to do something along the lines of exploring all true false values for the given situations?

 

[KataKoniK]

it is important to approach problems with a logical and systematic mindset. In this case, we are dealing with two quantified statements, \existsx\forally[p(y) --> q(x)] and \forally\existsx[p(y) --> q(x)]. In order to determine their equivalence, we must first understand the meaning of each statement.

The statement \existsx\forally[p(y) --> q(x)] can be read as "There exists an x such that for all y, if p(y) is true, then q(x) is true." This means that there is at least one value of x that satisfies the condition of p(y) implying q(x) for all possible values of y.

On the other hand, the statement \forally\existsx[p(y) --> q(x)] can be read as "For all y, there exists an x such that if p(y) is true, then q(x) is true." This means that for every possible value of y, there is at least one value of x that satisfies the condition of p(y) implying q(x).

At first glance, these statements may seem different. However, upon closer inspection, we can see that they are actually equivalent. This can be proven by using a direct proof.

Let us assume that \existsx\forally[p(y) --> q(x)] is true. This means that there exists at least one value of x, let's call it a, that satisfies the condition of p(y) implying q(a) for all possible values of y. By definition, this also means that for every possible value of y, there exists at least one value of x, namely a, that satisfies the condition of p(y) implying q(x). This is exactly what \forally\existsx[p(y) --> q(x)] states, therefore the two statements are equivalent.

Now, let us assume that \forally\existsx[p(y) --> q(x)] is true. This means that for every possible value of y, there exists at least one value of x, let's call it b, that satisfies the condition of p(y) implying q(b). By definition, this also means that there exists at least one value of x, namely b, that satisfies the condition of p(y) implying q(x) for all possible values of y. This is exactly what \existsx\forally[p(y) --> q(x)] states,