I'm self studying, Fundamentals of Abstract Analysis by Andrew Gleason, and while reading about how functions can be defined as sets I got confused when asked to solve concrete exercises of this type.

$\textrm{Pg. 40}$ A function closer to our level of technical competence is $\{\langle0,0\rangle,\langle1,1\rangle,\langle2,4\rangle,\langle3,9\rangle\}$. This is the function which assigns the value 0 to 0, 1 to 1, 4 to 2, and 9 to 3. It is a subset of the function which assigns to each real number it's square. All other functions will be sets of ordered pairs of a similar character. Note that $\{\langle0,0\rangle,\langle1,1\rangle,\langle2,4\rangle,\langle0,5\rangle\}$ is not a function.

$\textrm{3-4.1. Definition.}$ A function $f$ is a set of ordered pairs such that distinct members of $f$ have distinct first elements; that is,

$(\forall x,y,z)$ $(\langle x,y\rangle \in f \text{ and } \langle x,z\rangle \in f)$ $\implies$ $y=z$

From this, I thought I understood well and attempted this first exercise.

$\textrm{Exercise 1}$ The following sets are all functions:

$f_1 = \{\langle1,1\rangle,\langle2,1\rangle,\langle3,2\rangle,\langle4,0\rangle\}$, $f_2 = \{\langle2,1\rangle,\langle4,1\rangle,\langle1,2\rangle,\langle4,1\rangle\}$ $f_3 = \{\langle0,2\rangle,\langle2,2\rangle,\langle1,4\rangle,\langle3,0\rangle\}$, $f_4 = \{\langle4,1\rangle,\langle1,2\rangle,\langle2,1\rangle,\langle0,5\rangle\}$

Write out the domain and range of each of them. Which of them are injective? Is any one a restriction of another? Compute $f_1 \circ f_2$ and $f_2 \circ f_3$. Then compute $(f_1 \circ f_2)\circ f_3$ and $f_1\circ (f_2\circ f_3)$.

$\textrm{My Answer}$:

The domain of $f_1$ is $\{1,2,3,4\}$ , $f_2$ is $\{1,2,4\}$, $f_3$ is $\{0,1,2,3\}$, and $f_4$ is $\{0,1,2,4\}$.

The range of $f_1$ is $\{0,1,2\}$, $f_2$ is $\{1,2\}$, $f_3$ is $\{0,2,4\}$, and $f_4$ is $\{1,2,5\}$.

These sets do not need to be ordered, which may confuse someone, but I ordered them anyway.

None of the functions $f_1, f_2, f_3$ and $f_4$ are injective since $f_i(x)=f_j(y)\not \Rightarrow x=y$.

$f_2$ is a restriction of $f_4$ since $f_2 = f_4\setminus \langle 0,5 \rangle$.

Finally, the composition of functions:

$f_1\circ f_2 = \{f_1(f_2(x_1)), f_1(f_2(x_2)), f_1(f_2(x_3)), f_1(f_2(x_4))\}$

$=\{\langle2,f_1(1)\rangle, \langle4,f_1(1)\rangle, \langle1,f_1(2)\rangle, \langle4,f_1(2)\}$

$=\{\langle2,1\rangle, \langle4,1\rangle, \langle1,1\rangle, \langle4,1\rangle\}$

$=\{\langle1,1\rangle, \langle2,1\rangle, \langle4,1\rangle\}$

$f_2\circ f_3 =\{\langle0,1\rangle, \langle1,1\rangle, \langle2,1\rangle\}$, noting that $\langle3, f_3(x_4))\rangle$ is not defined.

$(f_1\circ f_2)\circ f_3 = f_1\circ(f_2\circ f_3)$ since composition of functions is associative; therefore,

$(f_1\circ f_2)\circ f_3 = f_1\circ(f_2\circ f_3) = \{\langle0,1\rangle, \langle1,1\rangle, \langle2,1\rangle\}$ Noting that $\langle3, f_1(0)\rangle$ is undefined which came from $\langle3, f_1(f_2(f_3(3)))\rangle$.

Now my question is:

Let $X = \{1,2,3\}$ and let $S$ denote the set:

$S = \{f \in X^X : f \text{ is a bijection}\}$

(There are questions that follow this setup that I believe I could answer if I only knew how to approach this problem.)

I'm familiar with $X^2$ being the cartesian product $X\times X$. So I'm wondering if I should use the omega notation $\omega_4=\{1,2,3\}$ to calculate $X^4$ which would be $(((\{1,2,3\}\times \{1,2,3\})\times \{1,2,3\})\times \{1,2,3\})$ which I believe would have 81 elements, all four-tuples and then I could need to pick all the bijective 4-tuples from this 81 element list, or should I be thinking about $S$ as the mapping $S: X\rightarrow X$, i.e. the mapping $X$ onto itself? I believe I should be able figure out what $f$'s are bijective once I get a hint how to approach this problem using what I know so far. Any hints or direction to further reading would be greatly appreciated.

  • $\begingroup$ Every bijective $f$ is a permutation. $\endgroup$ Feb 11, 2018 at 4:07

1 Answer 1


$X^{X}$ is the set of functions from $X$ to $X$, and $S$ is the subset of bijective functions. The notation $B^{A}$ for the set of functions from $A$ to $B$ is a standard notation in set theory.

With this in mind, note that an element $f\in X^{X}$ is of the form

$$f=\{ \{1,a \}, \{2,b \}, \{3, c\}\}$$

with $a,b,c\in X$. The condition of $f$ being bijective means that $a,b,c$ must be all different (surjectivity and injectivity are equivalent for functions between finite sets with the same cardinality). Hence, the set $S$ is given by

$$S=\{ f_{1}, \ldots, f_{6} \}$$

where $f_{i}$ corresponds to some permutation of the values of $a,b,c$.

  • $\begingroup$ this is perfect, thank you. I'll accept the answer this evening. $\endgroup$
    – user578053
    Feb 11, 2018 at 14:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy