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.

  • 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
    @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