Show that $ (\forall x)(A \lor B) \rightarrow A \lor (\forall x)B $ is, in general, NOT a theorem.

Question

Show that $$ (\forall x)(A \lor B) \rightarrow A \lor (\forall x)B $$ is, in general, NOT a theorem.

---

My answer:

First, I got the abstraction of the formula which is $ p \rightarrow A \lor q$ then I did a truth table for the abstraction. The truth table show one instance that is false. So the abstraction is not a tautology. Therefore the original formula $(\forall x)(A \lor B) \rightarrow A \lor (\forall x)B$ is also not a tautology.

$ \not\vDash_{taut} (\forall x)(A \lor B) \rightarrow A \lor (\forall x)B$

By the contrapositive of Completeness.

$ \not\vdash (\forall x)(A \lor B) \rightarrow A \lor (\forall x)B$

---

Is my answer correct ?

The original question was "In particular, find specific wffs $A$ and $B$ such that the above conditional is not a theorem." So also I need to know how can I do that ?

I use Mathematical Logic by George Tourlakis.

Answer 1

1. Predicate logic (quantificational logic) is an extension of propositional logic: there are predicate logic theorems that aren't propositional logic theorems, i.e. which aren't tautologies. Example: $\forall x(A \land B) \to (\forall xA \land \forall xB)$ is a predicate logic theorem, but obviously not a tautology. So showing a predicate logic wff is not a tautology does not show it is not a predicate logic theorem. Hence the reasoning suggested in the question is invalid.
2. Take the domain of quantification to be numbers, let $A$ be $Even(x)$, $B$ mean $Odd(x)$ is odd. Then $\forall x(A \lor B)$ is true: but there are assignments on which $A \lor \forall xB$ is false -- suppose we assign $x$ the number 3, then both disjuncts are false. So, being falsifiable, by completeness, $(\forall x)(A \lor B) \rightarrow A \lor (\forall x)B$ isn't in general a theorem.
3. Question: what happens if we insist that $A$ does not contain $x$ free?

Answer 2

In the above answer Peter Smith has shown why, in general : $(∀x)(A \lor B) → A \lor (∀x)B$ is not valid and thus (by Completeness) not a theorem.

We will prove the "special case" with the proviso : $x$ not free in $A$.

---

We will "mimick" the proof [see 6.4,1 Theorem, page 172] of :

$\vdash (\forall x)(A \rightarrow B) \rightarrow (A \rightarrow (\forall x)B)$, provided $x$ is not free in $A$.

We will use :

2.4.4 Theorem. (Double Negation) [page 67] : $\vdash \lnot \lnot A \equiv A$

and

2.4.11 Theorem [page 70] : $\vdash A \rightarrow B \equiv \lnot A \lor B$

to derive :

$\vdash A \lor B \equiv \lnot A \rightarrow B$ --- (*)

---

Proof :

1) $(∀x)(A \lor B)$ --- assumed

2) $A \lor B$ --- from 1) by 6.1.6 Corollary : $(\forall x)A \vdash A$

3) $\lnot A \rightarrow B$ --- from 2) by (*)

4) $\lnot A$ --- assumed

5) $B$ --- from 3) and 4) bt modus ponens

6) $(\forall x)B$ --- from 5) by 6.1.1 Metatheorem. (Weak Generalization) : Let $\Gamma \vdash A$ and let moreover $x$ not occur free in any formula found in the set $\Gamma$. Then $\Gamma \vdash (\forall x)A$ as well. Here $\Gamma = \{ (∀x)(A \lor B), \lnot A \}$ and $x$ is not free in $A$; thus, the (meta-)theorem applies.

7) $\lnot A \rightarrow (\forall x)B$ --- from 4) and 6) by 2.6.1 Metatheorem. (Deduction Theorem) : If $\Gamma \cup \{ A \} \vdash B$, then also $\Gamma \vdash A \rightarrow B$.

8) $A \lor (\forall x)B$ --- from 7) applying (*) again

9) $(∀x)(A \lor B) \rightarrow A \lor (\forall x)B$ --- from 8) by Deduction Theorem again.

Thus, we have proved :

$(∀x)(A \lor B) \rightarrow A \lor (\forall x)B$, provided that $x$ is not free in $A$.