10
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ You colud also use that every surjection $A\to A$ and $A$ is finite is bijective. $\endgroup$
    – nonuser
    Jan 10, 2023 at 6:32
  • 1
    $\begingroup$ Injectivity and surjectivity conditions are also vacuously satisfied - no need to re-write or do a proof by contradiction there. $\endgroup$ Jan 10, 2023 at 7:14

2 Answers 2

5
$\begingroup$

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

  1. There exists a function mapping $\emptyset\rightarrow \emptyset$.
  2. Such a function is unique.
  3. This function is a bijection.

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:

Consider the triple $f = (\emptyset, \emptyset, \emptyset)$. Since the domain is empty, it is vacuously true that every element in the domain has an image and moreover, that this image is unique. Therefore, $f$ is a function.

And follow that with uniqueness:

Let $g = (\emptyset, \emptyset, G)$ be a function. Since $G \subseteq \emptyset \times \emptyset$, it must be that $G = \emptyset$, and so that $g = f$. Hence, $f$ is the unique function mapping $\emptyset \rightarrow \emptyset$.

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.

$\endgroup$
1
$\begingroup$

Your proof is correct. I think Damian Pavlyshyn’s answer brings up most of the points I would, but I would like to add a bit more.

First, it is interesting and useful to note that we can slightly generalise the first part of your claim. In fact, for all sets $A$, there is a unique function $\emptyset \to A$ given by the triple $(\emptyset, A, \emptyset)$. Your argument works perfectly for this more general case.

Second, your proof that the function you defined is surjective needlessly uses proof by contradiction. You could instead note that you are asked to prove that a certain property holds for all $b \in \emptyset$; this follows vacuously. Any statement of the form $(\forall b \in \emptyset) P(b)$ follows vacuously. When proof by contradiction can be avoided in a proof, you’ll usually find that the proof is simpler and more straightforward (though this is not always true). There are other reasons to avoid proof by contradiction if possible, but they aren’t something to worry about for someone just getting in to proofs.

Third, it is also interesting to note that we can generalise your proof in another way. Note that for all $A$, we can define the identity function $1_A : A \to A$ by $1_A(x) = x$. More formally, we have $1_A = (A, A, \{(x, x) \mid x \in A\})$. We can show that the identity function is in fact a function and is a bijection. This gives us a function $1_\emptyset : \emptyset \to \emptyset$ which is a bijection; all that remains is to show it’s the only function with that domain and codomain.

Fourth, I am sure you probably got this part out of a book, but you can simplify the definition of condition (2) by writing it as $(\forall x, y_1, y_2) ((x, y_1) \in G \land (x, y_2) \in G \to y_1 = y_2)$. There is no need to quantify over $x_1$ and $x_2$ and then assume the two are equal. You can also combine the two conditions into the single condition $(\forall x \in A) (\exists! y \in B) ((x, y) \in G)$, where $\exists! y$ means “there is a unique $y$”.

$\endgroup$
1
  • $\begingroup$ You're right, I did use the same argument to show the more general case, a unique function exists from $\emptyset \rightarrow A$ and this function is injective. I guess another way to show bijectivity would be that when both sets are the same size, injectivity or surjectivity is enough to show bijectivity. Is the reason to avoid proof by contradiction related to intuitionist logic and how they avoid the law of excluded middle? Also I like avoiding the $\exists !$ cuantifier because I'm not sure if it can be expressed like a regular $\exists$. $\endgroup$
    – zlaaemi
    Jan 10, 2023 at 10:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .