One definition is that $\functionf$ is (a "rule") which associates to (each element of $\setX$) (a unique element of $\setY$).
But what is "a rule"? A more rigorous, set-theoretic definition is as follows.
$\functionf$ is a subset of $\setX\times \setY$ (so $\functionf\subseteq\setX\times\setY$) (also known as a relation from $\setX$ to $\setY$) satisfying the existence and uniqueness conditions: \[\begin{align}&(\forall \eltx \in \setX) (\exists \elty \in \setY) (\langle \eltx, \elty \rangle \in \functionf)\\ &(\langle \eltx, \elty_1 \rangle \in \functionf) \land (\langle \eltx, \elty_2 \rangle \in \functionf) \Rightarrow (\elty_1 = \elty_2) \end{align}\] Perhaps not so well known is that (each such function) has (a structure), and (functions between two fixed sets $\setX$ and $\setY$) may be classified according to (their structures).
(When the sets $\setX$ and $\setY$ are finite, this classification is key in elementary combinatorics.) Here we
- define that structure, and
- give an example of the structure associated to a well known function.
Given (an arbitrary function $\functionf:\setX\to \setY$), we may factor it into (a surjection) followed by (an injection) as follows: \[\bbox[navajowhite,10px,border:4px groove red]{\begin{array}{ccccc} \kernelreln(\rightcat\functionf) & \rightadj{\mathop\rightrightarrows\limits^{\rightcat\functionf\kp}} & \setX & \xtwoheadrightarrow{\textstyle \text{class map}} & \setX/\kernelreln(\rightcat\functionf) \equiv \kernelpart(\rightcat\functionf)\\ \Vert && \Vert && \rightadj\downarrow \rlap{\rightcat\functionf\rightadj\epsilon} \\ \kernelreln(\rightcat\functionf) & \mathop\rightrightarrows\limits_{\rightcat\functionf\kp} & \setX & {} \rlap{\mkern-3em \smash{\rightcat{\xrightarrow[\textstyle \functionf]{\mkern17em}}}} & \rightcat\setY\\ \end{array}}\taglabel{FF-SI}\] Here the “FF-SI” is simply a tag labeling this diagram, standing for
“(function factorization) into (a surjection) followed by (an injection)”, while
- $\kernelreln(\functionf)$ is an equivalence relation on $\setX$, the kernel equivalence relation of $\functionf$.
- $X/\kernelreln(\functionf) \equiv \kernelpart(\functionf)$ is (the partition of $\setX$) corresponding to ($\kernelreln(\functionf)$, the kernel partition of $\functionf$).
(The blocks of this partition) are precisely (the fibers of the function $\functionf$ which are non-empty). - (The vertical arrow on the right) is (an injection) (whose image) is precisely the (image of $\functionf$).
Thus it gives a bijection between $\kernelpart(\functionf)$ and $\image(\functionf)$.
- $\kernelreln(\functionf)$ or, equivalently, $\setX/\kernelreln(\functionf) \equiv \kernelpart(\functionf)$
(Each uniquely determines the other, via the bijective correspondence between equivalence relations and partitions.), - $\image(\functionf)$ considered as a subset of $\setY$, and
- the unique bijection (the connecting bijection) between (the kernel partition) and (the image) which makes (the above diagram commute).
by first (factoring $\functionf$) into (a surjection onto its image $\image(\functionf)$) followed by (the inclusion of $\image(\functionf)$ into $\setY$), as shown in (the lower part of the diagram below),
then applying $\ref{FF-SI}$ to get (the upper part of the diagram): \[\bbox[navajowhite,10px,border:4px groove red]{\begin{array}{ccccc} \kernelreln(\rightcat\functionf) & \mathop\rightrightarrows\limits^{\rightcat\functionf\kp} & \setX & \xtwoheadrightarrow{\textstyle \text{class map}} & \setX/\kernelreln(\rightcat\functionf) \equiv \kernelpart(\rightcat\functionf)\\ \Vert && \Vert && \llap{\wr\Vert} \downarrow & \rightadj\searrow \rlap{\rightcat\functionf\rightadj\epsilon} \\ \kernelreln(\rightcat\functionf) & \mathop\rightrightarrows\limits^{\rightcat\functionf\kp} & \setX & {} \rlap{\mkern-3em\xtwoheadrightarrow{\smash{\mkern15em}}} & \image(\functionf) & \subseteq & \rightcat\setY\\ \Vert && \Vert &&&& \rightcat\Vert \\ \kernelreln(\rightcat\functionf) & \mathop\rightrightarrows\limits_{\rightcat\functionf\kp} & \setX & {} \rlap{\mkern-3em\rightcat{\xrightarrow[\textstyle \functionf]{\smash{\mkern32em}}}} &&& \rightcat\setY\\ \end{array}}\taglabel{FF-SBI}\] As above, “FF-SBI” is merely a tag labeling this diagram, standing for
“(function factorization) into (a surjection) followed by (a bijection) followed by (an injection)”.
What is the structure, as defined above, associated to the squaring function $\text{sq} : {\R}\to {\R} : \eltx \mapsto \eltx^2$ which takes a real number $\eltx\in \R$ to its square $\eltx^2$?
(The above diagram) then instantiates into (the diagram below), where (the squaring function $\text{sq}$ appears at the lower right), and ($\eltx, \elty \in \R$). \[\boxed{\begin{array}{cccccccc} \{\langle \eltx,\elty \rangle \mid \eltx^2=\elty^2\} & \rightrightarrows & {\R} & \xtwoheadrightarrow{\textstyle \text{class map}} & \{\,\{\eltx,\elty\} \mid \eltx^2=\elty^2\} \\ \Vert && \Vert && \downarrow \\ \{\langle \eltx,\elty \rangle \mid \eltx^2=\elty^2\} & \rightrightarrows & {\R} & \xtwoheadrightarrow{} & \{\eltx\in {\R} \mid \eltx\ge 0\} & \subseteq & \rightcat\R \\ \Vert && \Vert &&&& \Vert\\ \{\langle \eltx,\elty \rangle \mid \eltx^2=\elty^2\} & \rightrightarrows & {\R} & {} \rlap{\mkern-3em \rightcat{\xrightarrow[\textstyle \text{sq}]{\smash{\mkern23em}}}} &&& \rightcat\R \\ && \eltx & {} \rlap{\mkern-3em \rightcat{\xmapsto[\textstyle \text{sq}]{\smash{\mkern23em}}}} &&& \eltx^2\\ \end{array}}\]
As an application of how the parts of a function may be used,
we consider the function from $[11] = \{1,2,3,4,5,6,7,8,9,10,11\}$ to
the set $\{\text{A}, \ldots, \text{Z} \}$ of the 26 upper case letters in the English alphabet
which corresponds to the word "MISSISSIPPI": \[\begin{array}{ccccccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11\\ \text{M} & \text{I} & \text{S} & \text{S} & \text{I} & \text{S} & \text{S} & \text{I} & \text{P} & \text{P} & \text{I} & \\ \end{array}\] Then its image is just $\{\text{M}, \text{I}, \text{S}, \text{P}\}$.
Its kernel partition and the kernel-partition/image correspondence are shown in the following table. \[\begin{array}{cccccc} & 2 & 3 \\ & 5 & 4 \\ & 8 & 6 & 9 \\ 1 & 11 & 7 & 10 \\[2ex] \text{M} & \text{I} & \text{S} & \text{P} \\ \end{array}\]
References
QKA, “The quotient-kernel adjunction”, 2016CFP, “Classifying functions by their parts”, 2016
No comments:
Post a Comment