Undistinguishable elements in posets

108 Views Asked by At

Given a finite partially ordered set $P = (V, <)$, I say that $x$ and $y$ in $V$ are indistinguishable in $P$ if for all $z \in V \backslash \{x, y\}$, I have $z < x$ iff $z < y$, and $x < z$ iff $y < z$. (If I looked at all $z \in V$, this would require that $x$ and $y$ are incomparable, but I don't want to impose this.)

Indistinguishability is not an equivalence relation, because transitivity fails: it may be that $x$ and $y$ are indistinguishable, $y$ and $z$ are indistinguishable, but $x$ and $z$ are distinguished by $z$: for instance, we could have $x < y < z$, all other elements of the posets having the same order relation to $x$, $y$ and $z$, but $y$ has a different relation to $x$ and to $z$. Yet, I can talk of a set of indistinguishable elements: $V' \subseteq V$ is an indistinguishable set of $P$ if for all $x, y \in V'$, for all $z \in V \backslash V'$, I have $z < x$ iff $z < y$, and $x < z$ iff $x < y$. Of course, $\emptyset$, $V$, and all singletons, are trivially indistinguishable sets. As a non-trivial example, any sequence of contiguous elements in a total order is an indistinguishable set.

With this definition, it is clear that the union of two overlapping indistinguishable sets is an indistinguishable set. Indeed, considering two such sets $S$ and $S'$ with $s \in S \cap S'$, either $S \cup S' = V$, or let $z \in V \backslash (S \cup S')$, and, letting $x, y \in S \cup S'$, either $x$ and $y$ are both in $S$ or both in $S'$ and the result is immediate, or we have (wlog) $x \in S$ and $y \in S'$, and from e.g. $x < z$ we deduce $t < z$ (because $x, t \in S$ and $S$ is indistinguishable) hence $y < z$ (because $t, y \in S'$ and $S'$ is indistinguishable).

Motivated by this, I can look at a partition $\Pi$ of $P$ in disjoint indistinguishable sets (overlapping sets can be merged as explained above, and it is always possible to cover $P$, be it by singletons), and for I can look at the quotient poset $P/\Pi$ where I identify the elements of each partition to a single element. The point of looking at indistinguishable sets is that this quotient poset is well-defined (in particular, no cycles can be created, unlike what happens if you quotient naively by an arbitrary partition).

My question: Does this notion of indistinguishability has a standard name in partial order theory? What is known about the structure of set of partitions in indistinguishable sets of a poset? I looked up a few synonyms like "equivalent" and "similar" to find related work, but to no avail. Thanks!

1

There are 1 best solutions below

1
On BEST ANSWER

It seems to me that your notion of "indistinguishable" is related to the notion of interval, trivial interval, and indecomposable partial order. You can find the definitions in Definition 3, in S. Thomassé On better-quasi-ordering countable series-parallel orders, Trans. Amer. Math. Soc., 352 (2000), 2491--2505.

There a subset $I$ of a poset $P$ is said to be an interval if for all $x,y\in I$ and all $z\in P\setminus I$ both $x<z \leftrightarrow y<z$ and $z<x \leftrightarrow z<y$. Then $x$ and $y$ are indistinguishable in your sense if and only if $\{x,y\}$ is an interval.