Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
source courses.csail.mit.edu/6.042/spring12/part1.pdf page 70 –  levi Aug 4 '12 at 11:19
1  
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. –  Raphael Aug 4 '12 at 13:43
2  
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). –  Niel de Beaudrap Aug 4 '12 at 14:02
3  
@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. –  Niel de Beaudrap Aug 4 '12 at 17:21
1  
meta-discussion –  Kaveh Aug 4 '12 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$.
share|improve this answer
1  
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. –  Jan Hudec Feb 5 '13 at 7:56
    
@JanHudec Thank you for pointing it out, you are absolutely correct. I have updated the answer. –  Pål GD Feb 5 '13 at 8:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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