Composition of Mappings Associative
From ProofWiki
Theorem
The composition of mappings is an associative binary operation:
- $\left({f_3 \circ f_2}\right) \circ f_1 = f_3 \circ \left({f_2 \circ f_1}\right)$
Proof
From the definition, we know that a mapping is a relation.
First, note that from the definition of composition of relations, the following must be the case before the above expression is even to be defined:
- $\operatorname{Dom} \left({f_2}\right) = \operatorname{Cdm} \left({f_1}\right)$
- $\operatorname{Dom} \left({f_3}\right) = \operatorname{Cdm} \left({f_2}\right)$
where $\operatorname{Cdm} \left({f}\right)$ denotes the codomain of the mapping $f$.
The two composite relations can be seen to have the same domain, as follows:
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \operatorname{Dom} \left({\left({f_3 \circ f_2}\right) \circ f_1}\right)\) | \(=\) | \(\displaystyle \operatorname{Dom} \left({f_1}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Domain of Composite Relation |
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \operatorname{Dom} \left({f_3 \circ \left({f_2 \circ f_1}\right)}\right)\) | \(=\) | \(\displaystyle \operatorname{Dom} \left({f_2 \circ f_1}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Domain of Composite Relation | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \operatorname{Dom} \left({f_1}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Domain of Composite Relation |
Also they have the same codomain, as is seen by:
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \operatorname{Cdm} \left({\left({f_3 \circ f_2}\right) \circ f_1}\right)\) | \(=\) | \(\displaystyle \operatorname{Cdm} \left({f_3 \circ f_2}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Codomain of Composite Relation | ||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \operatorname{Cdm} \left({f_3}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Codomain of Composite Relation |
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \operatorname{Cdm} \left({f_3 \circ \left({f_2 \circ f_1}\right)}\right)\) | \(=\) | \(\displaystyle \operatorname{Cdm} \left({f_3}\right)\) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | Codomain of Composite Relation |
As a mapping is a relation, we can use that the composition of relations is associative:
- $\forall x \in \operatorname{Dom} \left({f_1}\right): \left({f_3 \circ f_2}\right) \circ f_1 \left({x}\right) = f_3 \circ \left({f_2 \circ f_1}\right) \left({x}\right)$
Hence the result.
$\blacksquare$
Sources
- Nathan Jacobson: Lectures in Abstract Algebra: I. Basic Concepts (1951): $\text{I} \ \S 1$
- Paul R. Halmos: Naive Set Theory (1960)... (previous)... (next): $\S 10$: Inverses and Composites
- W.E. Deskins: Abstract Algebra (1964): Exercise $1.4: 5$
- J.A. Green: Sets and Groups (1965)... (previous)... (next): $\S 3.4$
- J.A. Green: Sets and Groups (1965)... (previous)... (next): $\S 4.2$: Example $65$
- Seth Warner: Modern Algebra (1965)... (previous)... (next): $\S 5$: Theorem $5.1$
- Richard A. Dean: Elements of Abstract Algebra (1966): $\S 0.5$: Theorem $7$
- George McCarty: Topology: An Introduction with Application to Topological Groups (1967): $\text{I}$: Theorem $6$
- Ian D. Macdonald: The Theory of Groups (1968): Appendix
- Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 16$
- T.S. Blyth: Set Theory and Abstract Algebra (1975): $\S 5$: Theorem $5.2$
- Thomas A. Whitelaw: An Introduction to Abstract Algebra (1978)... (previous)... (next): $\S 24.1$
- John F. Humphreys: A Course in Group Theory (1996): $\S 2$: Proposition $2.10$
