0
$\begingroup$

Generally the notion of maximal and minimal element is defined in a partially ordered set (binary relation is reflexive, antisymmetric and transitive).

A preorder is a binary relation that is reflexive and transitive.

Can we define the notion of maximal and minimal element in a preordered set?

$\endgroup$
7
  • $\begingroup$ Sure you can, the same way you do in a poset: $x$ is maximal if $x\leq y$ implies $x=y$. However, it will not generally have the properties you might want. For example, in the total pre-order on a set with more than one element, there are no maximal elements. $\endgroup$ Apr 5, 2019 at 5:54
  • 1
    $\begingroup$ @ArturoMagidin Why not define $x$ is maximal if $x\le y$ implies $y\le x$? I.e., $x$ is maximal if there is no $y$ such that $x\lt y$. $\endgroup$
    – bof
    Apr 5, 2019 at 8:49
  • $\begingroup$ @bof: again, you can, but it may not have the properties that you "expect"/"hope". The real question is: what do you want these elements to do in a preorder (and more especially, do you want them to behave in certain ways when you mod out by the equivalence to get an order)? $\endgroup$ Apr 5, 2019 at 13:55
  • 1
    $\begingroup$ @AlbertoTakase The standard definition of $x\lt y$ for a quasi-ordering $\le$ (e.g., the ordering of linear order types by embeddability) is $x\le y\land y\not\le x$. $\endgroup$
    – bof
    Apr 9, 2019 at 15:40
  • 1
    $\begingroup$ I appreciate the correction. I now understand ${\prec}:={\preceq}\setminus{\approx}$, where ${\approx}=\{(x,y):x\preceq y\preceq x\}$. I guess the notion of "minimal" for preorders $\preceq$ and binary relations $R$ (in the context of well-foundedness) are different. $\endgroup$ Apr 9, 2019 at 16:07

2 Answers 2

2
$\begingroup$

a is a minimal element when for all x <= a, a <= x.

The minimal elements of the preorder
x < y, y < x, x < a, y < a are x and y.

$\endgroup$
0
$\begingroup$

Definition. Let $X$ be a set. Let $\preceq$ be a preorder in $X$. Fix $S\subseteq X$.

A $\preceq$-minimal-element of $S$ is an element $t$ of $S$ such that $(\forall s\in S)[s\preceq t\:\Rightarrow\:s=t]$.

A $\preceq$-maximal-element of $S$ is an element $t$ of $S$ such that $(\forall s\in S)[t\preceq s\:\Rightarrow\:t=s]$.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .