I am studying for an exam to be taken next Friday and I am only stuck on one question in my revision guide, which I simply do not understand. (I even have the answers as well)
The question:
Show, by producing a counter-model in each case, that neither of the following is a valid argument:
(a) $$\forall x(G(x) \to H(x)),G(a) \mid= \forall xH(x)$$
(b) $$H(a) \to \forall xG(x), \lnot(G(a) \lor G(b)) \mid= \lnot\exists xH(x)$$
And the answer:
We need to find a counter-model, i.e. a model in which the formulas on the left-hand side of $\mid=$ are true and that on the right-hand side is false.
(a) Take $M = (\{1,2\},I)$, where $I(a) = 1, I(G) = \{1\}$ and $I(H) = \{1\}$. Then $\forall x(G(x) \to H(x))$ holds in $M$, $G(a)$ does too, but $H(2)$ does not hold. So $\forall xH(x)$ does not hold in $M$.
(b) Take $M = (\{1,2\},I)$, where $I(a) = 1$, $I(b) = 2$, $I(G) = 0$ and $I(H) = {2}$. Then $H(a) \to \forall xG(x)$ is satisfied and so is $\lnot(G(a)\lor G(b))$. But $H(b)$ holds, so it is not true that $\lnot \exists xH(x)$ holds.
What I know:
When answering these questions before looking at the answers I used the Predicate Tableux method to evaluate that a false outcome was possible when all statements were true.
I really have no idea how these answers were concluded. Is there a way to produce such a answer derived from a completed tableaux showing that a false outcome is possible when all statements are true? (The reason I ask is because I find tableaux rather easy and would like to stick to it to not cause ambiguity in the exam)
As stated in your problem, in order to prove that an argument is not valid, we have to produce a counter-model.
To use the tableaux method for finding a counter-model to :
we have to consider the formula :
and "run" the tableaux. If it will not close, the "open" path will give us a counter-example for (*).
This because the open path will define a "model" satisfying the formula (§).
But, in general, we have that $p \to q$ is equivalent to $\lnot (p \land \lnot q)$.
Thus, to find a model for $(p \land \lnot q)$ means that it is satisfiable; but if it is satisfiable, then its negation, i.e. $p \to q$ is not valid.
Finally, we have that $\vDash p \to q$ iff $p \vDash q$.
Thus, to prove that (§) is satisfiable is equivalent to prove that (*) is not a valid argument, i.e. that the conclusion : $∀xH(x)$, does not follow from the premises : $∀x(G(x) → H(x)), G(a)$.
Example
1) $∀x(G(x) → H(x)) \land G(a) \land \lnot ∀xH(x)$
2) $∀x(G(x) → H(x))$ --- from 1) by rule for $\land$
3) $G(a)$ --- as 2)
4) $\lnot ∀xH(x)$ --- as 2)
5) $\lnot H(b)$ --- from 4) by rule for $\lnot \forall$ : $b$ new
6) $G(a) → H(a)$ --- from 2) by rule for $\forall$ with $a$
7) $G(b) → H(b)$ --- from 2) by rule for $\forall$ with $b$
Now we use the $\to$ rule with 6), generating two branches : $8_L$ and $8_R$ :
$8_L$) $\lnot G(a)$ --- this path closes with 3) : $\times$
$8_R$) $H(a)$
Now we use again the $\to$ rule with 7), generating two branches : $9_L$ and $9_R$ :
$9_L$) $\lnot G(b)$ --- OPEN
$9_R$) $H(b)$ --- this path closes with 5) : $\times$.
Conclusion : the path through 1)-7), $8_R$), $9_L$) is open and thus all the formulae on it (including 1)) are satisfiable
The satisfying model must be manufactured starting from atoms :
From this, the answer :
We need a domain with two objects for the two parameters $a,b$ respectively (i.e. : $1,2$), such that the two subsets of the domain of $\mathcal M$ used to interpret the two predicates $G,H$ (i.e. $\mathcal I(G), \mathcal I(H)$) both contain the object assigned to $a$ (due to : $G(a)$ and $H(a)$); thus, we need :
We need also that the interpretation of $G$ does no contain the object assigned to $b$ (due to $\lnot G(b)$), i.e. :
Finally, we need that the interpretation of $H$ does no contain the object assigned to $b$ (due to $\lnot H(b))$, i.e. :
Now we can easily check that $\mathcal M \vDash \forall x(G(x) \to H(x))$ and that $\mathcal M \nvDash \forall xH(x)$.