8
$\begingroup$

** 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.

  • 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".2012-11-08
  • 0
    oh thank you. i needed confirmation i can now proceed with a clear conscience.2012-11-08
  • 0
    When you finish your proof, you should post it here as an answer and accept it (if it's correct).2012-11-08
  • 0
    definitely will.2012-11-08
  • 0
    Whatever happens, please do not deface your question by effectively erasing its text. Rolled back to previous version.2012-11-08
  • 0
    please bear with me I plan to post a beautified version + proof once I figure it out and run it past my tutor!2012-11-08
  • 0
    by the way, do i then create two other questions for the complete version of this question? am i not supposed to modify this question to include all three equivalence proofs? i've got one for surjectivity and another for bijectivity as b) and c) parts.2012-11-08
  • 0
    [Injection iff Left Invers](http://www.proofwiki.org/wiki/Injection_iff_Left_Inverse) at ProofWiki2012-11-08
  • 0
    @Shokodemon: if you have an answer/proof to the question alluded to in the title, post them as answers. You can do so if you scroll down an click on the "Answer your own question" link.2012-11-08
  • 1
    The statement is wrong if $X$ is empty and $Y$ nonempty.2012-11-18
  • 0
    i assume X,Y are not empty. is it enough to say they're not empty? also, i have posted what i think is a complete proof. is it ? did i miss something? i showed it for y1, need ishow this for y2? though the set $Y_{2}$ are the $y \in Y$ that don't get an x. i will accept once you guys give me the green light, as i am not 100% sure.2012-11-21

4 Answers 4

6

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

  • 0
    well done, appreciate the effort that went into this explanation the most.2015-01-31
  • 0
    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 understanding2015-01-31
  • 0
    @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.2015-01-31
4

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.

2

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$

2

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