nyuuzyou/wikis huggingface dataset:
Composite of Increasing Mappings is Increasing

== Theorem ==
Let $\struct {S_1, \preceq_1}$, $\struct {S_2, \preceq_2}$ and $\struct {S_3, \preceq_3}$ be ordered sets.
Let:
:$\phi: \struct {S_1, \preceq_1} \to \struct {S_2, \preceq_2}$
and:
:$\psi: \struct {S_2, \preceq_2} \to \struct {S_3, \preceq_3}$
be increasing mappings.
Then $\psi \circ \phi: \struct {S_1, \preceq_1} \to \struct {S_3, \preceq_3}$ is also an increasing mapping.
== Proof ==
By definition of composition of mappings:
:$\map {\paren {\psi \circ \phi} } x = \map \psi {\map \phi x}$
As $\phi$ is an increasing mapping, we have:
:$\forall x_1, y_1 \in S_1: x_1 \preceq_1 y_1 \implies \map \phi {x_1} \preceq_2 \map \phi {y_1}$
As $\psi$ is an increasing mapping, we have:
:$\forall x_2, y_2 \in S_2: x_2 \preceq_2 y_2 \implies \map \psi {x_2} \preceq_3 \map \psi {y_2}$
By setting $x_2 = \map \phi {x_1}, y_2 = \map \phi {y_1}$, it follows that:
:$\forall x_1, y_1 \in S_1: x_1 \preceq_1 y_1 \implies \map \psi {\map \phi {x_1} } \preceq_3 \map \psi {\map \phi {y_1} }$
That is:
:$\forall x_1, y_1 \in S_1: x_1 \preceq_1 y_1 \implies \map {\paren {\psi \circ \phi} } {x_1} \preceq_3 \map {\paren {\psi \circ \phi} } {y_1}$
Hence the result.
Category:Increasing Mappings
Composite of Injection on Surjection is not necessarily Either

== Theorem ==
Let $f$ be an injection.
Let $g$ be a surjection.
Let $f \circ g$ denote the composition of $f$ with $g$.
Then it is not necessarily the case that $f \circ g$ is either a surjection or an injection.
== Proof ==
Let $X, Y, Z$ be sets defined as:
Let $g: X \to Y$ be defined in two-row notation as:
:$\dbinom {a \ b \ c } {1 \ 2 \ 2}$
which is seen by inspection to be a surjection.
Let $f: Y \to Z$ be defined in two-row notation as:
:$\dbinom {1 \ 2} {x \ y}$
which is seen by inspection to be an injection.
The composition $f \circ g$ is seen to be:
:$\dbinom {a \ b \ c} {x \ y \ y}$
which is:
:not an injection (both $b$ and $c$ map to $y$)
:not a surjection (nothing maps to $z$).
Hence the result.
== Sources ==
* : Chapter $2$: Maps and relations on sets: Exercise $2$
Category:Injections
Category:Surjections
Category:Composite Mappings
Composite of Injections is Injection

== Theorem ==
A composite of injections is an injection.
That is:
:If $f$ and $g$ are injections, then so is $f \circ g$.
== Proof ==
Let $f$ and $g$ be injections.
Then:
== Sources ==
* : $\S 3.6$. Products of bijective mappings. Permutations: $\text{(i)}$
* : Chapter $\text{I}$: Sets and Functions: Factoring Functions
* : $\S 1.14$: Composition of Functions: Exercise $6$
* : $\S 5$. Induced mappings; composition; injections; surjections; bijections: Theorem $5.10 \ (1)$
* : Appendix $\text{A}.4$: Functions: Theorem $\text{A}.5$
* : Chapter $1$: Sets and mappings: $\S 1.3$: Mappings: Exercise $2$
* : Chapter $2$: Maps and relations on sets: Exercise $2 \ \text{(a)}$
* : $1$: Set Theory and Logic: $\S 2$: Functions
* : $1$: Set Theory and Logic: $\S 2$: Functions: Exercise $2.4 \ \text{(b)}$
* : $\S 2$: Problem $8$
* : Appendix $\text{A}$: Set Theory: Functions
Category:Injections
Category:Composite Mappings
Composite of Inverse of Mapping with Mapping

