Predicate Logic

Predicate logic, also known as first-order logic or the predicate calculus, is the formal system in mathematical logic that studies the internal structure of statements, the individual objects involved in them, and the relationships or properties they possess.

Unlike propositional logic, which treats each assertion as an atomic and indivisible block with a definite truth value, this system breaks down a sentence into fundamental elements. In doing so, it allows us to examine subjects, qualities, and the exact quantity of elements for which a condition holds.

This discipline arises directly to overcome the expressive limitations of propositional logic. Many intuitively valid arguments escape zero-order analysis due to its inability to connect the internal components of a proposition.

A classic example is the deductive syllogism:

1. All human beings are mortal.
2. Socrates is a human being.
3. Therefore, Socrates is mortal.

If we attempt to formalize this argument using propositional logic, we must assign a different variable to each statement: p for the first premise, q for the second, and r for the conclusion. The resulting structure, (p ∧ q) → r, is a contingency when evaluated via a truth table, incorrectly classifying the reasoning as invalid because it fails to form a tautology.

This failure occurs because propositional variables cannot capture the membership relationship between "Socrates" and the set of "human beings," nor the generalizing scope of the word "all." The true validity of the argument lies in the link between individual terms and shared predicates.

To resolve this limitation, predicate logic introduces two essential tools: terms and predicates to model specific properties of particular objects, and quantifiers (the universal quantifier ∀ and the existential quantifier ∃) to specify whether a statement holds for all or for at least one element of a given domain.

Components of Predicate Logic

To analyze the internal structure of an assertion, first-order logic decomposes formal language into basic elements. Each element serves a specific role in constructing precise statements.

These elements are primarily divided into terms, which point to the objects under study, and predicates, which express the characteristics or relations that these objects share.

Terms: Constants and Variables

A term is any formal expression that refers to an object within our framework of discussion. Terms are the formal equivalents of nouns or grammatical subjects in natural language.

There are two fundamental classes of terms:

On one hand, we have individual constants, which represent specific, fixed, and well-determined elements. They are typically denoted by lowercase letters from the beginning of the alphabet, such as a, b, or c, and correspond to proper names such as "Socrates," "the Earth," or the number 5.

On the other hand, we have individual variables, typically symbolized by the letters x, y, z. These letters do not represent a specific object, but rather a placeholder or generic element that can be replaced by any member of the domain.

Predicates and Arity

A predicate is an expression that asserts a property about one or more objects, or that describes a relationship among them. Formally, it acts as a template that turns into a proposition with a definite truth value as soon as terms are placed into its empty slots.

Predicates are denoted by uppercase letters such as P, Q, R, followed by parentheses enclosing the terms they affect. The number of objects a predicate requires to be complete is called its arity (or degree), which is simply the number of arguments it accepts.

Monadic predicates (arity 1) apply to a single object to assign it an intrinsic property. If we define P(x) as "x is an even number," the expression P(4) states "4 is an even number," which is a true statement, while P(7) is false.

Polyadic predicates (arity 2 or higher) link two or more objects through a relation. For instance, if we define the binary predicate M(x, y) as "x is greater than y," the formula M(8, 3) asserts that "8 is greater than 3," which is a true proposition.

Similarly, we can construct predicates with three or more arguments whenever needed. A common example is B(x, y, z) to denote that "x is between y and z."

Connectives and Grouping Symbols

Just as in propositional logic, we use logical connectives to build more complex statements from atomic predicates. We retain the exact same classical operators: negation (¬), conjunction (∧), disjunction (∨), conditional (→), and biconditional (↔).

For example, if we represent "x is prime" with P(x) and "x is even" with Q(x), the compound formula P(x) ∧ Q(x) asserts that object x satisfies both conditions simultaneously.

To avoid ambiguity in the order in which connectives are evaluated, we use parentheses, brackets, and braces. These grouping symbols clearly establish which parts of the statement fall under the scope of each logical operator.

The Identity Symbol

In many mathematical applications, we need to determine whether two distinct terms refer to the exact same object. For this purpose, the equality symbol (=) is included.

Equality formally functions as a special binary predicate. Writing x = y means that term x and term y name the exact same individual element within the domain of discourse.

Domain of Discourse and Quantifiers

A predicate containing free variables (also called a propositional function), such as P(x), does not constitute a proposition with a definite truth value on its own. To transform it into a true or false statement, we can substitute the variable with a specific constant or specify the number of elements that satisfy the given property.

The process of determining the extent or scope of a variable is known as quantification. The symbols used to specify how many elements satisfy a condition are called quantifiers, and they operate directly in conjunction with the chosen frame of reference.

Domain of Discourse

The domain of discourse, also called the universe of discourse or simply the domain, is the set of all possible objects over which the individual variables may range. This set must be nonempty to ensure the consistency of the logical system.

