Iterative Meets of Posets

58 Views Asked by At

Let $(P,\preceq)$ be a poset, where for each element $x \in P$ there finite elements $y \preceq x, y \in P$. Typically, the meet of a set of elements is supposed to be unique, however, I'm going to change that slightly. For a finite set of elements $S$, let $L(S)$ be the lower-bound set of $S$, thus $L(S) := \{x \in P | x \preceq y \forall y \in S\}$. Now, let $Meet(S,0)$ be the maximal of $L(S)$, namely, $Meet(S,0) := \{x \in L(S) | \nexists y \in L(S)\setminus x, x \preceq y \}$.

Then, for each positive integer $i$, $Meet(S,i) := Meet(Meet(S,i-1),0)$. If $Meet(S,i)$ is one element, $z$, then $Meet(S,i+k) = z$ for all positive $k$ as well. Is there a name for this kind of iterative meet? Are there important posets whose have the property that $Meet(S,i-1)$ can have multiple elements but $Meet(S,i)$ is always a single element, for $i > 0$, $|S|=2$?

1

There are 1 best solutions below

2
On

Let $(P,\leq)$ be a poset. If $S\subseteq P$, then $x\in P$ is a lower bound for $S$ if and only if $x\leq s$ for all $s\in S$. An element $x\in S$ is maximal in $S$ if for all $y\in S$, $x\leq y\implies x=y$; and dually, $x\in S$ is minimal in $S$ if for all $z\in S$, $z\leq x\implies z=x$. An element $t\in S$ is a minimum for $S$ if $t\leq s$ for all $s\in S$, and a *maximum for $S$ if $s\leq t$ for all $s\in S$. Finally, an element $x\in P$ is the infimum of $S$ if $x\leq s$ for all $s\in S$, and if $y\leq s$ for all $s\in S$, then $y\leq x$. Dually the supremum of $S$ is an element $x\in P$ such that $s\leq x$ for all $s\in S$, and if $s\leq y$ for all $s\in S$, then $x\leq y$.

So, your $L(S)$ is the set of lower bounds of $S$, and $\mathrm{Meet}(S,0)$ is the set of maximal elements in $L(S)$. Then you look at the lower bounds of this set, and take the maximal elements of that, etc.

We are assuming that your $P$, even if not finite, has the property that for every nonempty subset $S$, $L(S)$ is finite (since you are asking that each element have a finite set of lower bounds, and $L(S) = \cap L(\{s\})$ with the intersection running over all $s\in S$). That ensures that every element in $L(S)$ is less than or equal to a maximal element, and that $L(S)$ either has a maximum, or else has two or more maximal elements.

If $L(S)$ has two or more maximal elements, then $\mathrm{Meet}(S,0)$ is an antichain: a set in which no two elements are comparable. To see this, note that if $x$ and $y$ are distinct maximal elements of $L(S)$, then they must be incomparable: for if $x\leq y$ then $x=y$ (since $x$ is maximal), and likewise if $y\leq x$ then $y=x$ because $y$ is maximal.

Now, here's the thing: if $S$ is a set, $x,y\in S$, and $x$ and $y$ are incomparable, then neither $x$ nor $y$ are in $L(S)$: for if $z\in L(S)$, then $z\leq x$ and $z\leq y$; and since $x\nleq y$ then $x\notin L(S)$, and similary $y\nleq x\implies y\notin L(S)$.

That means that if $\mathrm{Meet}(S,k)$ has more than one element, then none of them can be in $\mathrm{Meet}(S,k+1)$: for none of them are in $L(\mathrm{Meet}(S,k))$, and hence none of them are maximal in $L(\mathrm{Meet}(S,k))$.

Now, after your first step, you have a subset of $L(S)$. If this subset has more than one element, then in your next step you will get a subset of $L(S)-\mathrm{Meet}(S,0)$. If this set has more than one element, then your next step will yield a subset of $L(S) - (\mathrm{Meet}(S,0)\cup\mathrm{Meet}(S,1))$; etc.

