Why is there no function with a nonempty domain and an empty range?

Let $A$ to be a nonempty set and $B= \emptyset$; then $ A \times B$ is a set. And let $F$ be a function $A \to B$. Then $F \subseteq A \times B$. By the axiom of specification, $F$ must exists (if I didn't mess up something).

But the book I'm reading, Elements of Set Theory by Enderton, says that no function could have a nonempty domain and an empty range, and no more detail is given.

So my confusion arises. His statement against my proof. The only axiom as far as I know to prove such a set does not exist is the axiom of regularity. But I can't give such a proof. So I need help. I hope someone could clearly explain why such a function doesn't exist, and why this doesn't contradict the axiom of specification.

Let me explain my confusion in more detail:

First of all, I know that $A \times \emptyset$ is empty. But $ \emptyset \times A$ is also an empty set, yet there is no problem with functions with an empty domain.

The book I'm reading defines a function as:

"A function is a relation such that for each $x$ in $\operatorname{dom} F$ there is only one $y$ such that $x \mathop F y$."

and a relation as:

"A relation is a set of ordered pairs."

Now, let me define the function $F$ as: $$F = \{\langle x,y \rangle \mid x \in A \text{ and } y \in B \text{ and ... other conditions} \}$$ so it's equal to: $$F = \{ \langle x,y \rangle \in A \times B \mid \text{... other conditions} \}.$$

Doesn't that mean that $F$ meets the conditions of the axiom of specification, and therefore exists?

What I would specifically like to ask is:

1. How do you define a function $F$ (as precisely as possible)?

2. Why does the argument above not imply that a function $F: A \to B$ always exists?

3. Does $F \subseteq A \times B$ still hold when $B = \emptyset$?

(The answer to #2 cannot simply be that $A \times B = \emptyset$, because $ B \times A = \emptyset$ as well, but a function $B \to A$ does exist.)

Solution 1:

The standard set-theoretic way to define functions is that:

1. The cartesian product of the sets $A$ and $B$, written as $A \times B$, is the set of all ordered pairs where the first element of the pair is in $A$ and the second in $B$: $$A \times B = \{(a,b): a \in A, b \in B\}.$$

   (Representing these ordered pairs as sets, and showing that the cartesian product of two sets is indeed a set under the axioms of set theory, are details that we may safely skip here.)

2. A relation $R$ between the sets $A$ and $B$ is any subset of their cartesian product: $R \subset A \times B$.

   (Often, by convention, we write $a \mathop R b$ as a shorthand for $(a,b) \in R$; this is particularly common when the symbol chosen for the relation is not a letter like $R$, but something abstract like $\sim$ or $\odot$.)

3. A function $f$ from $A$ to $B$ is a relation between $A$ and $B$ (i.e. a subset of their cartesian product) satisfying the following two extra conditions:

   • existence of images: for all $a \in A$, there is a $b \in B$ such that $(a,b) \in f$.

   • uniqueness of images: if $(a,b) \in f$ and $(a,b') \in f$, then $b = b'$.

   If the relation $f$ is a function, then, for each $a \in A$, there exists exactly one $b \in B$ satisfying $(a,b) \in f$. We call this $b$ the image of $a$ under $f$, written $f(a)$, so that: $$f(a) = b \iff (a,b) \in f.$$

So, what about when $B = \varnothing$? In that case, for any $A$, the cartesian product $A \times B = \varnothing$, since there exist no pairs $(a,b)$ such that $a \in A$ and $b \in B$. (The same, of course, is also true whenever $A = \varnothing$.)

Since the only subset of $\varnothing$ is $\varnothing$, the only relation between $A$ and $B$ is the empty relation $\varnothing$. The question, then, is: is the empty relation a function from $A$ to $B$?

• If $A \ne \varnothing$, no, it is not, because there exists at least one $a \in A$, but there can be no $b$ such that $(a,b) \in \varnothing$.

• If $A = \varnothing$, yes, it is. In this case, both the existence and uniqueness conditions are vacuously true, since there is no $a \in A$ for which they could fail.

Thus, there is a (single) function from the empty set to any set (including the empty set itself), but there is no function from a non-empty set to the empty set.

Solution 2:

You messed up because $A\times\varnothing$ is the empty set. So only if $A$ is empty as well such function exists.

Solution 3:

A function $f\colon A\to B$ is a subset of $A\times B$ such that

1. for every $a\in A$, there exists $b\in B$ such that $(a,b)\in f$;

2. for every $b,b'\in B$, if there exists $a\in A$ with $(a,b)\in f$ and $(a,b')\in f$, then $b=b'$.

The first condition expresses the fact that every element in $A$ has an image in $B$. The second condition expresses the fact that such image is uniquely determined by the element in the domain. Thus, if $a\in A$, we can write $f(a)$ to denote the unique element in $B$ such that $(a,f(a))\in f$.

Now, if $B=\emptyset$, we have $f\subset A\times\emptyset=\emptyset$, so $f$ is empty. Thus every element of $A$ fails to have an image in $B$ under $f$, and so a function $f\colon A\to\emptyset$ can exist only when also $A$ is empty.

On the contrary, if $A=\emptyset$, condition 1 cannot fail for any element of $\emptyset$, which has no elements; also condition 2 cannot fail, so there is indeed a function $f\colon \emptyset\to B$. It's unique, because $f\subseteq \emptyset\times B=\emptyset$, so $f=\emptyset$.

Solution 4:

Given sets $A$ and $B$, a function from $A$ to $B$ is a subset $f\subseteq A\times B$ such that $$\forall a\in A\ \exists ! b\in B\ ((a,b)\in f).$$

Thus, if $A\neq\emptyset$ and $B=\emptyset$, no function $f$ exists, since, given any $a\in A$ you can not find any $b\in B$ with $(a,b)\in A\times B$, as $A\times B$ is empty.

Solution 5:

$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\calcop}[2]{\notag \\ #1 \quad & \quad \text{"#2"} \notag \\ \quad & } \newcommand{\endcalc}{\notag \end{align}} $In essence, Enderton is saying that $$ \tag{0} F\text{ is a function} \;\land\; \text{dom }F \not= \emptyset \;\land\; \text{ran }F = \emptyset $$ is false. And from what I read in the question, and from snippets on the interwebs (e.g., http://tedsider.org/teaching/st/st_notes.pdf), his definitions for domain and range are \begin{align} \text{dom }F & \;=\; \{x \mid \langle \exists y :: xFy \rangle \} \\ \text{ran }F & \;=\; \{y \mid \langle \exists x :: xFy \rangle \} \\ \end{align}

Now, what does it mean that $\;\text{dom }F \not= \emptyset\;$?

$$\calc \text{dom }F \not= \emptyset \calcop{\equiv}{basic property of $\;\emptyset\;$} \langle \exists x :: x \in \text{dom }F \rangle \calcop{\equiv}{the above definition of $\;\text{dom}\;$} \langle \exists x :: \langle \exists y :: xFy \rangle \rangle \endcalc$$

Similarly,

$$\calc \text{ran }F = \emptyset \calcop{\equiv}{basic property of $\;\emptyset\;$} \lnot\langle \exists y :: y \in \text{ran }F \rangle \calcop{\equiv}{the above definition of $\;\text{ran}\;$} \lnot\langle \exists y :: \langle \exists x :: xFy \rangle \rangle \rangle \endcalc$$

Therefore we have a contradiction:

$$\calc \text{dom }F \not= \emptyset \;\land\; \text{ran }F = \emptyset \calcop{\equiv}{the above calculations} \langle \exists x, y :: xFy \rangle \;\land\; \lnot \langle \exists x, y :: xFy \rangle \calcop{\equiv}{logic: contradiction} \text{false} \endcalc$$

and it directly follows that $(0)$ is false, regardless of the definition of 'function'.

So (using Enderton's definitions) there is not even a relation $\;F\;$ with a non-empty domain and an empty range, and therefore (since every function is a relation) there is also no function with a non-empty domain and an empty range.

Note how no fixed sets $\;A\;$ or $\;B\;$ have been mentioned so far.

Enderton then abbreviates $$ F : A \to B \;\equiv\; F\text{ is a function} \;\land\; \text{dom }F = A \;\land\; \text{ran }F \subseteq B $$ Note how this definition is asymmetrical w.r.t. domain and range: $\;F : A \to \emptyset\;$ is false for non-empty $\;A\;$ (as we've just proved above), but $\;F : \emptyset \to B\;$ is true iff $\;F = \emptyset\;$ (since $\;\emptyset\text{ is a function}\;$), regardless of the value of $\;B\;$. This is exactly the asymmetry noted in the question.