3
$\begingroup$

The question I have asks to show that if a function $f: A \rightarrow A$ is one-to-one but not onto, it has at least two left inverses. I've worked out what I consider to be a solution, but what I found differs slightly from what the question is asking.

First note that since the function maps $A$ to itself and it is one-to-one but not onto, one can assume that A is not a finite set. Next, let $i,j \in \mathbb{N}$ and let $x_i \in A$ be a fixed element in A such that if $i \neq j$ then $x_i \neq x_j$. Now, let $n \in \mathbb{N}$ and define $g_n: A \rightarrow A$ as follows:

  1. Let $a,b \in A$. If $f(a)=b$ then let $g_n(b)=a$. Note that this is well defined since $f$ is one-to-one.
  2. If for $b \in A$, $\nexists a \in A$ such that $f(a)=b$, let $g_n(b)=x_n$

This function is a valid left inverse $\forall n \in \mathbb{N}$ since if $f(a)=b$, we have that $g_n(f(a))=g_n(b)=a$.

Since $f$ is onto, there must be at least one $b$ that satisfies the second rule. Also, since $A$ must be an infinite set, $x_n$ must be defined $\forall n \in \mathbb{N}$. This means that $g_n$ must also be defined $\forall n \in \mathbb{N}$, so there is an infinite number of left inverses.

I understand that an infinite number of inverses is still technically at least two inverses, but this wording has led me to think I've gotten something wrong here, and if there are any mistakes in my argument it would be fantastic if someone could point them out.

Thanks.

EDIT

This is what I handed in, of which I got full marks:

Let $A$ be a set such that $A \neq \emptyset$ and let $f \in F_A$ be a function, that is $f: A \rightarrow A$. Suppose $f$ is injective but not surjective. Note that this means that $A$ must be infinite set. Next, let $i,j \in \mathbb{N}$ and let $x_i \in A$ be a fixed element in A such that if $i \neq j$ then $x_i \neq x_j$. Now, let $n \in \mathbb{N}$ and define the family of functions $g_n: A \rightarrow A$ as follows:

  1. If for $b \in A$, $\exists a \in A$ such that $f(a)=b$ then let $g_n(b)=a$. Note that this is well defined since $f$ is injective, so $a$ will always be unique.
  2. If for $b \in A$, $\nexists a \in A$ such that $f(a)=b$, then let $g_n(b)=x_n$.

Now, let $a,b \in A$ such that $f(a)=b$. By rule i. for $g_n$, we have that $g_n(b)=a$, so $g_n \circ f(a)=g(f(a))=g(b)=a=\iota (a)$. Since $g_n \circ f=\iota$, $g_n$ is a left inverse of $f$, regardless of the value of $n$ since we did not use rule ii. of the definition of $g_n$.

As we noted before, $A$ must be an infinite set, so $x_n$ must be defined $\forall n \in \mathbb{N}$, hence $g_n$ must also be defined $\forall n \in \mathbb{N}$.

Lastly, we will show that no two left inverses by this definition can be equal, because if $g_1=g_2=g_3=\ldots$ then there would only be one left inverse.. Let $i,j \in \mathbb{N}$ such that $i \neq j$ and let $b \in A$ such that $\nexists a \in A$ where $f(a)=b$, which is possible since $f$ is not surjective. By rule ii. for $g_n$, $g_i(b)=x_i$ and $g_j(b)=x_j$. Since $i \neq j$, then $x_i \neq x_j$, hence $g_i \neq g_j$. $\therefore$ Since $f$ has an infinite number of left inverses in $F_A$, $f$ has at least two different left inverses $F_A$.

$\endgroup$

2 Answers 2

1
$\begingroup$

Example. Let $A=[0,1]$. Define $f:A\rightarrow A$ by $f(x)=x/2$. (So, $f$ is one-to-one but not onto.)

Let $k$ be any element in $A$.

Define $g_k:A\rightarrow A$ by $g_k(y)=2y$ for each $y\in \text{Range} \, f = [0,0.5]$ and $g_k(x)=k$ for each $x\notin \text{Range} \, f$.

Then $g_k$ is a left inverse of $f$. And there are infinitely many such functions $g_k$.


More generally, let $f:A\rightarrow A$ be any one-to-one function that isn't onto.

Let $k$ be any element in $A$.

For each $a\in \text{Range} \, f$, pick the unique $b \in A$ such that $f(b)=a$.

Define $g_k:A\rightarrow A$ by $g_k(a)=b$ for each $a\in \text{Range} \, f$ and $g_k(x)=k$ for each $x \notin \text{Range} \, f$.

Then $g_k$ is a left inverse of $f$. And there are infinitely many such functions $g_k$.


Definitions used:

Definition 1. Suppose $S$ is a set. Then the identity function on $S$ is the function $I_S: S \rightarrow S$ defined by $I_S(x)=x$.

Definition 2. Suppose $f:A\rightarrow B$ is a function. Then $g$ is a left inverse for $f$ if $g \circ f=I_A$; and $h$ is a right inverse for $f$ if $f\circ h=I_B$.

$\endgroup$
0
$\begingroup$

Consider the following function of Natural Numbers:

If n is 0, return 0. If n is more than 0, return n+1

This function is one-to-one, but not onto. What are its left-inverses?

$\endgroup$
1
  • $\begingroup$ This function would have an infinite number of left inverses using the rules I defined above. Correct me if I'm wrong but I don't see how this addresses the question I asked. $\endgroup$
    – Dastur
    May 24, 2019 at 19:41

You must log in to answer this question.

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