Predicates and Quantified Statements (Ch. 3) Notes - Key Concepts, Formulations, and Negations

3.1 Predicates and Quantified Statements

  • What is a predicate?

    • A predicate is a sentence that contains a finite number of variables and becomes a statement when specific values are substituted for the variables.

    • The domain of a predicate variable is the set of all values that may be substituted in place of the variable.

    • Predicate symbols are the placeholders for the property or relation; when you attach variables to them you get predicates (e.g., P(x): “x is a student at Bedford College”; Q(x, y): “x is a student at y”).

    • In some texts these objects are called propositional functions or open sentences.

  • Truth values of predicates with a domain D

    • If P(x) is a predicate with domain D, substituting x ∈ D yields a statement P(a) that is either true or false.

    • The truth set of a predicate P(x) is the set of all x ∈ D that make P(x) true:
      x∈D∣P(x) is true when substituted for x.{x \in D \mid P(x) \text{ is true when substituted for } x}.

    • Example: P(x) = “x^2 ≤ x” with domain D = R. The truth set is the subset of real numbers for which the inequality holds.

  • Example: predicate meanings and symbols

    • If P(x) = “x is a student at Bedford College”, Q(x) = “x is a student at” then P(x) and Q(x) are predicate symbols (often written as P(x) and Q(x)).

    • Sentences like “x is a student at Bedford College” are statements only after fixing a value for x (i.e., substituting in a variable).

  • The universal quantifier ∀ (the universal quantifier)

    • Notation: ∀x∈D Q(x)\forall x \in D\, Q(x) or ∀x[D,Q(x) (read: For all x in D, Q(x))]\forall x [ D, Q(x) \text{ (read: For all x in D, Q(x))} ]

    • Definition (truth of a universal statement): A universal statement is true iff Q(x) is true for every individual x in D; it is false if Q(x) is false for at least one x in D.

    • A counterexample is an x ∈ D for which Q(x) is false.

    • Historical note: Peirce and Frege contributed to the formal notion of quantifiers. The universal quantifier is often introduced with the slogan “for every”.

  • The existential quantifier ∃ (the existential quantifier)

    • Notation: ∃x∈D Q(x)\exists x \in D\, Q(x) or ∃x[D such that Q(x)]\exists x [ D \text{ such that } Q(x) ]

    • Definition (truth of an existential statement): An existential statement is true iff Q(x) is true for at least one x ∈ D; false if Q(x) is false for all x ∈ D.

    • A witness is a value x ∈ D for which Q(x) holds.

  • Basic examples of truth sets and quantified statements

    • Example: Let Q(n) be “n is a factor of 8.”

    • Domain a) D = {1, 2, 3, 4, 5, …} (positive integers). Truth set is {1, 2, 4, 8}.

    • Domain b) D = Z (all integers). Truth set is {±1, ±2, ±4, ±8}.

    • Universal statement example: ∀x ∈ {1,2,3,4,5}, x^2 ≥ x is true; but ∀x ∈ R, x^2 ≥ x is false (e.g., x = 0.5 gives 0.25 ≥ 0.5 which is false).

    • Existential statement example: ∃ m ∈ Z^+ such that m^2 = m is true (m = 1). If the domain is {5,6,7,8}, it is false (no witness).

  • Getting statements from predicates by quantification

    • Universal: “There exists x in D such that Q(x)” becomes a statement by binding all variables with ∀/∃; adding quantifiers turns predicates into statements.

  • Translating between formal and informal language

    • Examples of informal to formal and formal to informal translations:

    • Formal: ∀x[R,x2≥0]\forall x [ \mathbb{R}, x^2 \ge 0 ] maps to informal: “The square of every real number is nonnegative.”

    • Formal: ∃x[R,x2=2]\exists x [ \mathbb{R}, x^2 = 2 ] maps to informal: “There exists a real number whose square is 2.”

    • Trailing quantifiers: The universal quantifier can trail the rest of the sentence, e.g., “2n is even for any integer n.”

  • Implicit quantification

    • Some universal statements are implicit (they do not use words like all or every yet are universal by context). Example: “If a number is an integer, then it is a rational number” is universally quantified even without the word all.

    • Existential statements can be implicit too (e.g., “The number 24 can be written as a sum of two even integers” corresponds to ∃m, ∃n ∈ Z such that 24 = m + n).

  • The language of first-order logic and Tarski’s World (brief mentions)

    • Notation P(x) and Q(x) with a shared domain can be used to discuss relationships; P(x) ⊆ Q(x) means every element of truth set of P is in truth set of Q, i.e., ∀x (P(x) → Q(x)).

    • Tarski’s World (an educational computer program) is a visual tool to practice first-order logic and truth-value reasoning about blocks in a grid. It illustrates predicates such as Triangle(x), Blue(x), RightOf(x,y), etc., and the use of ∀ and ∃ in graphs of objects.

