1
$\begingroup$

I need help for a task I am trying to solve. Let $A$ be a not empty set and $f:A\rightarrow A$ is an injective function, but not a surjective function.

Let $g: A\rightarrow A$ be a function with $g(f(x))=x\forall x\in A$. Show that $g$ is not bijective.

I believe that I already solved that one. Since $f$ is injective but not surjective, there is at least one element $y_1$ in the set of destination $A$, that is not the image of at least one element of its domain. Since the domain and the set of destination is $A$, there is also at least one element $x_1$ in the domain, that $f$ does not map to $y$. Therefore $g: A\rightarrow A$ is not surjective, since the element $x_1$ of the set of destination $A$ is not an image of the domain $A$, $g(f(x_1))$ does not exist. Since $g$ is not surjective $\Rightarrow g$ is not bijective.

Show that there is an unambiguous bijective function $h: f[A]\rightarrow A$ with $h(f(x))=x\forall x\in A$.

Well I don't have any idea how to solve this task. The domain is not $A$ but $f[A]$ now, but I don't see how this change should prevent the function from being not surjective like in the first point, since the set of destination $A$ has more elements then $f[A]$ which would cause the problem of an element left alone. Also I am not quite sure how to prove that this is the "unambiguous" function.

$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

  1. The first proof is wrong: When you say "[...] there is also at least one element $x$ in the domain that $f$ does not map to $y$", that's a repetition of the fact that $f$ is not surjective. Also, to go from there to "$g$ is not surjective" is also incorrect. First of all, because $g$ is indeed surjective ($g(f(x))=x$ for all $x\in A$ implies that every $x$ is in the image of $g$), second $g(f(x))$ does exists, independetly from hypothesis on $g,f$ or anything. What $g$ fails to be is injective: Assume $g$ is injective, then from $g(f(x))=x$ we deduce $g(f(g(x)))=g(x)$ for all $x$, so using injectivity $f(g(x))=x$ and $f$ would be invertible, contrary to not being surjective.

  2. About this, notice that if you restrict the codomain of $f$ to $f[A]$, then $f$ remains injective, but it also becames surjective, hence a bijection. Next, you need to prove that the inverse of a map is unique: Think about the condition $f(f^{-1}(x))=x$, if $f$ is injective, how many values can $f^{-1}(x)$ take so that the previous equation holds?

$\endgroup$
6
  • $\begingroup$ Thank you! The answer for task number 1 was very helpful. Unfortunately I am still a bit unsure why f(g(x))=x gives us any information about the fact that f would be invertible. 2. f^-1(x) can take one value, since f is injective. And thats probably why h(f(x)=f^-1(x)=x is unique I guess. Right? $\endgroup$
    – Analysis_Mark
    Commented Jan 24, 2022 at 22:13
  • $\begingroup$ 1) If you already know $g(f(x))=x$ and you also prove $f(g(x))=x$, then $f$ is invertible and $g=f^{-1}$. Alternatively, if you prove $f(g(x))=x$, then you conclude that $f$, which is already injective, is also surjective and so invertible. 2) Exactly, $f^{-1}(x)$ can only have one value, hence uniqueness. Otherwise, take $g,h$ inverses for $f$, then $$g(x)=h(f(g(x)))=h(x)$$where I used $h(f(y))=y$ and $f(g(x))=x$, for all $x,y$. $\endgroup$
    – Alessandro
    Commented Jan 24, 2022 at 23:13
  • $\begingroup$ Thank you. Task number 1 is fully clear. 2) I still don't understand how to fully prove that one. Should I start like in Task 1 and say h must also be injective then show that if so, h is the invertible function of f and that there is no contradiction since f is bijective. I would see that f (h(x))= x which is equivalent to f(f^-1(x))=x. Since f is injective, f^-1(x)) can only have on value for x -> is unique for all x € A. Is that correct? $\endgroup$
    – Analysis_Mark
    Commented Jan 24, 2022 at 23:57
  • $\begingroup$ The first part is superfluous since once you construct the inverse of $f$, this is automatically injective (and surjective). The second part is exact, is the usual construction of $f^{-1}$: Given $y$, there is one element $x$ (and only one) such that $f(x)=y$, then you set $f^{-1}(y)=x$, this choice is unique, hence $f^{-1}$ is also unique $\endgroup$
    – Alessandro
    Commented Jan 25, 2022 at 9:27
  • $\begingroup$ All right. Also...how do we justify that we deduce g(f(g(x)))=g(x) from g(f(x))=x. Can you elaborate on that please? $\endgroup$
    – Analysis_Mark
    Commented Jan 25, 2022 at 15:40
0
$\begingroup$

Hint: $f:A\to[A]$ is bijective, so it has an inverse function. Use $h=f^{-1}$.

$\endgroup$

You must log in to answer this question.

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