Defining the domain of discourse is essential, as a mathematical statement can be true or false depending on the domain being considered. The semantic context sets the precise boundaries of validity for every formal expression.

For example, consider the statement "for every number x, x - 1 ≥ 0 holds." If we take the set of natural numbers ℕ = {1, 2, 3, ...} as our domain, the statement is true; however, if we expand the domain to the set of integers ℤ, the statement becomes false, since setting x = 0 yields a negative result.

Universal Quantifier

The universal quantifier is represented by the symbol ∀ and is read as "for all," "for each," or "for every." It is used to state that a given property is shared by every single element in the domain of discourse.

Formally, the expression ∀x P(x) asserts that regardless of which individual element from the domain is substituted for variable x, the resulting proposition is true. If the domain consists of elements {a₁, a₂, ..., a_n}, this statement is equivalent to the conjunction P(a₁) ∧ P(a₂) ∧ ... ∧ P(a_n).

To prove that a universal proposition is true, one must demonstrate that the property holds generally for an arbitrary element of the domain. In contrast, to disprove it, one does not need to check every single element: it is sufficient to produce a single element from the domain for which the condition fails, formally known as a counterexample.

Consider the claim "the square of any real number is strictly greater than zero," formalized as ∀x (x² > 0) with the set of real numbers ℝ as the domain. Evaluating the particular case x = 0 yields 0² = 0, which is not strictly greater than zero. The existence of this counterexample immediately proves that the universal statement is false.

Existential Quantifier

The existential quantifier is denoted by the symbol ∃ and is expressed in natural language as "there exists at least one," "there is," or "for some." It indicates that within the domain of discourse there is at least one element that satisfies the corresponding predicate.

The formula ∃x P(x) is true if we can identify at least one object in the domain that makes the resulting proposition true. In a finite domain of elements {a₁, a₂, ..., a_n}, this quantification is equivalent to the inclusive disjunction P(a₁) ∨ P(a₂) ∨ ... ∨ P(a_n).

Unlike the universal quantifier, proving an existential proposition requires finding just one valid instance that satisfies the condition. Conversely, proving an existential statement false requires showing that absolutely no element in the domain satisfies the given property.

Consider a simple arithmetic example with the predicate "x² = 9" over the domain of integers ℤ. If we write ∃x (x² = 9), it suffices to note that for x = 3 we have 3² = 9; therefore, the existentially quantified statement is true.

Uniqueness Quantifier

In mathematical reasoning, it is often necessary to state not only that a solution or element exists, but that exactly one such object exists. In these cases, we use the uniqueness quantifier, symbolized as ∃!, which is read as "there exists a unique" or "there is exactly one."

This operator serves as a formal shorthand combining the standard existential quantifier with the equality relation. Stating that there exists a unique element satisfying P(x) requires two conditions simultaneously: first, that at least one object satisfies the property; second, that any other element that also satisfies it must be identical to the first.

The rigorous definition of this concept is expressed as follows:

∃!x P(x) ≡ ∃x (P(x) ∧ ∀y (P(y) → y = x))

A classic example occurs when solving linear equations over the real numbers, such as 2x + 4 = 10. Because x = 3 is the only possible solution within ℝ, we can validly state ∃!x (2x + 4 = 10).

Scope of Quantifiers and Variable Binding

When a quantifier is applied to a logical formula, its reach does not extend indefinitely over all subsequent symbols. The segment of the formula over which the quantifier exerts its effect is called the scope of the quantifier.

To define this scope with complete precision, parentheses or brackets are placed immediately after the quantifier. Any element enclosed within these delimiters falls formally under its influence.

Consider the expression ∀x (P(x) → Q(x)). Here, the parentheses indicate that the scope of ∀x covers the entire conditional, applying to both P(x) and Q(x).

By contrast, if we write (∀x P(x)) → Q(x), the situation changes entirely. In this case, the scope of the universal quantifier is strictly limited to the subformula P(x), leaving Q(x) outside its reach.

Bound and Free Variables

The position of a variable relative to the scope of a quantifier determines its behavior within the formal system. Based on this, we distinguish between two types of variables: bound and free.

A variable is said to be bound if it occurs within the scope of a quantifier that binds that same variable letter. In the formula ∃x P(x), the variable x is bound because it is explicitly governed by the existential quantifier.

Conversely, a variable is called free if it is not acted upon by any corresponding quantifier. In the expression P(x), the variable x is free, since we do not specify which elements of the domain it refers to, nor whether it applies to all or some of them.

The same variable letter can appear both free and bound within a single formula. In the expression (∀x P(x)) ∧ Q(x), the first occurrence of x is bound by the universal quantifier, while the second occurrence in Q(x) is a free variable.

This distinction is crucial because it dictates whether an expression carries a definite truth value.

