Partial order up to equivalence

133 Views Asked by At

In certain contexts one runs into something like a partial order, but the antisymmetry property is weakened as follows: if $x \preceq y$ and $y \preceq x$ then $x \simeq y$, where $\simeq$ is a given equivalence relation. Examples include:

  • Cardinality relations: for sets $A$ and $B$, say $A \simeq B$ if there exists a bijection from $A$ to $B$, and $A \preceq B$ if there exists an injection from $A$ to $B$.
  • Logical consequence: for formulas $\phi$ and $\psi$ in propositional logic, say $\phi \simeq \psi$ if $\phi \leftrightarrow \psi$ is a tautology, and $\phi \preceq \psi$ if $\phi \rightarrow \psi$ is a tautology.
  • For functions $f,g: \mathbb{R} \to \mathbb{R}$, say $f \simeq g$ if $f$ and $g$ have the same roots, and $f \preceq g$ if $|f(x)| \leq |g(x)|$ for all $x \in \mathbb{R}$.

Note: If one also strengthens the reflexivity property to require $x \preceq y$ whenever $x \simeq y$, then this just becomes a partial order on the equivalence classes. However, some examples (such as the last above) do not have this strengthened reflexivity property.

Is there a standard name for this sort of thing? Partial order up to equivalence? Partial order with respect to $\simeq$? Subequivalence? Pseudo-partial-order or quasi-partial-order or something like that? I've tried googling a few guesses, but don't seem to have hit upon a name yet.

1

There are 1 best solutions below

0
On

The term you are looking for is "preorder" or "quasiorder".

We say that $(P,\leq)$ is a preorder if it is reflexive and transitive. If you define the equivalence relation $x\sim y\iff x\leq y\land y\leq x$, then the preorder induces a partial order on the equivalence classes of $\sim$.

In the other direction if you have a partial order on a set of pairwise disjoint sets $S$, you can define a preorder on the union of them, $\bigcup S=\{x\mid\exists A\in S: x\in A\}$, in the most obvious way.