Thus, you start with a finite $L(S)$. And at each step you get either (i) the empty set; or (ii) a singleton; or (iii) you get more than one element, and in the next step you will get a subset of an ever-shrinking finite set. That means that you will eventually get a single element, or you will get the empty set.

Yes, the empty set is possible: if $P=\{a,b,c,d\}$, and the only relations in addition to the reflexive one are $a\leq c$, $a\leq d$, $b\leq c$, and $b\leq d$, and we let $S=\{c,d\}$ then the set of lower bounds is $\{a,b\}$, both of which are maximal in $L(S)$. So $\mathrm{Meet}(S,0)=L(S) = \{a,b\}$. But now, neither $a$ nor $b$ are in $L(\{a,b\})$ (and neither are $c$ and $d$, of course), and in fact $L(\{a,b\})$ is empty, and so $\mathrm{Meet}(S,1)=\varnothing$.

On the other hand, if you get $\mathrm{Meet}(S,k)$ a singleton, then $\mathrm{Meet}(S,k+1)=\mathrm{Meet}(S,k)$, for the element itself is a lower bound and is, by construction, the maximum of the set of lower bounds.

So the only two possible eventual outcomes are: you will reach the empty set, or you will reach a singleton.

However, a singleton is not necessarily an object you may want to call the meet of $S$. For instance, consider the following poset: $P=\{a,b,c,d,e,f,g,h,i\}$. Now, I'll give you the least order relations (no element between the two I list, extend transitively, add the reflexivity):

  • $c\lt a$, $c\lt b$;
  • $d\lt a$, $d\lt b$;
  • $e\lt a$, $e\lt b$;
  • $f\lt c$, $f\lt d$, $f\lt e$;
  • $g\lt d$; $g\lt e$;
  • $h\lt c$; $h\lt g$
  • $i\lt h$; $i\lt f$.

All elements except $a$ and $b$ are less than or equal to each of $a$ and $b$. I can't draw a diagram here (I would normally use xymatrix which I believe is not MathJax supported), but you should try drawing an order diagram for this to see how it looks. I'm not sure what I would call "the meet of $\{a,b\}$", but your process yields the minimum of $P$, even though there are lots of other elements that are less than or equal to all of $a$ and $b$.

Indeed, take $S=\{a,b\}$. then $L(S) = P\setminus\{a,b\}$, and the maximal elements of $L(S)$ are $c$, $d$, and $e$. So $\mathrm{Meet}(S,0) = \{c,d,e\}$.

Now, the lower bounds of $\{c,d,e\}$ $f$, $h$, and $i$; $g$ is not, becase $g\not\lt c$. The maximal elements among them are $f$ and $h$, so $\mathrm{Meet}(S,1) = \{f,h\}$.

And now $L(\{f,h\})= \{i\}$, so the process terminates.

If you remove the relation $i\lt f$, then $L(\{f,h\})$ is empty, and you get the empty set, even though you still have that $i$ is less than or equal to $a$ and $b$ (and $c$, $d$, $e$, $g$, and $h$; everything except for $f$, in fact).

So I don't think thar your process captures what you want it to capture; you can define posets in which the process just keeps going "further down away from $S$" at every step, and ends in either the empty set or a singleton, as you wish.

Note that if $L(S)$ has a minimum, then the process will not end with the empty set, but it could not end until you get to the minimum... or it could end arbitrarily "above" the minimum (if you have a "choke point" between the minimum and the set $S$, for example).

So I suspect that this idea does not capture what you want it to capture, and so I would be surprised if it has a formal name.


Now, the meet of two elements is usually defined to be their greatest lower bound. A poset in which any two elements have a meet is called a lower semilattice. In a lower semilattice, any nonempty finite subset has a greatest lower bound; if in addition every infinite subset also has a greatest lower bound, we say that the poset is a **complete* lower semilattice. The dual concept for least upper bounds is the join, and you get upper semilattices and complete upper semilattices. If you have both least upper bounds and greatest lower bounds, and they satisfiy the absorption properties, then you get a lattice (and a complete lattice if you also get lubs and glbs for infinite subsets). There is a very rich theory of lattices, of course.