Left and Right inverse and generating space

66 Views Asked by At

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]$.

1

There are 1 best solutions below

2
On BEST ANSWER

(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$.