Universal property of the empty set

empty_set_universal_property.json

https://arbital.com/p/empty_set_universal_property

by Patrick Stevens Aug 25 2016 updated Aug 27 2016

The empty set can be characterised by how it interacts with other sets, rather than by any explicit property of the empty set itself.

[summary: The Empty set can be characterised by how it interacts with other sets, rather than by the usual definition as "the set that contains no elements". It therefore makes a very concrete example of defining an object through its Universal property. The property is:

The empty set is the unique set $~$X$~$ such that for every set $~$A$~$, there is a unique function from $~$X$~$ to $~$A$~$. (To bring this property in line with our usual definition, we denote that unique set $~$X$~$ by the symbol $~$\emptyset$~$.) ]

[summary(Technical): The Empty set $~$\emptyset$~$ satisfies the following Universal property: for every set $~$X$~$, there is a unique Function $~$f: \emptyset \to X$~$. That is, the empty set is an [-initial_object] in the category of sets.]

To start us off, recall that the Empty set $~$\emptyset$~$ is usually defined as the set which contains no elements. That property picks it out uniquely, because we have the "[axiom_of_extensionality Axiom of Extensionality]":

Two sets are the same if and only if their elements are all the same.

If we had two sets which both contained no elements, then all their elements would ([vacuous_truth vacuously]) be the same, so by extensionality the sets are the same.

In this article, we will introduce another way to characterise the empty set. Rather than working with the elements of the set, though, we will consider the functions which have the set as their domain. You might think at first that this is a very strange way to look at a set; and you might be right. But it turns out that if we do it this new way, characterising the empty set by examining the maps between sets %%note: "Map" is just a synonym for "function", in this context.%%, we end up with a recipe that is much, much more widely applicable.

The empty function

When we use set theory to capture the idea of a "function", we would usually implement $~$f: A \to B$~$ as a set of ordered pairs $~$(a, f(a))$~$, one for each element $~$a$~$ of the domain $~$A$~$, with the requirement that the elements $~$f(a)$~$ all must lie in $~$B$~$. This set of ordered pairs holds all of the information about the function, except that it has omitted the (almost always unimportant) fact that $~$B$~$ is the codomain. %%note:We usually only care about the image of the function.%%

This implementation of the function $~$f$~$ is just a set; it might look like $~$\{ (0,1), (1,2), (2,3), (3,4), \dots \}$~$, which would represent the function $~$f: \mathbb{N} \to \mathbb{N}$~$ given by $~$n \mapsto n+1$~$.

And we might ask, can we go the other way round? Given a set $~$X$~$, can we interpret it as a function? Well, of course we need $~$X$~$ to contain only ordered pairs (what could it mean for $~$(0,1,2)$~$ to lie in the implementation of the function $~$f$~$?), but also we must make sure that the function is Well-defined by ensuring that the first coordinates of each pair are all distinct. If we had the set $~$\{ (0,1), (0,2) \}$~$, that would indicate a function that was trying to take $~$0$~$ to both $~$1$~$ and $~$2$~$, and that's ambiguous as a function definition. But those are the only requirements: for any set that obeys those two conditions, we can find a function which is implemented as that set.

Very well. Now look at the empty set. That only contains ordered pairs: indeed, it doesn't contain anything at all, so everything in it is an ordered pair. %%note:If you're squeamish about this, see [vacuous_truth].%% And the first coordinates of each pair are distinct: indeed, there aren't any pairs at all, so certainly no two pairs have the same first coordinate.

So the empty set itself is implementing a function. We call this the "empty function"; it is the [-identity_function] on the empty set. %%note:Don't get worried about the empty set representing a function that is the identity function on itself. To worry about this is to make a [type_error type error] in your thinking. The same object (the empty set) is here standing for two different things, under two different "encoding schemes". Under one encoding scheme, where we look at sets as being functions, it's the empty function. Under another encoding scheme, where we look at sets just as being sets, it's the empty set.%%

Meditation: domain, codomain and image

If the empty set implements a function, then that function should have a domain. What is the domain here? %%hidden(Show solution): The domain is the empty set.

Indeed, there are no elements in the domain, because an element of the domain is just a thing in the first coordinate of one of the ordered pairs, but there aren't any ordered pairs so there can't be any elements of the domain. %%

