patternMinor
Validity of predicate logic formulas
Viewed 0 times
validityformulaslogicpredicate
Problem
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?
— 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.
$\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
- 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.
Solution
- Not a counter model, for as you say, the antecedent is not true when $x = 0$.
- A counter model: Every number has a number less than it in $\mathbb{R}$, however there are no least number.
- 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$.
- Not a counter model: The consequent is always true, let $y = \epsilon$, then for all $x$, it holds that $yxy = x$.
Context
StackExchange Computer Science Q#3034, answer score: 2
Revisions (0)
No revisions yet.