# Bijection from $A \rightarrow \varnothing$

My thoughts. We need to prove that:

1 $\forall x,y \in A, \text{ if } f(x) = f(y) \rightarrow x = y$

2 $\forall y \in \varnothing, \exists x \in A, f(x) = y$.

In (1), $f(x) = f(y)$ is false, since neither $f(x)$ nor $f(y)$ have a value, so (1) is vacuously true.

Also, $\forall y \in \varnothing, P(x, y)$ is vacuously true. So both statements are true.

Admittedly, Does there exist a bijection between empty sets? offers some guidance, but I am unsure whether my rationale for #1 is sound.

Let $f:A\to\varnothing$ denote a function.

If $a\in A$ then automatically $f(a)\in\varnothing$. This contradiction makes us conclude that $A=\varnothing$.

There is indeed a map $f:\varnothing\to\varnothing$. Its graph is a subset of $\varnothing\times\varnothing=\varnothing$ hence is $\varnothing$ itself. This shows that $f$ is unique. It is called the empty map. This map is vacuously bijective.

edit:

Every function $f:A\to\varnothing$ is a bijection.

Let $f:A\to\varnothing$ be a function. Then for every $z\in\varnothing$ there is a unique $x\in A$ such that $f(x)=z$.

This statement is vacuously true. This because we cannot find any $z\in\varnothing$ for wich it is not true (even stronger: we cannot find any $z\in\varnothing$ at all). And the statement expresses that $f$ is injective and surjective as well.

• As you showed, if $A\neq \emptyset$ then $f:A\rightarrow \emptyset$ is not a function. Therefore every function $A \rightarrow \emptyset$ is a bijection, and a unicorn, and a dragon vacuously. – Evan Rosica May 25 '17 at 2:07
• @Evan That only works under the condition that $A$ is not empty. In the edit of my answer that is not used so that it also works if $A$ is empty. – drhab May 25 '17 at 8:26

The fallacy is there exists no function $f:A\rightarrow\varnothing$ (A function from $A$ to $B$ is a subset of $A\times B$ such that for any $a\in A$ there exists a unique $b\in B$ such that $(a,b)$ is in the subset) if $A$ is not empty.

• There is no fallacy. The function is $\emptyset$. – copper.hat Feb 28 '16 at 16:44
• What do you mean by 'the function is $\varnothing$'. As I explained, if $A$ is not empty, then we cannot talk about 'the empty function' because of the very definition of 'a function'. – Levent Feb 28 '16 at 16:46
• Your answer is correct (except for the fallacy part). If $A$ is not empty, there is no such function, so $A$ must be the empty set. The corresponding bijection is, literally, $\emptyset$. – copper.hat Feb 28 '16 at 16:50
• Oh I see. Well, since the answer of the case $A=\varnothing$ is given in the cited question, I thought the question is about the case when $A\neq\varnothing$. – Levent Feb 28 '16 at 16:51

Functions $f:A\rightarrow B$ can be thought of as particular subsets of $A\times B$ (ones that satisfy the well-defined property). Since $A\times\emptyset=\emptyset$, there is only one subset of $A\times\emptyset$.

Additionally, for the domain of $f:A\rightarrow B$ to be $A$, for all $a\in A$, there must exist $b\in B$ such that $(a,b)\in f$. In your case, since $f=\emptyset$, $(a,b)\not\in f$, so it must be that there is no $a\in A$. Hence $A=\emptyset$.

A function $A\longrightarrow\emptyset$ is trivially a relation. i.e. a subset of $A\times\emptyset =\emptyset$. Then, the only possible relation is $\emptyset$, but $\emptyset$ isn't a function except if $A = \emptyset$ (why? hint: what is $f(a)$ for some $a\in A$?).

Claim 1: If $A\neq \emptyset$ then there does not exist a function $f:A\rightarrow \emptyset$.

By way of contradiction, assume that $A\neq \emptyset$ and $\exists f:A\rightarrow \emptyset$. Since $A$ is not empty, $\exists a\in A$, and since the codomain is the empty set, we have that $f(a) \in \emptyset$. This is a contradiction to our assumption. Therefore the claim is proved. $\square$

If you want to use the more rigorous definition of a function, you could write this proof as follows:

Suppose by way of contradiction that $A\neq\emptyset$ , and $f:A\rightarrow\emptyset$ . Recall that a function $f:A\rightarrow B$ is a relation and is thus a subset of the cartesian product $A\times B=\{(a,b):a\in A\land b\in B\}$ . Since $B=\emptyset$ , $\exists b\in B$ is false. However, by the definition of a function, $\forall a\in A,\exists b\in B(a,b)\in f$ , which is a contradiction, since $\neg\exists b\in B$ . Thus the claim is proved. $\square$

Thus, by either proof, we can see there are no functions $f:A\rightarrow \emptyset$ for $A\neq \emptyset$. Thus we have (vacuously) that all ($0$) of these functions are bijections, and unicorns, and superheroes, etc.

Claim 2: Let $A = \emptyset$ and $f:A\rightarrow \emptyset$. Then $f=\emptyset$ is a bijection from $\emptyset\rightarrow\emptyset$

To prove this claim, we need to use the rigorous definition of a function $f:A\rightarrow B$ as a type of relation, ie a subset of the Cartesian product $A\times B$, in which the following are true

1) $\forall a\in A,\exists b\in B((a,b)\in f)$

2) [$(a,b)\in f$ and $(a,b')\in f] \implies b=b'$

Since there are no $a\in A=\emptyset$ , the first condition is vacuously true. Likewise, since $f=\emptyset$ , the antecdent/hypothesis $(a,b)\in f$ and $(a,b')\in f$ is false, and therefore the second condition is vacuously true, and thus $f=\emptyset$ is a function.

Since there are no elements in either the domain or the codomain, we get bijectivity vacuously as the OP correctly noted. $\square$