### Axiomatic Set Theory 5: Relations

#### Posted by Tom Leinster

*Previously: Part 4. Next: Part 6*

I called this chapter of my course “Relations”, but I should have called it “Specifying subsets and functions”, because that’s what it’s all about. This week, we saw that it’s possible to define subsets of a set $X$ by expressions like

$\{ x \in X : \text{some property of }\ x\ \text{ holds} \},$

and functions $f$ by expressions like

$f(x) = \text{some formula in }\ x.$

I didn’t want to drown the students in notation, so I didn’t give precise definitions of “property” and “formula”. Instead, I aimed to give them practical tools that would apply to situations they’re likely to meet.

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.

## Re: Axiomatic Set Theory 5: Relations

I absolutely love these course notes! This may be an annoying remark, but the statement “An axiomatization is just an agreement about how we’re going to use the word ‘set’.” appearing on p. 8 bothers me just a little. An agreement about how to use a certain word is a form of definition of that word because what else could it be? If we see definitions as named (encapsulated) constructions in a formal (typed) language then axioms and axiomatic notions can be seen as definitions without definientia (see the lambda-D type theory, described in “Type Theory and Formal Proof”). Axioms and axiomatic notions are choices (which is why it makes no sense to say they are true or false, just like it does not make sens to say that about any definition), and what differentiates them from regular (unfoldable) definitions is that they are choices

to speak as ifsome statements had proofs or some objects could be constructed from more elementary objects. This similarity to regular definitions is perhaps to deep to be ignored?