What is the image? %%hidden(Show solution): The image is also the empty set.

Indeed, there are no elements in the image, because an element of the image is just a thing in the second coordinate of one of the ordered pairs, but there aren't any ordered pairs so there can't be any elements of the image. %%

What is the codomain? %%hidden(Show solution): Aha! Trick question. We said earlier that in looking at functions being implemented as sets, we threw away information about the codomain. We can't actually tell what the codomain of the function implemented by $~$\emptyset$~$ is. %%

Important fact

From the domain/image/codomain meditation above, we can now note that for every set $~$A$~$, there is a function from $~$\emptyset$~$ to $~$A$~$: namely, the empty function. Put another way, we can always interpret the empty set as being a function from $~$\emptyset$~$ to $~$A$~$, whatever $~$A$~$ is.

%%hidden(Example): Let $~$A = \{ 1 \}$~$, so we're showing that there is a function from $~$\emptyset$~$ to $~$\{1\}$~$: namely, the empty function, which is implemented as a set by $~$\emptyset$~$. This is a valid implementation of a function from $~$\emptyset$~$ to $~$\{1\}$~$, because $~$\emptyset$~$ is a set which satisfies the three properties that are required for us to be able to interpret it as a function from the domain $~$\emptyset$~$ to the codomain $~$\{1\}$~$:

%%

Moreover, for every set $~$A$~$, there is only one function from $~$\emptyset$~$ to $~$A$~$. Indeed, if we had a different function $~$f: \emptyset \to A$~$, then there would have to be some element of the domain $~$\emptyset$~$ on which $~$f$~$ differed from the empty function. But there aren't any elements of the domain at all, so there can't be one on which $~$f$~$ and the empty function differ. Hence $~$f$~$ is actually the same as the empty function.

The universal property of the empty set

The universal property of the empty set is as follows:

The empty set is the unique set $~$X$~$ such that for every set $~$A$~$, there is a unique function from $~$X$~$ to $~$A$~$. To bring this property in line with our usual definition, we denote that unique set $~$X$~$ by the symbol $~$\emptyset$~$.

We've just proved that our standard definition of $~$\emptyset$~$ does satisfy that universal property; that was the Important Fact just above.

Aside: why "universal"?

The property is a "universal property" because it's not "local" but "universal". Rather than considering the individual things we can say about the object $~$\emptyset$~$, the property talks about it in terms of every other set. That is, the property defines $~$\emptyset$~$ by reference to the "universe" of sets.

In general, a "universal property" is one which defines an object by specifying some way that the object interacts with everything else, rather than by looking into the object for some special identifying feature.

Does the universal property uniquely pick out $~$\emptyset$~$?

I sneakily slipped the words "is the unique set" into the property, without proving that they were justified. What use would it be if our universal property didn't actually characterise the good old $~$\emptyset$~$ we know and love? %%note:Well, it might still be of some use. But it would mean the universal property might not work as a definition of $~$\emptyset$~$. %% Let's see now that at least the property isn't totally stupid: there is a set which doesn't have the universal property.

$~$\{1\}$~$ doesn't satisfy the universal property

We need to show that the following is not true:

For every set $~$X$~$, there is a unique function from $~$\{1\}$~$ to $~$X$~$.

Have a think about this yourself.

%%hidden(Show possible solution): Let $~$X$~$ be any set at all with more than one element. For concreteness, let $~$X$~$ be $~$\{ a, b \}$~$.

Now, there are two functions from $~$\{1\}$~$ to $~$\{a,b\}$~$: namely, $~$f: 1 \mapsto a$~$, and $~$g: 1 \mapsto b$~$.

So $~$\{1\}$~$ fails to satisfy the universal property of $~$\emptyset$~$, and indeed it fails massively: for every set $~$X$~$ which has more than one element, there is more than one function $~$\{1\} \to X$~$. (Though all we needed was for this to hold for some $~$X$~$.) %%

Only the empty set satisfies the universal property

It's actually the case that the empty set is the only set which satisfies the universal property. There are three proofs, none of them very complicated and all of them pedagogically useful in different ways. Here, we will duplicate one of the most "category-theory-like" proofs, because it's really rather a new way of thinking to a student who has not met category theory before, and the style turns up all over category theory. To distinguish it from the other two proofs (which, remember, are detailed here), we'll call it the "maps" proof.

