Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

** proof under construction - will post when done and more or less confident it's true.

** also please easy with the downgrades.. i don't understand why i'm getting them.


what is meant by show that?

am i supposed to give an example? sure g(y) can be y/2 if f is x*2. am i supposed to give a proof ? (we are learning the axioms and the lemmas.) in which case sure, again, given the sets A, B, X, Y and g: Y -> X, and f an injective function defined f: A->B with A a subset of X and B a subset of Y. we know that f will map only specific values of X to specific values of Y, i then define f(x) = x*2 and g(y) = y/2 thus g o f = idX is valid.

(i am not sure if this counts as a correct proof, but i am trying)

I can explain it verbally. I understand the concept. but i have NO idea what the question wants from me. "show that" is too vague.

share|improve this question
2  
It means "Prove that a function $f: X \to Y$ is injective if and only if there exists a $g: Y \to X$ such that $g \circ f = \mbox{id}_X$". Usually "Show that" means "Prove that". –  wj32 Nov 8 '12 at 5:24
    
oh thank you. i needed confirmation i can now proceed with a clear conscience. –  Shokodemon Nov 8 '12 at 5:34
    
When you finish your proof, you should post it here as an answer and accept it (if it's correct). –  wj32 Nov 8 '12 at 5:34
    
definitely will. –  Shokodemon Nov 8 '12 at 5:54
1  
The statement is wrong if $X$ is empty and $Y$ nonempty. –  Michael Greinecker Nov 18 '12 at 11:35

4 Answers 4

up vote 4 down vote accepted
+100

$\newcommand{\Ident}{\operatorname{id}}$For posterity, trying to make this as conceptual and human-friendly as possible (at some expense of brevity).

Let $X$ and $Y$ be non-empty sets and let $f:X \to Y$ be a mapping.

If $x_{1}$ and $x_{2}$ are distinct elements of $X$, let's say ``$f$ identifies $x_{1}$ and $x_{2}$'' if $f(x_{1}) = f(x_{2})$. By definition, $f$ is injective if $f$ does not identify any pair of (distinct) points.

Further, say the effect of $f$ on $X$ can be undone if there exists a mapping $g:Y \to X$ such that $g \circ f = \Ident_{X}$, i.e., $(g \circ f)(x) = x$ for all $x$ in $X$. (Such a $g$ is called a left inverse of $f$.)

To say a function does not identify any pair of points is to say ``$f$ loses no information'', in the sense that an input of $f$ can be recovered uniquely from the corresponding output: If $f(x_{1}) = y = f(x_{2})$, then $x_{1} = x_{2}$.

In this terminology, the goal is to prove that the effect of $f$ on $X$ can be undone if and only if $f$ does not identify any pair of points.

Note that:

  1. If $f$ identifies $x_{1}$ and $x_{2}$, and if $g:Y \to Z$ is an arbitrary mapping, then $g \circ f:X \to Z$ also identifies $x_{1}$ and $x_{2}$. That is, if $f$ is not injective, then for every map $g$ with domain $Y$, $g \circ f$ is not injective. Contrapositively, if $g \circ f$ is injective, then $f$ is injective.

  2. If $f$ is injective and if $y$ is an element of $Y$, then $y = f(x)$ for at most one $x$ in $X$.


(Left-invertible implies injective) If there exists a map $g:Y \to X$ such that $g \circ f = \Ident_{X}$, then $f$ is injective by Observation 1 (since $\Ident_{X}$ is obviously injective).

(Injective implies left-invertible) Suppose $f$ does not identify any pair of points. Fix an element $x_{0}$ of $X$ arbitrarily, and define a mapping $g:Y \to X$ as follows:

  • If $y$ is in the image of $f$, i.e., if $y = f(x)$ for some $x$ in $X$ (hence for exactly one $x$ by Observation 2), define $g(y) = x$.

  • If $y$ is not in the image of $f$, then define $g(y) = x_{0}$.

Clearly $(g \circ f)(x) = x$ for all $x$ in $X$, i.e., $g \circ f = \Ident_{X}$.

share|improve this answer
    
well done, appreciate the effort that went into this explanation the most. –  grayQuant Jan 31 at 5:33
    
thanks for the submission, greatly appreciated. i'm reading through it right now. what do you mean by it's injective if it does NOT identify two distinct points? do you mean it's injective if it does not identify two distinct points as the same ? - double checking my understanding –  Shokodemon Jan 31 at 21:34
    
@Shokodemon: The definition is tucked in toward the top of the post. :) As used here, "$f$ identifies distinct points $x_1$ and $x_2$" if $f(x_1) = f(x_2)$. If you think of a mapping $f$ as "labeling" each input $x$ with the value $y = f(x)$, then two inputs $x_1 \neq x_2$ are "identified" (i.e., "made identical") precisely when their "labels" do not distinguish them. –  Andrew D. Hwang Jan 31 at 23:56

