Contents Previous Next


Introduction

module Types.introduction where

open import Lang.dataStructures using (List; []; _::_;; one; three; seven; nine)

We being with exploration of Type Theory, our “programming language” using which we “implement” math. Instead of the more familiar method of writing esoteric symbols on a piece of paper, we represent those esoteric symbols as code, which a compiler can then parse and type-check, thus guaranteeing the code’s (and hence the represented math’s) correctness. Though to programmers this might seem very natural, it is an extremely powerful method for doing math as the burden of verification becomes automated − thus significantly reducing testing time.

Most of mathematics, as we know it, is based on the foundations of Set Theory. In order to realize our goal of implementing math in Type Theory, the foundations need to be shaken up a bit, and reformulated from the ground-up.

Set Theory

Set Theory is a mathematical theory which studies collections of objects, called sets. These objects, called members or elements of the set, can literally be anything. The other main component of Set Theory is first-order logic, which is used to construct and reason around sets. The language of Set Theory can be used to define almost all of mathematical objects.

Figure 1: Set

Set Theory, having existed for centuries, has underdone several alterations, revisions (rewrites) as well as paradox removal (bug fixes, if you will). In fact, theories in mathematics follow similar lifecycles as seen in the programming world (or vice versa to be exact) leading to various flavors / versions / “forks” of the theory. The best-known amongst them is Zermelo-Fraenkel set theory (ZFC).

Basics of Set Theory

Zermelo-Frenkel Set theory (ZFC) consists of:

  1. Sets which are a collection of objects.
  2. a propositional first order logic system to create and manipulate them.
  3. relations, maps and functions amongst sets.
  4. properties of 3.

Relations

  1. Belongs

The basic relation of set theory is that of membership: , i.e. a statement such as a ∈ Set A which implies a is an element of the set A.

  1. Equality

Two sets A and B are equal if ∀ x, x ∈ A iff x ∈ B, read as: for all x, x is an element of A if and only if x is also an element of B.

  1. Subsets

A is a subset of B if every element of A is an element of B, denoted as A ⊆ B.

Operations

Given sets A and B, one can perform some basic operations with them yielding the following sets:

  1. The set A∪B, called the union of A and B, whose elements are the elements of A and the elements of B.

  2. The set A∩B, called the intersection of A and B, whose elements are the elements common to A and B.

  3. The set A−B, called the difference of A and B, whose elements are those elements of A that are not members of B.

Properties of Operations

  1. Associativity
A∪(B∪C)=(A∪B)∪C
A∩(B∩C)=(A∩B)∩C
  1. Commutativity
A∪B=B∪A
A∩B=B∩A
  1. Distributivity
A∪(B∩C)=(A∪B)∩(A∪C)
A∩(B∪C)=(A∩B)∪(A∩C)
  1. Idempotency
A∪A=A
A∩A=A
A∪∅=A
A∩∅=∅
A−A=∅

ZFC comprises of a bunch of axioms, which we are not going to peer into here. The interested reader may explore them on Zermelo–Fraenkel set theory: Wikipedia or nlab.

Type Theory

Type theory is a formal system of symbolic logic where every term has a “type”. “Term” here refers to mathematical terms such as variable x, function f, operation and so on. Bertrand Russell was the first to propose this theory in order to fix Russell’s Paradox which plagued naive set theory, though Per Martin-Löf was the one to come up with a more practically useful version of it, called “Intuitionistic Type Theory”. The Type Systems seen in programming languages are almost the same thing (though as one’s pedanticalness increases while studying math, one would beg to differ).

Figure 2: Haskell Type System

A type system in programming languages typically specifies data and appears like a tree of objects, where each successive level tries to represent data more specifically. E.g., A Float is a subtype of Number and is a more specialized case of a Number.

Figure 3: Scala Type System

In a system of type theory, each term has a type. For example, 4, 2+2 and 2 * 2 are all separate terms with the type for natural numbers. This is indicated as \(2 : ℕ\) or 2 is of type natural number.

Type theories have explicit computation and it is encoded in rules for rewriting terms. These are called “conversion rules” or, if the rule only works in one direction, a “reduction rule”. For example, 2+2 and 4 are syntactically different terms, but the former reduces to the latter. This reduction is written 2+2 ↠ 4.

Functions in type theory have a special reduction rule: the argument to the function is substituted for every instance of the parameter in the function definition. Let’s say the function double is defined as double(x) = x + x or mathematically \(double: x ↦ x + x\). Then, the function call double 2 would be reduced by substituting 2 for every x in the function definition. Thus, double 2 ↠ 2+2.

Implications of Type Theory

Foundations of Mathematics

Logic itself is subsumed in the plain idea of operations on terms of types, by observing that any type X may be thought of as the type of terms satisfying some proposition. Under this “propositions are types”-paradigm a proof of the proposition is nothing but a term of the corresponding type. This identification leads to a very fruitful identification of operations on types with logical operations. We discuss about this in Proofs as Data.

Programming Language

Since such a proof is constructive, the term witnessing it being a concrete implementation, and since type theory strictly works by rewriting rules, one may identify the construction of a term in type theory as a program whose output is a certain type. Under this “proofs as programs”-paradigm, type theory is a mathematical formalization of a programming language.

Calculus for Category Theory

On the other hand, if one regards, as is natural, any term t:X to exist in a context Γ of other terms x:Γ, then t is naturally identified with a “map” t:Γ→X, hence: with a morphism. Viewed this way the types and terms of type theory are identified, respectively, with the objects and morphisms of category theory. From this perspective, type theory provides a formal language for speaking about categories.

Coming up

We begin with the basics of types - their universes, followed by relations between types and their properties. We then study the most basic relation - equality. Next we study operations between types and their relations. We then move on to look at more complex types − the product, sum and function types.


Universes and families