Mathematics.

formal logic

First-Order Logic

Mathematical Logic30 minDifficulty3 out of 10

You should know: predicate logic, quantifiers

Overview

First-order logic (FOL), also called predicate logic or first-order predicate calculus, extends propositional logic with predicates, quantifiers (∀, ∃), and terms built from variables, constants, and functions, allowing statements about objects and their properties and relations. A first-order language is specified by a signature: a set of constant symbols, function symbols, and predicate (relation) symbols, together with logical symbols shared across all languages (connectives, quantifiers, variables, equality). Quantifiers range only over individual objects in a domain of discourse — not over sets, functions, or predicates themselves, which is what distinguishes 'first-order' from 'second-order' logic, where quantification over predicates or functions is allowed. First-order logic is the standard formal backbone of most of mathematics, including the axiomatizations of set theory (ZFC) and arithmetic (Peano arithmetic).

Intuition

Propositional logic can only combine whole, already-true-or-false statements like 'Socrates is mortal' as an atomic block; first-order logic lets you reach inside and say 'for every person x, if x is a man, then x is mortal,' quantifying over individuals in a domain. The key subtlety is quantifier order: 'every person has a mother' (∀x∃y Mother(y,x)) is utterly different from 'some single person is the mother of everyone' (∃y∀x Mother(y,x)) — swapping ∀ and ∃ changes the claim from mundane to absurd, which is exactly why careful quantifier bookkeeping is the central skill first-order logic demands.

Formal Definition

Definition

A first-order formula is built from atomic formulas (predicate applied to terms) using connectives and quantifiers:

∀x φ(x)(’for all x, φ(x) holds’)\forall x\, \varphi(x) \quad \text{('for all } x\text{, } \varphi(x)\text{ holds')}
Universal quantifier
∃x φ(x)(’there exists x such that φ(x) holds’)\exists x\, \varphi(x) \quad \text{('there exists } x\text{ such that } \varphi(x)\text{ holds')}
Existential quantifier
∀x φ(x)≡¬∃x ¬φ(x)\forall x\, \varphi(x) \equiv \neg \exists x\, \neg\varphi(x)
Quantifier duality
∀x ∃y P(x,y)≢∃y ∀x P(x,y)\forall x\, \exists y\, P(x,y) \not\equiv \exists y\, \forall x\, P(x,y)
Quantifier order matters

Worked Examples

  1. The domain is integers; the statement quantifies universally over x and asserts existence of a related y.

    ∀x ∃y S(x,y)\forall x\, \exists y\, S(x,y)

Answer: ∀x ∃y S(x,y).

Practice Problems

Difficulty 2/10

Translate 'There is no largest natural number' into first-order logic (domain ℕ, use < for 'less than').

Difficulty 3/10

Is the first-order sentence ∀x (P(x) → Q(x)) equivalent to ∀x P(x) → ∀x Q(x)? Justify with an example.

Difficulty 4/10

Show that ¬∀x φ(x) is logically equivalent to ∃x ¬φ(x).

Quiz

First-order logic differs from second-order logic in that first-order logic:
Which of the following correctly expresses quantifier duality?
Swapping the order of ∀x∃y and ∃y∀x in a formula:

Summary

  • First-order logic adds predicates, terms, and quantifiers (∀, ∃) ranging over individuals in a domain, built from a signature of constants, functions, and relations.
  • Quantifier order is not generally interchangeable: ∀x∃y P(x,y) and ∃y∀x P(x,y) can have different truth values.
  • First-order logic is the standard formal language underlying most axiomatic mathematics, including ZFC set theory and Peano arithmetic.

References

  1. WebsiteWikipedia — First-order logic