Given a relation $R \subseteq A \times A$. Then, $R$ might be injective or left-unique. My question is a language question: why is an injective relation called "left-unique"? My feeling would rather to call them (wrongly!) "right-unique", since its "right" elements have a unique (or none) partner on the "left".
I'm looking for a good way of visualizing or explaing the term "left-unique". Thanks!
On
Good question. I also had the same confusion, but when I think of it in terms of relations (which is simply a set of ordered pairs), it makes more sense than as with functions.
A relation is left-unique if every two distinct pairs $(a,b)$ and $(c,d)$ have different first-coordinates (hence, “left”). So a relation containing $(3,4)$ and $(5,4)$ is not left-unique. Now translate this to functions: if $f(3) = 4$ and $f(5) = 4$, then the function—(and all functions are relations∗)—is not left-unique. This matches our definition of injection, which states:
$$f(a) = f(b) \implies a=b$$
So our function is not injective.
∗All functions are relations that have the additional property of “determinism”, also known as “well-definedness,” or “right-uniqueness.”
Functional definition of determinstic: $$a = b \implies f(a) = f(b) \qquad \text{(converse of injection)}$$ In math (but not necessarily computer science) all functions must be deterministic by definition. A function that is not deterministic is not a function—it’s a general relation.
Relational definition of the same concept (right-unique): $$aRu \land aRv \implies u=v$$
A relation containing $(4,3)$ and $(4,5)$ is not right-unique, just as a function with $f(4)=3$ and $f(4)=5$ is not deterministic (i.e., not a function).
It makes sense, because an injective relation has the property that $aRb$ and $a'Rb$ forces $a = a'$. That is, you have a uniqueness property on the left side. This is not happening on the right side: uniqueness statements involve equating two things which a priori need not be equal, which is happening on the left; on the right, $b$ is merely a passenger.