Open Sentences and Closed Statements

A formula containing at least one free variable is called an open sentence or a propositional function. Open expressions are neither true nor false on their own; they act as conditions or predicates awaiting evaluation.

For example, the formula x + 2 = 5 is an open sentence. We cannot assign it a truth value until we substitute x with a specific number or bind the variable using a quantifier.

When all variables in a formula are bound, we obtain a closed formula or a sentence (statement). Only closed formulas constitute propositions in the strict sense, as they make a complete assertion that is unambiguously true or false within a given domain.

Negating Quantified Statements

Negating a quantified statement means asserting that the original condition does not hold as specified. This logical operation changes both the truth value and the quantifier present in the formula.

In everyday language, errors when contradicting generalized statements are very common. Predicate logic provides exact formal rules to perform these negations correctly.

De Morgan's Laws for Quantifiers

The equivalences governing the negation of quantifiers are known as De Morgan's laws for quantifiers. These rules directly connect the universal quantifier with the existential quantifier through predicate negation.

The first rule states that negating a universal statement is equivalent to asserting that there exists at least one element that does not satisfy the property. Symbolically, this is expressed as:

¬(∀x P(x)) ≡ ∃x ¬P(x)

The second rule states that negating an existential statement is equivalent to asserting that no element satisfies the condition—meaning that every element fails it. Its formal expression is:

¬(∃x P(x)) ≡ ∀x ¬P(x)

Practical Interpretations and Applications

To disprove the claim "all prime numbers are odd," we do not need to show that all primes are even. It is sufficient to find a single instance that violates the rule.

If we define P(x) as "x is odd" over the domain of prime numbers, the initial statement is formalized as ∀x P(x). Applying negation yields the equivalent formula ∃x ¬P(x), which states that there exists at least one prime number that is not odd. Since 2 is prime and also even, we have identified the counterexample that verifies the negation. Thus, we confirm that the original universal statement is false.

The same reasoning works in reverse. Consider the statement "there exist real numbers whose square is negative," formalized as ∃x (x² < 0) over the domain of real numbers ℝ. Its formal negation is ¬(∃x (x² < 0)), which by De Morgan's laws is equivalent to ∀x ¬(x² < 0). Simplifying the negated inequality gives the true statement ∀x (x² ≥ 0), confirming that no real number has a negative square.

Nested Quantifiers

In formal analysis, it is common to work with predicates that take more than one argument. When a statement contains two or more variables governed by quantifiers, we refer to them as nested quantifiers or multiple quantifiers.

In these structures, each quantifier acts sequentially on the scope of the quantifiers that follow it. Statements are read strictly from left to right to determine their precise truth conditions.

Basic Quantifier Combinations

When relating two variables from the same domain, we can combine quantifiers in four elementary ways.

The universal-universal combination (∀x ∀y) states that the relation holds for every ordered pair of elements. For instance, the commutative property of addition over the real numbers is formalized as ∀x ∀y (x + y = y + x).

The existential-existential combination (∃x ∃y) indicates that there is at least one pair that satisfies the property. In arithmetic, the expression ∃x ∃y (x + y = 10) is true over the integers, since choosing specific values such as x = 4 and y = 6 is sufficient.

Mixed combinations connect both types of quantification in a specified order. The formula ∀x ∃y P(x, y) asserts that for every element x, we can find at least one element y that satisfies the relation, allowing the choice of y to depend directly on x.

In contrast, the formula ∃y ∀x P(x, y) asserts the existence of a single, fixed object y that satisfies the condition simultaneously for every possible value of x.

Order and Logical Asymmetry

When consecutive quantifiers are of the same type, their order does not change the formal meaning of the statement. That is, ∀x ∀y P(x, y) ≡ ∀y ∀x P(x, y) and ∃x ∃y P(x, y) ≡ ∃y ∃x P(x, y).

However, when alternating between different quantifiers, the order is critical. The implication holds in only one direction: the statement ∃y ∀x P(x, y) → ∀x ∃y P(x, y) is logically valid, but its converse is not.

To see this asymmetry, consider the predicate L(x, y) defined as "x is less than y" over the domain of integers ℤ.

If we write ∀x ∃y (x < y), we assert that "for every integer x, there exists an integer y greater than it." This proposition is true because, given any x, we can simply choose y = x + 1.

If we reverse the order and write ∃y ∀x (x < y), the statement means "there exists a fixed integer y that is strictly greater than every integer in the universe." This assertion is false, as there is no largest integer.

Formal Modeling: Additive Identity

A fundamental example of nested quantification in algebra is the formal definition of the additive identity. Over the set of integers ℤ, the property states that there is an element that, when added to any other number, leaves that number unchanged. The formal statement is:

∃e ∀x (x + e = x)

