I was attempting this problem right now and would like to share my solution, in-order to check (your original comments from the question are in quotes):
Question:
The inverse, $\displaystyle{R^{-1}}$, of a binary relation $R$, from $A$ to $B$, is the relation from $B$ to $A$ defined by $$b\hspace{3mm}R^{-1}\hspace{3mm}a\hspace{5mm}\textrm{iff}\hspace{5mm}a\hspace{3mm}R\hspace{3mm}b.$$
Fill in the remaining entries in this table:
\begin{array}{|c|c|}
\hline
R\space is& iff\space \displaystyle{R^{-1}}\space is\\ \hline
total&a\space surjection\\ \hline
a\space function&\\ \hline
a\space surjection&\\ \hline
an\space injection&\\ \hline
a\space bijection&\\ \hline
\hline
\end{array}
I'm confused because according to the table on Wikipedia, a
surjection can also be injective, then why isn't the answer bijective
for the first one? It would still make R total.
Here, I make a distinction between a binary function and a binary relation. This question is taken from Mathematics for Computer Science text book, and there the authors are dealing with binary relation. Binary function is a special case. In internet and most other text books, the topic is a binary function.
My answers were:
\begin{array}{|c|c|}
\hline
R\space is& iff\space \displaystyle{R^{-1}}\space is\\ \hline
total&a\space surjection\\ \hline
a\space function&total\\ \hline
a\space surjection&a \space bijection\\ \hline
an\space injection&a \space bijection\\ \hline
a\space bijection& a \space bijection\\ \hline
\hline
\end{array}
Is this correct? I don't get it really because if R is surjective
(doesn't say ONLY surjective) then $\displaystyle{R^{-1}}$ must be a
bijection or surjection since at most 1 element is mapped. Someone
help me understand this because I don't get it at all. Isn't it just
the same on each side of the table? There are 2 cases where a function
is surjective and 2 cases where a function is injective so I don't get
it.
Well, my answers are follows:
\begin{array}{|c|c|}
\hline
R\space is& iff\space \displaystyle{R^{-1}}\space is\\ \hline
total&a\space surjection\\ \hline
a\space function&injection\\ \hline
a\space surjection&a \space total\\ \hline
an\space injection&a \space function\\ \hline
a\space bijection& a \space bijection\\ \hline
\hline
\end{array}
Please note that the original question came with the following hint:
Hint: Explain what’s going on in terms of “arrows” from A to B in the diagram for R.
Here are my reasonings:
- A binary relation R is a function when it has the $ [\leq 1] $ arrows out property. When we reverse the relationship, then this corresponds to a $ [\leq 1] $ arrow in property. The $=$ part of the injection definition should guarantee that this is true even when the R is a total function. On the other hand, inverse relation can't be a surjection because that would break the function part of R.
- A binary relation R is a surjection when it has the $ [\geq 1] $ arrows in property. So for ${R^{-1}}\space$, there will be $ [\geq 1] $ arrows out, which makes it a total
- A binary relation R is an injection when it has the $ [\leq 1] $ arrows in property. So for ${R^{-1}}\space$, there will be $ [\leq 1] $ arrows out, which makes it a function (actually this statement is the corollary of my first bullet point)
- A binary relation R is a bijection when it has both the $ [= 1] $ arrow out and $ [= 1] $ arrow in property. So ${R^{-1}}\space$ will also be a bijection by symmetry.