== Theorem ==
Let $f: S \to T$ be a mapping.
Then:
:$f \circ f^{-1} = I_{\Img f}$
where:
: $f \circ f^{-1}$ is the composite of $f$ and $f^{-1}$
: $f^{-1}$ is the inverse of $f$
: $I_{\Img f}$ is the identity mapping on the image set of $f$.
== Proof ==
By Inverse of Mapping is One-to-Many Relation, $f^{-1}$ is a one-to-many relation:
:$f^{-1} \subseteq T \times S$
whose domain is the image set of $f$.
By definition of composition of relations:
:$f \circ f^{-1} := \set {\tuple {x, z} \in T \times T: \exists y \in S: \tuple {x, y} \in f^{-1} \land \tuple {y, z} \in f}$
Thus $f \circ f^{-1}$ is a relation on $T \times T$.
Let $x \in \Img f$.
Then:
:$\exists y \in S: \tuple {x, y} \in f^{-1}$
As $f$ is a mapping, and so by definition a many-to-one relation;
:$\map f y = x$
for all $y$ such that $\tuple {x, y} \in f^{-1}$.
That is:
:$\forall x \in \Img f: f \circ \map {f^{-1} } x = x$
Hence the result by definition of identity mapping.
== Also see ==
* Composite of Mapping with Inverse
== Sources ==
* : Chapter $0$: Functions
Category:Equivalence Relations
Category:Inverse Mappings
Category:Composite Mappings
Composite of Isomorphisms is Isomorphism/Algebraic Structure

== Theorem ==
Let:
:$\struct {S_1, \odot_1, \odot_2, \ldots, \odot_n}$
:$\struct {S_2, *_1, *_2, \ldots, *_n}$
:$\struct {S_3, \oplus_1, \oplus_2, \ldots, \oplus_n}$
be algebraic structures.
Let:
:$\phi: \struct {S_1, \odot_1, \odot_2, \ldots, \odot_n} \to \struct {S_2, *_1, *_2, \ldots, *_n}$
:$\psi: \struct {S_2, *_1, *_2, \ldots, *_n} \to \struct {S_3, \oplus_1, \oplus_2, \ldots, \oplus_n}$
be isomorphisms.
Then the composite of $\phi$ and $\psi$ is also an isomorphism.
== Proof ==
If $\phi$ and $\psi$ are both isomorphisms, then they are by definition:
:homomorphisms
:bijections.
From Composite of Homomorphisms on Algebraic Structure is Homomorphism:
:$\phi \circ \psi$ and $\psi \circ \phi$ are both homomorphisms.
From Composite of Bijections is Bijection:
:$\phi \circ \psi$ and $\psi \circ \phi$ are both bijections.
Hence by definition both are also isomorphisms.
== Sources ==
* : Chapter $\text I$: Algebraic Structures: $\S 6$: Isomorphisms of Algebraic Structures: Theorem $6.1: \ 3^\circ$
* : Chapter $\text I$: Algebraic Structures: $\S 6$: Isomorphisms of Algebraic Structures: Exercise $6.2$
* : $\S 1.2$
Category:Composite of Isomorphisms is Isomorphism
Category:Isomorphisms (Abstract Algebra)
Composite of Isomorphisms is Isomorphism/R-Algebraic Structure

== Theorem ==
Let:
:$\struct {S_1, \ast_1}_R$
:$\struct {S_2, \ast_2}_R$
:$\struct {S_3, \ast_3}_R$
be $R$-algebraic structures with the same number of operations.
Let:
:$\phi: \struct {S_1, \ast_1}_R \to \struct {S_2, \ast_2}_R$
:$\psi: \struct {S_2, \ast_2}_R \to \struct {S_3, \ast_3}_R$
be isomorphisms.
Then the composite of $\phi$ and $\psi$ is also an isomorphism.
== Proof ==
If $\phi$ and $\psi$ are both isomorphisms, then they are by definition:
:homomorphisms
;bijections.
So:
:From Composite of Homomorphisms for R-Algebraic Structures is Homomorphism we have that $\phi \circ \psi$ and $\psi \circ \phi$ are both homomorphisms
:From Composite of Bijections is Bijection we have that $\phi \circ \psi$ and $\psi \circ \phi$ are both bijections;
and hence by definition also isomorphisms.
Category:Composite of Isomorphisms is Isomorphism
Category:Isomorphisms (Abstract Algebra)
Composite of Mapping with Inverse

