Negating an equals sign?

Question

If, when negating a statement, and part of that statement is $3y = x$, can you just say $3y$ does not $= x$ by putting a line through the $=$ sign or is there another way to negate the statement?

The statement was "For all $x$ there exists a $y$, such that $[(y>x) \land (x=3y)]$."

Which I turned into "For all $x$ there exists a $y$ such that [$(y\leq x) \lor (x \neq 3y)]$."

But I'm fairly sure that last bit is wrong, and you have to negate it another way?

By switching them so that its for all y there exists an x? Is that the only thing or must i negate the rest of the statement? — Heelloppp, Sep 07 '15 at 05:17
No, you need to switch the quantifiers but leave the variables in the same order. See my answer below. — Jair Taylor, Sep 07 '15 at 05:24

score 2 · Answer 1 · answered Sep 07 '15 at 05:25

No, it is not sufficient to just slash out the equals sign. See the article on universal quantification here: https://en.wikipedia.org/wiki/Universal_quantification#Negation

Generally, then, the negation of a propositional function's universal quantification is an existential quantification of that propositional function's negation; symbolically:

score 2 · Answer 2 · answered Sep 07 '15 at 05:27

2

You are trying to negate $\forall x \exists y (y \gt x \wedge x=3y)$ When you negate a quantified sentence, the rule is you change the sense of the quantifier d negate the contents. So $$\lnot[\forall x \exists y (y \gt x \wedge x=3y)]\\ \Leftrightarrow \exists x \lnot\exists y (y \gt x \wedge x=3y)\\ \Leftrightarrow \exists x \forall y \lnot(y \gt x \wedge x=3y)$$

answered Sep 07 '15 at 05:27

Ross Millikan

374,822

Ah ok thanks. So i can get this far: $\forall x \exists y -(y<= x ^ ... )$ But what happens to the x = 3y? *I should of added that you need to write the equation without any negatives – Heelloppp Sep 07 '15 at 05:31
Ignore that negative -_- – Heelloppp Sep 07 '15 at 05:40
You can use DeMorgan's laws to make the last into $\exists x \forall y (y \le x \vee x\neq 3y)$ This last agrees with your result except for the quantitifers – Ross Millikan Sep 07 '15 at 13:34

score 1 · Answer 3 · answered Sep 07 '15 at 05:23

If $P(x)$ is a statement about $x$ then $\neg \forall x P(x)$ is equivalent to $\exists x \neg P(x)$, not $ \forall x \neg P(x)$. For example, if I say "it is not true that every man is tall" this is not the same as saying "it is true that every man is not tall." Instead "it is not true that every man is tall" is equivalent to saying "there is a man who is not tall."

Similarly, $\neg \exists x P(x)$ is equivalent to $\forall x \neg P(x)$. Putting these together, if $P(x,y)$ is a statement about $x$ and $y$ then $$\neg \forall x \exists y P(x,y)$$ is equivalent to $$\exists x \forall y \neg P(x,y).$$ Do you see how to finish your example?

Ah ok thanks. So i can get this far: ∀x∃y(y<=x...) But what happens to the x = 3y? *I should of added that you need to write the equation without any negatives — Heelloppp, Sep 07 '15 at 05:42

mrp · Accepted Answer · 2016-03-11T22:18:40.237

0

Other people have told you how to negate the quantifiers, so you know that $$\neg\forall x\exists y (y > x \land x = 3y) \iff \exists x \forall y \neg (y > x \land x = 3y).$$ So now how do you negate $(y > x \land x = 3y)$? By applying De Morgan's law, we get $$\neg (y > x \land x = 3y) \iff \neg (y > x) \lor \neg(x = 3 y)$$ Note that $a \neq b$ means that $(a > b) \lor (a < b)$. So we get $$\neg (y > x) \lor \neg(x = 3y) \iff (y \leq x) \lor ((x > 3y) \lor (x < 3y)),$$ so taken together we get $$\neg \forall x \exists y (y > x \land x = 3y) \iff \exists x \forall y ((y \leq x) \lor ((x > 3y) \lor (x < 3y))).$$

edited Mar 11 '16 at 22:18

answered Sep 07 '15 at 06:25

mrp

5,086

Oh wow, a≠b means that (a>b)∨(a<b). I never thought of it that way. That's actually pretty awesome. Thanks for that! Just a thought, how come its a≠b means that (a>b)v(a<b) and not a≠b means that (a>b)^(a<b). – Heelloppp Sep 07 '15 at 06:29
@Heelloppp Because a number $a$ can not both be smaller and larger than another number $b$. So intuitively, if $a$ and $b$ are not equal, then $a$ must either be strictly greater or strictly smaller than $b$. – mrp Sep 07 '15 at 07:01
Oh right i got and and or mixed up, mb. Thanks for the help. – Heelloppp Sep 07 '15 at 09:38

score 0 · Answer 5 · 2015-09-07T07:11:25.207

There is no problem in the negation of the equality, as indeed

$$\lnot(x=3y)\equiv x\ne3y.$$

The problem is with the use of the quantifiers. As a generalization of De Morgan's laws (see below), you have

$$\lnot(\forall x:P(x))\equiv \exists x:\lnot P(x),\\ \lnot(\exists x:P(x))\equiv \forall x:\lnot P(x).$$

Then $$\lnot(\forall x:\exists y:y>x\land x=3y)\equiv \\ \exists x:\lnot(\exists y:y>x\land x=3y)\equiv \\ \exists x:\forall y:\lnot(y>x\land x=3y)\equiv \\ \exists x:\forall y:y\le x\lor x\ne 3y.$$

$$\forall x:P(x)$$ can be seen as $$P(x_0)\land P(x_1)\land P(x_2)\land P(x_3)\cdots$$ Taking the negation, $$\lnot P(x_0)\lor\lnot P(x_1)\lor\lnot P(x_2)\lor\lnot P(x_3)\cdots$$ which is $$\exists x:\lnot P(x).$$ (Repeat backward with $Q(x)=\lnot P(x).$)

Negating an equals sign?

5 Answers5