3.2 Predicates and Quantified Statements II

  • Negation of quantified statements

    • Theorem 3.2.1 (Negation of a Universal Statement):
      ¬(∀x ∈ D, Q(x)) ≡ ∃x ∈ D such that ¬Q(x).
      Therefore, the negation of a universal statement ("all are") is equivalent to an existential statement ("some are not").

    • Theorem 3.2.2 (Negation of an Existential Statement):
      ¬(∃x ∈ D, Q(x)) ≡ ∀x ∈ D, ¬Q(x).
      The negation of an existential statement ("some are") is equivalent to a universal statement ("none are" or "all are not").

  • Negating quantified statements: examples

    • Negation of a universal statement: ¬(∃ primes p, p is odd) becomes ∃ p prime with p not odd.

    • Negation of an existential statement: ¬(∃ triangles T with sum of angles 200°) becomes ∀ triangles T, sum of angles != 200°. (In practice we write as ∀T, sum not equal to 200°.)

  • Negating universal conditional statements

    • For a universal conditional statement ∀x ∈ D, (P(x) → Q(x)), its formal negation is:
      ¬(∀x, P(x) → Q(x)) ≡ ∃x ∈ D such that P(x) ∧ ¬Q(x).
      In words: There exists an x with P(x) true and Q(x) false.

    • Example: ¬(∀ real x, if x > 2 then x^2 > 4) ≡ ∃x with x > 2 and x^2 ≤ 4.

  • The contrapositive, converse, and inverse for universal conditionals

    • For ∀x ∈ D, (P(x) → Q(x)):

    • Contrapositive: ∀x ∈ D, (¬Q(x) → ¬P(x))

    • Converse: ∀x ∈ D, (Q(x) → P(x))

    • Inverse: ∀x ∈ D, (¬P(x) → ¬Q(x))

    • Important facts:

    • The universal conditional is logically equivalent to its contrapositive, i.e., ∀x (P(x) → Q(x)) ≡ ∀x (¬Q(x) → ¬P(x)).

    • The universal conditional is not generally equivalent to its converse or its inverse.

  • Necessary, sufficient, and only if for universal conditionals

    • Definitions extended to universal conditionals:

    • “5x, P(x) is a sufficient condition for Q(x)” means ∀x, (P(x) → Q(x)).

    • “5x, P(x) is a necessary condition for Q(x)” means ∀x, (¬P(x) → ¬Q(x)) (equivalently, ∀x, (Q(x) → P(x))).

    • “5x, P(x) only if Q(x)” means ∀x, (Q(x) → P(x)) (equivalently, ∀x, (¬P(x) → ¬Q(x))).

  • Equivalent forms of universal and existential statements

    • Universal statements equivalence (finite domain): If D = {x1, x2, …, xn}, then
      ∀x ∈ D, Q(x) ≡ Q(x1) ∧ Q(x2) ∧ … ∧ Q(xn).

    • Existential statements equivalence (finite domain): If D = {x1, x2, …, xn}, then
      ∃x ∈ D, Q(x) ≡ Q(x1) ∨ Q(x2) ∨ … ∨ Q(xn).

  • Bound variables and scope

    • A bound variable is bound by its quantifier; its scope begins at the quantifier and ends at the end of the quantified expression.

    • Variable naming is flexible; renaming bound variables does not change the meaning (provided you use the same scope).

    • Analogy to programming: local variables are bound by the function and have limited scope.

    • Examples and notes: Different sentences using the same letter x may have different bindings and scopes depending on the quantifier structure.

  • Implicit quantification

    • Some statements are implicitly universal (e.g., If a number is an integer, then it is a rational number).

    • Some statements are implicitly existential (e.g., The number 24 can be written as a sum of two even integers).

    • Mathematicians often use a double-arrow notation to indicate implicit quantification (e.g., x > 2 ⇒ x^2 > 4 equivalently expressed as ∀x > 2, x^2 > 4).

  • Using 1 and 3; The denotations P(x), Q(x) and truth sets

    • P(x) and Q(x) denote predicates with a common domain; P(x) ⊆ Q(x) means ∀x, P(x) → Q(x).

    • The text also introduces learning aids and notation via Tarski’s World to illustrate the semantics of predicates and quantifiers visually.

  • Quick takeaways

    • Universal vs existential look different but are duals: ¬(∀) ≡ ∃¬, ¬(∃) ≡ ∀¬.

    • The negation of a universal conditional is ∃x (P(x) ∧ ¬Q(x)).

    • For finite domains, you can reduce ∀ and ∃ to finite conjunctions/disjunctions over the domain.

    • Trailing quantifiers, implicit quantification, and the interpretation of necessary/sufficient/only-if extend naturally to quantified statements.