== Theorem ==
Let $f: S \to T$ be a mapping.
Then:
:$\forall x \in S: \map {f^{-1} \circ f} x = \eqclass x {\RR_f}$
where:
:$\RR_f$ is the equivalence induced by $f$
:$\eqclass x {\RR_f}$ is the $\RR_f$-equivalence class of $x$.
== Proof ==
Let $y = \map f x$.
Then by the definition of induced equivalence:
:$x \in \eqclass x {\RR_f}$
By the definition of the inverse of a mapping:
:$f^{-1} = \set {\tuple {y, x}: \tuple {x, y} \in f}$
Thus:
:$\eqclass x {\RR_f} = \set {s \in \Dom f: \map f s = \map f x}$
By definition:
:$\map {f^{-1} } y = \eqclass x {\RR_f}$
Hence the result.
== Also see ==
* Composite of Inverse of Mapping with Mapping
== Sources ==
* : Chapter $0$: Functions
* : Chapter $\text{I}$: Sets and Functions: Problem $\text{AA}$: Relations
Category:Equivalence Relations
Category:Inverse Mappings
Category:Composite Mappings
Composite of Mapping with Inverse of Another is Identity implies Mappings are Equal

== Theorem ==
Let $A$ and $B$ be classes.
Let $f$ and $g$ be mappings on $A \times B$.
Let $f$ and $g$ be such that:
:$f \circ g^{-1} = I_B$
where:
:$g^{-1}$ denotes the inverse of $g$
:$I_B$ denotes the identity mapping on $B$
:$\circ$ denotes composition of mappings.
Then:
:$f = g$
== Proof ==
Let $\tuple {a, b} \in f$.
Then because $\tuple {b, b} \in I_B$ we must have:
:$\tuple {b, a} \in g^{-1}$
and so by definition of inverse of mapping:
:$\tuple {a, b} \in g$
Hence:
:$f \subseteq g$
Let $\tuple {a, b} \in g$.
Then by definition of inverse of mapping:
:$\tuple {b, a} \in g^{-1}$
Then because $\tuple {b, b} \in I_B$ we must have:
:$\tuple {a, b} \in f$
Hence:
:$g \subseteq f$
Hence by definition of set equality:
:$f = g$
== Sources ==
* : Chapter $6$: Order Isomorphism and Transfinite Recursion: $\S 1$ A few preliminaries
Category:Composite Mappings
Category:Inverse Mappings
Category:Identity Mappings
Composite of Monomorphisms is Monomorphism

== Theorem ==
Let:
:$\struct {S_1, \circ_1, \circ_2, \ldots, \circ_n}$
:$\struct {S_2, *_1, *_2, \ldots, *_n}$
:$\struct {S_3, \oplus_1, \oplus_2, \ldots, \oplus_n}$
be algebraic structures.
Let:
:$\phi: \struct {S_1, \circ_1, \circ_2, \ldots, \circ_n} \to \struct {S_2, *_1, *_2, \ldots, *_n}$
:$\psi: \struct {S_2, *_1, *_2, \ldots, *_n} \to \struct {S_3, \oplus_1, \oplus_2, \ldots, \oplus_n}$
be monomorphisms.
Then the composite of $\phi$ and $\psi$ is also a monomorphism.
== Proof ==
From Composite of Homomorphisms on Algebraic Structure is Homomorphism, $\psi \circ \phi$ is a homomorphism.
From Composite of Injections is Injection, $\psi \circ \phi$ is an injection.
A monomorphism is an injective homorphism.
Hence $\psi \circ \phi$ is a monomorphism.
== Sources ==
* : $\S 1.2$
Category:Monomorphisms (Abstract Algebra)
Composite of Order Isomorphisms is Order Isomorphism

