User:Ascii/ProofWiki Sampling Notes for Theorems/Order Theory
Jump to navigation
Jump to search
- Identity Mapping is Order Isomorphism
- Let $\left({S, \preceq}\right)$ be an ordered set.
- The identity mapping $I_S$ is an order isomorphism from $\left({S, \preceq}\right)$ to itself.
- Equivalence of Definitions of Order Isomorphism
- Composite of Order Isomorphisms is Order Isomorphism
- Let $\left({S_1, \preceq_1}\right)$, $\left({S_2, \preceq_2}\right)$ and $\left({S_3, \preceq_3}\right)$ be ordered sets.
- Let $\phi: \left({S_1, \preceq_1}\right) \to \left({S_2, \preceq_2}\right)$ and $\psi: \left({S_2, \preceq_2}\right) \to \left({S_3, \preceq_3}\right)$ be order isomorphisms.
- Then $\psi \circ \phi: \left({S_1, \preceq_1}\right) \to \left({S_3, \preceq_3}\right)$ is also an order isomorphism.
- Dual Ordering is Ordering
- Let $\left({S, \preceq}\right)$ be an ordered set and $\succeq$ denote the dual ordering of $\preceq$.
- Then $\succeq$ is an ordering on $S$.
- Duals of Isomorphic Ordered Sets are Isomorphic
- Let $\left({S, \mathop{\preccurlyeq_1} }\right)$ and $\left({T, \mathop{\preccurlyeq_2} }\right)$ be ordered sets.
- Let $\left({S, \mathop{\succcurlyeq_1} }\right)$ and $\left({T, \mathop{\succcurlyeq_2} }\right)$ be the dual ordered sets of $\left({S, \mathop{\preccurlyeq_1} }\right)$ and $\left({T, \mathop{\preccurlyeq_2} }\right)$ respectively.
- Let $f: \left({S, \mathop{\preccurlyeq_1} }\right) \to \left({T, \mathop{\preccurlyeq_2} }\right)$ be an order isomorphism.
- Then $f: \left({S, \mathop{\succcurlyeq_1} }\right) \to \left({T, \mathop{\succcurlyeq_2} }\right)$ is also an order isomorphism.
- Supremum is Unique
- Let $\left({S, \preceq}\right)$ be an ordered set.
- Let $T$ be a non-empty subset of $S$.
- Then $T$ has at most one supremum in $S$.
- Infimum is Unique
- Let $\left({S, \preceq}\right)$ be an ordered set.
- Let $T$ be a non-empty subset of $S$.
- Then $T$ has at most one infimum in $S$.
- Power Set is Complete Lattice
- Let $S$ be a set.
- Let $\left({\mathcal P \left({S}\right), \subseteq}\right)$ be the relational structure defined on $\mathcal P \left({S}\right)$ by the relation $\subseteq$.
- Then $\left({\mathcal P \left({S}\right), \subseteq}\right)$ is a complete lattice.
- Subset of Toset is Toset
- Let $\left({S, \preceq}\right)$ be a totally ordered set.
- Let $T \subseteq S$.
- Then $\left({T, \preceq \restriction_T}\right)$ is also a totally ordered set.
- Totally Ordered Set is Lattice
- Every totally ordered set is a lattice.
- Dual of Total Ordering is Total Ordering
- Let $\preccurlyeq$ be a total ordering.
- Then its dual ordering $\succcurlyeq$ is also a total ordering.
- Trichotomy Law (Ordering)
- Let $\left({S, \preceq}\right)$ be an ordered set.
- Then $\preceq$ is a total ordering if and only if:
- $\forall a, b \in S: \left({a \prec b}\right) \lor \left({a = b}\right) \lor \left({a \succ b}\right)$
- Strictly Increasing Mapping is Increasing
- A mapping that is strictly increasing is an increasing mapping.
- Strictly Decreasing Mapping is Decreasing
- A mapping that is strictly increasing is an decreasing mapping.
- Strictly Monotone Mapping is Monotone
- A mapping that is strictly monotone is a monotone mapping.
- Order Embedding into Image is Isomorphism
- Let $\left({S, \preceq_1}\right)$ and $\left({T, \preceq_2}\right)$ be ordered sets.
- Let $S'$ be the image of a mapping $\phi: \left({S, \preceq_1}\right) \to \left({T, \preceq_2}\right)$.
- Then:
- $\phi$ is an order embedding from $\left({S, \preceq_1}\right)$ into $\left({T, \preceq_2}\right)$
- if and only if:
- $\phi$ is an order isomorphism from $\left({S, \preceq_1}\right)$ into $\left({S', \preceq_2 \restriction_{S'}}\right)$.
- Strictly Monotone Mapping with Totally Ordered Domain is Injective
- Let $\left({S, \preceq_1}\right)$ be a totally ordered set.
- Let $\left({T, \preceq_2}\right)$ be an ordered set.
- Let $\phi: \left({S, \preceq_1}\right) \to \left({T, \preceq_2}\right)$ be a strictly monotone mapping.
- Then $\phi$ is injective.
- Mapping from Totally Ordered Set is Order Embedding iff Strictly Increasing
- Let $\left({S, \preceq_1}\right)$ be a totally ordered set and let $\left({T, \preceq_2}\right)$ be an ordered set.
- Let $\phi: S \to T$ be a mapping.
- Then $\phi$ is an order embedding iff $\phi$ is strictly increasing.
- Finite Totally Ordered Set is Well-Ordered
- Every finite totally ordered set is well-ordered.