Premiss: For $f: X \rightarrow Y$ $\wedge$ X,Y non-empty
Proposition: $f$ is injective $\iff$ there is a $f: Y \rightarrow X$ with $g \circ f:$$id_{x}$
Proof: {a direct proof}

In two parts; we show

a) $\Leftarrow$: for $f(x_{1}) = f(x_{2})$, f is injective,
b) $\Rightarrow$: it follows then with a) that an $f: Y \rightarrow X$ with $g \circ f:$$id_{x}$ exists.

  1. Then for a):

    Assume $f(x_{1}) = f(x_{2})$.
    Then $x_{1}$ $=$ $id_{x_{1}}$ $=$ $g \circ f(x_{1})$ $=$ $g \circ (x_{2})$ $= id_{x_{2}} = x_{2}$.

  2. for b):

    Assume $g: Y \rightarrow X$
    Then by the definition of a relation: $y_{1}\in$$f(X)$ $\wedge$ $y_{2}$$\in$[Y$\diagdown$$f(X)]$ And by definition of $g$ alongside $f$'s injectivity we have $g(y_{1}) = f^{-1}(y_{1}) = x_{1}$ $\Rightarrow$ $g \circ f=$$id_{x}$

QED $\boxdot$

share|improve this answer

First of all, notice that the statement is false.

Suppose $Y\neq\emptyset$; then the unique map $f\colon \emptyset\to Y$ is obviously injective, but there's no map $g\colon Y\to\emptyset$, in particular no left inverse for $f$.

Let $f\colon X\to Y$ be a mapping with $X\ne\emptyset$. Then $f$ is injective if and only if there exists $g\colon Y\to X$ such that $g\circ f=\mathit{id}_X$.

Proof. ($\Leftarrow$) Suppose $g\circ f=id_X$. If $x_1,x_2\in X$ and $f(x_1)=f(x_2)$, then $g(f(x_1))=g(f(x_2))$ In other words $$ x_1=\mathit{id}_X(x_1)=g\circ f(x_1)=g(f(x_1))=g(f(x_2))=g\circ f(x_2)=\mathit{id}_X(x_2)=x_2 $$

More generally, if the composition $g\circ f$ is injective, then $f$ is injective.

($\Rightarrow$) Consider the set $I=\{f(x):x\in X\}$ (the image of $f$). Fix $x_0\in X$ (which is possible because $X\ne\emptyset$). Consider $$ g=\{(y,x):(x,y)\in f\}\cup\{(y,x_0):y\in Y\setminus I\} $$ Then $g$ is a mapping $g\colon Y\to X$.

Indeed, for every $y\in Y$ there exists $x\in X$ such that $(y,x)\in g$: if $y\in I$, then $y=f(x)$ for some $x\in X$, so by definition $(x,y)\in f$ and so $(y,x)\in g$; if $y\in Y\setminus I$, then $(y,x_0)\in g$.

Suppose now $(y,x_1)\in g$ and $(y,x_2)\in g$. If $y\in Y\setminus I$, then $x_1=x_0=x_2$. If $y\in I$, then $(x_1,y)\in f$ and $(x_2,y)\in f$, which amounts to saying that $y=f(x_1)$ and $y=f(x_2)$; since $f$ is injective, we have $x_1=x_2$.

Final claim: $g\circ f=\mathit{id}_X$. Indeed, if $x\in X$, we have $(x,f(x))\in f$, so $(f(x),y)\in g$, which means $g(f(x))=x$, by definition.

QED

share|improve this answer

Claim: Let $X$ and $Y$ be nonempty sets, then $f : X \to Y$ is injective if and only if there exists $g : Y \to X$ such that $g \circ f = \text{id}_X$.

Proof: Suppose $f : X \to Y$ is injective, then by definition $f(x) = f(y)$ implies $x = y$ which means that if $y \in \operatorname{im}(f)$, then there exists a unique $x \in X$ such that $f(x) = y$. Define $g : Y \to X$ as follows: Fix $x \in X$ and define $$g(y) = \begin{cases} f^{-1}(y) & \text{if } y \in \operatorname{im}(f), \\ x & \text{if } y \notin \operatorname{im}(f). \end{cases}$$

Observe that $g \circ f(x) = g \big( f(x) \big) = f^{-1}\big( f(x) \big) = x = \operatorname{id}_X(x)$ by injectivity of $f$ and construction of $g$.

Conversely, suppose that there exists $g : Y \to X$ such that $g \circ f = \operatorname{id}_X$. Suppose $f(x) = f(y)$, then by hypothesis, we have $x = \operatorname{id}_X(x) = g \circ f(x) = g \circ f(y) = \operatorname{id}_X(y) = y$. Conclude by definition that $f$ is injective.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.