CSE2500 Chapter 3: THE LOGIC OF QUANTIFIED STATEMENTS

Key Symbols and Their Meanings

3.1 Predicates and Quantified Statements I

Predicates

• A predicate is a statement containing variables

• The truth set of a predicate is the set of all values that make the predicate true

• Domain refers to the set of all possible values for the variables

Example: Finding Truth Sets

• Given Q(n): "n is a factor of 8"

  • Truth set with domain of positive integers: {1, 2, 4, 8}

  • Truth set with domain of all integers: {1, 2, 4, 8, -1, -2, -4, -8}

Universal Quantifier (∀)

• Indicates that a predicate is true for all elements in a domain

• Example: ∀x ∈ H, x is mortal (read as "For every x in H, x is mortal")

• A universal statement is true when the predicate is true for all elements

• A universal statement is false if there exists at least one counterexample

Existential Quantifier (∃)

• Indicates that a predicate is true for at least one element in a domain

• Example: ∃p ∈ P such that p is a student in CSE2500

• An existential statement is true if the predicate is true for at least one element

• An existential statement is false if the predicate is false for all elements

Universal Conditional Statements

• Form: ∀x, if P(x) then Q(x)

• Most important form of statement in mathematics

• Can be written informally in various ways:

  • "If a real number is greater than 2, then its square is greater than 4"

  • "All integers are rational numbers"

Equivalent Forms

• ∀x ∈ U, if P(x) then Q(x) ≡ ∀x ∈ D, Q(x) where D is the subset of U where P(x) is true

• ∀x ∈ D, Q(x) ≡ ∀x, if x is in D then Q(x)

3.2 Predicates and Quantified Statements II

Negating Quantified Statements

• Negation of ∀: ¬(∀x, P(x)) ≡ ∃x, ¬P(x)

  • "It is not true that all X are Y" ≡ "There exists at least one X that is not Y"

• Negation of ∃: ¬(∃x, P(x)) ≡ ∀x, ¬P(x)

  • "It is not true that there exists an X that is Y" ≡ "All X are not Y"

Negating Universal Conditional Statements

• ¬(∀x, if P(x) then Q(x)) ≡ ∃x, P(x) ∧ ¬Q(x)

  • "Not all X with property P have property Q" ≡ "There exists an X with property P that doesn't have property Q"

Relation Among ∀, ∃, ∧, and ∨

• Universal statements (∀) are related to AND (∧) statements

  • If domain is finite: ∀x ∈ {a,b,c}, Q(x) ≡ Q(a) ∧ Q(b) ∧ Q(c)

• Existential statements (∃) are related to OR (∨) statements

  • If domain is finite: ∃x ∈ {a,b,c}, Q(x) ≡ Q(a) ∨ Q(b) ∨ Q(c)

Vacuous Truth

• A universal statement is vacuously true if the domain is empty or if the condition P(x) is false for all x

• Example: "All elephants in this room are pink" is vacuously true if there are no elephants in the room

Variants of Universal Conditional Statements

• Contrapositive: ∀x, if ¬Q(x) then ¬P(x)

  • Logically equivalent to the original statement

• Converse: ∀x, if Q(x) then P(x)

  • Not logically equivalent to the original statement

• Inverse: ∀x, if ¬P(x) then ¬Q(x)

  • Not logically equivalent to the original statement

Necessary and Sufficient Conditions

• P is a sufficient condition for Q means "if P then Q"

• P is a necessary condition for Q means "if Q then P" (or "only if P, Q")

• "Only if" indicates a necessary condition

  • "A product is 0 only if one of the factors is 0" means "If a product is 0, then one of the factors is 0"

3.3 Statements with Multiple Quantifiers

Order of Quantifiers Matters

• ∀x ∃y P(x,y) ≠ ∃y ∀x P(x,y)

  • "For every x, there exists a y such that P(x,y)" means you can find a (possibly different) y for each x

  • "There exists a y such that for every x, P(x,y)" means there is one specific y that works for all x

Examples

• "∀x ∃y (x loves y)" means "Everyone loves someone" (possibly different for each person)

• "∃y ∀x (x loves y)" means "There is someone whom everyone loves" (same person)

Same Quantifiers

• Order doesn't matter when quantifiers are the same type:

  • ∀x ∀y P(x,y) ≡ ∀y ∀x P(x,y)

  • ∃x ∃y P(x,y) ≡ ∃y ∃x P(x,y)

Negating Statements with Multiple Quantifiers

• ¬(∀x ∃y P(x,y)) ≡ ∃x ∀y ¬P(x,y)

• ¬(∃x ∀y P(x,y)) ≡ ∀x ∃y ¬P(x,y)

Formal Logical Notation

• ∀x in D, P(x) can be written as ∀x (x in D → P(x))

• ∃x in D such that P(x) can be written as ∃x (x in D ∧ P(x))

3.4 Arguments with Quantified Statements

Universal Instantiation

• Form:

  • ∀x, P(x)

  • a is a particular element

  • Therefore, P(a)

• Example: "All men are mortal. Socrates is a man. Therefore, Socrates is mortal."

Universal Modus Ponens

• Form:

  • ∀x, if P(x) then Q(x)

  • P(a), for a particular a

  • Therefore, Q(a)

• Combines universal instantiation with modus ponens

Universal Modus Tollens

• Form:

  • ∀x, if P(x) then Q(x)

  • ¬Q(a), for a particular a

  • Therefore, ¬P(a)

• Combines universal instantiation with modus tollens

• Used in proof by contradiction

Testing Validity with Diagrams

• Universal statements (∀x ∈ A, P(x)) can be represented by placing set A inside the set of things with property P

• This helps visualize relationships in arguments to determine validity

Common Reasoning Errors

• Converse Error: Assuming "if P then Q" means "if Q then P"

• Inverse Error: Assuming "if P then Q" means "if not P then not Q"

• These are invalid unless the original premise is a biconditional (if and only if)

Application Tips

1. When finding truth values:

   • For universal statements (∀), check if the predicate is true for ALL elements in the domain

   • For existential statements (∃), check if the predicate is true for AT LEAST ONE element in the domain

2. When negating statements:

   • ∀ becomes ∃ (and vice versa)

   • The predicate gets negated

   • For multiple quantifiers, negate from left to right, changing each quantifier type

3. When analyzing arguments:

   • Use universal instantiation to apply universal statements to specific cases

   • Check the form of the argument (universal modus ponens or universal modus tollens)

   • Be careful of converse and inverse errors

4. When translating between formal and informal language:

   • "All X are Y" = ∀x, if x is X then x is Y

   • "No X are Y" = ∀x, if x is X then x is not Y

   • "Some X are Y" = ∃x such that x is X and x is Y

   • "Some X are not Y" = ∃x such that x is X and x is not Y

Key Definitions to Remember

• Predicate: A statement that contains variables

• Truth Set: Set of values that make a predicate true

• Domain: Set of all possible values for variables

• Universal Quantifier (∀): Indicates truth for all elements

• Existential Quantifier (∃): Indicates truth for at least one element

• Vacuous Truth: A universal statement that is true because the condition is never satisfied

• Sufficient Condition: If P is sufficient for Q, then P implies Q

• Necessary Condition: If P is necessary for Q, then Q implies P