Syntax of First Order Logic

131 Views Asked by At

Give a counter example to show that a sentence of the form $\forall x (F \vee G) \rightarrow (\forall x F) \vee (\forall x G)$

I know that I should use two particular formulas $F$ and $G$ from some language and also a particular structure interpreting that language in such a way that $\forall x (F \vee G) \rightarrow (\forall x F) \vee (\forall x G)$ is not true in that structure, not sure where to go with this though.

3

There are 3 best solutions below

0
On

Hint: Suppose that $F$ and $G$ are complement of each other. i.e. $\forall x (Fx\leftrightarrow \neg G x)$ and $\exists x (\neg G x)$ and $\exists x (\neg F x)$.

0
On

$\forall x\in\{1,2\}.\ x=1\lor x=2$

vs.

$(\forall x\in\{1,2\}.\ x=1)\lor (\forall x\in\{1,2\}.\ x=2)$

0
On

(1) You can reflect informally. What does the wff say? "If everything [in the relevant domain] is either $F$ or $G$, then either everything is $F$ or everything is $G$" Does that informal claim strike you as true? Can you think of an obvious counterexample?? [Well, surely so! Take the domain to be people. Think of a way of carving people into $F$s and $G$'s, where no one is both ...] Use your informal counterexample to the informal claim to describe an official formal model in which the given formal wff fails.

(2) You can proceed more methodically. If

$$\forall x (Fx \vee Gx) \rightarrow (\forall x Fx \vee \forall x Gx)$$

is to be false in a model, you'll need the antecedent true and consequent false. For the consequent to be false both $\forall xFx$ and $\forall xGx$ to be false. So we'll need an element in the model, call it '$1$' such that

(a) not-$F1$,

and we need an element in the model, call it '$2$', such that

(b) not-$G2$.

Let's see if we can make do with just these two elements in the model. Well to make the antecedent true, we'd have to make

(c) $F1 \vee G1$

(d) $F2 \vee G2$

both true. Which tell us we must have

(e) $F2$

(f) $G1$.

So now it is trivial to make (a), (b), (e) and (f) all true together and we are done ....