Notice that the existential quantifier precedes the universal quantifier. This formula asserts the existence of a single, global identity element. In ℤ, this element is unique: e = 0.

Rules of Inference for Quantified Statements

To determine the validity of an argument in predicate logic, we cannot simply apply propositional rules of inference directly. Quantifiers bind the internal structure of formulas, preventing direct operations with connectives such as implication or disjunction.

The standard deductive method temporarily eliminates quantifiers using instantiation rules to obtain atomic propositions about individual elements. Once these formulas are isolated, we apply standard propositional inference rules, and, if the conclusion requires it, reintroduce quantifiers using generalization rules.

Below are the four fundamental rules of inference for quantifiers.

Universal Instantiation (UI)

Universal Instantiation states that if a property holds for all elements in the domain, it must necessarily hold for any specific object or particular constant c in that domain.

Formally, this rule allows us to derive P(c) from the premise ∀x P(x). The term c can be a known concrete object or an arbitrary element representing any member of the domain.

For example, starting from the true premise "all even numbers are divisible by 2," formalized as ∀x (P(x) → D(x)), we can apply this rule by selecting the specific constant 4. Instantiating yields the valid particular conclusion P(4) → D(4).

Universal Generalization (UG)

Universal Generalization allows us to conclude that a property holds for all elements in the domain if we have shown that it holds for an element c chosen completely arbitrarily.

Under this principle, from the proof of P(c), we can formally infer the general statement ∀x P(x). This is the standard procedure used in mathematical proofs when beginning with "let c be an arbitrary element."

The essential restriction for applying this rule is that the constant c must have no prior constraints and must not have been introduced through an existential hypothesis. If the element remains strictly generic throughout the deduction, the result can be extended to all members of the domain.

Existential Instantiation (EI)

Existential Instantiation states that if we know at least one element exists that satisfies a condition, we can assign a temporary constant symbol c to that object for use in subsequent deduction steps.

From an existential premise ∃x P(x), the rule allows us to deduce P(c). This step simply names the object whose existence is already guaranteed within the domain.

The mandatory restriction for this rule is that the constant c must be an entirely new symbol in the deduction and cannot appear in the final conclusion. We must never reuse a constant that has already appeared in prior premises or steps, as doing so would falsely assume that two distinct properties necessarily belong to the exact same individual.

Existential Generalization (EG)

Existential Generalization allows us to assert the existence of at least one element satisfying a property whenever we have established that the condition is true for a specific object or constant c.

Formally, from the concrete assertion P(c), we validly infer the quantified formula ∃x P(x). This rule reflects the basic intuition that a single true instance is sufficient to verify an existential statement.

For example, knowing that the number 5 satisfies 2(5) + 1 = 11, we can immediately generalize by stating that there exists an integer solving the equation, written as ∃x (2x + 1 = 11).

Below is a summary of these four fundamental inference rules:

Rule of Inference	Premise	Conclusion	Condition of Application
Universal Instantiation (UI)	∀x P(x)	P(c)	c is any element or constant in the domain.
Universal Generalization (UG)	P(c)	∀x P(x)	c must be an arbitrary element with no prior restrictions.
Existential Instantiation (EI)	∃x P(x)	P(c)	c must be a newly introduced constant not used previously.
Existential Generalization (EG)	P(c)	∃x P(x)	c is a known particular element in the domain.

Proof of the Classical Syllogism

With these instantiation and generalization rules, we can formally resolve the problem introduced at the beginning of the article. Let us return to the classical syllogism regarding Socrates to demonstrate its validity step by step.

The natural language argument consists of two premises and a conclusion:

1. All human beings are mortal.
2. Socrates is a human being.
3. Therefore, Socrates is mortal.

To translate this reasoning into first-order logic, we define the individual constant and predicates. We assign the constant s to represent "Socrates," the predicate H(x) for "x is a human being," and the predicate M(x) for "x is mortal."

Next, we formalize the complete logical structure of the argument:

• First premise: ∀x (H(x) → M(x))
• Second premise: H(s)
• Conclusion to prove: M(s)

Now we proceed with the formal deduction by combining the rules of inference for quantifiers with standard propositional rules:

1. State the first universal premise: ∀x (H(x) → M(x)).
2. Apply Universal Instantiation (UI) to step 1, substituting the bound variable x with the specific constant s (Socrates). This yields the conditional statement H(s) → M(s).
3. State the second premise: H(s), asserting that Socrates is indeed a human being.
4. From steps 2 and 3, having the conditional H(s) → M(s) and affirming its antecedent H(s), apply Modus Ponens (MP) to conclude M(s).

The derived conclusion matches the argument's final claim. Predicate logic thus formally demonstrates that the syllogism is valid, overcoming the expressive limitations of propositional logic.

Predicate Logic Topics