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, , is injective given the following condition.

.

Definition: A function, , has a left inverse given the following condition.

.


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 be a function with a left inverse.

  • By definition, . Let such a function, , be defined for this section of the proof.

  • Let .

  • It is clear, from the fact that has a left inverse, that and .

  • Then is can be shown that and .

  • Since and is a function, . Had been true, would have mapped a single value to two different values, which contradicts the definition of a function.

  • It can, therefore, be concluded that given .

  • Thus, is injective.


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

  • Let be an injective function.

  • By definition, given .

  • Let .

  • Also, let there be a function, , such that .

  • Clearly the fact that is injective shows that , ensuring is a function.

  • . Since is unique to , a function, , such that can be defined.

  • It can then be shown that .

  • Therefore, .


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.

No comments:

Post a Comment