User:Jshflynn/Subsequence Relation is Pre-Ordering

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $A$ be a set of sequences.


Let $\approx$ be a relation on $A$ such that for all $a, b \in A$ we have that $a \approx b$ iff $a$ is a subsequence of $b$.


Then $\approx$ is a preordering on $A$.


Proof

Let $\langle a_n \rangle, \langle b_n \rangle, \langle c_n \rangle \in A$.


Reflexivity

Let $I_\N$ be the identity mapping on $\mathbb{N}$.


As $I_\N$ is a strictly increasing sequence and:


$\langle a_n \rangle = \langle a_{I_n} \rangle$


It follows from the definition of subsequence that $\langle a_n \rangle \approx \langle a_n \rangle$.


$\Box$

Transitivity

Let $\langle a_n \rangle \approx \langle b_n \rangle$ and $\langle b_n \rangle \approx \langle c_n \rangle$


By the definition of subsequence:


$\operatorname{Ran}\left(\langle a_n \rangle \right) \subseteq \operatorname{Ran}\left(\langle b_n \rangle \right)$


And


$\operatorname{Ran}\left(\langle b_n \rangle \right) \subseteq \operatorname{Ran}\left(\langle c_n \rangle \right)$


So from Subset Relation is Transitive:


$\operatorname{Ran}\left(\langle a_n \rangle \right) \subseteq \operatorname{Ran}\left(\langle c_n \rangle \right)$


Hence all terms of $\langle a_n \rangle$ are terms of $\langle c_n \rangle$.


Now choosing $a_i , a_j$ as terms of $\langle a_n \rangle$ such that $i < j$.


We have from above that $a_i$ and $a_j$ are in $\langle b_n \rangle$ and from the assumption that $\langle a_n \rangle \approx \langle b_n \rangle$ we also have that $a_i$ precedes $a_j$ in $\langle b_n \rangle$.


From above we have that $a_i$ and $a_j$ are in $\langle c_n \rangle$ and from the assumption that $\langle b_n \rangle \approx \langle c_n \rangle$ we also have that $a_i$ precedes $a_j$ in $\langle c_n \rangle$.


Hence $\langle a_n \rangle$ is a subsequence of $\langle c_n \rangle$ and $\approx$ is transitive.


$\blacksquare$