Logical quantifiers

• We said P="x=3" is not a statement. Its truth value cannot be determined, since we don't know what x is.
• However if we write this as P(x), it's still not a statement, but it becomes a statement when we `plug in' a value for x.
• e.g. P(3) is a true statement and P(2) is a false statement.
• A sentence of the form P(x) is called an "open sentence" or a "predicate."



• When dealing with predicates P(x), there are two very useful operations, called quantifiers.
  • "for all," denoted symbolically by " (upside down "A" as in "All") "x P(x) means "For all values of x, P(x) is true."
  • "there exists," denoted symbolically by $ (backwards "E" as in "Exists") $x P(x) means "There exists at least one value of x such that P(x) is true."
• The possible values for x have to be specified somehow. (Implicitly or explicitly.)



• Examples:
  Let P(x)="x will run for President," and suppose the allowable values for x are U.S. Senators. Then:
  • "x P(x) means "Every U.S. Senator will run for President" or "U.S. Senators will run for President." (false)
  • $x P(x) means "At least one U.S. Senator will run for President" or "A U.S. Senator will run for President." (true)



• Negation formulas: ¬["x P(x)] <=> $x [¬P(x)]
  "It is not the case that P(x) is true for every x" <=> "P(x) is false for at least one x"
  
  ¬[$x P(x)] <=> "x [¬P(x)]
  "It is not the case that P(x) is true for at least one x" <=> "P(x) is false for every x"



• Caution!
  • The following sentence is ambiguous: "All Penn students are not liberal."
  • Does it mean that "There are no liberal Penn students" or that "At least one Penn student is not liberal"?
    
  • Usually we can guess from the context, but it should be avoided.
  Unambiguous versions would be "No Penn student is liberal." or "Not all Penn students are liberal."


• Multiple quantifiers:
  • Sometimes we want to deal with predicates P(x,y) depending on two variables.
  • If we use quantifiers, we generally have to be careful about the order:
  • "x $y P(x,y) is not the same as $y "x P(x,y)
  
  although
  
  • $x $y P(x,y) is the same as $y $x P(x,y)
  
  
  • "x "y P(x,y) is the same as "y "x P(x,y)
  
  
  • Examples:
    Suppose x can be any student and y can be any professor, and that P(x,y)="x is taking y's class." Then
    • "x $y P(x,y) means "For every student, there is a professor teaching a class that the student is in."
    
    
    • $x "y P(x,y) means "There is some student who is in every professor's class."
    
    
    • "y $x P(x,y) means "For every professor, there is a student taking that professor's class."
    
    
    • $y "x P(x,y) means "Some professor has every student in his/her class."
    
    None of these sentences are equivalent.
  
  
  
  • Negation of multiple quantifiers proceeds sequentially.
    e.g. ¬["x $y P(x,y)] <=> $x ¬[$y P(x,y)] <=> $x "y [¬P(x,y)]
    In English:
    • It is not true that for every student, there is a professor teaching a class that the student is in.
    • There is at least one student for whom it is not true that there is a professor teaching a class the student is in.
    • There is at least one student such that for every professor, the student is not in that professor's class.
    • There is at least one student who is not taking any professor's classes.