Mathematics Foundations/2.2 Predicate Logic

2.2 Predicate Logic Introduction Predicate logic, also known as first-order logic or quantificational logic, extends propositional logic by introducing variables, quantifiers, predicates, and functions. While propositional logic can only represent statements as atomic units, predicate logic allows us to express the internal structure of statements and relationships between objects, making it significantly more powerful for mathematical reasoning. Basic Components Variables Variables represent objects from a domain of discourse (the set of all objects being considered). They are typically denoted by lowercase letters such as x, y, z. Constants Constants represent specific objects from the domain of discourse. They are typically denoted by lowercase letters such as a, b, c. Predicates A predicate is a statement about objects that can be true or false depending on the values of its variables. Predicates are typically denoted by uppercase letters such as P, Q, R. Examples: P(x): "x is prime" Q(x, y): "x is greater than y" R(x, y, z): "x lies between y and z" Functions A function maps objects to objects in the domain. Functions are typically denoted by lowercase letters such as f, g, h. Examples: f(x): "the father of x" g(x, y): "the sum of x and y" h(x): "the square root of x" Quantifiers Quantifiers allow us to express statements about collections of objects. Universal Quantifier The universal quantifier (read as "for all" or "for every") is used to express that a predicate is true for all values of a variable in the domain. Example: means "For all x, P(x) is true." Specific examples: : "For all real numbers x, x² is non-negative." : "Every prime number is either 2 or odd." Existential Quantifier The existential quantifier (read as "there exists" or "for some") is used to express that a predicate is true for at least one value of a variable in the domain. Example: means "There exists an x such that P(x) is true." Specific examples: : "There exists a real number x such that x² = 2." : "There exists a prime number that is even." Well-Formed Formulas (WFFs) A well-formed formula in predicate logic is defined recursively: 1. If P is an n-ary predicate and t₁, t₂, ..., tₙ are terms (variables, constants, or functions), then P(t₁, t₂, ..., tₙ) is a WFF. 2. If φ is a WFF, then is a WFF. 3. If φ and ψ are WFFs, then , , , and are WFFs. 4. If φ is a WFF and x is a variable, then and are WFFs. 5. Nothing else is a WFF. Translating Natural Language to Predicate Logic Domain of Discourse When translating statements into predicate logic, it's important to specify the domain of discourse—the set of objects that variables can represent. Examples of Translation Example 1: "All mathematicians are logical." Domain: People Let M(x): "x is a mathematician" Let L(x): "x is logical" Translation: Example 2: "Some students like all professors." Domain: People Let S(x): "x is a student" Let P(x): "x is a professor" Let L(x, y): "x likes y" Translation: Example 3: "Every natural number has a successor." Domain: Natural numbers Let S(x, y): "y is the successor of x" Translation: Negating Quantified Statements Negation of Universal Statements The negation of a universal statement is an existential statement: Example: The negation of "All birds can fly" is "There exists a bird that cannot fly." Negation of Existential Statements The negation of an existential statement is a universal statement: Example: The negation of "Some students passed the exam" is "No students passed the exam" or "All students did not pass the exam." Multiple Quantifiers Statements with multiple quantifiers can express complex relationships. Order of Quantifiers The order of quantifiers is significant when different types of quantifiers are used. Example: Compare these two statements: : "For every x, there exists a y such that P(x, y)." : "There exists a y such that for all x, P(x, y)." These statements generally have different meanings. Concrete Example: Let P(x, y) be "x < y" with domain as real numbers. : "For every real number, there exists a larger real number." (True) : "There exists a real number that is larger than all real numbers." (False) Bound and Free Variables Bound Variables A variable is bound if it is within the scope of a quantifier that uses that variable. Free Variables A variable is free if it is not bound by any quantifier. Example: In the formula , x is bound and y is free. Validity and Satisfiability Validity A formula is valid if it is true under all possible interpretations (assignments of meanings to predicates, functions, and constants) in all possible domains. Examples of valid formulas: Satisfiability A formula is satisfiable if there exists at least one interpretation under which the formula is true. Inference Rules in Predicate Logic Universal Instantiation (UI) From , we can infer P(c) for any constant c in the domain. Existential Generalization (EG) From P(c) for some specific constant c, we can infer . Universal Generalization (UG) If we can prove P(c) for an arbitrary constant c, then we can infer . Existential Instantiation (EI) From , we can infer P(c) for some new constant c not appearing elsewhere in the proof. Applications in Mathematics Predicate logic is fundamental to mathematical reasoning and formal mathematics: It provides the language for expressing mathematical theorems precisely It forms the basis for axiomatic systems in mathematics It allows for rigorous proofs of mathematical statements It is essential for understanding the foundations of mathematics Limitations of First-Order Logic Despite its power, first-order predicate logic has certain limitations: It cannot express statements like "for every property P, ..." (second-order logic) It cannot fully capture concepts like finiteness or countability Gödel's incompleteness theorems show that no consistent first-order system that includes basic arithmetic can be complete Exercises 1. Translate the following statements into predicate logic: a) "Every even number greater than 2 is the sum of two prime numbers." (Goldbach's conjecture) b) "Between any two distinct real numbers, there is a rational number." c) "If all humans are mortal and Socrates is human, then Socrates is mortal." 2. Negate the following statements and simplify using quantifier negation rules: a) b) c) 3. Determine which variables are free and which are bound in the following formulas: a) b) c) 4. Prove that and are logically equivalent. 5. Use inference rules to prove: "If all mathematicians are logical and some philosophers are mathematicians, then some philosophers are logical." References Enderton, H.B. (2001). "A Mathematical Introduction to Logic". Mendelson, E. (2015). "Introduction to Mathematical Logic". Rosen, K.H. (2019). "Discrete Mathematics and Its Applications". Ebbinghaus, H.D., Flum, J., & Thomas, W. (1994). "Mathematical Logic". Boolos, G.S., Burgess, J.P., & Jeffrey, R.C. (2007). "Computability and Logic".