0
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Evan Rosica May 25 '17 at 2:07
  • $\begingroup$ @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. $\endgroup$ – drhab May 25 '17 at 8:26
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ There is no fallacy. The function is $\emptyset$. $\endgroup$ – copper.hat Feb 28 '16 at 16:44
  • $\begingroup$ 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'. $\endgroup$ – Levent Feb 28 '16 at 16:46
  • 1
    $\begingroup$ 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$. $\endgroup$ – copper.hat Feb 28 '16 at 16:50
  • 1
    $\begingroup$ 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$. $\endgroup$ – Levent Feb 28 '16 at 16:51
1
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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$?).

$\endgroup$
0
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.