Table of Contents
Preordered sets
Abbreviation: Qoset
Definition
A preordered set (also called a quasi-ordered set or qoset for short) is a structure $\mathbf{P}=\langle P,\preceq\rangle$ such that $P$ is a set and $\preceq $ is a binary relation on $P$ that is
reflexive: $x\preceq x$ and
transitive: $x\preceq y \text{ and } y\preceq z\Longrightarrow x\preceq z$
Remark:
Morphisms
Let $\mathbf{P}$ and $\mathbf{Q}$ be qosets. A morphism from $\mathbf{P}$ to $\mathbf{Q}$ is a function $f:P\rightarrow Q$ that is preorder-preserving:
$x\preceq y\Longrightarrow f(x)\preceq f(y)$
Examples
Example 1:
Basic results
Properties
Classtype | Universal Horn class |
---|---|
Universal theory | Decidable |
First-order theory | Undecidable |
Amalgamation property | |
Strong amalgamation property | |
Epimorphisms are surjective |
Finite members
$\begin{array}{lr} f(1)= &1\\ f(2)= &2\\ f(3)= &\\ f(4)= &\\ f(5)= &\\ f(6)= &\\ f(7)= &\\ \end{array}$
Subclasses
Superclasses
References
Trace: » preordered_sets