The "maps" way

We'll approach this in a slightly sneaky way: we will show that if two sets have the universal property, then there is a bijection between them. %%note: The most useful way to think of "bijection" in this context is "function with an inverse".%% Once we have this fact, we're instantly done: the only set which bijects with $~$\emptyset$~$ is $~$\emptyset$~$ itself.

Suppose we have two sets, $~$\emptyset$~$ and $~$X$~$, both of which have the universal property of the empty set. Then, in particular (using the UP of $~$\emptyset$~$) there is a unique map $~$f: \emptyset \to X$~$, and (using the UP of $~$X$~$) there is a unique map $~$g: X \to \emptyset$~$. Also there is a unique map $~$\mathrm{id}: \emptyset \to \emptyset$~$. %%note: We use "id" for "identity", because as well as being the empty function, it happens to be the identity on $~$\emptyset$~$.%%

The maps $~$f$~$ and $~$g$~$ are inverse to each other. Indeed, if we do $~$f$~$ and then $~$g$~$, we obtain a map from $~$\emptyset$~$ (being the domain of $~$f$~$) to $~$\emptyset$~$ (being the image of $~$g$~$); but we know there's a unique map $~$\emptyset \to \emptyset$~$, so we must have the composition $~$g \circ f$~$ being equal to $~$\mathrm{id}$~$.

We've checked half of "$~$f$~$ and $~$g$~$ are inverse"; we still need to check that $~$f \circ g$~$ is equal to the identity on $~$X$~$. This follows by identical reasoning: there is a unique map $~$\mathrm{id}_X : X \to X$~$ by the fact that $~$X$~$ satisfies the universal property %%note: And we know that this map is the identity, because there's always an identity function from any set $~$Y$~$ to itself.%%, but $~$f \circ g$~$ is a map from $~$X$~$ to $~$X$~$, so it must be $~$\mathrm{id}_X$~$.

So $~$f$~$ and $~$g$~$ are bijections from $~$\emptyset \to X$~$ and $~$X \to \emptyset$~$ respectively.

Recap

To summarise the discussion above, we have shown that the universal property of the empty set uniquely characterises the empty set. We could actually use it as a definition of the empty set:

We define the empty set to be the unique set $~$X$~$ such that for every set $~$A$~$, there is a unique function from $~$X$~$ to $~$A$~$.

This is a bit of a strange definition when we're talking about sets, but it opens the door to many different and useful constructions. You might like to think about the following similar universal properties, and what they define.

Aside: definition "up to isomorphism"

With universal properties, it is usually the case that we obtain a characterisation of objects only "up to isomorphism": the universal property doesn't care about bijections. If the object $~$X$~$ satisfies a universal property, and the object $~$Y$~$ is isomorphic to $~$X$~$, then $~$Y$~$ will probably satisfy the universal property as well. (Normally this doesn't really matter, since objects which are isomorphic are "basically the same" in most of the ways we care about.)

In this case, though, we do end up with a uniquely-defined object, because it so happens that the only object isomorphic %%note: In this case, when talking about sets, "isomorphic to" means "bijecting with".%% to the empty set is the empty set itself.

An example where we don't end up with a uniquely-defined object is the "reverse" of the empty set's universal property: "the set $~$X$~$ such that for every set $~$A$~$, there is a unique function from $~$A$~$ to $~$X$~$". (You may have thought about this property in the previous section.) In this case, the sets which satisfy that "reverse" universal property are exactly the sets with one element.

You should try to go through the "maps" way of showing that the universal property of the empty set picks out a unique set, but instead of using the UP of the empty set, try using the "reverse" property. The same structure of proof will show that if two sets satisfy the "reverse" universal property, then there is a bijection between them. So we do still retain that if two sets satisfy the "reverse" UP, then they are isomorphic; and indeed if we have two sets with one element, there really is a bijection between them (given by matching up the single element of each set).

This is a general phenomenon: most universal properties don't define an object uniquely, but they do give us the fact that if any two objects satisfy the universal property, then the two objects are isomorphic.