3.3 Statements with Multiple Quantifiers

  • What this section addresses (conceptual)

    • When multiple quantifiers appear, the order and scope matter. The truth of a statement can depend on whether you start with a universal or an existential quantifier and which variable they bind first.

    • Common pattern: there exists a person who supervises every detail of a production process, i.e., ∃p ∀d Supervision(p, d).

  • Example: “There is a person supervising every detail of the production process.”

    • Formal reading: ∃p ∀d Supervises(p, d).

    • Conversely, if the sentence were “Every detail is supervised by some person,” the structure would be ∀d ∃p Supervises(p, d).

  • General implications

    • The order of quantifiers changes the meaning dramatically.

    • With multiple quantifiers, you can often switch order only under specific logical conditions; otherwise, the two readings may be nonequivalent.

  • Exercises and practice themes (from the chapter)

    • Translate natural language statements with two or more quantifiers into formal notation and vice versa.

    • Determine when a statement is true in a given domain and provide counterexamples when it is false.

    • Explore the interaction of universal/existential quantifiers with conditions, implications, and negations.

  • Summary guidance for multiple quantifiers

    • Identify the order of quantifiers first (which is outermost and which is inner).

    • Decide the intended meaning from the natural language and translate step by step.

    • Check whether the domain is finite or infinite, as this affects practical evaluation (e.g., finite domains can sometimes be checked by enumeration).

Key notational reminders used in these notes

  • Predicates and domains:

    • P(x), Q(x): predicates with domain D.

    • Truth set of P(x): x∈D∣P(x) true.{x \in D \mid P(x) \text{ true} }.

  • Quantifiers:

    • Universal: ∀x∈D Q(x)\forall x \in D\, Q(x)

    • Existential: ∃x∈D Q(x)\exists x \in D\, Q(x)

  • Logical connectives and equivalences (standard):

    • ¬ for not, ∧ for and, ∨ for or, → for implication.

    • Negation rules:

    • ¬(∀x ∈ D, Q(x)) ≡ ∃x ∈ D, ¬Q(x)

    • ¬(∃x ∈ D, Q(x)) ≡ ∀x ∈ D, ¬Q(x)

    • ¬(∀x ∈ D, P(x) → Q(x)) ≡ ∃x ∈ D, P(x) ∧ ¬Q(x)

  • Important forms:

    • Universal conditional: ∀x ∈ D, (P(x) → Q(x))

    • Contrapositive: ∀x ∈ D, (¬Q(x) → ¬P(x))

    • Converse: ∀x ∈ D, (Q(x) → P(x))

    • Inverse: ∀x ∈ D, (¬P(x) → ¬Q(x))

  • Vacuous truth

    • A universal statement can be true by default if P(x) is false for every x in D (e.g., All bowls contain blue balls when there are no balls in the bowl).