Mathemedumacation: July 2011

Sunday, July 17, 2011

[JFF] Injective Functions and Left Inverses

Just For Fun

Postulate: A function is injective if and only if it has a left inverse.

Definition: A function, $f:A\rightarrow B$ , is injective given the following condition.: $\texttt{Given }a_1,a_2\in A\texttt{ where }a_1\neq a_2, f(a_1)\neq f(a_2)$ .
Definition: A function, $f:A\rightarrow B$ , has a left inverse given the following condition.: $\exists g:B\rightarrow A\texttt{ s.t. }\forall a\in A, (g\circ f)(a)=a$ .

In order to prove the postulate above, it will suffice to show that both of the following conditions are true.

A function is injective if it has a left inverse.

A function has a left inverse if it is injective.

I will begin by showing that a function is injective if it has a left inverse.

Let $f:A\rightarrow B$ be a function with a left inverse.

By definition, $\exists g:B\rightarrow A\texttt{ s.t. }\forall a\in A, (g\circ f)(a)=a$ . Let such a function, $g$ , be defined for this section of the proof.

Let $a_1,a_2\in A, b_1,b_2\in B, a_1\neq a_2,f(a_1)=b_1,f(a_2)=b_2$ .

It is clear, from the fact that $f$ has a left inverse, that $(g\circ f)(a_1)=a_1$ and $(g\circ f)(a_2)=a_2$ .

Then is can be shown that $(g\circ f)(a_1)=g(f(a_1))=g(b_1)=a_1$ and $(g\circ f)(a_2)=g(f(a_2))=g(b_2)=a_2$ .

Since $a_1\neq a_2$ and $g$ is a function, $b_1\neq b_2$ . Had $b_1=b_2$ been true, $g$ would have mapped a single value to two different values, which contradicts the definition of a function.

It can, therefore, be concluded that given $a_1,a_2\in A\texttt{ where }a_1\neq a_2, f(a_1)\neq f(a_2)$ .

Thus, $f$ is injective.

Now, I will show that an injective function must have a left inverse.

Let $f:A\rightarrow B$ be an injective function.

By definition, given $a_1,a_2\in A\texttt{ where }a_1\neq a_2, f(a_1)\neq f(a_2)$ .

Let $a_1,a_2\in A,b_1,b_2\in B\texttt{ s.t. }a_1\neq a_2\texttt{ and }f(a_1)=b_1\textt{,}f(a_2)=b_2$ .

Also, let there be a function, $g:B\rightarrow A$ , such that $g(b_1)=a_1\texttt{ and }g(b_2)=a_2$ .

Clearly the fact that $f$ is injective shows that $b_1\neq b_2$ , ensuring $g$ is a function.

$\forall a_i\in A, \exists b_i\texttt{ s.t. }f(a_i)=b_i$ . Since $b_i$ is unique to $a_i$ , a function, $g$ , such that $g(b_i)=a_i$ can be defined.

It can then be shown that $g(b_i)=g(f(a_i))=(g\circ f)(a_i)=a_i$ .

Therefore, $\exists g:B\rightarrow A\texttt{ s.t. }\forall a\in A, (g\circ f)(a)=a$ .

I admit that the second part of this proof could use some refinement. Any ideas are welcome.
Since both conditions have been proven, the postulate is thus proven.

Subscribe to: Posts (Atom)