Category Theory Illustrated – Types

7 hours ago

Type theory is an alternative foundational language for mathematics, alongside set theory and category theory, focusing on types rather than sets.
Russell's paradox in naive set theory, involving the set of all sets that do not contain themselves, motivates the development of type theory and ZFC set theory.
In type theory, terms are bound to a single type, preventing self-containment and avoiding Russell's paradox, unlike set theory where elements can belong to multiple sets.
Types are defined by type formation rules (type-level arrows), term introduction rules (constructors), and term elimination rules (functions that use the type).
Examples of types include Booleans, Maybe (Option), natural numbers (inductive types), lists, Either, and Tuple, each with specific formation, introduction, and elimination rules.
Church encoding allows types to be represented as functions, embedding elimination rules directly into the type's definition.
Simply-typed lambda calculus (STLC) and polymorphic lambda calculus (System F) are formal type systems with typing rules for functions and polymorphism.
The Curry-Howard-Lambek correspondence links intuitionistic logic, simply-typed lambda calculus, and cartesian closed categories, showing types as propositions and programs as proofs.

Hasty Briefsbeta