3
$\begingroup$

I have these two statements, and I have to decide if they are logical equivalent.

$\forall x\in M : p(x)\land q(x)$

and

$(\forall x\in M : p(x)) \land (\forall x \in M : q(x))$

My answer is yes. But I'm not sure, because I have to do a lot of these questions and my answer to them all is "yes", which has made me a little suspicious.

  • 0
    It's correct that these are logically equivalent. Are you being asked to _prove_ formally that they are equivalent, or just to determine it by informal intuitive reasoning? In the former case, how the proof should look depends _completely_ on the details of whichever logical system you're supposed to work within. You'll need to share some knowledge of the logical axioms and inference rules you're using in order to get useful answers.2011-09-04

1 Answers 1

5

The answer is indeed yes. For this let us consider the definition of the truth value of $\forall x:\varphi(x)$. Such sentence is true if and only if for every $x\in M$ the formula $\varphi$ is true for $x$.

This may seem circular, however we look at the structure $M$ and if we can tell externally that every $x$ satisfies $\varphi$, then $M$ satisfies $\forall x:\varphi(x)$.


Now suppose that in $M$ the following is true $\forall x: (p(x)\land q(x))$.

  1. That to say that for every $x\in M$ the sentence $p(x)\land q(x)$ is true in $M$.

  2. Therefore for every $x$ (in $M$) we have that $p(x)$ holds and $q(x)$ holds (simply because $p(x)\land q(x)$ holds if and only if $p(x)$ and $q(x)$ hold).

  3. So for every $x\in M$ we have that $p(x)$, thus $\forall x:p(x)$ and for all $x\in M$ we have $q(x)$, so $\forall x:q(x)$.

  4. Hence, the conjunction of these statement is true.

Conversely, suppose in $M$ it is true that $\forall x:p(x)\land \forall x:q(x)$.

  1. For every $x\in M$ then $p(x)$ and $q(x)$ both hold, from the assumption.

  2. So for every $x\in M$ holds $p(x)\land q(x)$.

  3. Thus, in $M$ it is true that $\forall x : (p(x)\land q(x))$.