If $R \subseteq A \times B$ is a surjective relation, as is $S \subseteq B \times A$, are they bijective relations?

Question

Suppose two sets $A$ and $B$, two relations $R \subseteq A \times B$ and $S \subseteq B \times A$. If both of them are surjective, then both of them are bijective relations.

Is this correct?

Can we disprove this with the following example:

• $A = \{ 1, 2 \}$
• $B = \{3\}$
• $R = A \times B = \{ (1, 3) , (2,3) \} $
• $S = B \times A = \{ (3,1), (3,2) \}$

Both of $R,S$ are certainly surjective but $R$ isn't injective, isn't it?

Answer 1

Definitions:

Taking some notes from the answer from Musa Al-hassy here, I want to establish some common ground since there appears to be confusion among other users and, indeed, these terms while having definitions don't appear to be in common use. At least in my experience anyhow.

• We say $R$ is a relation on $A$ to $B$ if $R \subseteq A \times B$.
• We say $R$ is a total relation if $\forall a \in A$ $\exists b \in B$ such that $(a,b) \in R$. (Think of a total function, your typical definition of function.)
• We say $R$ is a deterministic relation if $$(\forall a \in A)(\forall b,b' \in B)\Big((a,b) \in R \land (a,b') \in R \implies b = b'\Big)$$ What this says is that $R$ is single-valued, in a sense, if you think of it in terms of functions: whenever $a$ is related to something, if at all, it is only related to one thing. Alternatively, it can be thought of in terms of partial functions (where any given input has at most one output).
• We say $R$ is a function if it is total and deterministic.
• We define the transpose $R^T$ of a relation $R$ by reversing everything. That is, $(a,b) \in R \iff (b,a) \in R^T$, or $$R^T = \Big\{ (b,a) \; \Big| \; (a,b) \in R \Big\}$$
• We say $R$ is a surjective relation if $R^T$ is a total relation.
• We say $R$ is an injective relation if $R^T$ is a deterministic relation.
• Naturally, $R$ is a bijective relation if $R$ is both surjective and injective.

---

Visualization:

Visualizing relations as directed graphs is helpful. In such a graph, $x$ points to $y$ iff $(x,y) \in R$. In such a case, then, the above properties may be visualized as so:

• $R$ is a total relation if every node has at least one arrow from it. Examples and non-examples on the sets $A=B=\{1,2,3\}$ will follow this and most properties. (Note that these visual intuitions become murkier in the event $A \ne B$.)

• $R$ is a deterministic relation if every node has no more than one arrow from it.

• The transpose relation $R^T$ is the same graph for $R$, but with its arrows reversed:

• $R$ is a surjective relation if $R^T$ is total. That is, every node in $R^T$ has an arrow going from it. In turn, $R$ is surjective if every node has an arrow going to it. (Again, think about an analogy to surjective functions.)

• $R$ is an injective relation if $R^T$ is deterministic; that is, every node in $R^T$ has at most one arrow leaving it. In turn, $R$ is an injective relation if every node in $R$ has at most one arrow going from it. (Think about function injectivity or partial functions.)

• Finally, $R$ is a bijective relation if and only if it is both injective and surjective. Thus, every node has precisely one arrow entering and leaving it. Or, put differently, each node has precisely one arrow leaving it, and they all go to different nodes. (Again, think about bijective functions.)

---

Now, To Your Question:

Your relation $R$ is surjective. Graphically, it is presented as below:

Notice how there are no arrows pointing to $1$ or $2$. While my above diatribes were focused on subsets of $A \times A$ rather than $A \times B$, there is no issue here, since every element of $B$ in particular has an arrow pointing to it. Indeed, note that

$$R^T = \Big\{ (3,1),(3,2) \Big\}$$

(Note that $R \subseteq A \times B \iff R^T \subseteq B \times A$.) For totality, we would require that, for all $b \in B$ there is $a \in A$ where $(b,a) \in R^T$. Since the only $b \in B$ is $B = \{3\}$, we're good in this respect.

Your other relation is $S = R^T$, coincidentally, graphically presented below:

As you can see, this is surjective, since every element of $A$ has an arrow pointing to it. Indeed,

$$S^T = R = \Big\{(1,3),(2,3)\Big\}$$

so each element of $A = \{1,2\}$ has an arrow pointing from it - and in $S$, every element of $B = \{3\}$ has an arrow pointing to it.

Are these bijective relations, though? Indeed not; the first is not injective. This follows as $R^T$ has the pairs $(3,1),(3,2)$ in it, but $1 \ne 2$.

Thus, you are correct -- you have found a pair of surjective relations on $A \times B$ and $B \times A$ where one is not a bijection.

---

...granted, this question is quite old, so I imagine you don't need help now. But hopefully this helps someone in the future, and, if nothing else, gets this question out of the unanswered queue.