The n-Category Café

The story for specifying subsets goes like this. Given a property $P(x)$ of elements $x$ of a set $X$, we can ask whether there’s a subset $A$ of $X$ such that

$$x \in A \iff P(x)$$

($x \in X$). If there is, we say that $P(x)$ specifies a subset of $X$ and write $A$ as $\{x \in X : P(x)\}$.

Our task is to show that lots of properties specify subsets, so that we can use the usual set-builder notation with abandon. And we carry out this task in two steps:

• We establish some basic properties that specify subsets. These are the building blocks. For example, if we’ve got an element $x$ of a set $X$, then we get the singleton subset $\{x\}$. And if we’ve got two functions $f, g: X \to Y$, we get their equalizer $\{x \in X: f(x) = g(x)\}$.

• Then we establish various ways of combining properties. These are the familiar logical operators: propositional ones like “and” and “not”, quantifiers, and so on. For example, if $P(x, y)$ is a property of elements $x \in X$ and $y \in Y$ that specifies a subset of $X \times Y$, and $Q()$ is a property of elements $y \in Y$ that specifies a subset of $Y$, then we can define a subset of $Y$ by $$\{ y \in Y : ((\exists x \in X)P(x, y)) \ \text{ and not } \ Q(y) \}.$$

By combining the basic properties, we end up being able to specify subsets in just about any way we might ever want to.

That’s how we specify subsets by “just writing them down”. But this week, I also explained how to do the same for “functions”.

The key here is the notion of graph. I showed my class the theorem that for sets $X$ and $Y$, the functions $X \to Y$ correspond to the relations between $X$ and $Y$ that are functional, in the sense that each element of $X$ is related to exactly one element of $Y$. The graph of a function is a functional relation, and conversely, every functional relation is the graph of exactly one function.

This correspondence between functions $X \to Y$ and functional relations between $X$ and $Y$ — which are subsets of $X \times Y$ — is extremely useful. It lets us use all our technology for specifying subsets to specify graphs. For instance, even proving that every injective function between nonempty sets has a retraction is most easily done if you can “just write it down”.

That’s one of the examples that I gave in the notes of specifying a function by its graph, but there are several more besides. And next week, we’ll use this tactic to prove the existence of coproducts.