First, these are the definitions I'm working with:
A function can be defined by its domain, codomain and graph, so $g:A \rightarrow B$ is equal to the ordered triplet $g = (A, B, G)$ where $G \subseteq A \times B$. Also, for it to be a function, $G$ must satisfy the following:
1 – $(\forall x)[x \in A \rightarrow (\exists y)(y \in B \land (x, y) \in G)]$ (Every element has an image)
2 – $(\forall x_1, x_2, y_1, y_2) [((x_1, y_1) \in G \land (x_2, y_2) \in G \land x_1 = x_2) \rightarrow y_1 = y_2]$ (The image of every element is unique)
A function $g:A \rightarrow B$ is an injection if:
$(\forall a_1, a_2 \in A) (g(a_1) = g(a_2) \rightarrow a_1 = a_2)$
A function $g:A \rightarrow B$ is a surjection if:
$(\forall b \in B) (\exists a \in A)(g(a) = b)$
A function $g:A \rightarrow B$ is a bijection if: It is both an injection and a surjection.
Now, first we need to determine, is there actually a function $f:\emptyset \rightarrow \emptyset$? If there is, then $f = (\emptyset, \emptyset, G)$ where $G \subseteq \emptyset \times \emptyset = \emptyset$. This then mean that $G = \emptyset$ (by double inclusion). Then $f = (\emptyset, \emptyset, \emptyset)$. Now, is this a function? Well it's just a matter of verifying that the two properties listed above hold for $\emptyset$:
1- $(\forall x)[x \in \emptyset \rightarrow (\exists y)(y \in \emptyset \land (x, y) \in \emptyset)]$. And this is vacuously true since $x \in \emptyset$ is always false.
2 – $(\forall x_1, x_2, y_1, y_2) [((x_1, y_1) \in \emptyset \land (x_2, y_2) \in \emptyset \land x_1 = x_2) \rightarrow y_1 = y_2]$. Similarly, this is also vacuously true since $(x_1, y_1) \in \emptyset$ is always false, which impies $((x_1, y_1) \in \emptyset \land (x_2, y_2) \in \emptyset \land x_1 = x_2)$ is always false, which then implies that the complete statement is always true.
So then $f = (\emptyset, \emptyset, \emptyset)$ is a function and is the only function that can be defined from $\emptyset$ to $\emptyset$. To prove that $f$ is a bijection, we first prove that it is an injection and then that it is a surjection.
First notice that $(\forall a_1, a_2 \in \emptyset) (f(a_1) = f(a_2) \rightarrow a_1 = a_2)$ can be rewritten as $(\forall a_1, a_2)(a_1 \in \emptyset \rightarrow (a_2 \in \emptyset \rightarrow (f(a_1) = f(a_2) \rightarrow a_1 = a_2)))$. This is probably the part of the proof that I'm most unsure of. Looking at the second form of the definition of injectivity is clear that $f$ is injective since the statement is vacuously true.
To prove that the function is surjective, suppose that it isn't, then $\neg (\forall b \in \emptyset) (\exists a \in \emptyset)(f(a) = b)$ is a true statement, then $(\exists b \in \emptyset) (\forall a \in \emptyset)(f(a) \neq b)$, which is clearly false since there is no element in $\emptyset$, hence a contradiction.
Then the function is surjective and injective thus bijective, this concludes the proof.
Are there any spots where my proof doesn't hold? can it be improved? Please let me know!
Best Answer
Congratulations, your proof is correct! What you have defined is called the empty function with codomain $\emptyset$.
Since the proof is right, I'll make a few comments about style. On the whole I understood it all the way through and didn't need to do any backtracking, which is already the sign of a well-written proof! But not to worry - there is still rom for improvement.
Structure
The statement that you are to prove consists of three parts, whose most natural ordering seems to me to be
In your argument, you have proved 2, then 1, then 3. It is not strictly incorrect to prove uniqueness before existence, but it can get you in trouble and is not intuitive to read.
My guess it that you wrote it in this order because that was how you reasoned about it. That is, "what should this $f$ look like? Well, it must have an empty graph, so let's define that object."
When you're writing proofs primarily to convince a reader of the correctness of the result (for example, when writing a research paper, but not when writing a textbook, where the primary aim is exposition), you want to exclude extraneous detail, so best practice would be to introduce your candidate function $f$ without preamble. I would write your existence argument like this:
And follow that with uniqueness:
Formal logic
Mathematics is written in full sentences, and strings of formal logic are very unusual in mathematical writing. You'll notice that in my proposed examples, I have no logical symbols at all, but hopefully I was able to unambiguously convey the logical argument.
This is because formal logic is difficult to parse, and contains every piece of information about the statement, even when only a small amount is needed for the argument at hand. Compare in my existence statement the phrase "since the domain is empty," which is the reason that everything holds vacuously to $$ (\forall x)[x \in \emptyset \rightarrow (\exists y)(y \in \emptyset \land (x, y) \in \emptyset)], $$ where the "$(\exists y)(y \in \emptyset \land (x, y) \in \emptyset)$" part is included in the text despite being long, complicated and completely irrelevant to the argument.
"Clearly"
Remove this word, as well as "obviously" and friends, from your mathematical vocabulary. If something really is clear, you should have no trouble explaining it in one sentence, and that leads to a stronger text. If you can't do this, you're using the word to cover up a messy argument.
This is a minor point, as you only write it once, and the sentence can be improved simply by erasing the word "clearly." Nevertheless, I thought that I would raise it, as it's a good thing to keep in mind.