# Prove or disprove: $\exists x \forall y \,\,\varphi \models \forall y \exists x \,\ \varphi$

Prove or disprove: $\exists x \forall y \,\,\varphi \models \forall y \exists x \,\ \varphi$

where $\varphi$ is a first-order-logic formula

About notation: I call LHS as $A$ and RHS as $B$. Then $A \models B$ means that $B$ is true in every structure in wich $A$ is true. Now question is if this is the case here, with proof.

Let's say we have $\varphi : = R(x,y)$ where $R$ stands for relation.

Then LHS says that

For some $x$, all $y$ are such that $R(x,y)$

RHS says that

For any $y$, there is a $x$ such that $R(x,y)$

Now if we expand those two sentences, we have for LHS:

There exists a $x \in \mathbb{N}$, such that for any number $y$, we have that $x >y$. This is wrong because there can't be number that is greater than all numbers.

For RHS we have:

For any $y \in \mathbb{N}$, there exists a number $x$ such that $x > y$. This is correct because for any number there is always a bigger number.

For this reason we have no model here and this means the statement is false.

I like to know if this is correct pls because I need it for exam and I would do it like that in exam if they ask similar question?

• What do you get for proving the LHS wrong? – Kenny Lau Jan 21 '18 at 13:00
• If the premises is false the relation holds vacuously. The def of $\vDash$ says: tehre is no model of the premises where the consequence is false. – Mauro ALLEGRANZA Jan 21 '18 at 13:09
• @conime You probably mean $>$ instead of $<$ in your model. – Magdiragdag Jan 21 '18 at 13:16
• @Magdiragdag Thank you because I made this yellow I accidently delete wrong sign – roblind Jan 21 '18 at 13:34
• @conime That sounds unnecessarily complicated ... . As you said, if A is true then there is some x such that for all y R(x,y). OK, so let's call this x 'Bob'. So, 'Bob' stands in relation R to everything (including itself). But then it is true that for everything, there is something that stands in relation R to it (namely 'Bob'). So, B is true. – Bram28 Jan 21 '18 at 14:22

You are given $\exists x\forall y\;\varphi(x,y)$. So let $x_0$ be such that $\forall y\;\varphi(x_0,y)$. In particular, for arbitrary $y$, we have $\varphi(x_0,y)$.
Now let $y$ be arbitrary. As just seen, we have $\varphi(x_0,y)$, hence $\exists x\;\varphi(x,y)$. As $y$ was arbitrary, $\forall y\exists x\;\varphi(x,y)$, as was to be shown.
All you have done so far is to show one particular structure in which $A$ is false and $B$ is true. This tells you nothing about $A\vDash B$, which is about structures where $A$ is true. It does not care what might happen to $B$ in structures that don't satisfy $A$.
• I'm not sure if I understand that correct. Would my solution be correct if we were looking for $B \models A$? If this is wrong I really don't know what to do for this example : / – roblind Jan 21 '18 at 13:35
• @conime: Yes, your argument does disprove $B\vDash A$. Since $\exists x \forall y \,\,\varphi \models \forall y \exists x \,\ \varphi$ is alctually true, you should be looking for a proof rather than a counterexample. – Henning Makholm Jan 21 '18 at 13:38
'Informal semantical proof': If A is true then there is some $x$ such that for all $y$ such that $R(x,y)$. OK, so let's call this x 'Bob'. So, 'Bob' stands in relation $R$ to everything (including itself). But then it is true that for everything, there is something that stands in relation $R$ to it (namely 'Bob'!). So, for all $y$ there is some $x$ such that $R(x,y)$. So, B is true.