f g (g b) The sum type is used for logical or and for union. Natural numbers The natural numbers are usually implemented in the style of Peano Arithmetic. There is a canonical term, "0 : nat" for zero. Canonical values larger than zero use the constructor function "S : nat nat". Thus, "S 0" is one. "S (S 0)" is two. "S (S (S 0)))" is three. Etc. The decimal numbers are just notationally equal to those terms. 1 : nat ::= S 0 2 : nat ::= S (S 0) 3 : nat ::= S (S (S 0)) ... The natural numbers are defined with an eliminator function "R" that uses recursion to define a function for all nats. It takes a function "P : nat U" which is the type of the function to define. It also takes a term "PZ : P 0" which is the value at zero and a function "PS : P n P (S n)" which says how to transform the value at "n" into the value at "n + 1". Thus, its computation rules are: R P PZ PS 0 PZ R P PZ PS (S ) PS (R P PZ PS ) The function "add", that was used earlier, can be defined using "R". add : natnatnat ::= R (λ n:nat . natnat) (λ n:nat . n) (λ g:natnat . (λ m:nat . S (g m))) Identity type The identity type is the third concept of equality in type theory. The first is "notational equality", which is for definitions like "2 : nat ::= (S (S 0))" that have no mathematical meaning but are useful to readers. The second is "judgemental equality", which is when two terms compute to the same term, like "x + (1 + 4)" and "x + (4 + 1)", which both compute to "x + 5". But type theory needs another form of equality, known as the "identity type" or "propositional equality". The reason it needs the identity type is because some equal terms do not compute to the same term. Assuming "x : nat", the terms "x + 1" and "1 + x" do not compute to the same term. Recall that "+" is a notation for the function "add", which is a notation for the function "R". We cannot compute on "R" until the value for "x" is specified and, until it is