Chapter 2

The Category of Sets

The theory of sets was invented as a foundation for all of mathematics. The notion of sets and functions serves as a basis on which to build intuition about categories in general. This chapter gives examples of sets and functions and then discusses commutative diagrams. Ologs are then introduced, allowing us to use the language of category theory to speak about real world concepts. All this material is basic set theory, but it can also be taken as an investigation of the category of sets, which is denoted Set.

2.1   Sets and functions

People have always found it useful to put things into bins.

art

The study of sets is the study of things in bins.

2.1.1   Sets

You probably have an innate understanding of what a set is. We can think of a set X as a collection of elements xX, each of which is recognizable as being in X and such that for each pair of named elements x, x′ ∈ X we can tell if x = x′ or not.1 The set of pendulums is the collection of things we agree to call pendulums, each of which is recognizable as being a pendulum, and for any two people pointing at pendulums we can tell if they’re pointing at the same pendulum or not.

art
Figure 2.1 A set X with nine elements, and a set Y with no elements, Y = ∅.

Notation 2.1.1.1. The symbol ∅ denotes the set with no elements (see Figure 2.1), which can also be written as { }. The symbol ℕ denotes the set of natural numbers:

{0, 1, 2, 3, 4, , 877,}.   (2.1)

The symbol ℤ denotes the set of integers, which contains both the natural numbers and their negatives,

{,551,,2,1,0,1,2,}.   (2.2)

If A and B are sets, we say that A is a subset of B, and write AB, if every element of A is an element of B. So we have ℕ ⊆ ℤ. Checking the definition, one sees that for any set A, we have (perhaps uninteresting) subsets ∅ ⊆ A and AA. We can use set-builder notation to denote subsets. For example, the set of even integers can be written {n ∈ ℤ | n is even}. The set of integers greater than 2 can be written in many ways, such as

{n|n>2}or{n|n>2}or{n|n3}.

The symbol ∃ means “there exists.” So we could write the set of even integers as

{n|n is even}={n|m such that 2m=n}.

The symbol ∃! means “there exists a unique.” So the statement “∃!x ∈ ℝ such that x2 = 0” means that there is one and only one number whose square is 0. Finally, the symbol ∀ means “for all.” So the statement “∀m ∈ ℕ ∃n ∈ ℕ such that m < n” means that for every number there is a bigger one.

As you may have noticed in defining ℕ and ℤ in (2.1) and (2.2), we use the colon-equals notation “AXY Z” to mean something like “define A to be XY Z.” That is, a colon-equals declaration does not denote a fact of nature (like 2 + 2 = 4) but a choice of the writer.

We also often discuss a certain set with one element, denoted {☺}, as well as the familiar set of real numbers, ℝ, and some variants such as ℝ⩾0 ≔ {x ∈ ℝ | x ⩾ 0}.

Exercise 2.1.1.2.

Let A ≔ {1, 2, 3}. What are all the subsets of A? Hint: There are eight.

A set can have other sets as elements. For example, the set

X{{1,2},{4},{1,3,6}}

has three elements, each of which is a set.

2.1.2   Functions

If X and Y are sets, then a function f from X to Y, denoted f : XY, is a mapping that sends each element xX to an element of Y, denoted f(x) ∈ Y. We call X the domain of the function f, and we call Y the codomain of f.

art
Figure 2.2 A function from a set X to a set Y.

Note that for every element xX, there is exactly one arrow emanating from x, but for an element yY, there can be several arrows pointing to y, or there can be no arrows pointing to y (see Figure 2.2).

Slogan 2.1.2.1.

Given a function f : XY, we think of X as a set of things, and Y as a set of bins. The function tells us in which bin to put each thing.

Application 2.1.2.2. In studying the mechanics of materials, one wishes to know how a material responds to tension. For example, a rubber band responds to tension differently than a spring does. To each material we can associate a force-extension curve, recording how much force the material carries when extended to various lengths. Once we fix a methodology for performing experiments, finding a material’s force-extension curve would ideally constitute a function from the set of materials to the set of curves.

Exercise 2.1.2.3.

