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
  • 4
    $\begingroup$ Yes, exactly so. $\endgroup$
    – bof
    Mar 28, 2017 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, 2017 at 4:05
  • $\begingroup$ @user400188 No, we only require one witness to the existence of at least one thing. $\endgroup$ Mar 28, 2017 at 4:11
  • $\begingroup$ math.stackexchange.com/questions/2182629/logical-truth-question/… $\endgroup$
    – Bram28
    Mar 28, 2017 at 16:12

1 Answer 1

1
$\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$
4
  • $\begingroup$ I love your examples. But I can't understand your proof which uses formulars that I can't understand. $\endgroup$ Apr 15, 2017 at 3:04
  • $\begingroup$ @Jingguo Yao What exactly is it you don't understand? $\endgroup$ Apr 15, 2017 at 8:18
  • $\begingroup$ In $\mathcal{M} = \langle D, I \rangle$, what do $D$ and $I$ represent? $\endgroup$ Apr 15, 2017 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$ Apr 15, 2017 at 8:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .