First-order logic (FOL) is powerful, but its expressive power is fundamentally constrained. It quantifies over individuals, not over properties or relations themselves. To specify complex system invariants or formalize substantial portions of mathematics, we must ascend to higher-order logic (HOL), where predicates and functions become first-class citizens. This allows quantification over sets of individuals, functions between sets, and even relations between functions. The journey begins with extending the simply typed lambda calculus.

The Simply Typed Lambda Calculus (STLC) provides a core foundation by assigning a type to every term, preventing paradoxes like self-application. In HOL, we extend this framework, often called Church's Simple Theory of Types, to include not just base types like individuals ($i$) and booleans ($o$), but also function types ($α → β$). This allows us to construct expressions that represent predicates, such as $P: i → o$, and quantify over them. For example, the principle of mathematical induction, which is an axiom schema in FOL, can be expressed as a single, higher-order proposition.

This ability to bind variables that range over functions and predicates is the hallmark of higher-order quantification. It allows for a level of abstraction that is crucial for specifying generic properties, such as stating that a relation is transitive or that a function is continuous, without having to instantiate them for every specific case.

While HOL increases expressive power, dependent types take this a step further by allowing types to depend on values. This is where systems like Coq, Lean, and Agda truly shine. The two fundamental dependent type constructors are Pi ($\\Pi$) and Sigma ($\\Sigma$) types.

A common example is defining vectors of a specific length. The type Vec A n represents a vector of elements of type A with length n. The type itself depends on the value n. A function that takes the head of a non-empty vector would have a Pi-type: head : Π n:ℕ, Vec A (n+1) → A.

Sigma-types, $\Sigma x:A. B(x)$, represent dependent pairs. An element of this type is a pair $(a, b)$ where $a$ is of type $A$ and $b$ is of type $B(a)$. This allows us to bundle a value with a proof about that value. For example, a type representing a number and a proof that it is even could be written as $\Sigma n:\mathbb{N}. \text{isEven}(n)$.

This leads to a powerful idea: propositions as types and proofs as terms. This is the Curry-Howard Isomorphism in a higher-order setting. A proposition is true if and only if its corresponding type is inhabited (i.e., we can construct a term of that type). This term is the proof. For example, a proof of $P \to Q$ is a function that transforms a proof of $P$ into a proof of $Q$.

But this power introduces a new problem. If types can contain values, and types are themselves values, we risk paradoxes like Girard's paradox—a higher-order version of Russell's paradox. To prevent this, type systems in proof assistants implement a hierarchy of universes: $Type_0, Type_1, Type_2, ...$. The rule is simple: $Type_i$ has type $Type_{i+1}$. This stratification, known as predicativity, prevents a type from containing itself, thus ensuring logical consistency.

In these systems, equality is not a single concept. We must distinguish between definitional equality and propositional equality.

Definitional equality, denoted $a \equiv b$, is computational. For example, the type checker knows that $2+2 \equiv 4$ because it can reduce the left side. Propositional equality, $a = b$, is a type that needs a proof. We can prove that $2 \times 2 = 4$, but the type checker doesn't see them as definitionally the same term. The efficiency of the type-checking algorithm relies heavily on how definitional equality is implemented, typically through normalization by evaluation or similar reduction strategies.

Finally, to represent expressions with binders (like quantifiers or lambdas) within the logic itself, we use higher-order abstract syntax (HOAS). Instead of defining custom machinery for variable binding and substitution, HOAS uses the lambda abstraction of the metalanguage (the logic itself) to represent binders in the object language. This elegantly sidesteps the complexities of variable capture and renaming, leveraging the trusted core of the type theory to handle syntax.

Now, let's test your understanding of these advanced logical systems.

Higher-order logic and dependent types provide a framework of unparalleled expressive power, allowing us to embed mathematical structures and program specifications directly into our type systems, turning proof into a form of programming.