Here is a simplified account of how the brain receives light. The eye contains about 100 million photoreceptor (PR) cells. Each connects to a retinal ganglion (RG) cell. No PR cell connects to two different RG cells, but usually many PR cells can attach to a single RG cell.

Let PR denote the set of photoreceptor cells, and let RG denote the set of retinal ganglion cells.

a. According to the above account, does the connection pattern constitute a function RGPR, a function PRRG, or neither one?

b. Would you guess that the connection pattern that exists between other areas of the brain are function-like? Justify your answer.

Example 2.1.2.4. Suppose that X is a set and X′ ⊆ X is a subset. Then we can consider the function X′ → X given by sending every element of X′ to “itself” as an element of X. For example, if X = {a, b, c, d, e, f} and X′ = {b, d, e}, then X′ ⊆ X. We turn that into the function X′ → X given by bb, dd, ee.2

As a matter of notation, we may sometimes say the following: Let X be a set, and let i : X′ ⊆ X be a subset. Here we are making clear that X′ is a subset of X, but that i is the name of the associated function.

Exercise 2.1.2.5.

Let f : ℕ → ℕ be the function that sends every natural number to its square, e.g., f(6) = 36. First fill in the blanks, then answer a question.

a. 2 ↦ ________

b. 0 ↦ ________

c. −2 ↦ ________

d. 5 ↦ ________

e. Consider the symbol → and the symbol ↦. What is the difference between how these two symbols are used so far in this book?

Given a function f : XY, the elements of Y that have at least one arrow pointing to them are said to be in the image of f; that is, we have

im(f){yY|xX such that f(x)=y}.   (2.3)

The image of a function f is always a subset of its codomain, im(f) ⊆ Y.

Exercise 2.1.2.6.

If f : XY is depicted by Figure 2.2, write its image, im(f) as a set.

Given a function f : XY and a function g : YZ, where the codomain of f is the same set as the domain of g (namely, Y), we say that f and g are composable

XfYgZ.

The composition of f and g is denoted by gf : XZ. See Figure 2.3.

Slogan 2.1.2.7.

Given composable functions XfYgZ, we have a way of putting every thing in X into a bin in Y, and we have a way of putting each bin from Y into a larger bin in Z. The composite, gf : XZ, is the resulting way that every thing in X is put into a bin in Z.

Exercise 2.1.2.8.

art
Figure 2.3 Functions f : XY and g : YZ compose to a function gf : XZ (follow the arrows).

If AX is a subset, Example 2.1.2.4 showed how to think of it as a function i : AX. Given a function f : XY, we can compose AiXfY and get a function fi: AY. The image of this function is denoted

f(A)im(fi),

see (2.3) for the definition of image.

Let X = Y ≔ ℤ, let A ≔ {−1, 0, 1, 2, 3} ⊆ X, and let f : XY be given by f(x) = x2. What is the image set f(A)?

Solution 2.1.2.8.

