0
$\begingroup$

I'm trying to get a better understanding of models in predicate logic.

This is an old exam-task:

Decide if the sequent is valid:

$$ \vdash \forall x  \exists y R(x, y)  \lor  \forall x  \exists y  \neg R(x, y) $$

The answer/counter-model is: A = {0, 1}, R^m = {(1, 1), (1, 0)}

The counter-model makes sence to me, but at the same time it doesn't. It makes sense to me if the left side of the "or" gets the input (1 ,1) and the variables x and y cannot be equal. And x, y corresponds to (1,1) respectively. And the right side of the "or" gets the input (0, 1).

R^m = {(1, 1), (1, 0)} My understanding is that R is satisfied for these two inputs only?

If so, wouldn't the left side of the "or"  be true no matter which of the two inputs and hence the whole expression would be true?

Is a valid sequent, in predicate logic, a sequent that holds for any model?

Can someone explain why this is a counter-model?

$\endgroup$
  • $\begingroup$ There is no reason to suggest the values $x, y$ cannot be equal. $\endgroup$ – Graham Kemp Oct 23 '18 at 3:06
2
$\begingroup$

You are correct. $M = \{0, 1\}$, $R^M = \{(1, 1), (0, 1)\}$ is not a countermodel because the left disjunct is true. If $x=0,$ then $R(0,1)$ holds and if $x=1$ then $R(1,1)$ holds (so in either case $y=1$ works).

Instead, you can show $R^M= \{(0,0), (0,1)\}$ is a countermodel.

A sequent of the form $\vdash S$ is valid iff $S$ is true in all models, so this countermodel shows it is not valid. More generally, a sequent of the form $\Pi\vdash \Gamma,$ where $\Pi$ and $\Gamma$ are finite lists of sentences, is valid iff for any model where all sentences in $\Pi$ are true, at least one of the sentences in $\Gamma$ is true.

EDIT OP has edited the question to reflect the fact that the actual countermodel given in the solution was $\{(1,1), (1,0)\},$ which is a correct choice.

$\endgroup$
  • $\begingroup$ Thank you for your answer but now I'm even more confused. Isn't {(0, 0), (0, 1)} the same principle as {(1, 1), (0, 1)} ? Doesn't R hold for both (0, 0) and (0, 1)? $\endgroup$ – Lars Logik Oct 22 '18 at 21:34
  • $\begingroup$ I'm sorry! The answer to the question is R^m = {(1,1),(1,0)}. Not {(1,1),(0,1)}. I don't see why it would make a differense, if it does. $\endgroup$ – Lars Logik Oct 22 '18 at 21:48
  • 1
    $\begingroup$ @LarsLogik It does make a difference. That one is a countermodel. For the left disjunct to hold, we need for all $x,$ there is a $y$ such that $(x,y)\in R.$ Let $x=0.$ There is no $y$ such that $(0,y)\in R.$ So the left disjunct does not hold. (Then we'd need to show the right doesn't hold either.) $\endgroup$ – spaceisdarkgreen Oct 22 '18 at 22:00
  • $\begingroup$ @spaceisdarkgreen You did good! $\endgroup$ – Bram28 Oct 22 '18 at 22:08
  • $\begingroup$ Of course, I see. All x is A={0,1} and when x is 0 then there is no y. Thanks alot! $\endgroup$ – Lars Logik Oct 22 '18 at 22:09
1
$\begingroup$

Maybe it is easier to give some concrete meaning to these predicates first.

So, assume the domain is all people, and interpret $R(x,y)$ as $x$ likes $y$.

Finally, assume that there is someone (call this person 'Happy Bob') who likes everyone ... and finally assume that there is someone else (say, 'Grumpy Alice') who doesn't like anyone at all.

This is a counter-model to the claim, because $\forall x \exists yR(x,y)$ says that everyone likes someone, which is not true, since it is not true for Grumpy Alice.

Likewise, $\forall x \exists y \neg R(x,y)$ says that for everyone there is someone they don't like, which is also not true, since it is not true for Happy Bob.

And now maybe you can see the 'trick' to the counterexample: you need an object that is related in the $R$ relationship to everything, as well as an object that is related in the $R$ relationship to nothing. This is exactly what happens in the counter-model provided by the book.

$\endgroup$
  • $\begingroup$ This clear things up. Thank you. $\endgroup$ – Lars Logik Oct 22 '18 at 22:20
1
$\begingroup$

We want it not to be true that either $\forall x~\exists y~R(x,y)$ or $\forall x~\exists y~\lnot R(x,y)$ holds.

Since a universal quantifier is falsified by a single exception, therefore we want an exception for each disjunct.

  • Let us say for $0$, we would like there to be no $y$ for which $R(0,y)$ holds.
  • Let us say for $1$, we would like there to be no $y$ for which $R(1,y)$ does not hold.
  • Well, we don't need any additional terms, so a universe of $\{0,1\}$ will do.   Keep it simple.
    • So we must build some $R$, where $R\subseteq\{0,1\}$, that fits the above.
    • Well, clearly: $R=\{(1,0),(1,1)\}$
  • Done.   There is a universe and a relation which $\forall x~\exists y~R(x,y)~\lor ~\forall x~\exists y~\lnot R(x,y)$ is falsified.
$\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.