Notas Documentation

5. Products and Coproducts

5. Products and Coproducts

Notes

An initial object in a category is an object that has 1 and only 1 morphism going to any object in the category. Object a is more initial than b if \(a \rightarrow b\).

In the category of sets, this is the Void Haskell type with absurd :: Void -> a as the universally polymorphic morphism.

A terminal object a category is an object that has 1 and only 1 morphism going to it from any object in the category. Object a is more terminal than b if \(a \leftarrow b\).

In the category of sets, this is a singleton set: () in Haskell, with unit :: a -> () as the morphism.

For any category \(C\), we can define the opposite category \(C^{op}\) by reversing the morphisms. If \(f :: a \rightarrow b\), \(g :: b \rightarrow c\) with their composition \(g \circ f = h :: a \rightarrow c\), then we can define \(f^{op} :: a \leftarrow b\), \(g^{op} :: b \leftarrow c\) and \(h^{op} :: a \leftarrow c\). The terminal object in \(C\) is the initial \(C^{op}\), and vice versa.

An isomorphism is a pair of morphisms such that \(f \circ g = id\) and \(g \circ f = id\).

Initial objects are unique up to unique isomorphisms. Take 2 initial objects, \(i_1\) and \(i_2\), with morphisms \(f :: i_1 \rightarrow i_2\) and \(g :: i_2 \rightarrow i_1\). \(g \circ f\) is a morphism from \(i_1 \rightarrow i_1\). Since \(i_1\) is initial, there can be only 1 morphism from it, so \(g \circ f = id_{i_1}\). Similarly, \(f \circ g = id_{i_2}\). \(f\) and \(g\) must be the inverse of each other. Therefore, any 2 initial objects are isomorphic.

Products

A product of two objects \(a\) and \(b\) is the object \(c\) equipped with two projections (\(p :: c \rightarrow a\) and \(q :: c \rightarrow b\)) such that for any other object \(c'\) equipped with two projections there is a unique morphism \(m :: c' \rightarrow c\) that factorizes those projections.

For example, consider the product between the types Int and Bool. There could be two candidates for the product of those two types, Int and (Int, Bool):

2 candidates for the product of Int and Bool: Int and (Int, Bool)

In this case, \(p'\) and \(q'\) could be constructed in terms of \(m\):

m :: Int -> (Int, Bool)
m x = (x, True)

p :: (Int, Bool) -> Int
p (x, _) = x

q :: (Int, Bool) -> Bool
q (_, x) = x

p' :: Int -> Int
p' x = p (m x)     -- this would equal x

q' :: Int -> Bool
q' x = q (m x)     -- this would equal True

Coproducts

A coproduct of two object \(a\) and \(b\) is the object \(c\) equipped with two injections (\(i :: a \rightarrow c\) and \(j :: b \rightarrow c\)) such that for any other object \(c'\) equipped with two injections there is a unique morphism \(m :: c \rightarrow c'\) that factorizes those injections:

A coproduct of a and b

In the category of sets, the coproduct is the disjoint union of two sets. In programming, a coproduct can be a tagged union of 2 types - cannonically Either in Haskell:

data Either a b = Left a | Right b

Asymmetries

The terminal object can be obtained from reversing the morphism directions of an initial object. A coproduct can be obtained from reversing the morphisms of a product. However, asymmetries exist in the category of sets. Take a function from a singleton set:

f100 :: () -> Integer
f100 () = 100

Functions are total, in that they are defined for every element of the domain set. However, functions don’t have to cover the whole codomain. f100 is a total function in that is covers every value of (), but only covers one value of the codomain: 100 in the set of integers. Functions that have a smaller domain than the codomain embed the domain in the codomain. Functions that tightly fill their codomains, on the other hand, are surjective or onto.

Functions can also map many elements of the domain onto one element of the codomain:

intToTrue:: Integer -> Bool
intToTrue _ = True

In this sense, they collapse the domain into the codomain. Functions that do not do this are injective or one-to-one.

