1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What do you get for proving the LHS wrong? $\endgroup$ – Kenny Lau Jan 21 '18 at 13:00
  • 1
    $\begingroup$ 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. $\endgroup$ – Mauro ALLEGRANZA Jan 21 '18 at 13:09
  • 1
    $\begingroup$ @conime You probably mean $>$ instead of $<$ in your model. $\endgroup$ – Magdiragdag Jan 21 '18 at 13:16
  • $\begingroup$ @Magdiragdag Thank you because I made this yellow I accidently delete wrong sign $\endgroup$ – roblind Jan 21 '18 at 13:34
  • 1
    $\begingroup$ @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. $\endgroup$ – Bram28 Jan 21 '18 at 14:22
3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ 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 : / $\endgroup$ – roblind Jan 21 '18 at 13:35
  • $\begingroup$ @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. $\endgroup$ – Henning Makholm Jan 21 '18 at 13:38
3
$\begingroup$

'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.

And here is a formal proof in Fitch:

enter image description here

$\endgroup$

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.