Proof that the empty set is a relation

Question

In the book Naive Set Theory, Halmos mentions that the "The least exciting relation is the empty one." and proves that the empty set is a set of ordered pairs because there is no element of the empty set that is not an ordered pair. Since the empty set is a set of ordered pairs, it follows that it is a relation.

I understand this line of reasoning but couldn't I use that same line of reasoning to prove that the empty set is a set of singletons? And since the empty set is a set of singletons (because it contains no elements which are not singletons) it is not a relation (because a relation is a set of ordered pairs, not singletons). Why is this reasoning invalid?

Answer 1

There’s no actual contradiction here. Let $A$ be any set, and let $S=\big\{\{a\}:a\in A\big\}$, the set of singletons of elements of $A$. Then $\varnothing\subseteq S$, so $\varnothing$ can be described (somewhat confusingly) as a set of singletons, but this is so vacuously: it’s a set of singletons because it does not contain anything that isn’t a singleton, not because it actually contains any singletons. Similarly, $\varnothing$ is a set of ordered pairs of elements of $A$, but only vacuously so, in that it does not contain anything that isn’t such an ordered pair. In fact, if $X$ is any set, $\varnothing$ could be called a set of elements of $X$, simply because $\varnothing\subseteq X$, but this is only vacuously true. It’s best just to notice that $\varnothing$ is a subset of every set and not to try to talk about the nature of its (non-existent) elements.

In particular, it’s better to say simply that every subset of $A\times A$ is by definition a relation on $A$ and then note that $\varnothing\subseteq A\times A$.

Answer 2

The reasoning is valid up to the last step. It is true that the empty set is also a set of singletons. But why can't a set of singletons also be a relation? If you think about how you would prove this, you would need to take an element of the set (which is a singleton) and show that element is not an ordered pair. But in this case, there are no elements to take!

(Similarly, the empty set is also a set of real numbers, and a set of cows, and a set of kings of Canada. This doesn't mean that there is a cow that is king of Canada!)

Answer 3

The empty set is a set of singletons and a set of pairs and a set of topological spaces and a set all of whose members are unicorns. That may seem contradictory, but it isn't. The reason for this lies in the underlying logic. Let $U(x)$ be a predicate that is true of $x$ iff $x$ is a unicorn and consider the sentence $$ \forall x \colon x \in \emptyset \to U(x). $$ This sentence is true, because "$x \in \emptyset$" is false for any $x$. So the right hand side actually doesn't matter and for any formula $\varphi(x)$ the sentence $$ \forall x \colon x \in \emptyset \to \varphi(x) $$ is true by the same reasoning.

So where exactly does your attempt to prove that $\emptyset$ is no relation go wrong? Well... "$x$ is a relation" may be formalized in the following way: Let $\psi(x)$ be the formula $$ \forall y \in x \exists a \exists b \colon y = (a,b) $$ (Note that "$y = (a,b)$" is an abbreviation for a first order formula $\pi(y,a,b)$ that is satisfied iff $y = (a,b)$.)

If $\emptyset$ were not a relation, then $\neg \psi(\emptyset)$ would be true, i.e. $$ \exists y \in \emptyset \forall a \forall b \colon y \neq (a,b) $$ or more precisely $$ \exists y \forall a \forall b \colon y \in \emptyset \wedge y \neq (a,b). $$ However, $y \in \emptyset$ is false for any $y$ and thus $\neg \psi(\emptyset)$ is also false. Therefore $\psi(\emptyset)$ must be true and $\emptyset$ is proved to be a relation. By changing $\psi$ in the obvious way, we may also prove that $\emptyset$ is a set of singletons or a set of unicorns or...

Answer 4

It's all because the empty set is the same empty set regardless of "what it's empty of". Yes, the empty set is a "set of singletons" by this reasoning.

Therefore it is false (or anyway, too vague) to include "not singletons" in your proposition: "a relation is a set of ordered pairs, not singletons". The empty set is "a set of singletons", but it also "contains no singletons". So which is that phrase "not singletons" supposed to mean here -- that it doesn't contain any singletons, or that it is not "a set of singletons"? The empty set qualifies by the former condition but not the latter.

You could more precisely say "a relation contains 0 or more ordered pairs and no singletons", and then it's clear why the empty set qualifies. Or you could say "no set of singletons is a relation", which is simply false under the terminology we've agreed, since we've already agreed that the empty set is "a set of singletons" and also is "a set of ordered pairs". You incorrectly excluded the possibility of a set which is both of those things when you extended "a relation is a set of ordered pairs" to "a relation is a set of ordered pairs, not singletons". There was no justification for adding "not singletons".

In general one must be precise when saying "a set of ordered pairs", whether we mean "a set containing zero or more ordered pairs and no element that is not an ordered pair", or "a set containing one or more ordered pairs and no element that is not an ordered pair". By pointing out that the empty set is to be considered a relation, the author makes clear (if it wasn't already) that the former is intended here. If the latter were meant, then you would be justified in saying that "a set of singletons cannot be a set of ordered pairs". But if the latter were meant then the empty set wouldn't be a relation at all, so you wouldn't be worrying about it anyway!

If, via some notion of types, "the empty set of ordered pairs" and "the empty set of singletons" were different objects, then sure, the empty set of ordered pairs would be a relation and the empty set of singletons would not. But that's not the set theory that you're currently working in.

Answer 5

I like to borrow language from primality proving: The empty set contains no witness to it not being a set of ordered pairs. The empty set contains no witness to it not being a set of singletons. The empty set contains no witness to it not being simultaneously a set of singletons and a set of ordered pairs.

There is no substantial difference saying this rather than "... contains no element such that ..." The word witness just seems more active in this usage.

Aside: The language is from Fermat, Miller-Rabin, and Solovay-Strassen primality tests. For example, in the Fermat test, if you find an $a$ such that $a^{n-1} \not \cong 1 \pmod{n}$, it is a witness for the compositeness of $n$. Similar language is used in other tests.

Answer 6

Adding to the other answers: I like to think of the vacuous truth using its negation.

Let $P(x)$ be any arbitrary statement about an arbitrary $x$. The statement $$ \exists x \in \emptyset \text{ such that } \lnot P(x) \tag 1 $$ is easily seen to be false, since there exists no $x$ in the empty set.

The statement's negation, $$ \lnot\left( \exists x \in \emptyset \text{ such that } \lnot P(x) \right), \tag 2 $$ is logically equivalent to $$ \forall x\in\emptyset, P(x). \tag 3 $$ Since the original statement $(1)$ was false, its negation $(2)$ must be true, and hence $(3)$ is true for all statements $P(x)$.

Answer 7

A set of singletons can be a relationship as long as the set of singletons doesn't actually have any singletons or anything else that isn't an ordered pair. The empty set is a set of singletons that doesn't have any singletons and doesn't have anything that isn't an ordered pair. So the empty set is a set of singletons that is a relation. It's the only set of singletons that is.