Some functions are both surjective and injective. They are bijections, and are properly invertable. An ismorphism in the category of sets is a bijection.

Challenges

5.1

Show that the terminal object is unique up to unique isomorphism.

We can basically just reverse the proof for the initial object.

Take 2 terminal objects, \(t_1\) and \(t_2\), with morphisms \(f :: t_2 \rightarrow t_1\) and \(g :: t_1 \rightarrow t_2\). \(g \circ f\) is a morphism from \(t_2 \rightarrow t_2\). Since \(t_2\) is terminal, there can be only 1 morphism to it from any object, and objects in a category have the identity morphism already, so \(g \circ f = id_{t_2}\). Similarly, \(f \circ g = id_{t_1}\). \(f\) and \(g\) must be the inverse of each other. Therefore, any 2 terminal objects are isomorphic. The terminal object is unique up to unique isomorphism.

5.2

What is a product of two objects in a poset?

To recap: a poset, or partially ordered set, is a category where a morphism is a relation between objects: for example, the relation of being less than or equal. It has:

  • Identity morphisms: an object is less than or equal to itself.

  • Composition: \(a \leq b \land b \leq c \rightarrow a \leq c\).

  • Partial order: additional condition that \(a \leq b \land b \leq a \rightarrow a = b\).

However, a partial order is not a total/linear order, in which every object has a morphism to every other.

If we have 2 objects, \(a\) and \(b\), we seek a \(c\) that is the product of those objects, with morphisms \(p :: c \rightarrow a\) and \(q :: c \rightarrow b\).

Given that the morphisms in this posset are the relation of being less than or equal, the morphisms from \(c\) are \(p :: c <= a\) and \(q :: c <= b\).

The product \(c\) must be a number that is less than or equal to a or b. It must also be the biggest number less than or equal to a and b, as if were not, then the morphism \(m :: c' <= c\) would factorize \(p'\) and \(q'\):

m :: c' <= c

p :: c <= a
q :: c <= b

p' :: c' <= a
q' :: c' <= b

p' :: m.p -> c' <= c && c <= a == c' <= a
q' :: m.p -> c' <= c && c <= b == c' <= b

So, for example, if \(a = 5\) and \(b = 6\), then \(c \leq 5 \land c \leq 6\). In this case, \(c = 5\), as \(5 \leq 5 \land 5 \leq 6\). If \(c' = 4\), then \(m :: c' <= c\).

5.3

What is a coproduct of two objects in a poset?

A coproduct \(c\) of \(a\) and \(b\) in the poset defined in 5.2 would have the morphisms \(i :: a \leq c\) and \(j :: b \leq c\). It should also be the object where \(m :: c \leq c'\). In the example poset, it would be the smallest number less than or equal to both a and b.

If \(a = 5\) and \(b = 6\), then the coproduct \(a \leq c \land b \leq c\). This would be \(c = 6\). If \(c' = 7\), then \(m :: c <= c'\).

5.4

Implement the equivalent of Haskell Either as a generic type in your favorite language (other than Haskell).

from typing import Generic, TypeVar

T = TypeVar("T")
U = TypeVar("U")


class Either(Generic[T, U]):
    pass


class Left(Either[T, U]):
    def __init__(self, value: T) -> None:
        self.value = value


class Right(Either[T, U]):
    def __init__(self, value: U) -> None:
        self.value = value


left = Left[str, int]("hello")
right = Right[str, int](10)

assert type(left.value) == str
assert type(right.value) == int

assert left.value == "hello"
assert right.value == 10

5.5

Show that Either is a “better” coproduct than int equipped with two injections:

int i(int n) { return n; }
int j(bool b) { return b? 0: 1; }

Hint: Define a function int m(Either const & e); that factorizes i and j.

In this instance, m :: Either int bool -> int

int m(Either const & e) {
   return (e.tag == Either::isLeft) ? e.left : e.right ? 0 : 1;
}
Free document hosting provided by Read the Docs.