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{.}$