The empty function
, i.e., the set of all functions from has only one element: the empty set.
The empty set contains no elements to map to for any . We can show this is true by taking a restriction of , given by , since, of course, .
Let’s look at the equivalence class of . Let us form a partition on . We know there exists at least one map, namely for all (note ). Now assume there exists another, so that we have and , where both are equivalence classes. Then there exist and such that , and . Then it is obvious that , since nothing maps to . So for we have , , so ; but this cannot be, since is empty. So there is no , and therefore is the only element in all of .
Proposition N9.1. If , then is empty.
Proof. A map means that some element must map to something, but for any . Thus there is no such map, and . ∎
Unions of families
Take families and , with
Then
In the finite case:
Part 1
Exercise N9.2 (Problem 1). Show solution
It must be a relation which satisfies 3 axioms:
- Reflexivity: for all .
- Symmetry: for all .
- Transitivity: for all .
Exercise N9.3 (Problem 2). Show solution
True. If , then all must map to some , so there must exist some . Therefore every .
Exercise N9.4 (Problem 3). Show solution
.
Exercise N9.5 (Problem 4). Show solution
True. This seems vacuously true: since there is no , there are no and such that or such that . So is true, and is injective.
Exercise N9.6 (Problem 5). Show solution
This cannot be true (it is false) when , since “for all there exists such that ” cannot be true: as we showed above, every has at most one element, .
Exercise N9.7 (Problem 6). Show solution
is all such that , where is an equivalence relation.
Exercise N9.8 (Problem 7). Show solution
When it is bijective.
Exercise N9.9 (Problem 8). Show solution
.
Exercise N9.10 (Problem 9). Let be a function, and let on be
Show that is an equivalence relation.
Show solution
Since is defined, as well. Then:
- Reflexive: is obviously true.
- Symmetric: holds, so .
- Transitive: if and , then (transitive law), so .
Exercise N9.11 (Problem 10). If and , show that is injective as well.
Show solution
Consider that is a biconditional. Given this, we can construct , which can be written (with ). Notice that for , , which is to say (with ). Therefore
so we can say . Thus is injective.
Exercise N9.12 (Problem 11). Let be a bijection. Show that .
Show solution
Consider an arbitrary . Given the bijection, we know that , and since it is bijective, , for all , . Thus no matter what or are, we have
Exercise N9.13 (Problem 12). (a) If and , then . We intend to prove this.
Show solution
(a) The distance of and from each other is some multiple of 3, say . The same must be true for , say . Thus the distance from to is with , so
(b) The equivalence class in this case is all multiples of 3: , so .
(c) There are infinitely many integers divisible by 3, so each class is countably infinite; but there are exactly three distinct equivalence classes, , , .
Exercise N9.14 (Problem 13). Show solution
(a) Since is linear with nonzero slope (as a map ), it must be bijective, so injectivity is automatically satisfied.
(b) Since is linear with nonzero slope, it must be bijective, so surjectivity is automatically satisfied.
(c) Since is bijective, exists, and it is given by
Exercise N9.15 (Problem 14). Given , .
Show solution
(a) , so at most we have functions. But a function chooses one of the 2 elements of for each of the 3 elements of , so there are really VALID functions.
(b) None (?)
(c) At least 6 functions are surjective.
Exercise N9.16 (Problem 15). Let be an equivalence relation on . Show that (the set of equivalence classes) forms a partition of .
Show solution
To start, I prefer the notation personally, so that is what I will use. The union of all being is obvious. So we must mainly prove that it is a set of disjoint unions. Assume there is with (for contradiction). Then and , but by the transitive property, ! Thus there is a contradiction, and they must be in the same class. Therefore all distinct equivalence classes are disjoint, and therefore they form a partition.
Exercise N9.17 (Problem 16). is bijective there exists such that and . We attempt to show this is true.
Show solution
Let us say we have a “left inverse function” given by . Let ; we show that if then . Now and , so means .
Conversely, if , define on by (well defined because is injective) and arbitrarily on the rest of (possible when ). Then .
Now the “right inverse”: for all there exists with .
- For : . ✓
- For : for each choose an with and set . Then . ✓
For the direction “bijection ”, the first part () was proven in Problem 11; the second is given by for all , so .
Exercise N9.18 (Problem 17). Show solution
(a) Yes: any has an is bijective.
(b) for all :
(c) , , , . Notice then that .
(d) , .