User:Ascii/ProofWiki Sampling Notes for Theorems/Order Theory

From ProofWiki
Jump to navigation Jump to search
  1. 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.
  2. Equivalence of Definitions of Order Isomorphism
  3. 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.
  4. 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$.
  5. 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.
  6. 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$.
  7. 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$.
  8. 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.
  9. 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.
  10. Totally Ordered Set is Lattice
    Every totally ordered set is a lattice.
  11. Dual of Total Ordering is Total Ordering
    Let $\preccurlyeq$ be a total ordering.
    Then its dual ordering $\succcurlyeq$ is also a total ordering.
  12. 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)$
  13. Strictly Increasing Mapping is Increasing
    A mapping that is strictly increasing is an increasing mapping.
  14. Strictly Decreasing Mapping is Decreasing
    A mapping that is strictly increasing is an decreasing mapping.
  15. Strictly Monotone Mapping is Monotone
    A mapping that is strictly monotone is a monotone mapping.
  16. 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)$.
  17. 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.
  18. 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.
  19. Finite Totally Ordered Set is Well-Ordered
    Every finite totally ordered set is well-ordered.