# Thread: Want to negate the following statements

1. ## Re: Want to negate the following statements

I used "Introduction to Mathematical Logic" by Mendelson, but it may not be the best choice. I am not sure about newer editions, but it used Hilbert proof calculus, which is extremely difficult to use in practice. Also, its proofs of Gödel's completeness and incompleteness theorems were detailed, but pretty dense and not very illuminating.

2. ## Re: Want to negate the following statements

Originally Posted by emakarov

The negated formula is correct. Concerning English, I think "there is someone who doesn't like everyone" means $\exists x \neg\forall y M(x,y)$. To express $\exists x \forall y \neg M(x,y)$, I would say, "there is someone who doesn't like anybody."
Makarov,

"there is someone who doesn't like everyone" doesn't mean $\exists x \neg\forall y M(x,y)$

Because $\exists x \neg\forall y M(x,y)$ is

$\exists x \exists y \neg M(x,y)$

which means "there is someone who doesn't like someone". am I right ?

3. ## Re: Want to negate the following statements

I would say that the meaning of "I don't like everyone" is similar to that of "I don't like someone," however strange this may seem. Granted, there is an a priori ambiguity concerning the place of the universal quantifier ("everyone") with respect to the negation. I found an article "Navigating negative quantificational space" that says the following (pp. 3-4). When a universally quantified noun phrase is the subject, as in "Every student didn’t solve the problem," then there is indeed an ambiguity. (I've often seen this interpreted as "Not every student solved the problem," but I personally much rather prefer the latter way of saying this.) However, the article says that when a universally quantified phrase is in object position, there is no ambiguity and the quantifier is inside the scope of negation, so "The students didn’t solve every problem" is interpreted as "It is not the case that the students solved every problem."

However, the article also claims that the "some" in the object position must be interpreted outside the scope of negation. So, "John didn’t see some students" means "There are some students that John did not see." Interestingly, "any" is left inside negation: "John didn’t see any students" means "It is not the case that John saw some students."

4. ## Re: Want to negate the following statements

Thanks for the detailed explanation. I hope such ambiguities don't arise while dealing with mathematical statements.

5. ## Re: Want to negate the following statements

Originally Posted by issacnewton
Hi

I have to negate the following statements and then express again
in English. I need to know if I am making any mistakes.

a)Everyone who is majoring in math has a friend who needs
help with his homework.

b)Everyone has a roommate who dislikes everyone.

c)There is someone in the freshman class who doesn't
have a roommate.

d)Everyone likes someone,but no one likes everyone.

a) Let P(x)= x is majoring in math
Q(x)=x needs help with homework
M(x,y)=x and y are friends

The statement would be

$\exists x (P(x))\rightarrow \exists y (M(x,y)\wedge Q(y))$

So the negated statement would be

$\neg \left[\exists x (P(x))\rightarrow \exists y (M(x,y)\wedge Q(y))\right]$

$\neg \left[\neg(\exists x (P(x)) \vee \exists y (M(x,y)\wedge Q(y))\right]$

$\neg \left[\forall x \neg P(x) \vee \exists y (M(x,y)\wedge Q(y))\right]$

$\neg (\forall x \neg P(x)) \wedge \neg \exists y (M(x,y)\wedge Q(y))$

$\exists x P(x) \wedge \forall y \neg (M(x,y)\wedge Q(y))$

$\exists x P(x) \wedge \forall y (\neg M(x,y) \vee \neg Q(y))$

To translate this statement back to English would be

Some person is majoring in math and everyone is either not a
friend of this person or doesn't need help in homework.

b) let Q(x,y)=x and y are roommates
M(x,y)=x likes y

The statement would be

$\forall x \left[\exists y (Q(x,y) \wedge \forall z(\neg M(y,z)))\right]$

so the nagated statement would be

$\neg \forall x \left[\exists y (Q(x,y)\wedge \forall z(\neg M(y,z)))\right]$

$\exists x \forall y \left[\neg Q(x,y) \vee \exists z(M(y,z)) \right]$

Translation:

Either there is some person who is not roommate with anybody or there is
someone who is liked by all.

c)let P(x)= x is in freshman class.
M(x)=x has a roommate.

The statement would be

$\exists x \left[ P(x)\wedge \neg M(x) \right]$

So the negated statement is

$\neg \exists x \left[ P(x)\wedge \neg M(x) \right]$

$\forall x \left[ \neg P(x) \vee M(x) \right]$

Translation:

Everyone either is not in freshman class or has a roommate.

d)let M(x,y)= x likes y

The statement would be

$\forall x \left[ \exists y (M(x,y))\wedge \exists z \neg M(x,z) \right]$

The negated statement would be

$\neg \forall x \left[ \exists y (M(x,y))\wedge \exists z \neg M(x,z) \right]$

$\neg \left[\forall x \exists y (M(x,y))\wedge \forall x \exists z \neg M(x,z) \right]$

$(\neg \forall x \exists y M(x,y)) \vee (\neg \forall x \exists z \neg M(x,z) )$

$\left[\exists x \forall y \neg M(x,y)\right] \vee \left[\exists x \forall z M(x,z)\right]$

Translation:

Either there is someone who likes everyone or there is someone who doesn't like
everyone.

Thanks
What laws of logic did you apply in proving that:

~ $\forall x (P(x))\rightarrow \exists y (M(x,y)\wedge Q(y))\Longleftrightarrow$ $\exists x P(x) \wedge \forall y (\neg M(x,y) \vee \neg Q(y))$

6. ## Re: Want to negate the following statements

You are right that the left-hand side should start with \neg\forall, not \neg\exists, as in the OP. The scope of the universal quantifier should be the rest of the statement. Then we have the following.

