Introduction to Predicate Logic

Why Predicate Logic?

In our journey through formal mathematics, we’ve explored propositional logic—a powerful yet limited tool. Propositional logic allows us to reason about the truth of statements built from simpler ones using logical connectives. However, it falls short when we need to express statements about generalizations, properties, or specific relationships involving objects.

Predicate logic (also known as first-order logic) extends propositional logic by enabling precise expressions involving objects, their properties, and relationships between them. It’s an essential tool in mathematics, computer science, and logic because it captures a richer class of statements we frequently encounter.

Motivation and Limitations of Propositional Logic Revisited

Consider the statement:

“All prime numbers greater than 2 are odd.”

Using propositional logic alone, this statement can’t be properly captured. While propositional logic handles statements like “A number is prime,” it doesn’t support quantifying over numbers or expressing relationships like “greater than.”

This is where predicate logic comes into play, providing the necessary expressive power.

The Need for Expressing Generalizations, Properties, and Relationships

In mathematics and formal reasoning, we regularly encounter statements such as:

• “For every integer \(x\), \(x^2 \ge 0\).”
• “There exists a prime number greater than 1000.”
• “Every continuous function on a closed interval is bounded.”

Predicate logic gives us the tools—quantifiers, predicates, and terms—to rigorously state and analyze these types of claims.

What is Predicate Logic (First-Order Logic)?

Predicate logic enhances propositional logic by introducing:

• Terms: Variables, constants, and functions denoting mathematical objects.
• Predicates: Properties or relationships about objects.
• Quantifiers: Statements of generality or existence (“for all,” “there exists”).

These new elements significantly expand the expressive capability of logic, making it possible to formalize complex mathematical reasoning fully.

Historical Context and Significance

Predicate logic was formalized in the late 19th and early 20th centuries by logicians like Gottlob Frege, Bertrand Russell, and Alfred Tarski. It quickly became foundational, underpinning modern mathematics through the axiomatization of set theory.

In computer science, predicate logic provides the theoretical backbone for automated reasoning, databases, logic programming (like Prolog), and formal verification of software and hardware.

Comparison with Propositional Logic

Propositional logic deals with statements that can only be true or false without internal structure. Predicate logic, on the other hand, deals explicitly with the internal structure of statements, using quantification and detailed internal references to objects and their properties.

For example, propositional logic treats the statement “x is prime” as a simple true or false proposition. Predicate logic allows us to clarify precisely what “x” is and to reason explicitly about varying values of “x.”

Example Illustrating the Difference:

• Propositional logic:
  • “P: 2 is prime.”
  • “Q: 3 is odd.”
• Predicate logic:
  • “\(\forall x (\text{Prime}(x) \land x > 2 \rightarrow \text{Odd}(x))\)”

Here, predicate logic explicitly quantifies over numbers and specifies conditions clearly, something impossible in propositional logic.

Exercises

1. Provide examples of three mathematical statements that can be expressed clearly in predicate logic but not in propositional logic.
2. Can predicate logic express the following statement? Explain why or why not:
   • “There are infinitely many prime numbers.”
3. Rewrite the following informal statement in formal predicate logic:
   • “Every integer divisible by 4 is even.”

This foundational introduction sets the stage for exploring the syntax, semantics, and proof methods of predicate logic in greater detail.