1
$\begingroup$

We are given the relation $R$ between $\mathbb{N}$ and $\mathbb{N}$: $$ R\colon \mathbb{N}\rightarrow \mathbb{N}\colon n \mapsto n^3- 3n^2 - n $$ and we are asked: is $R$ a map, bijection, injection or surjection?

First of all, it is clear that not every natural number $n$ has a corresponding mapping, e.g. 1 would map to -3, which is $\notin \mathbb{N}$, similarly for 2 (which would map to -6) and 3 (would map to -2). In conclusion: not every element in the source set $\mathbb{N}$ has an associated target element, and also not every element in the target set $\mathbb{N}$ has an associated source element.

This rules out bijection and surjection. It should be an injection, since every target element has a unique source element. My colleague thinks that $R$ is both a map and an injection, since "all injections are maps". However, I believe that $R$ is not a map, since not every element in the source set has a target element. Various sources on the internet (and books) seem to define maps and injections as being restricted to the domain of $R$, in which case my colleague is correct that injections are maps.

We are stuck. Which one of us is right?

EDIT We are following the (non-standard?) definitions from a course on Discrete Mathematics, which are as follows:

  • A relation between two sets is called a mapping if from every element there departs exactly one arrow.
  • A relation is called an injection if from every element at most one arrow departs and in every element at most one arrow arrives.
$\endgroup$
  • $\begingroup$ Colleague is right that all injections are maps, but this is not an injection, precisely because it is not a map. (Unless you have a non-standard definition of injective relation.) $\endgroup$ – Thomas Andrews Sep 16 at 15:41
  • $\begingroup$ OK, so, these are the definitions from the course on Discrete Mathematics at Ghent University (Belgium): "A relation between two sets is called a mapping if from every element there departs exactly one arrow." "A relation is called an injection if from every element at most one arrow departs and in every element at most one arrow arrives." So these are maybe non-standard definitions? $\endgroup$ – CedricDeBoom Sep 16 at 15:48
  • $\begingroup$ How do you define "arrow arrives/departes"? I take it that "$\dots$there departs exactly one arrow" means that for a relation $R$ on $A\times B$ we take any $a\in A$ then there exists exactly one $b\in B$ such that $(a,b)\in R$, correct? $\endgroup$ – André Armatowski Sep 16 at 16:09
  • $\begingroup$ With these definitions in mind, the relation $R$ is not a map, but is an injection. There are no arrows departing $1$, $2$ and $3$, hence it is not a map. More than one arrow arrive only into $-3$, but $-3\notin\mathbb N$. Your colleague is incorrect in stating that all injections are maps. For example, an empty relation (such that no arrows depart or arrive) is an injection according to your definition, but not a map. $\endgroup$ – Randy Marsh Sep 16 at 16:42
  • $\begingroup$ @AndréArmatowski Yes indeed! $\endgroup$ – CedricDeBoom Sep 17 at 6:03
1
$\begingroup$

A (binary) relation between sets $X$ and $Y$ is nothing else than a subset of the Cartesian product $X × Y$. In your question we have $R \subset \mathbb N \times \mathbb N$. In my opinion it is misleading to write it the form $n \mapsto n^3- 3n^2 - n $, I would prefer to write $$R = \{ (n,m) \in \mathbb N \times \mathbb N \mid m = n^3- 3n^2 - n \} .$$

I recommend to have a look at https://en.wikipedia.org/wiki/Binary_relation.

  1. $R$ is not a function $\mathbb N \to \mathbb N$. As you have shown, for $n = 1, 2,3$ we do not have $m \in \mathbb N$ such that $(n,m) \in R$. However, we may regard it is as a partial function which means that for each $n \in \mathbb N$ we have at most one $m \in \mathbb N$ such that $(n,m) \in R$. The restriction $\mathbb N \setminus \{1, 2, 3\} \to \mathbb N$ is a function.

  2. $R$ is an injective relation. This means that if $(n, m) \in R$ and $(n', m) \in R$, then $n = n'$. In fact, consider the function $\phi : \mathbb R \to \mathbb R,\phi(x ) = x^3 -3x^2-x$. Its derivative $\phi'(x) = 3x^2 - 6x -1$ is positive for $x > \xi = 1 + \sqrt{4/3}$, thus $\phi$ is strictly increasing on $(\xi,\infty)$. Since $ 4 > \xi$, we get injectivity.

  3. $R$ is not a surjective relation which means that there exists $m \in \mathbb N$ such for all $n \in \mathbb N$ we have $(n,m) \notin R$. In fact, we have $\phi(4)= 12, \phi(5) = 45$. Since $\phi$ is strictly increasing on $(\xi,\infty)$, we may take $m = 13$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Yes, I totally follow your line of reasoning here, and I agree with your suggestion to rewrite the relation as a subset of the cartesian product. Thanks! $\endgroup$ – CedricDeBoom Sep 17 at 6:01
0
$\begingroup$

I would say it is a (not well-defined) map from $\mathbb{N}$ to $\mathbb{N}$ (since it takes inputs from $\mathbb{N}$ and outputs into the target space $\mathbb{N}$). It is not an injection since it is not even well-defined.

But it is a well-defined map from $\mathbb{N}\setminus\{1,2,3\}$ to $\mathbb{N}$, in fact it is an injection

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So, you would restrict $R$ to its domain in order to say something about its nature? $\endgroup$ – CedricDeBoom Sep 16 at 16:03
0
$\begingroup$

In the definition you give at the end of your post we have that every injective function is a injective relation but every injective relation is not a injective function (injective function here means a relation which is a function and a injective relation).

For example, let $A=\{a,b,c\}$, $B=\{b,c\}$ and $R=\{(b,b),(c,c)\}\subset A\times B$ then $R$ is not a function from $A$ to $B$ as there is no arrow departing from $a$ (the requirement of your definition of mapping would be that there is an arrow departing from $a$).

On the other hand, from every element of $A$ there is at most one arrow departing (The wording "at-most" suggests that no arrow departing is allowed) and also at most one arrow arrives to each element of $B$ making $R$ an injective relation.

Summary: Injections (in terms of relations) are not always mappings.

| cite | improve this answer | |
$\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.