The following predicate logic formula is invalid (i.e. not a tautology):

$\Bigl[\forall x \,\exists y {\,.\,} P(x,y)\Bigr] \implies \Bigl[\exists y \, \forall x {\,.\,} P(x,y)\Bigr]$

Which of the following are counter-models (i.e. counterexamples) for it?

  1. The predicate $P(x,y) \equiv \bigl[ y \cdot x = 1 \bigr]$, where the domain of discourse is $\mathbb{Q}$.
  2. The predicate $P(x,y) \equiv \bigl[ y<x \bigr]$, where the domain of discourse is $\mathbb{R}$.
  3. The predicate $P(x,y) \equiv \bigl[ y \cdot x = 2 \bigr]$, where the domain of discourse is $\mathbb{R} \smallsetminus \{ 0 \}$.
  4. The predicate $P(x,y) \equiv \bigl[y \,x \,y = x\bigr]$, where the domain of discourse is $\{0,1\}^\ast$
    — that is, the set of all binary strings, including the empty string).

Is my answer below true ?

Answer: I think the first model is not a counter model since 0 is a member of rational numbers there exists no rational y for which $x \cdot y = 1$. So $\forall x \,\exists y {\,.\,} P(x,y)$ is false, thereby validating the conditional for this choice of predicate $P$. Also sentence 4 is not a counter model. The other two are counter-models.

  • $\begingroup$ source courses.csail.mit.edu/6.042/spring12/part1.pdf page 70 $\endgroup$
    – levi
    Commented Aug 4, 2012 at 11:19
  • 1
    $\begingroup$ Yes. If this is an exercise you have to hand in, make sure you give solid proofs (which answer the question for you, by the way). I am closing this as "too localized" as this is not likely to be useful for anybody else. $\endgroup$
    – Raphael
    Commented Aug 4, 2012 at 13:43
  • 2
    $\begingroup$ While it's important to make sure you get your reasoning straight, it's also important to have confidence in your reasoning — if you can keep your resoning simple and crisp, there isn't any particular reason to hesitate unless you're uncertain of your definitions. In each case, you have a countermodel if and only if the predicate causes the conditional to evaluate as false. This only happens if the hypothesis is true and the consequent is false. So it's enough to argue precisely how that comes about (or fails to). $\endgroup$ Commented Aug 4, 2012 at 14:02
  • 3
    $\begingroup$ @Raphael: I didn't really see whether levi was learning on his own, but my comment is really meant more as advice than criticism. In order to master a subject, the most important thing to learn is independence — but it is indeed something that has to be learned, and as with most subjects it can be easier to learn if someone teaches you how it works. $\endgroup$ Commented Aug 4, 2012 at 17:21
  • 1
    $\begingroup$ meta-discussion $\endgroup$
    – Kaveh
    Commented Aug 4, 2012 at 20:46

1 Answer 1

  1. Not a counter model, for as you say, the antecedent is not true when $x = 0$.
  2. A counter model: Every number has a number less than it in $\mathbb{R}$, however there are no least number.
  3. A counter model: For $x$, let $y = 1/x$, so the antecedent holds, there is no $y$ such that for all $x$, we have that $x \cdot y = 2$.
  4. Not a counter model: The consequent is always true, let $y = \epsilon$, then for all $x$, it holds that $yxy = x$.
  • 1
    $\begingroup$ 4 is not a counter model, but for different reason; it's not counter model because for every $x$ it holds for the same $y = \epsilon$, so both sides are true. $\endgroup$
    – Jan Hudec
    Commented Feb 5, 2013 at 7:56
  • $\begingroup$ @JanHudec Thank you for pointing it out, you are absolutely correct. I have updated the answer. $\endgroup$ Commented Feb 5, 2013 at 8:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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