== Theorem ==
Let $\struct {S_1, \preceq_1}$, $\struct {S_2, \preceq_2}$ and $\struct {S_3, \preceq_3}$ be ordered sets.
Let:
:$\phi: \struct {S_1, \preceq_1} \to \struct {S_2, \preceq_2}$
and:
:$\psi: \struct {S_2, \preceq_2} \to \struct {S_3, \preceq_3}$
be order isomorphisms.
Then $\psi \circ \phi: \struct {S_1, \preceq_1} \to \struct {S_3, \preceq_3}$ is also an order isomorphism.
== Proof ==
From Composite of Bijections is Bijection, $\psi \circ \phi$ is a bijection, as, by definition, an order isomorphism is also a bijection.
From Inverse of Composite Bijection, the inverse of $\psi \circ \phi$ is given by:
:$\paren {\psi \circ \phi}^{-1} = \phi^{-1} \circ \psi^{-1}$
By definition of composition of mappings:
:$\map {\psi \circ \phi} x = \map \psi {\map \phi x}$
By definition of order isomorphism, we have:
:$\phi: \struct {S_1, \preceq_1} \to \struct {S_2, \preceq_2}$ is an increasing mapping
and:
:$\psi: \struct {S_2, \preceq_2} \to \struct {S_3, \preceq_3}$ is an increasing mapping.
Hence from Composite of Increasing Mappings is Increasing:
:$\psi \circ \phi: \struct {S_1, \preceq_1} \to \struct {S_3, \preceq_3}$ is an increasing mapping.
Similarly by definition of order isomorphism:
:$\phi^{-1}: \struct {S_2, \preceq_2} \to \struct {S_1, \preceq_1}$ is an increasing mapping
and:
:$\psi^{-1}: \struct {S_3, \preceq_3} \to \struct {S_2, \preceq_2}$ is an increasing mapping.
Hence from Composite of Increasing Mappings is Increasing:
:$\phi^{-1} \circ \psi^{-1}: \struct {S_3, \preceq_3} \to \struct {S_1, \preceq_1}$ is an increasing mapping.
Hence we have that:
:$\psi \circ \phi: \struct {S_1, \preceq_1} \to \struct {S_3, \preceq_3}$ is an increasing mapping
and:
:$\paren {\psi \circ \phi}^{-1}: \struct {S_3, \preceq_3} \to \struct {S_1, \preceq_1}$ is an increasing mapping
and it follows by definition that $\psi \circ \phi$ is an order isomorphism.
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 14$: Orderings: Theorem $14.1: \ 3^\circ$
* : Chapter $\text {III}$: The Natural Numbers: $\S 14$: Orderings: Exercise $14.6$
* : $\S 6.30$
Category:Order Isomorphisms
Composite of Ordered Ring Isomorphisms is Ordered Ring Isomorphism

== Theorem ==
Let $\struct {S_1, +_1, \circ_1, \preccurlyeq_1}, \struct {S_2, +_2, \circ_2, \preccurlyeq_2}, \struct {S_3, +_3, \circ_3, \preccurlyeq_3}$ be ordered rings.
Let $\phi: S_1 \to S_2$ and $\psi: S_2 \to S_3$ be ordered ring isomorphisms.
Then the composite mapping $\psi \circ \phi: S_1 \to S_3$ is also an ordered ring isomorphism.
== Proof ==
From Composite of Order Isomorphisms is Order Isomorphism, $\psi \circ \phi: \struct {S_1, \preccurlyeq_1} \to \struct {S_3, \preccurlyeq_3}$ is an order isomorphism.
From Composite of Isomorphisms in Algebraic Structure is Isomorphism, $\psi \circ \phi$ is an algebraic structure isomorphism.
From Isomorphism Preserves Groups, it follows that $\psi \circ \phi$ is a group isomorphism from $\struct {S_1, +_1}$ to $\struct {S_3, +_3}$.
From Isomorphism Preserves Semigroups, it follows that $\psi \circ \phi$ is a semigroup isomorphism from $\struct {S_1, \circ_1}$ to $\struct {S_3, \circ_3}$.
Hence the result.
== Sources ==
* : Chapter $\text {IV}$: Rings and Fields: $23$. The Field of Rational Numbers
Category:Ring Isomorphisms
Category:Order Isomorphisms
Composite of Ordered Ring Monomorphisms is Ordered Ring Monomorphism

== Theorem ==
Let $\struct {S_1, +_1, \circ_1, \preccurlyeq_1}, \struct {S_2, +_2, \circ_2, \preccurlyeq_2}, \struct {S_3, +_3, \circ_3, \preccurlyeq_3}$ be ordered rings.
Let $\phi: S_1 \to S_2$ and $\psi: S_2 \to S_3$ be ordered ring monomorphisms.
Then the composite mapping $\psi \circ \phi: S_1 \to S_3$ is also an ordered ring monomorphism.
== Proof ==
From Composite of Order Embeddings is Order Embedding, $\psi \circ \phi: \struct {S_1, \preceq_1} \to \struct {S_3, \preceq_3}$ is an order embedding.
From Composite of Monomorphisms is Monomorphism, $\psi \circ \phi$ is a monomorphism.
From Group Monomorphism preserves Group, it follows that $\psi \circ \phi$ is a group monomorphism from $\struct {S_1, +_1}$ to $\struct {S_3, +_3}$.
From Semigroup Monomorphism preserves Semigroup, it follows that $\psi \circ \phi$ is a semigroup monomorphism from $\struct {S_1, \circ_1}$ to $\struct {S_3, \circ_3}$.
Hence the result.
== Sources ==
* : Chapter $\text {IV}$: Rings and Fields: $23$. The Field of Rational Numbers
Category:Ring Monomorphisms
Category:Order Embeddings
Category:Ordered Rings
Composite of Ordered Semigroup Isomorphisms is Isomorphism

