Equivalence of statements with quantifiers

103 Views Asked by At

Given two formulas $\varphi $ and $\varphi '$, does the statement $\forall x (\varphi (x) \wedge \varphi ' (x)) \leftrightarrow (\forall x \varphi (x) \wedge \forall y \varphi ' (y)) $ hold?

1

There are 1 best solutions below

0
On BEST ANSWER

The answer is yes.

Informally:

  1. If you assume $\forall x(\varphi (x) \wedge \varphi ' (x))$ to be true and you take an arbitrary constant $a$, then rules of inference will give you, $\varphi (a)$ from which you can conclude that $\forall x\varphi (x)$ is true. Similarly you can get $\forall x\varphi '(x)$. Another inference rule will allow you to reach the LHS of $\leftrightarrow$.
  2. If you assume that $\forall x \varphi (x) \wedge \forall y \varphi ' (y)$ is true and you take an arbitrary constant $a$, (after eliminating the conjunction), you can get both $\varphi (a)$ and $\varphi '(a)$, from then it follows that $\varphi (a)\land \varphi '(a)$ is true and then you just need to introduce $\forall$ to get the RHS of $\leftrightarrow$.