~∀x (P(x) -> ∃y (M(x,y) /\ Q(y))) <=>
∃x ~(P(x) -> ∃y (M(x,y) /\ Q(y))) <=>
∃x (P(x) /\ ~∃y (M(x,y) /\ Q(y))) <=>
∃x (P(x) /\ ∀y ~(M(x,y) /\ Q(y))) <=>
∃x (P(x) /\ ∀y (M(x,y) -> ~Q(x,y)))

7. ## Re: Want to negate the following statements

Originally Posted by emakarov
You are right that the left-hand side should start with \neg\forall, not \neg\exists, as in the OP. The scope of the universal quantifier should be the rest of the statement. Then we have the following.

~∀x (P(x) -> ∃y (M(x,y) /\ Q(y))) <=>
∃x ~(P(x) -> ∃y (M(x,y) /\ Q(y))) <=>
∃x (P(x) /\ ~∃y (M(x,y) /\ Q(y))) <=>
∃x (P(x) /\ ∀y ~(M(x,y) /\ Q(y))) <=>
∃x (P(x) /\ ∀y (M(x,y) -> ~Q(x,y)))
O.k ,but which laws of logic did you use in the above proof?

Can the four quantification rules ( UE,UI,EE,EI) PLUS the propositional calculus rules solve the above problem??

8. ## Re: Want to negate the following statements

In this problem we are using equivalences, e.g., ~∀x P(x) <=> ∃x ~P(x). I am not sure what UE and UI stand for, but if it is universal elimination and universal introduction, then those are things of completely different nature. In any case, quantifier rules are propositional rules are sufficient to derive any true formula.

The proof in post #21 used the following equivalences:

~∀x P(x) <=> ∃x ~P(x)
~∃x P(x) <=> ∀x ~P(x)
~(A /\ B) <=> A -> ~B
~~A <=> A

9. ## Re: Want to negate the following statements

Originally Posted by emakarov
In this problem we are using equivalences, e.g., ~∀x P(x) <=> ∃x ~P(x). I am not sure what UE and UI stand for, but if it is universal elimination and universal introduction, then those are things of completely different nature. In any case, quantifier rules are propositional rules are sufficient to derive any true formula.

The proof in post #21 used the following equivalences:

~∀x P(x) <=> ∃x ~P(x)
~∃x P(x) <=> ∀x ~P(x)
~(A /\ B) <=> A -> ~B
~~A <=> A
How do you prove :~∀x P(x) <=> ∃x ~P(x)

11. ## Re: Want to negate the following statements

Originally Posted by emakarov
As i said by using :

Universal Elimination,Universal Introduction,Existensial Elimination,Existential Introduction.

Plus the proposional rules

In any system whether axiomatic or not

12. ## Re: Want to negate the following statements

Originally Posted by alexandros
How do you prove :~∀x P(x) <=> ∃x ~P(x)
Copi gives the following set of QUANTIFIER NEGATION, QN
\begin{align*}\left( {\forall \nu } \right)\Phi (\nu ) &\equiv \neg \left( {\exists \nu } \right)\neg \Phi (\nu ) \\ \neg \left( {\forall \nu } \right)\Phi (\nu ) &\equiv \left( {\exists \nu } \right)\neg \Phi (\nu ) \\ \left( {\forall \nu } \right) \neg \Phi (\nu ) &\equiv \neg \left( {\exists \nu } \right) \Phi (\nu ) \\ \neg \left( {\forall \nu } \right) \neg \Phi (\nu ) &\equiv \left( {\exists \nu } \right) \Phi (\nu ) \end{align*}.

However, I think that you may be asking a more historical type question.
A question that has many centuries of thought behind it.
Here is a good reference to The Square of Opposition.

13. ## Re: Want to negate the following statements

Originally Posted by alexandros
As i said by using :

Universal Elimination,Universal Introduction,Existensial Elimination,Existential Introduction.
It sounds like you have natural deduction (ND) in mind. However, the following:

In any system whether axiomatic or not
confuses me. If you are talking about ND, then it is not "any" system; it is a specific system. Also, it is not axiomatic; it uses inference rules instead of axioms. If, on the other hand you take some system like Hilbert calculus, then it does not have introduction and elimination rules.

Could you state more precisely which calculus you are using? For example, are your rules similar to the ones from the ND link above?

14. ## Re: Want to negate the following statements

Here is a Fitch-style natural deduction derivation of ∃x ~P(x) from ~∀x P(x). The other direction is easier because it does not use double-negation elimination.

Code:
~∀x P(x)
~∃x ~P(x)
~P(x)
∃x ~P(x)
⊥
~~P(x)
P(x)
∀x P(x)
⊥
~~∃x ~P(x)
∃x ~P(x)

15. ## Re: Want to negate the following statements

Originally Posted by emakarov
Here is a Fitch-style natural deduction derivation of ∃x ~P(x) from ~∀x P(x). The other direction is easier because it does not use double-negation elimination.

Code:
~∀x P(x)
~∃x ~P(x)
~P(x)
∃x ~P(x)
⊥
~~P(x)
P(x)
∀x P(x)
⊥
~~∃x ~P(x)
∃x ~P(x)
I have my doubts w.r.t the above proof.

For example instead of x we could have used, a ,for Antony and proceed in part of the proof as follows:

$\neg Pa$ ...........................Let Pa stand for : Antony is a phony

$\exists x\neg Px$

$\neg\exists x\neg Px\wedge\exists x\neg Px$...........................contradiction

Hence : $\neg\neg Pa$ and

Pa

$\forall x Px$

Thus we proved that:

IF Antony is not phony ,then every body is phony

Is that reasonable??

Page 2 of 3 First 123 Last