== Theorem ==
Let $\struct {S_1, \circ_1, \preccurlyeq_1}, \struct {S_2, \circ_2, \preccurlyeq_2}, \struct {S_3, \circ_3, \preccurlyeq_3}$ be ordered semigroups.
Let $\phi: S_1 \to S_2$ and $\psi: S_2 \to S_3$ be ordered semigroup isomorphisms.
Then the composite mapping $\psi \circ \phi: S_1 \to S_3$ is also an ordered semigroup isomorphism.
== Proof ==
From Composite of Isomorphisms in Algebraic Structure is Isomorphism, $\psi \circ \phi$ is an algebraic structure isomorphism.
From Isomorphism Preserves Semigroups, it follows that $\psi \circ \phi$ is a semigroup isomorphism from $\struct {S_1, \circ_1}$ to $\struct {S_3, \circ_3}$.
From Composite of Order Isomorphisms is Order Isomorphism, $\psi \circ \phi: \struct {S_1, \preceq_1} \to \struct {S_3, \preceq_3}$ is an order isomorphism.
Hence the result.
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 15$: Ordered Semigroups: Exercise $15.1$
Category:Ordered Semigroup Isomorphisms
Category:Composite Mappings
Composite of Orderings is not necessarily Ordering

== Theorem ==
Let $A$ be a set.
Let $\RR$ and $\SS$ be orderings on $A$.
Then their composite $\RR \circ \SS$ is not necessarily also an ordering on $A$.
== Proof ==
Let $\RR$ and $\SS$ be orderings as asserted.
Both $\RR$ and $\SS$ are both antisymmetric and transitive.
But we have:
:From Composite of Antisymmetric Relations is not necessarily Antisymmetric, it is not necessarily the case that $\RR \circ \SS$ is itself antisymmetric.
:From Composite of Transitive Relations is not necessarily Transitive, it is not necessarily the case that $\RR \circ \SS$ is itself transitive.
Hence it is not necessarily the case that $\RR \circ \SS$ is an ordering.
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 14$: Orderings: Exercise $14.27 \ \text {(c)}$
Category:Orderings
Category:Composite Relations
Composite of Permutations is Permutation

== Theorem ==
Let $f, g$ are permutations of a set $S$.
Then their composite $g \circ f$ is also a permutation of $S$.
== Proof ==
This follows from the fact that a permutation is a bijection. 
The domain and codomain are coincident.
The result follows from Composite of Bijections is Bijection.
== Sources ==
* : Exercise $1.3: \ 5$
* : $\S 3.6$. Products of bijective mappings. Permutations
* : $\S 4.1$. Binary operations on a set: Example $59$
* : $\S 25.4 \ \text{(i)}$: Some further results and examples on mappings
Category:Permutations
Category:Composite Mappings
Composite of Quotient Mappings

