Category Theory
Toposes and Logic
Types in Rust are logical propositions. The compiler is a proof checker. Every program that compiles is a mathematical proof. The Curry-Howard-Lambek correspondence is one of the most remarkable connections in mathematics.
- Coq and Agda: programming = proving theorems
- Rust borrow checker: checking propositions about lifetimes
- Isabelle/HOL: formal verification of safety-critical software
- Lean 4: mathematical theorems as programs in an ML-like language
Subobject Classifier: Categorical Truth
The **subobject classifier** Ω is an object representing 'truth' in a category. In Set: Ω = {true, false}. For each subobject A ⊆ B there is a characteristic function χ_A: B → Ω.
**Intuitionistic logic:** In general toposes Ω is not a Boolean algebra but a Heyting algebra. This means the law of excluded middle (P ∨ ¬P) does NOT hold! Geometric toposes (sheaves on topological spaces) are a key example.
What corresponds to the subobject classifier Ω in ordinary programming?
Topos: A Category with Geometry and Logic
A **topos** is a category that has all finite limits, exponential objects, and a subobject classifier Ω. Toposes are 'generalized sets' in which mathematics can be done.
**Hask is not a true topos:** Due to non-termination (⊥ = undefined) and seq, the category Hask violates some laws. Agda and Coq give true toposes. Nevertheless, intuition from topos theory is useful for Haskell.
Which of the following is a topos?
The Curry-Howard-Lambek Correspondence
The **Curry-Howard-Lambek correspondence** is a deep three-way connection: Logic ↔ Types ↔ Categories. Every proof = program = morphism.
**Coq and Agda:** In these languages, types are literally mathematical propositions. Writing a program of type A = proving theorem A. The entire compiler is a proof checker. This is the direct practical embodiment of the Curry-Howard correspondence.
What does the type Either A B correspond to under the Curry-Howard correspondence?
Key Takeaways
- Subobject classifier Ω: object representing truth (= Bool in Set)
- Topos: category with limits, exponentials, and Ω-generalized sets
- In topos Set logic is Boolean; in general toposes it's intuitionistic
- Curry-Howard-Lambek: Type = Proposition, Program = Proof, Category = Logic
- Either = ∨, Pair = ∧, function = ⊃ in dependent type languages
Related Topics
Toposes unify geometry, logic, and types.
- Limits and Adjunctions — Topos axioms include finite limits
- Monads — State monad = topos-based approach to state
Вопросы для размышления
- Why can't ¬¬P ⊃ P be proved in intuitionistic logic without additional axioms?
- How does the type Vec n a (vector of length n) in Agda/Idris correspond to a logical proposition?
- What does the statement 'programming is applied proof theory' mean?