By definition of image (see (2.3), we have

f(A)={y|aA such that fi(a)=y}.

Since A = {−1, 0, 1, 2, 3} and since i(a) = a for all aA, we have f(A) = {0, 1, 4, 9}. Note that an element of a set can only be in the set once; even though f(−1) = f(1) = 1, we need only mention 1 once in f(A). In other words, if a student has an answer such as {1, 0, 1, 4, 9}, this suggests a minor confusion.

Notation 2.1.2.9. Let X be a set and xX an element. There is a function {☺} → X that sends ☺ ↦ x. We say that this function represents xX. We may denote it x: {☺} → X.

Exercise 2.1.2.10.

Let X be a set, let xX be an element, and let x: {☺} → X be the function representing it. Given a function f : XY, what is fx?

Remark 2.1.2.11. Suppose given sets A, B, C and functions AfBgC. The classical order for writing their composition has been used so far, namely, gf : AC. For any element aA, we write gf(a) to mean g(f(a)). This means “do g to whatever results from doing f to a.”

However, there is another way to write this composition, called diagrammatic order. Instead of gf, we would write f; g : AC, meaning “do f, then do g.” Given an element aA, represented by a: {☺} → A, we have an element a; f; g.

Let X and Y be sets. We write HomSet(X, Y) to denote the set of functions XY.3 Note that two functions f, g : XY are equal if and only if for every element xX, we have f(x) = g(x).

Exercise 2.1.2.12.

Let A = {1, 2, 3, 4, 5} and B = {x, y}.

a. How many elements does HomSet(A, B) have?

b. How many elements does HomSet(B, A) have?

Exercise 2.1.2.13.

a. Find a set A such that for all sets X there is exactly one element in HomSet(X, A). Hint: Draw a picture of proposed A’s and X’s. How many dots should be in A?

b. Find a set B such that for all sets X there is exactly one element in HomSet(B, X).

Solution 2.1.2.13.

a. Here is one: A ≔ {☺}. (Here is another, A ≔ {48}, and another, A ≔ {a1}).

art

Why? We are trying to count the number of functions XA. Regardless of X and A, in order to give a function XA one must answer the question, Where do I send x? several times, once for each element xX. Each element of X is sent to an element in A. For example, if X = {1, 2, 3}, then one asks three questions: Where do I send 1? Where do I send 2? Where do I send 3? When A has only one element, there is only one place to send each x. A function X → {☺} would be written 1 ↦ ☺, 2 ↦ ☺, 3 ↦ ☺. There is only one such function, so HomSet(X, {☺}) has one element.

b. B = ∅ is the only possibility.

art

To give a function BX one must answer the question, Where do I send b? for each bB. Because B has no elements, no questions must be answered in order to provide such a function. There is one way to answer all the necessary questions, because doing so is immediate (“vacuously satisfied”). It is like commanding John to “assign a letter grade to every person who is over 14 feet tall.” John is finished with his job the moment the command is given, and there is only one way for him to finish the job. So HomSet(∅, X) has one element.

For any set X, we define the identity function on X, denoted

idX:XX,

to be the function such that for all xX, we have idX(x) = x.

Definition 2.1.2.14 (Isomorphism). Let X and Y be sets. A function f : XY is called an isomorphism, denoted f : XY, if there exists a function g : YX such that gf = idX and fg = idY.

art
Figure 2.4 An isomorphism XY.

art

In this case we also say that f is invertible and that g is the inverse of f. If there exists an isomorphism XY, we say that X and Y are isomorphic sets and may write XY.

Example 2.1.2.15. If X and Y are sets and f : XY is an isomorphism, then the analogue of Figure 2.2 will look like a perfect matching, more often called a one-to-one correspondence. That means that no two arrows will hit the same element of Y, and every element of Y will be in the image. For example, Figure 2.4 depicts an isomorphism XY between four element sets.

Application 2.1.2.16. There is an isomorphism between the set NucDNA of nucleotides found in DNA and the set NucRNA of nucleotides found in RNA. Indeed, both sets have four elements, so there are 24 different isomorphisms. But only one is useful in biology. Before we say which one it is, let us say there is also an isomorphism NucDNA ≅ {A, C, G, T} and an isomorphism NucRNA ≅ {A, C, G, U}, and we will use the letters as abbreviations for the nucleotides.

The convenient isomorphism NucDNANucRNA is that given by RNA transcription; it sends

AU, CG, GC, TA.

(See also Application 5.1.2.21.) There is also an isomorphism NucDNANucDNA (the matching in the double helix), given by

AT, CG, GC, TA.

Protein production can be modeled as a function from the set of 3-nucleotide sequences to the set of eukaryotic amino acids. However, it cannot be an isomorphism because there are 43 = 64 triplets of RNA nucleotides but only 21 eukaryotic amino acids.

Exercise 2.1.2.17.

Let n ∈ ℕ be a natural number, and let X be a set with exactly n elements.

a. How many isomorphisms are there from X to itself?

b. Does your formula from part (a) hold when n = 0?

Proposition 2.1.2.18. The following facts hold about isomorphism.

  1. Any set A is isomorphic to itself; i.e., there exists an isomorphism AA.
  2. For any sets A and B, if A is isomorphic to B, then B is isomorphic to A.
  3. For any sets A, B, and C, if A is isomorphic to B, and B is isomorphic to C, then A is isomorphic to C.

Proof.     1. The identity function idA: AA is invertible; its inverse is idA because idA ○ idA = idA.

2. If f : AB is invertible with inverse g : BA, then g is an isomorphism with inverse f.

3. If f : AB and f′ : BC are each invertible with inverses g : BA and g′: CB, then the following calculations show that f′ ○ f is invertible with inverse gg′:

(ff)(gg)=f(fg)g=fidBg=fg=idC(gg)(ff)=g(gf)f=gidBf=gf=idA

Exercise 2.1.2.19.

Let A and B be these sets:

art

Note that the sets A and B are isomorphic. Suppose that f : B → {1, 2, 3, 4, 5} sends “Bob” to 1, sends ♣ to 3, and sends r8 to 4. Is there a canonical function A → {1, 2, 3, 4, 5} corresponding to f?4

Solution 2.1.2.19.

No. There are a lot of choices, and none is any more reasonable than any other, i.e., none are canonical. (In fact, there are six choices; do you see why?)

The point of this exercise is to illustrate that even if one knows that two sets are isomorphic, one cannot necessarily treat them as the same. To treat them as the same, one should have in hand a specified isomorphism g : AB, such as ar8, 7 ↦ “Bob”, Q ↦ ♣. Now, given f : B → {1, 2, 3, 4, 5}, there is a canonical function A → {1, 2, 3, 4, 5} corresponding to f, namely, fg.

Exercise 2.1.2.20.

Find a set A such that for any set X, there is an isomorphism of sets

XHomSet(A,X).

Hint: A function AX points each element of A to an element of X. When would there be the same number of ways to do that as there are elements of of X?

Solution 2.1.2.20.

Let A = {☺}. Then to point each element of A to an element of X, one must simply point ☺ to an element of X. The set of ways to do that can be put in one-to-one correspondence with the set of elements of X. For example, if X = {1, 2, 3}, then ☺ ↦ 3 is a function AX representing the element 3 ∈ X. See Notation 2.1.2.9.

Notation 2.1.2.21. For any natural number n ∈ ℕ, define a set

n¯{1,2,3,,n}.   (2.4)

We call n the numeral set of size n. So, in particular, 2 = {1, 2}, 1 = {1}, and 0 = ∅.

Let A be any set. A function f : nA can be written as a length n sequence

f=(f(1),f(2),,f(n)).   (2.5)

We call this the sequence notation for f.

Exercise 2.1.2.22.

a. Let A = {a, b, c, d}. If f : 10A is given in sequence notation by (a, b, c, c, b, a, d, d, a, b), what is f(4)?

b. Let s: 7 → ℕ be given by s(i) = i2. Write s in sequence notation.

Solution 2.1.2.22.

a. c

b. (1, 4, 9, 16, 25, 36, 49)

Definition 2.1.2.23 (Cardinality of finite sets). Let A be a set and n ∈ ℕ a natural number. We say that A has cardinality n, denoted

|A|=n,

if there exists an isomorphism of sets An. If there exists some n ∈ ℕ such that A has cardinality n, then we say that A is finite. Otherwise, we say that A is infinite and write |A| ⩾ ∞.

Exercise 2.1.2.24.

a. Let A = {5, 6, 7}. What is |A|?

b. What is |{1, 1, 2, 3, 5}|?

c. What is |ℕ|?

d. What is |{n ∈ ℕ | n ⩽ 5}|?

We will see in Corollary 3.4.5.6 that for any m, n ∈ ℕ, there is an isomorphism mn if and only if m = n. So if we find that A has cardinality m and that A has cardinality n, then m = n.

Proposition 2.1.2.25. Let A and B be finite sets. If there is an isomorphism of sets f : AB, then the two sets have the same cardinality, |A| = |B|.

Proof. If f : AB is an isomorphism and Bn, then An because the composition of two isomorphisms is an isomorphism.

2.2   Commutative diagrams

At this point it is difficult to precisely define diagrams or commutative diagrams in general, but we can get a heuristic idea.5 Consider the following picture:

art

We say this is a diagram of sets if each of A, B, C is a set and each of f, g, h is a function. We say this diagram commutes if gf = h. In this case we refer to it as a commutative triangle of sets, or, more generally, as a commutative diagram of sets.

Application 2.2.1.1. In its most basic form, the central dogma of molecular biology is that DNA codes for RNA codes for protein. That is, there is a function from DNA triplets to RNA triplets and a function from RNA triplets to amino acids. But sometimes we just want to discuss the translation from DNA to amino acids, and this is the composite of the other two. The following commutative diagram is a picture of this fact

art

Consider the following picture:

art

We say this is a diagram of sets if each of A, B, C, D is a set and each of f, g, h, i is a function. We say this diagram commutes if gf = ih. In this case we refer to it as a commutative square of sets. More generally, it is a commutative diagram of sets.

Application 2.2.1.2. Given a physical system S, there may be two mathematical approaches f : SA and g : SB that can be applied to it. Either of those results in a prediction of the same sort, f′ : AP and g′ : BP. For example, in mechanics we can use either the Lagrangian approach or the Hamiltonian approach to predict future states. To say that the diagram

art

commutes would say that these approaches give the same result.

Note that diagram (2.6) is considered to be the same diagram as each of the following:

art

In all these we have h = gf, or in diagrammatic order, h = f; g.

2.3   Ologs

In this book I ground the mathematical ideas in applications whenever possible. To that end I introduce ologs, which serve as a bridge between mathematics and various conceptual landscapes. The following material is taken from Spivak and Kent [43], an introduction to ologs.

art

2.3.1   Types

A type is an abstract concept, a distinction the author has made. Each type is represented as a box containing a singular indefinite noun phrase. Each of the following four boxes is a type:

art

Each of the four boxes in (2.8) represents a type of thing, a whole class of things, and the label on that box is what one should call each example of that class. Thus ⌜a man⌝ does not represent a single man but the set of men, each example of which is called “a man.” Similarly, the bottom right box represents an abstract type of thing, which probably has more than a million examples, but the label on the box indicates the common name for each such example.

Typographical problems emerge when writing a text box in a line of text, e.g., the text box a man seems out of place, and the more in-line text boxes there are, the worse it gets. To remedy this, I denote types that occur in a line of text with corner symbols; e.g., I write ⌜a man⌝ instead of a man.

2.3.1.1   Types with compound structures

Many types have compound structures, i.e., they are composed of smaller units. Examples include

art

It is good practice to declare the variables in a compound type, as in the last two cases of (2.9). In other words, it is preferable to replace the first box in (2.9) with something like

art

so that the variables (m, w) are clear.

Rules of good practice 2.3.1.2. A type is presented as a text box. The text in that box should

  (i) begin with the word a or an;

  (ii) refer to a distinction made and recognizable by the olog’s author;

(iii) refer to a distinction for which instances can be documented;

(iv) be the common name that each instance of that distinction can be called; and

 (v) declare all variables in a compound structure.

The first, second, third, and fourth rules ensure that the class of things represented by each box appears to the author to be a well defined set, and that the class is appropriately named. The fifth rule encourages good readability of arrows (see Section 2.3.2).

I do not always follow the rules of good practice throughout this book. I think of these rules being as followed “in the background,” but I have nicknamed various boxes. So ⌜Steve⌝ may stand as a nickname for ⌜a thing classified as Steve⌝ and ⌜arginine⌝ as a nickname for ⌜a molecule of arginine⌝. However, one should always be able to rename each type according to the rules of good practice.

2.3.2   Aspects

An aspect of a thing x is a way of viewing it, a particular way in which x can be regarded or measured. For example, a woman can be regarded as a person; hence “being a person” is an aspect of a woman. A molecule has a molecular mass (say in daltons), so “having a molecular mass” is an aspect of a molecule. In other words, when it comes to ologs, the word aspect simply means function. The domain A of the function f : AB is the thing we are measuring, and the codomain is the set of possible answers or results of the measurement.

art

art

So for the arrow in (2.10), the domain is the set of women (a set with perhaps 3 billion elements); the codomain is the set of persons (a set with perhaps 6 billion elements). We can imagine drawing an arrow from each dot in the “woman” set to a unique dot in the “person” set, just as in Figure 2.2. No woman points to two different people nor to zero people—each woman is exactly one person—so the rules for a function are satisfied. Let us now concentrate briefly on the arrow in (2.11). The domain is the set of molecules, the codomain is the set ℝ>0 of positive real numbers. We can imagine drawing an arrow from each dot in the “molecule” set to a single dot in the “positive real number” set. No molecule points to two different masses, nor can a molecule have no mass: each molecule has exactly one mass. Note, however, that two different molecules can point to the same mass.

2.3.2.1   Invalid aspects

To be valid an aspect must be a functional relationship. Arrows may on their face appear to be aspects, but on closer inspection they are not functional (and hence not valid as aspects).

Consider the following two arrows:

art

art

A person may have no children or may have more than one child, so the first arrow is invalid: it is not a function. Similarly, if one drew an arrow from each mechanical pencil to each piece of lead it uses, one would not have a function.

Warning 2.3.2.2. The author of an olog has a worldview, some fragment of which is captured in the olog. When person A examines the olog of person B, person A may or may not agree with it. For example, person B may have the following olog

art

which associates to each marriage a man and a woman. Person A may take the position that some marriages involve two men or two women and thus see B’s olog as wrong. Such disputes are not “problems” with either A’s olog or B’s olog; they are discrepancies between worldviews. Hence, a reader R may see an olog in this book and notice a discrepancy between R’s worldview and my own, but this is not a problem with the olog. Rules are enforced to ensure that an olog is structurally sound, not to ensure that it “correctly reflects reality,” since worldviews can differ.

Consider the aspect an objecthasa weight. At some point in history, this would have been considered a valid function. Now we know that the same object would have a different weight on the moon than it has on earth. Thus, as worldviews change, we often need to add more information to an olog. Even the validity of an object on earthhasa weight is questionable, e.g., if I am considered to be the same object on earth before and after I eat Thanksgiving dinner. However, to build a model we need to choose a level of granularity and try to stay within it, or the whole model would evaporate into the nothingness of truth. Any level of granularity is called a stereotype; e.g., we stereotype objects on earth by saying they each have a weight. A stereotype is a lie, more politely a conceptual simplification, that is convenient for the way we want to do business.

Remark 2.3.2.3. In keeping with Warning 2.3.2.2, the arrows in (2.12*) and (2.13*) may not be wrong but simply reflect that the author has an idiosyncratic worldview or vocabulary. Maybe the author believes that every mechanical pencil uses exactly one piece of lead. If this is so, then a mechanical pencilusesa piece of lead is indeed a valid aspect. Similarly, suppose the author meant to say that each person was once a child, or that a person has an inner child. Since every person has one and only one inner child (according to the author), the map a personhas as inner childa child is a valid aspect. We cannot fault the olog for its author’s view, but note that we have changed the name of the label to make the intention more explicit.

2.3.2.4   Reading aspects and paths as English phrases

Each arrow (aspect) XfY can be read by first reading the label on its source box X, then the label on the arrow f, and finally the label on its target box Y. For example, the arrow

art

is read “a book has as first author a person.”

Remark 2.3.2.5. Note that the map in (2.14) is a valid aspect, but a similarly benign-looking map a bookhas as authora person would not be valid, because it is not functional. When creating an olog, one must be vigilant about this type of mistake because it is easy to miss, and it can corrupt the olog.

Sometimes the label on an arrow can be shortened or dropped altogether if it is obvious from context (see Section 2.3.3). Here is a common example from the way I write ologs.

art

Neither arrow is readable by the preceding protocol (e.g., “a pair (x, y), where x and y are integers x an integer” is not an English sentence), and yet it is clear what each map means. For example, given (8, 11) in A, arrow x would yield 8 and arrow y would yield 11. The label x can be thought of as a nickname for the full name “yields as the value of x,” and similarly for y. I do not generally use the full name, so as not to clutter the olog.

One can also read paths through an olog by inserting the word which (or who) after each intermediate box. For example, olog (2.16) has two paths of length 3 (counting arrows in a chain):

art

The top path is read “a child is a person, who has as parents a pair (w, m), where w is a woman and m is a man, which yields, as the value of w, a woman.” The reader should read and understand the content of the bottom path, which associates to every child a year.

2.3.2.6   Converting nonfunctional relationships to aspects

There are many relationships that are not functional, and these cannot be considered aspects. Often the word has indicates a relationship—sometimes it is functional, as in a personhasa stomach, and sometimes it is not, as in a fatherhasa child. Clearly, a father may have more than one child. This one is easily fixed by realizing that the arrow should go the other way: there is a function a childhasa father.

What about a personownsa car. Again, a person may own no cars or more than one car, but this time a car can be owned by more than one person too. A quick fix would be to replace it by a personownsa set of cars. This is okay, but the relationship between ⌜a car⌝ and ⌜a set of cars⌝ then becomes an issue to deal with later. There is another way to indicate such nonfunctional relationships. In this case it would look like this:

art

This setup will ensure that everything is properly organized. In general, relationships can involve more than two types, and in olog form looks like this:

art

For example,

art

Exercise 2.3.2.7.

On page 25, the arrow in (2.12*) was indicated as an invalid aspect:

art

Create a valid olog that captures the parent-child relationship; your olog should still have boxes ⌜a person⌝ and ⌜a child⌝ but may have an additional box.

Rules of good practice 2.3.2.8. An aspect is presented as a labeled arrow pointing from a source box to a target box. The arrow label text should

   (i) begin with a verb;

  (ii) yield an English sentence, when the source box text followed by the arrow text followed by the target box text is read;

 (iii) refer to a functional relationship: each instance of the source type should give rise to a specific instance of the target type;

(iv) constitute a useful description of that functional relationship.

2.3.3   Facts

In this section I discuss facts, by which I mean path equivalences in an olog. It is the notion of path equivalences that makes category theory so powerful.

A path in an olog is a head-to-tail sequence of arrows. That is, any path starts at some box B0, then follows an arrow emanating from B0 (moving in the appropriate direction), at which point it lands at another box B1, then follows any arrow emanating from B1, and so on, eventually landing at a box Bn and stopping there. The number of arrows is the length of the path. So a path of length 1 is just an arrow, and a path of length 0 is just a box. We call B0 the source and Bn the target of the path.

Given an olog, its author may want to declare that two paths are equivalent. For example, consider the two paths from A to C in the olog

art

We know as English speakers that a woman parent is called a mother, so these two paths AC should be equivalent. A mathematical way to say this is that the triangle in olog (2.17) commutes. That is, path equivalences are simply commutative diagrams, as in Section 2.2. In the preceding example we concisely say “a woman parent is equivalent to a mother.” We declare this by defining the diagonal map in (2.17) to be the composition of the horizontal map and the vertical map.

I generally prefer to indicate a commutative diagram by drawing a check mark, ✓, in the region bounded by the two paths, as in olog (2.17). Sometimes, however, one cannot do this unambiguously on the two-dimensional page. In such a case I indicate the commutative diagram (fact) by writing an equation. For example, to say that the diagram

art

commutes, we could either draw a check mark inside the square or write the equation

A[f,g]A[h,i]

above it.6 Either way, it means that starting from A, “doing f, then g” is equivalent to “doing h, then i.”

Here is another example:

art

Note how this diagram gives us the established terminology for the various ways in which DNA, RNA, and protein are related in this context.

Exercise 2.3.3.1.

Create an olog for human nuclear biological families that includes the concepts of person, man, woman, parent, father, mother, and child. Make sure to label all the arrows and that each arrow indicates a valid aspect in the sense of Section 2.3.2.1. Indicate with check marks (✓) the diagrams that are intended to commute. If the 2-dimensionality of the page prevents a check mark from being unambiguous, indicate the intended commutativity with an equation.

Solution 2.3.3.1.

art

Note that neither of the two triangles from child to person commute. To say that they did commute would be to say that “a child and its mother are the same person” and that “a child and its father are the same person.”

Example 2.3.3.2 (Noncommuting diagram). In my conception of the world, the following diagram does not commute:

art

The noncommutativity of diagram (2.18) does not imply that no person lives in the same city as his or her father. Rather it implies that it is not the case that every person lives in the same city as his or her father.

Exercise 2.3.3.3.

Create an olog about a scientific subject, preferably one you think about often. The olog should have at least five boxes, five arrows, and one commutative diagram.

2.3.3.4   A formula for writing facts as English

Every fact consists of two paths, say, P and Q, that are to be declared equivalent. The paths P and Q will necessarily have the same source, say, s, and target, say, t, but their lengths may be different, say, m and n respectively.7 We draw these paths as

P:a0=sf1a1f2a2f3fm1am1fmam=tQ:b0=sg1b1g2b2g3gn1bn1gnbn=t               (2.19)

Every part of an olog (i.e., every box and every arrow) has an associated English phrase, which we write as 〈〈〉〉. Using a dummy variable x, we can convert a fact into English too. The following general formula may be a bit difficult to understand (see Example 2.3.3.5). The fact PQ from (2.19) can be Englished as follows:

Given x, 〈〈s〉〉 consider the following.We know that x is 〈〈s〉〉,which 〈〈f1〉〉〈〈a1〉〉, which 〈〈f2〉〉〈〈a2〉〉, which  〈〈fm1〉〉〈〈am1〉〉, which 〈〈fm〉〉〈〈t〉〉,that we call P(x).We also know that x is 〈〈s〉〉,which 〈〈g1〉〉〈〈b1〉〉, which 〈〈g2〉〉〈〈b2〉〉, which  〈〈gn1〉〉〈〈bn1〉〉, which 〈〈gn〉〉〈〈t〉〉,that we call Q(x).Fact: Whenever x is 〈〈s〉〉, we will have P(x)=Q(x).    (2.20)

Example 2.3.3.5. Consider the olog

art

To put the fact that diagram (2.21) commutes into English, we first English the two paths: F = “a person has an address which is in a city” and G = “a person lives in a city.” The source of both is s = “a person” and the target of both is t = “a city.” Write:

Given x, a person, consider the following.

We know that x is a person,

who has an address, which is in a city,

that we call P(x).

We also know that x is a person,

who lives in a city

that we call Q(x).

Fact: Whenever x is a person, we will have P(x) = Q(x).

More concisely, one reads olog 2.21 as

A person x has an address, which is in a city, and this is the city x lives in.

Exercise 2.3.3.6.

This olog was taken from Spivak [38].

art

It says that a landline phone is physically located in the region to which its phone number is assigned. Translate this fact into English using the formula from (2.20).

Exercise 2.3.3.7.

In olog (2.22), suppose that the box ⌜an operational landline phone⌝ is replaced with the box ⌜an operational cell phone⌝. Would the diagram still commute?

2.3.3.8   Images

This section discusses a specific kind of fact, generated by any aspect. Recall that every function has an image (2.3), meaning the subset of elements in the codomain that are “hit” by the function. For example, the function f : ℤ → ℤ given by f(x) = 2 * x: ℤ → ℤ has as image the set of all even numbers.

Similarly, the set of mothers arises as the image of the “has as mother” function:

art

Exercise 2.3.3.9.

For each of the following types, write a function for which it is the image, or write “not clearly useful as an image type.”

a. ⌜a book⌝

b. ⌜a material that has been fabricated by a working process of type T

c. ⌜a bicycle owner⌝

d. ⌜a child⌝

e. ⌜a used book⌝

f. ⌜a primary residence⌝

__________________

1Note that the symbol x′, read “x-prime,” has nothing to do with calculus or derivatives. It is simply notation used to name a symbol that is somehow like x. This suggestion of kinship between x and x′ is meant only as an aid for human cognition, not as part of the mathematics.

2This kind of arrow, ↦, is read “maps to.” A function f : XY means a rule for assigning to each element xX an element f(x) ∈ Y. We say that “x maps to f(x)” and write xf(x).

3The notation HomSet(−, −) will make more sense later, when it is seen in a larger context. See especially Section 5.1.

4Canonical, as used here, means something like “best choice,” a choice that stands out as the only reasonable one.

5Commutative diagrams are precisely defined in Section 6.1.2.

6We defined function composition in Section 2.1.2, but here we are using a different notation. There we used classical order, and our path equivalence would be written gf = ih. As discussed in Remark 2.1.2.11, category theorists and others often prefer the diagrammatic order for writing compositions, which is f; g = h; i. For ologs, we roughly follow the latter because it makes for better English sentences, and for the same reason, we add the source object to the equation, writing A[f, g] ≃ A[h, i].

7If the source equals the target, s = t, then it is possible to have m = 0 or n = 0, and the ideas that follow still make sense.