# Quantifer Proof

## Homework Statement

Consider the following statement:

##\forall x, ((x \in \mathbb{Z} \wedge \neg(\exists y, (y \in \mathbb{Z} \wedge z = 7y))) \rightarrow (\exists z, (z \in \mathbb{Z} \wedge x = 2z)))##

a)Negate this statement.
b)Write the original statement in English.
c) Which statement is true? Explain.

## The Attempt at a Solution

a) I negate the statement as ##\forall x, P(x) \rightarrow G(x)##

answer: ##\exists x, ((x \in \mathbb{Z} \wedge \neg(\exists y, (y \in \mathbb{Z} \wedge z = 7y))) \wedge \forall z, (z \in \mathbb{Z} \vee x \ne 2z)##

and then simplifying the statement with y,

= ##\exists x, ((x \in \mathbb{Z} \wedge \forall y, (y \notin \mathbb{Z} \vee z \ne 7y))) \wedge \forall z, (z \notin \mathbb{Z} \vee x \ne 2z)##

b) statement in English: There exists an x, such that x is an integer and for all y, y is an integer or x =/= 2y, and for all z, z is not an integer or x =/= 2z.

c) The negation of the original statement is true.

If we suppose for all x, x is an integer and for all y, y is not an integer or x =/= 2y (the hypothesis in the original statement) then the conclusion, there exists a z such that z is an integer and x = 2z, cannot be true.

This is because "for all y, y is not an integer or x =/= 2y" <=> "there exists a z such that z is an integer and x = 2z" is a contradiction.

So the negation of this statement must be true.

My biggest confusion is what i put in bold. I think this might be an unreasonable assumption.. but I don't know how else to see which statement is true. My question is, can I make this assumption because x,y,z seem to be elements of the same universe?

Also I should have named this "quantifier question".. not sure how to edit the title.

andrewkirk
Homework Helper
Gold Member
Some observations:
• In the antecedent you have used a ##z## that is a free variable (ie unquantified). Was that supposed to be ##x##? If it is a z then neither the original statement nor its negation has a truth value, as both contain a free variable and hence are not a sentence.
• The 'simplified' version of the negated formula is a correct negation of the original formula you wrote, but the unsimplified one is not, because the first conjunct of the consequent should be ##z\notin \mathbb Z##, not ##z\in \mathbb Z##
• For (b), you have written 2y where it should be 7y, if your rendition of the original formula is correct. Also, you have put an 'or' where there should be an 'and'
• If we replace ##z## by ##x## in the antecedent of the original then your statement about (c) is correct. Otherwise both are indeterminate.
• Can you give an example of a value of #x## that falsifies the original statement (after replacing the z in the antecedent by x), thereby proving its negation?

Some observations:
• In the antecedent you have used a ##z## that is a free variable (ie unquantified). Was that supposed to be ##x##? If it is a z then neither the original statement nor its negation has a truth value, as both contain a free variable and hence are not a sentence.
• The 'simplified' version of the negated formula is a correct negation of the original formula you wrote, but the unsimplified one is not, because the first conjunct of the consequent should be ##z\notin \mathbb Z##, not ##z\in \mathbb Z##
• For (b), you have written 2y where it should be 7y, if your rendition of the original formula is correct. Also, you have put an 'or' where there should be an 'and'
• If we replace ##z## by ##x## in the antecedent of the original then your statement about (c) is correct. Otherwise both are indeterminate.
• Can you give an example of a value of #x## that falsifies the original statement (after replacing the z in the antecedent by x), thereby proving its negation?
Thanks for the response

The z in the antecedent was supposed to be an x.
To your third point, this was another typo.. here is the corrected version:

original statement to negate: ##\forall x ((x \in \mathbb{Z} \wedge \neg (\exists y, (y \in \mathbb{Z} \wedge x = 2y))) \rightarrow \exists z, (z \in \mathbb{Z} \wedge x = 2z)))##

a) so the negation is: ##\exists x, (x \in \mathbb{Z} \wedge \neg (\exists y, y \in \mathbb{Z} \wedge x = 2y)) \wedge \forall z, (z \notin \mathbb{Z} \vee x \ne 2z)##

and the simplification: ##\exists x, (x \in \mathbb{Z} \wedge (\forall y, y \notin \mathbb{Z} \vee x \ne 2y)) \wedge \forall z, (z \notin \mathbb{Z} \vee x \ne 2z)##

b) There exists an x, such that x is an integer and for all y, y is not an integer or x ##\ne## 2y, and for all z, z is not an integer or x ##\ne## 2z... I checked this a few times I don't think either of the or's should be changed to and.

So for c)... I need to find some integer x such that for all y, ##y \notin \mathbb{Z}## or ##x \ne 2y## and all z, ##z \notin \mathbb{Z}## or ##x \ne 2z##.

and since y and z are elements of the same universe, we only need to show: there exists some integer x such that for all y, ##y \notin \mathbb{Z}## or ##x \ne 2y##

If i make x an odd integer, then either ##x \ne 2y## or ##y \notin \mathbb{Z}##.

but if ##x \ne 2y## then ##y \in \mathbb{Z}## and if ##y \notin \mathbb{Z}## then ##x = 2y##
... so x being an odd integer seems like a dead end..

if I make x an even integer then ##x =2y## and ##y \in \mathbb{Z}## is true..
##x \ne 2y## and ##y \in \mathbb{Z}## is not true..
so x being an even integer seems like a dead end..

I think x being even or odd will give me the counterexample since one of the conditions is x being divisible by 2...

EDIT: if we let x be an even integer then x = 2k for some integer k.
So ##x \ne 2y## and ##y \notin \mathbb{Z}## is a true statement.
We know ##P \wedge Q \rightarrow P \vee Q## so we conclude that ##x \ne 2y## or ##y \notin \mathbb{Z}## is true.

so if x is an even integer, then ##x \ne 2y## and ##y \notin \mathbb{Z}##. So we've shown the antecedent is true and that the conclusion is false. And so we conclude the negation of the statement must be true.

Last edited: