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.

Show that there is a false statement of the form:

$$\big(\exists xG(x)\land\exists xH(x)\big)\to\exists x\big(G(x)\land H(x)\big)$$


my question is , is the $ x $ in $H(x) $ must be the same $x$ in $G(x)$ ? or it's not necessary that they are equal ??

if they can be diffrent i can show this easily , but if the must be the same element in the doman - the same individual - i think that any statement in this form must be true


this problem is in " first order mathematical logic by angelo margaris , 1990 ed "

page 30

share|improve this question
1  
Think about the "scope" of the existential quantifiers. This determines which $x$ has to be "the same" as another $x$. –  hardmath Feb 22 '13 at 20:01

2 Answers 2

up vote 5 down vote accepted

$(\exists x G(x))\land \exists x H(x) )\rightarrow (\exists x ( G(x) \land H(x) ) ) $

The left-hand side could equivalently be expressed as:

$$\exists x G(x) \land \exists y H(y)$$

This makes clear that all the left-hand side claims is the existence of some x such that G(x), and the existence of something, say y, such that $H(y)$

Whereas on the right hand side, there is only one quantified variable: $x$, in the right hand side, so the scope of the existent $x$ on the right-hand side is "over" all of $(G(x) \land H(x))$: there is some $x$ such that both $G(x)$ and $H(x)$ hold, for that given $x$.

Can you see how the left hand side does not necessarily imply the right hand side, but that the right-hand side implies the left hand side of the implication?

Added example:

Suppose the domain of x is all people.
Suppose $G(x)$ means "x is a woman"
Suppose $H(x)$ means "x is a man".

Then, we have the left hand side asserting:

There exists someone that is a woman, and there exists someone who is a man.

That is certainly true: men exist, and women exist.

But now let's see how the right-hand-side translates:

There is someone who (is both a woman and a man).

I hope this example helps make clear that we can easily construct an example in which $\exists x G(x) \land \exists x H(x)$ is true, but $\exists x (G(x) \land H(x)$ is clearly false. And because of this, the implication is false.

There exists

share|improve this answer
    
thanx alot :) , it's obivous now for me :) thanx again :) –  Maths Lover Feb 22 '13 at 21:25
    
Your welcome, MrWhy! –  amWhy Feb 22 '13 at 21:26

In the expression

$$\big(\exists xG(x)\land\exists xH(x)\big)\to\exists x\big(G(x)\land H(x)\big)\;,\tag{1}$$

the scope of the first existential quantifier is just $G(x)$, the scope of the second is just $H(x)$, and the scope of the third is $G(x)\land H(x)$. This means that the lefthand expression says that there is some $x$ such that $G(x)$ is true, and there is some $x$ such that $H(x)$ is true; there is no connection between the two things whose existence is asserted. In fact, the meaning of $(1)$ would be unchanged if we rewrote it as

$$\big(\exists xG(x)\land\exists yH(y)\big)\to\exists x\big(G(x)\land H(x)\big)\;.$$

The righthand side, however, is asserting the existence of a single $x$ that satisfies both $G(x)$ and $H(x)$.

share|improve this answer
    
M.Scott , thanx very much :)) .. –  Maths Lover Feb 22 '13 at 21:26
    
@MrWhy: You’re welcome! –  Brian M. Scott Feb 22 '13 at 21:28

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.