FA18:Lecture 7 jectivity

From CS2800 wiki

We define 'jectivity and related it to the existence of inverses.

Function Properties

Some functions behave more "nicely" than others. One set of properties that functions can have is their 'jectivity, which we define here. We'll see below that these properties are closely related to inverse functions.


Definition: Injective
A function [math]f : A \href{/cs2800/wiki/index.php/%5Cto}{\to} B [/math] is injective if, for all [math]x_1 [/math] and [math]x_2 \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math], whenever [math]f(x_1) = f(x_2) [/math], we have [math]x_1 = x_2 [/math].
one-to-one is a synonym for injective.

A good way of thinking about injectivity is that the domain is "injected" into the codomain without being "compressed". In other words, no two (different) inputs go to the same output.

The following function is not injective:


because [math]f(b) [/math] and [math]f(c) [/math] are both 2 (but [math]b \neq c [/math]).


Definition: Surjective
A function [math]f : A \href{/cs2800/wiki/index.php/%5Cto}{\to} B [/math] is surjective if for every output [math]y \href{/cs2800/wiki/index.php/%5Cin}{\in} B [/math], there exists an input [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math] such that [math]f(x)=y [/math].
Onto is a synonym for surjective.

In short, every element of the codomain gets "hit". (Mnemonic device: the prefix sur- means "over" or "above", as in "surcharge" or "surname", etc. So each element of the codomain has at least one preimage (and maybe more)).

The following function is not surjective:


because there is no [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} \href{/cs2800/wiki/index.php/Enumerated_set}{\{a,b\}} [/math] with [math]f(x) = 3 [/math].


A bijection (or bijective function) gives a way of matching every element of one set to every element of another set. Formally:

Definition: Bijective
A function [math]f:A\href{/cs2800/wiki/index.php/%5Cto}{\to}B [/math] is bijective if it is both injective and surjective.

Relationship between inverses and 'jectivity

You may have noticed a pattern in the examples above. The injective functions seem to have left inverses, and the surjective functions have right inverses; two-sided inverses seem to be connected with bijectivity. Indeed, there is a connection between 'jectivity and inverses, as we will prove in the next lecture:

We did part of the proof of the first part of the first claim. You can see the first part of all three claims by clicking on them; the second parts are left as an exercise.

example: file formats

Suppose you are writing a program to convert data from one file format to another (or a function to convert one data structure to another). Such a program describes a function [math]f : A \href{/cs2800/wiki/index.php/%5Cto}{\to} B [/math]. You can think of [math]A [/math] as describing the original file format, and [math]B [/math] as describing the new file format.

It is sensible to check that [math]f [/math] is a bijection. The reason a bijection is desirable is because it has a two-sided inverse [math]g [/math] which can be used to convert the file back into the original format.

If [math]f [/math] is not injective, then it is "lossy": some information about the original file is lost.

If [math]f [/math] is not surjective, then the resulting file format has more data than the original. Further edits to the data in the [math]B [/math] format (in other words, functions from [math]B [/math] to [math]B [/math]) may prevent the object from being mapped back to the original file format.

example: user operations

Many user interfaces can be thought of as a collection of functions that transform a document into another document. For example, let [math]A [/math] be the set of all plain text files. Pressing the 'x' key in a text editor causes an 'x' to be inserted; you can think of this as applying a function [math]f : A \href{/cs2800/wiki/index.php/%5Cto}{\to} A [/math] that takes the document without the 'x' and outputs the document with the 'x'.

If you want to provide an undo/redo capability, then the functions should be bijections. If they are, then their two-sided inverses give the undo operations.

Sometimes you can make a function into a bijection by adding an "undo log": by expanding the set [math]A [/math] you can keep enough history to implement an undo function.

example: solvable equations

One way of understanding surjections and right inverses is as the existence of a solution to an equation. For example, the function [math]f : \href{/cs2800/wiki/index.php?title=%E2%84%9D&action=edit&redlink=1}{ℝ} \href{/cs2800/wiki/index.php/%E2%86%92}{→} \href{/cs2800/wiki/index.php?title=%E2%84%9D&action=edit&redlink=1}{ℝ} [/math] given by [math]f(x) := sin(x) [/math] is not surjective. This is reflected in the fact that you cannot solve the equation [math]f(x) = y [/math] for an arbitrary [math]y [/math]; indeed, there is no [math]x [/math] with [math]f(x) = 7 [/math].

If we restrict the codomain of [math]f [/math] so that the function becomes surjective (i.e. let [math]g : \href{/cs2800/wiki/index.php?title=%E2%84%9D&action=edit&redlink=1}{ℝ} → \lt nowiki\gt [-1,1]\lt /nowiki\gt be given by \lt math\gt g(x) := sin(x) [/math]), then there is a right inverse (namely the [math]arcsin [/math] function).