Project: More on Inverses, Composition and Relations

David M. Clark and W. Ted Mahavier

( Chapter 3: W. Ted Mahavier < E.L. May < K.M. Shannon ¹ )

If each of \(X\) and \(Y\) is a person, then the relation \(X < Y\) indicates that the notes originated with \(Y\) and were subsequently modified by \(X\text{,}\) who takes full responsibility for the current version. While \(Y\) is credited with the genesis of the notes, s/he makes no claim to the accuracy of the current version which may or may not reflect her/his original version.

Section Project: More on Inverses, Composition and Relations

Problem 2.32.

Is Problem 1.28 valid if we define \((a, b) = \{\{a, 1\}, \{2, b\}\}\text{?}\)
How would one formally define an ordered triple? An ordered quadruple?

Problem 2.33.

Show that the composition of one-to-one functions is one-to-one by letting \(g:\B \to \C\) and \(h:\A \to \B\) be one-to-one functions and showing that \(g\circ h:\A \to \C\) is one-to-one.

Problem 2.34.

Show that the composition of onto functions is onto.

The word identity is used in a number of different contexts in mathematics. The function \(f: \R \to \R\) defined by \(f(x) = x\) is called the identity function because it identifies every number with itself. Similarly, \(0\) is called an additive identity because adding \(0\) to a number does not change the number, so \(0+x\) is identified with \(x\text{.}\) By the same reasoning, \(1\) is called the multiplicative identity.

Problem 2.35.

Let \(\mathbf S\) denote the set of all bijections from \(\A\) to itself. According to Problems 2.33 and Problem 2.34, \(\circ\) is a binary operation on \(\mathbf S\text{,}\) that is, \(f\circ g \in \mathbf S\) whenever \(f\) and \(g\) are in \(\mathbf S\text{.}\) We define a special bijection \(i:\A \to \A\) called the identity function on \(\A\) as

\begin{equation*} i(x) = x \mbox{ for all } x\in \A\text{.} \end{equation*}

Show that \(i\) is an identity for \(\mathbf S\text{,}\) that is,

\(f\circ i = f = i\circ f\) and
\(\displaystyle f\circ f^{-1} = i = f^{-1}\circ f\)

for all \(f \in \mathbf S\text{.}\) This shows that \(i\) serves as an identity for composition in the same way that 0, 1, \(\emptyset\) work as identities for \(+\text{,}\) × and \(\oplus\text{,}\) respectively.

Problem 2.36.

Consider the list below of all 6 different bijections from \(\{0,1,2\}\) onto itself. For example \(p\) maps \(0 \to 1\text{,}\) \(1 \to 2\) and \(2 \to 0\text{.}\)

Table 2.37. Six Bijections


i	p	q	f	g	h

012	012	012	012	012	012

012	120	201	021	210	102

Make a composition table for these 6 bijections, illustrating Problems 2.33, Problem 2.34 and Problem 2.35 above.

Problem 2.38.

A function \(f:\B \to \C\) is said to be left cancelative if, for all sets \(\A\) and all functions \(g,h:\A \to \B\text{,}\)

\begin{equation*} f \circ g = f \circ h \ \mbox{ implies } \ \ g = h\text{.} \end{equation*}

Show that \(f\) is left cancelative if and only if \(f\) is one-to-one.

Problem 2.39.

A function \(f:\B \to \C\) is said to be right cancelative if, for all sets \(\D\) and all functions \(g,h:\C \to \D\text{,}\)

\begin{equation*} g \circ f = h \circ f, \ \ \mbox{ implies } \ \ g = h\text{.} \end{equation*}

Show that \(f\) is right cancelative if and only if \(f\) is onto \(\C\text{.}\)