At the heart of Lean lies a powerful system called Dependent Type Theory (DTT). Unlike in many programming languages where types and values live in separate worlds, DTT allows types to depend on values. This seemingly simple idea has profound consequences. It blurs the line between writing a program and proving a mathematical theorem.

Think of a function that returns the n-th element of a list. In a traditional type system, you might define its type as (List<A>, Int) -> A. This signature promises to return an element of type A, but it doesn't guarantee the index n is actually valid for the given list. Accessing an out-of-bounds index leads to a runtime error. Dependent types solve this by encoding the list's length directly into its type. A function could then have a type that requires the index n to be less than the length, making out-of-bounds access a compile-time error. The type itself depends on a value, the length of the list.

The most significant consequence of DTT is the Curry-Howard isomorphism correspondence. This principle establishes a direct link between logic and computation: a proposition is a type, and a proof of that proposition is a program of that type. If you can construct a program that has a certain type, you have effectively proven the corresponding proposition. For example, the proposition A ∧ B (A and B) can be seen as the type of pairs (a, b), where a is a proof of A and b is a proof of B.

This duality is what makes Lean both a functional programming language and an interactive theorem prover. Every piece of Lean code is a mathematical object with a precise type. This means you aren't just writing code that runs; you are constructing formal evidence that your code adheres to specific logical properties.

In standard functional programming, a function type like A -> B represents a function that takes a term of type A and returns a term of type B. The return type B is fixed; it doesn't change based on the input value. Dependent functions generalize this. Their return type can depend on the value of the input.

These are expressed using dependent function types, also known as Pi-types (Π-types). They have a specific syntax in Lean. Let's compare a standard function type with a dependent one.

The Π-type syntax (x : A) -> B x represents a function that takes a term x of type A and returns a term of a type B x, which itself depends on x. This structure is powerful enough to represent universal quantification (∀). The logical statement ∀ x : A, P(x) (for all x of type A, the property P(x) holds) is represented by the Π-type (x : A) -> P x. A proof of this statement is a function that, given any term x of type A, produces a proof of P(x).

If a type can be treated like a value, does a type have a type itself? Yes. In Lean, the type of a type is called a universe. This concept is necessary to avoid logical paradoxes, like Russell's paradox, which arises from self-referential sets. Lean establishes a hierarchy of universes: Sort u.

The main universes you will encounter are:

• Prop: The universe of propositions. The type of True, False, x = y, etc. It is Sort 0. A key feature of Prop is proof irrelevance: any two proofs of the same proposition are considered definitionally equal. This is crucial for separating logic from computation.
• Type u: The universe of computational types. Nat, String, and List Nat live in Type (which is shorthand for Type 0). Type u is an alias for Sort (u + 1). So, Type 0 is Sort 1, Type 1 is Sort 2, and so on.

This hierarchy ensures that no type contains itself, preventing paradoxes. For any u, the type Type u lives in the next universe up, Type (u + 1).

A judgment in type theory is an assertion that a term has a certain type. When you write def x : Nat := 5, you are making a judgment that the term 5 has the type Nat. Lean's kernel is responsible for checking these judgments to ensure they are valid. This brings us to a final key concept: definitional equality. Two terms are definitionally equal if they compute to the same normal form. For instance, 2 + 2 is definitionally equal to 4. This is a stronger notion than propositional equality, which is a proposition that must be proven. Definitional equality is checked automatically by Lean's type checker.

Ready to test your understanding?

By uniting programs and proofs under the umbrella of Dependent Type Theory, Lean provides a robust framework for building verified software and formalizing mathematics.