2
$\begingroup$
  1. $\exists y \forall x P(x, y)$ means: There exists some $y$ such that $P(x, y)$ holds for all $x$.

  2. $\forall x \exists y P(x, y)$ means: For all $x$, there exists some $y$ such that $P(x, y)$ holds.

My understanding is that 1 implies 2. Here is my reasoning:

1 means that there is some $y$ such that $P(x, y)$ holds for all $x$. Let name it as $a$. So $P(x, a)$ holds for all $x$. Then for all $x$, there exists $a$ such that $P(x, a)$ holds. So 2 can be deduced.

In other words, one $y$ needs to make $P(x, y)$ holds for all $x$ in 1. $y$ stays the same. In 2, to make $P(x, y)$ hold for all $x$, $y$ does not need to be the same thing.

Is my understanding correct?

$\endgroup$
  • 4
    $\begingroup$ Yes, exactly so. $\endgroup$ – bof Mar 28 '17 at 3:15
  • $\begingroup$ I am slightly confused here. The existential quantifier allows for more than one y to make P(x,y) hold. Should not we prove that this works for multiple y as well? $\endgroup$ – user400188 Mar 28 '17 at 4:05
  • $\begingroup$ @user400188 No, we only require one witness to the existence of at least one thing. $\endgroup$ – Graham Kemp Mar 28 '17 at 4:11
  • $\begingroup$ math.stackexchange.com/questions/2182629/logical-truth-question/… $\endgroup$ – Bram28 Mar 28 '17 at 16:12
0
$\begingroup$

Yes, it is true that $\exists y \forall x \phi \models \forall x \exists y \phi$, and your explanation is correct.

Suppose that for some structure $\mathcal{M} = \langle D, I \rangle$ and some variable assignment $v$, $[[\exists y \forall x \phi]]^\mathcal{M}_v = 1$. Then there is some $d \in D$ such that $[[\forall x \phi]]^\mathcal{M}_{v[y \mapsto d]} = 1$, and consequently, there is some $d \in D$ such that for all $d' \in D$: $[[\phi]]^\mathcal{M}_{v[y \mapsto d][x \mapsto d']} = 1$. But then, for any $d' \in D$ there is some $d \in D$ such that $[[\phi]]^\mathcal{M}_{v[y \mapsto d][x \mapsto d']} = 1$, so for any $d' \in D$, $[[\exists y \phi]]^\mathcal{M}_{v[x \mapsto d']} = 1$, and hence $[[\forall x \exists y \phi]]^\mathcal{M}_v = 1$.

The proof might seem a bit circular because at some point you just need to swap the quantifiers on the meta level the same way as you eventually do at the level of the object language, but this meta level argumentation should make it clear why the consequence holds (and is essentially what you did).

Example: Suppose that $\mathcal{M} = \langle \mathbb{N}, \geq \rangle$ and $\phi \bumpeq x \geq y$.
$\exists y \forall x (x \geq y)$ is a true statement in the model since there is some $y$ such that $x \geq y$ for all $x$, with $y = 0$.
Then obviously for all $x$ there is some $y$ (namely $0$) such that $x \geq y$, and therefore $\forall x \exists y (x \geq y)$ is true in model $\mathcal{M}$.

On the other hand, the reverse direction does not hold: $\forall x \exists y \phi \not \models \exists y \forall x \phi$
Example: Suppose that $\mathcal{M} = \langle \mathbb{N}, = \rangle$ and $\phi \bumpeq x = y$.
Then obviously, for any $x$ there is a $y$ such that $x = y$, so $\forall x \exists y (x = y)$ is true in $\mathcal{M}$.
However, there is no $y$ such that $x = y$ for all $x$, hence $\exists y \forall x (x = y)$ is false.

$\endgroup$
  • $\begingroup$ I love your examples. But I can't understand your proof which uses formulars that I can't understand. $\endgroup$ – Jingguo Yao Apr 15 '17 at 3:04
  • $\begingroup$ @Jingguo Yao What exactly is it you don't understand? $\endgroup$ – lemontree Apr 15 '17 at 8:18
  • $\begingroup$ In $\mathcal{M} = \langle D, I \rangle$, what do $D$ and $I$ represent? $\endgroup$ – Jingguo Yao Apr 15 '17 at 8:37
  • $\begingroup$ $D$ represents the universe/the domain of the structure and $I$ the interpretation of the non-logical symbols (= individual constants, relations, functions). $\endgroup$ – lemontree Apr 15 '17 at 8:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.