== Theorem ==
Let $S$ be a set.
Let $\RR_1$ be an equivalence on $S$, and $\RR_2$ be an equivalence on the quotient set $S / \RR_1$.
We can find an equivalence $\RR_3$ on $S$ such that $\paren {S / \RR_1} / \RR_2$ is in one-to-one correspondence with $S / \RR_3$ under the mapping:
:$\phi: \paren {S / \RR_1} / \RR_2 \to S / \RR_3: \eqclass {\eqclass x {\RR_1} } {\RR_2} \mapsto \eqclass x {\RR_3}$.
== Proof ==
Define $\RR_3$ to be the equivalence induced by:
:$x \mapsto \eqclass {\eqclass x {\RR_1} } {\RR_2}$
By definition of $\RR_3$:
:$\eqclass {\eqclass x {\RR_1} } {\RR_2} = \eqclass {\eqclass y {\RR_1} } {\RR_2} \implies \eqclass x {\RR_3} = \eqclass y {\RR_3}$
Therefore, $\phi$ is well-defined.
Again by definition of $\RR_3$: 
:$\eqclass x {\RR_3} = \eqclass y {\RR_3} \implies \eqclass {\eqclass x {\RR_1} } {\RR_2} = \eqclass {\eqclass y {\RR_1} } {\RR_2}$
which means $\phi$ is an injection.
Lastly, note that every element of $S / \RR_3$ is of the form $\eqclass x {\RR_3}$ for some $x \in S$.
It is now immediate from the definition of $\phi$ that it is surjective.
Hence $\phi$ is a bijection, as desired.
== Sources ==
* : Chapter $1$: Equivalence Relations: $\S 17 \gamma$
Category:Quotient Mappings
Category:Composite Mappings
Composite of Quotient Mappings in Topology is Quotient Mapping

== Theorem ==
Let $T_1 = \struct {S_1, \tau_1}$, $T_2 = \struct {S_2, \tau_2}$, $T_3 = \struct {S_3, \tau_3}$ be topological spaces.
Let $f: S_1 \to S_2$ and $g: S_2 \to S_3$ be quotient mappings.
Then $g \circ f : S_1 \to S_3$ is a quotient mapping.
== Proof ==
Composite of Surjections is Surjection shows that $g \circ f$ is surjective.
Composite of Continuous Mappings is Continuous shows that $g \circ f$ is continuous.
Let $U \subseteq S_3$ such that $\paren {g \circ f}^{-1} \sqbrk U$ is open in $T_1$.
By definition of quotient mapping:
:$f \sqbrk {\paren {g \circ f}^{-1} \sqbrk U}$ is open in $T_2$.
By definition of quotient mapping:
:$g \circ f \sqbrk {\paren {g \circ f}^{-1} \sqbrk U}$ is open in $T_3$.
From :
:$g \circ f \sqbrk {\paren {g \circ f}^{-1} \sqbrk U} = U$
It follows that $U$ is open in $T_3$.
Therefore, $g \circ f : S_1 \to S_3$ is a continuous surjective mapping that fulfills the following condition:
:For all $U \subseteq S_3$, if $\paren {g \circ f}^{-1} \sqbrk U$ is open in $T_1$, then $U$ is open in $T_3$.
It follows that $g \circ f$ is a quotient mapping by definition.
== Sources ==
* : $2$: Topological Spaces and Continuous Functions: $\S 22$: The Quotient Topology
Category:Quotient Topology
Composite of Reflexive Relations is Reflexive

== Theorem ==
Let $A$ be a set.
Let $\RR$ and $\SS$ be reflexive relations on $A$.
Then their composite $\RR \circ \SS$ is also reflexive.
== Proof ==
Recall the definition of composition of relations:
Hence in this particular context:
:$\RR \circ \SS := \set {\tuple {x, z} \in A \times A: \exists y \in A: \tuple {x, y} \in \SS \land \tuple {y, z} \in \RR}$
Let $x \in A$ be arbitrary.
By definition of reflexive relation:
:$\tuple {x, x} \in \SS$
:$\tuple {x, x} \in \RR$
and so setting $y = z = x$:
:$\tuple {x, x} \in \set {\tuple {x, z} \in A \times A: \exists y \in A: \tuple {x, y} \in \SS \land \tuple {y, z} \in \RR}$
Hence the result.
Category:Composite Relations
Category:Reflexive Relations
Composite of Relation Isomorphisms is Relation Isomorphism

