0
$\begingroup$

I am having a really hard time with the following table because can't there be several answers? It's not making sense to me since there can be 2 situations where it can be injective or surjective. Here is the 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.

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.

$\endgroup$
6
  • $\begingroup$ Iff means the implication goes both ways. Can you think of a total relation whose inverse is not bijective? Likewise for a surjective and injective relation. $\endgroup$ Aug 31, 2017 at 22:04
  • $\begingroup$ Then can't I just write the same word on both sides of the table? $\endgroup$
    – Hedylove
    Aug 31, 2017 at 22:08
  • 1
    $\begingroup$ @JozemiteApps You've asserted that $R$ is an injection iff $R^{-1}$ is a bijection, and also that $R^{-1}$ is a bijection iff $R$ is a bijection; so your assertions imply that "injection" is equivalent to "bijection". That's not true: consider the function $\exp$, which is injective but not bijective as a function $\mathbb{R} \to \mathbb{R}$. $\endgroup$ Sep 1, 2017 at 7:41
  • $\begingroup$ @PatrickStevens a bijection is an injection and surjection, that's why I put bijection for both. The table doesn't say surjection only or injection only. $\endgroup$
    – Hedylove
    Sep 1, 2017 at 23:23
  • $\begingroup$ Replace "total", "a function", "a surjection", "an injection" and "a bijection" with "bigger than 3", "bigger than 4", "divisible by 7", "prime" and "equal to 7" respectively, and replace $R^{1}$ by $R$. What does the question now read? How does your answer differ? (Hint: you've just asserted that all primes are equal to $7$.) $\endgroup$ Sep 2, 2017 at 6:09

1 Answer 1

1
$\begingroup$

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.
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .