Quantifer Proof

  • #1
334
44

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.

Homework Equations




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.
 

Answers and Replies

  • #2
andrewkirk
Science Advisor
Homework Helper
Insights Author
Gold Member
3,928
1,489
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?
 
  • #3
334
44
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.
I understand your second point, I made a(a bunch) of mistakes typing what I had.
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:

Related Threads on Quantifer Proof

  • Last Post
Replies
24
Views
2K
Replies
2
Views
540
  • Last Post
Replies
2
Views
593
  • Last Post
Replies
3
Views
796
  • Last Post
Replies
11
Views
874
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
5
Views
620
  • Last Post
Replies
3
Views
628
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
3
Views
2K
Top