0
$\begingroup$

I've been asked the question:

For a function $ f $ from X $ \to $ Y, $ f^{-1}(f(A)) = A $ for every subset A of $ X $ if and only if: (a) $ f $ is injective (b) $ f $ is surjective (c) $ f $ is bijective.

A function is invertible only if it's bijective, and so I thought that the answer would be (c). But the correct answer, apparently, is (a).

Is there anything in the question that makes it clear that what's being asked is a left inverse, in which case it's sufficient for the function to be only injective? I'm guessing it has something to do with the statement "for every subset A of X" -- am I correct, or is there something else?

Also, if you were to specify "right inverse", how would you modify the question?

$\endgroup$
  • $\begingroup$ Why did you write "apparently the answer is (a)"? if $f(x)=y\in f(A)$ such that $x\in A$, shouldn't that be enough for $f$ being bijective? The only exception would be the restriction of 1-1: Exists an $y\in f(A)$ such that $f^{-1}(y) \ne x \in A$. $\endgroup$ – Lincon Ribeiro Feb 23 at 17:37
  • 1
    $\begingroup$ @LinconRibeiro See my answer - you cannot in fact conclude bijectivity from the OP's property. $\endgroup$ – Noah Schweber Feb 23 at 17:56
3
$\begingroup$

Remember that the notation "$f^{-1}(S)$" refers to the set $$\{x\in dom(f): f(x)\in S\}.$$ No assumptions on $f$ need to be made for this to make sense. In particular, using this notation does not presuppose that $f$ has an inverse.

Similarly, "$f(S)$" refers to the set $$\{x\in codom(f): \exists s\in S(f(s)=x)\}$$ (or, perhaps more simply, $\{f(s): s\in S\}$).

Unwinding definitions a bit, the problem here is just asking about the property

$(*)\quad$ For every set $A\subseteq dom(f)$ we have $$\{x\in dom(f): f(x)=f(a)\mbox{ for some $a\in A$}\}=A.$$


Now let's see why the answer to the question is (a) - that property $(*)$ holds iff $f$ is injective.

First, let's show that injectivity of $f$ implies $(*)$. It's helpful to note that we trivially have $A\subseteq \{x\in dom(f): f(x)=f(a)\mbox{ for some $a\in A$}\}$, so to show that property $(*)$ holds we only need to pay attention to the reverse inclusion. Suppose $f$ is injective and let $A\subseteq dom(f)$ be arbitrary. Let $x\in dom(f)$ such that $f(x)=f(a)$ for some $a\in A$. Since $f$ is injective, $x$ must actually be this $a$; that is, if $f(x)=f(a)$ for some $a\in A$ then $x\in A$ already. So the left hand side set is a subset of $A$, and per the comment above we're done.

Note that this is the surprising direction - that injectivity alone guarantees a property which at first glance may seem to be bijectivity. So before going on to the next point, make sure the argument above makes sense.

Now let's show that $(*)$ implies injectivity. Suppose for every $A\subseteq dom(f)$ we have $\{x\in dom(f): f(x)=f(a)\mbox{ for some $a\in A$}\}=A$. Fix $u,v\in dom(f)$ such that $f(u)=f(v)$; we want to show $u=v$. Let $A=\{u\}$. Then $\{x\in dom(f): f(x)=f(a)\mbox{ for some $a\in A$}\}$ contains $v$, so by our assumption $v\in A$; but $A=\{u\}$, so $v=u$.

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