Proving Logical Equivalence Involving Null Quantification

81 Views Asked by At

$\mathbf {Theorem}.$ Suppose $x$ does not occur as a free variable in $A$ and the domain of discourse is non-empty. Then $\left(\forall xP(x)\right)$ $\lor$ $A$ $\iff$ $\forall x(P(x)\ \lor A)$.

$\it Proof.\ $$(\Rightarrow)$ Suppose $\left(\forall xP(x)\right)$ $\lor$ $A$. Then either $\forall xP(x)$ or $A$ is true.

Case 1. $\forall xP(x)$. Let $y$ be arbitrary. Since $P(x)$ is true for all $x$, it follows that $P(y)$ is true, and so $P(y) \lor A$ is true. Since $y$ was arbitrary, we can conclude that $\forall x(P(x) \lor A)$.

Case 2. $A$ is true. Let $y$ be arbitrary. Since $A$ is true, it follows that $P(y) \lor A$ is true. Since $y$ was arbitrary, we can conclude that $\forall x(P(x) \lor A)$.

Since these cases cover all the possibilities, we can conclude that $\left(\forall xP(x)\right)\lor A\Rightarrow\forall x\left(P(x)\lor A\right)$.

($\Leftarrow$) Suppose $\forall x\left(P(x) \lor A\right)$. If $\forall xP(x)$, then of course $\left(\forall xP(x)\right) \lor A$. Now suppose $\lnot\forall x P(x)$. Then we can choose some object $x_{0}$ such that $\lnot P(x_{0})$. Since $\forall x\left(P(x) \lor A\right)$ and $x_{0}$ is an object in the domain, it follows that $P(x_{0})\lor A$ is true. Since $P(x_{0})$ is false and $\lnot P(x_{0})\Rightarrow A$, we can conclude by modus ponens that $A$ is true. Therefore, $\forall x\left(P(x)\lor A\right)\Rightarrow \left(\forall xP(x)\right)\lor A.\qquad \Box$