4
$\begingroup$

I recently encountered what seems to me like an inconsistency in the usage of the term bijective. This is pretty basic stuff, but it somehow never occurred to me before. I'd like to make sure I'm using the term properly with respect to relations.

The definition (and, I assume, etymology) of bijective is usually given for functions as:

  (1)   injective and surjective.

But I've also heard the term used for relations. Thinking back, it would refer to a relation that is:

  (2)   injective and uniquely defined.

The point being that the bijective property should actually refer to the "one-to-one" nature of the relation or function in question.

(Functions get uniquely defined 'for free'. The extra ingredient for a bijective function is surjectivity, probably with the purpose that its inverse is then also a bijective function.)

But the two definitions are incompatible with the interpretation of functions as well-defined relations. Taking them both literally would result in contradiction: a non-surjective function would be bijective by (2), but not bijective by (1).

How is this usually dealt with? Is there a generally accepted alternative term for (2)?


Edit 1: As it turns out I am unable to find any reference to definition (2). I suppose my new question now becomes: Is there a nice term for uniquely defined, injective relations / injective partial functions?


Edit 2: Take a look at this Wikipedia section:

https://en.wikipedia.org/wiki/Finitary_relation#Analogy_with_functions

According to this, a relation can be bijective without being a function. It still doesn't correspond to (2) though. It keeps its etymological meaning: injective and surjective, i.e., the inverse of a function.

The nouns bijection, injection and surjection are reserved for functions, but the adjectives can apply to relations too.

(2) is called one-to-one there which, I suppose, is acceptable. :-)

$\endgroup$
  • 7
    $\begingroup$ I for one have never heard "bijective" used to describe anything that was not a function. $\endgroup$ – Ben Millwood Sep 1 '13 at 23:53
  • 2
    $\begingroup$ Can you provide any resources using it as in (2)? It would be interesting to look at. $\endgroup$ – rschwieb Sep 2 '13 at 0:10
  • $\begingroup$ What do you mean by a injective relation $R$? I suppose that this means that for any $a$ and $b$ in the domain of $R$ with $a\ne b$, we have that the sets $R\bigl(\{a\}\bigr)$ and $R\bigl(\{b\}\bigr)$ are distinct. On the other hand, your clause (2), at least to me, means simply "injective function", and have nothing to do with surjectivity. $\endgroup$ – Matemáticos Chibchas Sep 2 '13 at 3:45
  • $\begingroup$ @rschwieb: Here is one resource giving the definition as (2): proofwiki.org. But you're right, it was not easy to find. $\endgroup$ – mhelvens Sep 2 '13 at 10:35
  • $\begingroup$ @MatemáticosChibchas: a relation $R$ is injective iff $(a, c) \in R$ and $(b, c) \in R$ implies $a = b$. And I'd actually call clause (2) an injective partial function, as it is not necessarily fully defined. --- That it has nothing to do with surjectivity is exactly the point of my question. $\endgroup$ – mhelvens Sep 2 '13 at 10:36
2
$\begingroup$

Actually "bijective", like "injective" and "surjective", is a perfectly well defined notion, and any object that claims this badge has to be a function. Most people would not consider applying the notion at all in a context where the object is not assumed to be a function to begin with, but it is acceptable to define a bijective relation to be a one-to-one correspondence, in other words a relation that is actually a bijective function (this seems to be the case for this definition, which does not correspond to (2) of the question).

Other notional may be less clearly defined; notably "one-to-one" has always been a mystery to me, because it means "bijective" when used as in my previous sentence, but a "one-to-one map" is actually only an injective function.

The notion descibed in (2) might be called an "injective partial function" as you do without causing much confusion. However it does create the precedent of applying the adjective "injective" to something that is not a function (or a module, a resolution, or a metric space). Alternative terms one could think of proposing are "invertible partial function" (but it is not really invertible, as composition with its "inverse" partial function only gives a partial identity), or "partial bijection" (but one has to understand that "partial" applies to both sides, so nothing of surjectivity is left) or "partial injection" (no confusion, but like "injective partial function" the terminology appears to be asymmetric, while the notion itself is not). Finally "zero-or-one-to-zero-or-one correspondence" does seem to suggest the proper definition, but is frankly quite awkward.

$\endgroup$
  • $\begingroup$ You're right about the proofwiki definition 5. It does not correspond to (2); I made a mistake. However, take a look at this Wikipedia section. It gives a fairly compelling vocabulary for all of these notions. What do you think? It partly disagrees with your answer. In particular: a bijection indeed has to be a function, but bijective in and of itself just means injective and surjective, i.e., the inverse of a function. --- (2) is called one-to-one, as you suggest. I updated my question with this information. $\endgroup$ – mhelvens Sep 2 '13 at 13:03
1
$\begingroup$

It seems I'm a bit late to the party, but I have some reassuring news regarding consistency of definition :)

Recall that a relation between $A$ and $B$ is a a subset of $A \times B$. Then a function is a totally defined and deterministic (ie think computers) relation ---deterministic relations are also called "partial functions".

More precisely, $$R \text{ total } :\equiv \forall x :: \exists y :: x \ R \ y$$ $$R \text{ deterministic } :\equiv \forall x :: \forall y, y' :: x \ R \ y \land x \ R \ y' \implies y = y'$$

Anyhow, since we are working in the context where functions are special kinds of relations, it makes little sense to take "function definitions" and "rewrite" them for relations. A more sensible approach would be to take "relation properties" and observe what form they take for the case of functions.

For a relation $R$, we have the following notions $$R \text{ surjective } :\equiv R^T \text{ total }\;\; \text{ ;; } \;\; R \text{ injective } :\equiv R^T \text{ deterministic} $$ where transpose is defined $$R^T := \{ (y,x) \ | \ x \ R \ y\}$$

Now a bijective relation is one that is both surjective and injective.

Here's the cool part: chasing definitions above, we find that $R$ is a bijection iff $R^T$ is a mapping! Thus, in the function case, we regain the "traditional" concept of a function being a mapping whose inverse (ie transpose) is also a mapping!

I hope you've found this as useful as I have :)

For more on relations, see "Relational Mathematics" by Gunther Schmidt. The above defns were taken from there.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.