== Theorem ==
Let $\struct {S_1, \RR_1}$, $\struct {S_2, \RR_2}$ and $\struct {S_3, \RR_3}$ be relational structures.
Let:
:$\phi: \struct {S_1, \RR_1} \to \struct {S_2, \RR_2}$
and:
:$\psi: \struct {S_2, \RR_2} \to \struct {S_3, \RR_3}$
be relation isomorphisms.
Then $\psi \circ \phi: \struct {S_1, \RR_1} \to \struct {S_3, \RR_3}$ is also a relation isomorphism.
== Proof ==
From Composite of Bijections is Bijection, $\psi \circ \phi$ is a bijection, as, by definition, an relation isomorphism is also a bijection.
By definition of composition of mappings:
:$\map {\psi \circ \phi} x = \map \psi {\map \phi x}$
As $\phi$ is a relation isomorphism, we have:
:$\forall x_1, y_1 \in S_1: x_1 \mathrel {\RR_1} y_1 \implies \map \phi {x_1} \mathrel {\RR_2} \map \phi {y_1}$
As $\psi$ is a relation isomorphism, we have:
:$\forall x_2, y_2 \in S_2: x_2 \mathrel {\RR_2} y_2 \implies \map \psi {x_2} \mathrel {\RR_3} \map \psi {y_2}$
By setting $x_2 = \map \phi {x_1}, y_2 = \map \phi {y_1}$, it follows that:
:$\forall x_1, y_1 \in S_1: x_1 \mathrel {\RR_1} y_1 \implies \map \psi {\map \phi {x_1} } \mathrel {\RR_3} \map \psi {\map \phi {y_1} }$
Similarly we can show that:
:$\forall x_3, y_3 \in S_3: x_3 \mathrel {\RR_3} y_3 \implies \map {\phi^{-1} } {\map {\psi^{-1} } {x_3} } \mathrel {\RR_1} \map {\phi^{-1} } {\map {\psi^{-1} } {y_3} }$
Hence the result, by definition of a relation isomorphism.
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 14$: Orderings: Exercise $14.9 \ \text{(b)}$
Category:Relation Isomorphisms
Composite of Strictly Increasing Mappings is Strictly Increasing

== Theorem ==
Let $\struct {S_1, \preceq_1}$, $\struct {S_2, \preceq_2}$ and $\struct {S_3, \preceq_3}$ be ordered sets.
Let:
:$\phi: \struct {S_1, \preceq_1} \to \struct {S_2, \preceq_2}$
and:
:$\psi: \struct {S_2, \preceq_2} \to \struct {S_3, \preceq_3}$
be strictly increasing mappings.
Then $\psi \circ \phi: \struct {S_1, \preceq_1} \to \struct {S_3, \preceq_3}$ is also a strictly increasing mapping.
== Proof ==
By definition of composition of mappings:
:$\map {\paren {\psi \circ \phi} } x = \map \psi {\map \phi x}$
As $\phi$ is a strictly increasing mapping, we have:
:$\forall x_1, y_1 \in S_1: x_1 \prec_1 y_1 \implies \map \phi {x_1} \prec_2 \map \phi {y_1}$
where $a \prec_1 b$ denotes that $a \preceq_1 b$ and $a \ne b$.
As $\psi$ is a strictly increasing mapping, we have:
:$\forall x_2, y_2 \in S_2: x_2 \prec_2 y_2 \implies \map \psi {x_2} \prec_3 \map \psi {y_2}$
where $a \prec_2 b$ denotes that $a \preceq_2 b$ and $a \ne b$.
By setting $x_2 = \map \phi {x_1}, y_2 = \map \phi {y_1}$, it follows that:
:$\forall x_1, y_1 \in S_1: x_1 \prec_1 y_1 \implies \map \psi {\map \phi {x_1} } \prec_3 \map \psi {\map \phi {y_1} }$
That is:
:$\forall x_1, y_1 \in S_1: x_1 \prec_1 y_1 \implies \map {\paren {\psi \circ \phi} } {x_1} \prec_3 \map {\paren {\psi \circ \phi} } {y_1}$
Hence the result.
Category:Increasing Mappings
Composite of Surjection on Injection is not necessarily Either

== Theorem ==
Let $f$ be an injection.
Let $g$ be a surjection.
Let $g \circ f$ denote the composition of $g$ with $f$.
Then it is not necessarily the case that $g \circ f$ is either a surjection or an injection.
== Proof ==
Let $X, Y, Z$ be sets defined as:
Let $f: X \to Y$ be defined in two-row notation as:
:$\dbinom {a \ b \ c } {1 \ 2 \ 3}$
which is seen by inspection to be an injection.
Let $g: Y \to Z$ be defined in two-row notation as:
:$\dbinom {1 \ 2 \ 3 \ 4} {x \ y \ y \ z}$
which is seen by inspection to be a surjection.
The composition $f \circ g$ is seen to be:
:$\dbinom {a \ b \ c} {x \ y \ y}$
which is:
:not an injection (both $b$ and $c$ map to $y$)
:not a surjection (nothing maps to $z$).
Hence the result.
Category:Injections
Category:Surjections
Category:Composite Mappings