Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Henning Makholm Sep 4 '11 at 15:49

1 Answer 1

up vote 5 down vote accepted

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))$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.