I was watching the following video, and around 6:12, he says "Whenever there is a total injective relation, there is always a total injective function" as well.
I cannot quite understand this statement because if there are less elements in set A then set B, and its a total injective relation, there needs to be at least one element in set A that maps to two elements in set B, meaning that it is not a "function". Can anyone explain me what he means here?
Thanks!
Best Answer
"Whenever there is a total injective relation, there is always a total injective function" does not mean "Whenever there is a total injective relation, the exact same relation is a total injective function". The function that is guaranteed to exist might very well be different from the original relation.
That said, his statement is true assuming the axiom of choice. For a total injective relation $R$ on a set $X \times Y$, define a function $f:X \to Y$ in the following way: for each $a \in X$, since there is at least "one arrow out" of $a$ (by his definition of totality) there is at least one $b \in Y$ such that $aRb$ i.e. the set $B_a=\{b \in Y: aRb\}$ is non-empty. Hence, by the axiom of choice, we can choose a unique $b_a \in B_a$. Now simply define $f(a)$ to be this $b_a$. If $R$ is injective, you can check that this function is too. In general, this function $f$ is, of course, not the same as the original relation $R$ from which we constructed it.