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)$

Example 1:

Properties

Classtype Universal Horn class Decidable Undecidable

Finite members

$\begin{array}{lr} f(1)= &1\\ f(2)= &2\\ f(3)= &\\ f(4)= &\\ f(5)= &\\ f(6)= &\\ f(7)= &\\ \end{array}$