Negation in Logic

Date: 8/3/96 at 21:0:5
From: Thomas Williams
Subject: A Person who Knows Everybody...

What is the negation of the sentence "In every village, there is a 
person who knows everybody else in that village."?

My guess is "In at least one village, there is at least one person who 
knows at least one person in that village."

Am I close at all?

Date: 8/4/96 at 16:42:15
From: Doctor Mike
Subject: Re: A Person who Knows Everybody...

Hello Thomas, 
  
Close, but not quite there.  Think of it this way.  If you use 
"special person" to mean a person who knows everyone in his/her 
village, then the original sentence becomes: 

  "Every village has a special person." 

The negation would then be : 
  "Some village does NOT have a special person."
  
So what does it mean for a village not to have a special person?  It 
means that every person in that village could be matched up with some
person that he/she does not already know.  The negation should be: 

  "In at least one village, each person does not know everyone else."

or perhaps something like: 

  "In at least one village, and for every person in that village, that 
   person does not know everybody." 

or alternatively: 

  "There exists a village, such that for every person in that village,
   there is another person that the first person does not know."
   
In general, for language exercises like this, there are two basic 
rules. The negation of a sentence like "For every...there exists 
a...such that X is true." is a sentence like "There exists a...such 
that for all...X is false.".  (The other basic rule is the reverse of 
this.)  

It is also often easier to see what is happening if some symbols are 
used.  See if you follow the symbolic version below for the sentence 
and the negation. 
 
  "For all V, there is a P in V, such that for all Q in V, P knows Q."
  
  "There is a V, such that for every P in V, there is a Q in V such
   that P does not know Q." 
  
I hope this helps.  Write back if you have more questions. 

-Doctor Mike,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/