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?
- The predicate $P(x,y) \equiv \bigl[ y \cdot x = 1 \bigr]$, where the domain of discourse is $\mathbb{Q}$.
- The predicate $P(x,y) \equiv \bigl[ y<x \bigr]$, where the domain of discourse is $\mathbb{R}$.
- The predicate $P(x,y) \equiv \bigl[ y \cdot x = 2 \bigr]$, where the domain of discourse is $\mathbb{R} \smallsetminus \{ 0 \}$.
- 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.