0
$\begingroup$

Let X be a nonempty space, then if the map $f:X\rightarrow X$ is injective then there is $g:X \rightarrow X$ such that $g\circ f=Id_{X}$ and we say $g$ is left inverse and consider $Le(f)$ the set of left inverse of $f$. Also if the map $f:X\rightarrow X$ is surjective then there is $h:X \rightarrow X$ such that $f\circ h=Id_{X}$ and we say $h$ is right inverse and consider $Ri(f)$ the set of all right inverse of $f$. Note that if $f$ is injective map then any map in $Le(f)$ will be surjective and also if $f$ is surjective map then any map in $Ri(f)$ will be injective.

If we have injective map $f:X\rightarrow X$ then we have $Le(f)$ then we can consider $Ri(Le(f))$ where it is union $Ri(g)$ in which $g \in Le(f)$. Also we can consider $Le(Ri(Le(f)))$ and so on. My question is that it is possible in finite step of this process we obtain all surjective or all injective maps on $X$ to itself?

Remark: For case $X$ is finite, injectivity and surjectivity is equlivalent, so consider infinite case, namely $X=[0,1]$.

$\endgroup$
3
  • $\begingroup$ You do know what a generating function is? If yes, why did you use that tag? If not, why did you use that tag? $\endgroup$
    – jjagmath
    May 14, 2023 at 0:45
  • $\begingroup$ @jjagmath if you see my question you will find some things, that is: question is idea oriented not subject oriented, and all subjects are born of ideas، and don't try to define cognitive ideas with the subject, you must be classify subjects by congitive idea, and so be calm and know that cognitive ideas belong everywhere, so I can tag any subject. $\endgroup$
    – Deliasaghi
    May 14, 2023 at 10:06
  • 1
    $\begingroup$ Tags are for people in this forum to be able to search for questions related for an specific subject, not just a decoration you may add to your question. $\endgroup$
    – jjagmath
    May 14, 2023 at 12:56

1 Answer 1

2
$\begingroup$

(Rewritten for general answer)

In the infinite case, you will never get all surjections or all injections, even setting aside that you will not get a bijection (which is a surjection and a bijection) if you don't start with a bijection.

We begin with a straighforward observation:

Lemma. Let $X$ and $Y$ be nonempty sets, and let $g\colon X\to Y$ be a surjection. If $f_1$ and $f_2$ are two right inverses of $g$, then $|X\setminus f_1(Y)|=|X\setminus f_2(Y)|$.

Proof. For each $y\in Y$, we know that $f_i(y)\in g^{-1}(\{y\})$. In addition, the sets $g^{-1}(\{y\})$ partition $X$, as $y$ ranges over $Y$. Now notice that for each $y\in Y$, we have that $g^{-1}(\{y\})\setminus\{f_1(y)\}$ is bijectable with $g^{-1}(\{y\})\setminus\{f_2(y)\}$, since we are simply removing one element in both cases. So $$\begin{align*} |X\setminus f_1(Y)| &= \left| \bigcup_{y\in Y}(g^{-1}(y)\setminus \{f_1(y)\})\right| \\ &= \sum_{y\in Y}|g^{-1}(y)\setminus\{f_1(y)\}| \\ &= \sum_{y\in Y} |g^{-1}(y)\setminus \{f_2(y)\}| \\ &= \left|\bigcup_{y\in Y}(g^{-1}(y)\setminus \{f_2(y)\})\right|\\ &= |X\setminus f_2(Y)|. \end{align*}$$ This proves the theorem. $\Box$

The following now follows:

Theorem. Let $X$ be an infinite set. If $f\colon X\to X$ is an injection, then the sets $$\mathrm{Le}(f), \mathrm{Ri}(\mathrm{Le}(f)), \mathrm{Le}(\mathrm{Ri}(\mathrm{Le}(f))),\ldots$$ do not contain all injections, all surjections, all nonbijective injections, all nonbijective surjections, nor all bijections. Likewise, if $g\colon X\to X$ is a surjection, then the sets $$\mathrm{Ri}(g), \mathrm{Le}(\mathrm{Ri}(g)), \mathrm{Ri}(\mathrm{Le}(\mathrm{Ri}(g))),\ldots$$ do not contain all injections, all surjections, all nonbijective injections, all nonbijective surjections, nor all bijections (even if we take the process transfinitely).

Proof. Since bijections have unique left and right inverses, if $f$ is a bijection, then the sets only contain $f$ and $f^{-1}$. In any case, the sets cannot contain more than two bijections, and if they contain a bijection they contain only that bijection and its inverse. So we may assume that $f$ is injective but not surjective. The elements of $\mathrm{Le}(f)$ must all agree on $f(X)$, so they are not all surjections. Moreover, since $f$ is a right inverse of each $g\in\mathrm{Le}(f)$, by the Lemma every $h\in\mathrm{Ri}(\mathrm{Le}(\mathrm{Ri}(f)))$ satisfies $|X\setminus h(X)|=|X\setminus f(X)|$. Thus, every injection in each of those sets will the complement of its image of the same cardinality as $f$. As there are injections that have images with complements of different cardinality (all cardinalities up to $|X|$, in fact), we will not obtain all possible nonbijective injections, even if we take this process transfinitely.

Since we cannot obtain all possible nonbijective injections, we also cannot obtain all possible nonbijective surjections either. $\Box$

The same argument works for any function between infinite sets $X$ and $Y$, whether they have the same cardinality or not.

If $X$ and $Y$ are finite, and $f\colon X\to Y$ is injective, then we have two cases:

  1. If $f$ is bijective, then the process will yield only $f$ and $f^{-1}$.

  2. If $f$ is not bijective, then the process will yield all injections from $X$ to $Y$ and all surjections from $Y$ to $X$.

To see 2, let us for simplicity assume that $X=\{a_1,\ldots,a_n\}$ and $Y=\{b_1,\ldots,b_{n+r}\}$, and $f(a_i)=b_i$. We show that $\mathrm{Ri}(\mathrm{Le}(f))$ contains an injection $h$ that agrees with $X$ on all $a_r$ except a particular $a_i$, and with $h(a_i)\in Y\setminus f(X)$. This will suffice, by repeating the construction until we obtain the injection we want.

Indeed, let $g\colon Y\to X$ be given by $$g(b_j) =\left\{\begin{array}{ll} a_j &\text{if }1\leq j\leq n,\\ a_i &\text{if }n+1\leq j\leq n+r. \end{array}\right.$$ Then define $h\colon X\to Y$ by $$h(a_j)=\left\{\begin{array}{ll} b_j &\text{if }j\neq i\\ b_{n+1}&\text{if }j=i. \end{array}\right.$$

Since we can obtain any injection, we can also obtain any surjection $Y\to X$ through this process. Symmetrically, if we start with a surjection between finite sets, $g\colon X\to Y$, if it is bijective the process will yield only $g$ and $g^{-1}$; if it is not bijective the process will yield all injections $Y\to X$ and all surjections $X\to Y$.

$\endgroup$
2
  • $\begingroup$ Thanks. Can you predict the possibility of the existence of a function where the statement is true?! $\endgroup$
    – Deliasaghi
    May 9, 2023 at 13:48
  • $\begingroup$ @Deliasaghi It is never true (even if you exclude bijections). I'll post a proof later, but if $f_1$ and $f_2$ are both right inverses of a surjection $g$, then $|X\setminus f_1(X)|=|X\setminus f_2(X)|$. That you never get all injections (and hence never get all surjections) follows. $\endgroup$ May 13, 2023 at 3:51

You must log in to answer this question.

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