What are “real-world” examples of posets which are not (semi-) lattices?

Question

I know the classic counterexamples which amount to taking a few elements and constructing something like „equip elements $a,a^\prime$ with other elements that are both minimal upper bounds“, but that seems just to be a proof-of-concept. Many „generic“ posets that come to mind, like the substructures of some algebra, usually have a meet and sometimes even a join because they are meet complete.

My motivation is that I want to look some behavior of finite/countable posets, but I realized that in my head, I always imagined lattices like $\mathbb N$ with divisibility.

Answer 1

Example 1 (Easy) All differentiable functions $\mathbb R\to\mathbb R$, ordered pointwise. If $f(x)=x$ then both $f\wedge(-f)$ and $f\vee(-f)$ do not exist.

Example 2 (Difficult) All bounded self-adjoint operators on a Hilbert space of dimension greater than 1, partially ordered by the rule $\mathbf A\leq\mathbf B$ iff $\mathbf B-\mathbf A$ has only nonnegative elements in its spectrum. For the proof, see the paper.

Answer 2

Let me give two partial examples:

---

An extremely important example of a naturally-occurring non-lattice is the Turing degrees. While they form an upper semilattice, in general there is no greatest lower bound between two Turing degrees. It's also worth noting that (due to the Exact Pair Theorem) the Turing degrees are not countably-upper-complete, even though every countable set of Turing degrees is bounded above: if $X$ is a countable set of Turing degrees closed under (finite) least upper bounds, then the whole $X$ never has a least upper bound!

The Turing degrees do, however, form a semilattice. So this doesn't give a full answer to your question. However, I do think it's interesting enough to include.

---

If we're willing to kill the axiom of choice, then something quite weird can happen: it's possible that the class of cardialities is not even a semilattice!$^1$

Specifically, it is consistent with ZF that there are sets $A,B$ such that:

• $(1)$ $A$ and $B$ have no maximal lower bound: If $C$ injects into $A$ and $C$ injects into $B$, then there is some $D$ which injects into each $A$ and $B$ and into which $C$ injects but which does not inject into $C$.

• $(2)$ $A$ and $B$ have no minimal upper bound: If $A$ and $B$ each inject into $C$, then there is some $D$ which injects into $C$ and into which $A$ and $B$ each inject but into which $C$ does not inject.

This isn't actually as weird as it sounds - it happens in Cohen's original model of $\neg$AC. Cohen takes a (countable) model $M$ of ZFC and produces a larger model $M[G]$, "generated" over $M$ by a new $\omega$-sequence of new reals $G$. He then considers an intermediate structure $M\subset N\subset M[G]$; we have $G\subset N$ and $ran(G)\in N$ but $G\not\in N$, that is, $N$ remembers the individual reals in $G$ and the set of reals enumerated by $G$ but forgets the order in which $G$ enumerated them. Now - in $N$ - let $$A=\{x\in ran(G): x<0\}, \quad B=\{y\in ran(G): y>0\}.$$ It turns out that, in $N$, both $A$ and $B$ are infinite, Dedekind-finite, and no infinite set injects into both $A$ and $B$.

This immediately gives point $(1)$ above, since $C$ must be finite. It also gives $(2)$, with a bit more thought. Suppose $f:A\rightarrow C, g:B\rightarrow C$ are injections. Without loss of generality, $ran(f)\cup ran(g)=C$. Both $I:=C\setminus ran(f)$ and $J:=C\setminus ran(g)$ must be nonempty, since otherwise we would have either $A$ inject into $B$ or $B$ inject into $A$. But then - fixing $c\in C$ - both $A$ and $B$ inject into $C\setminus\{c\}$ (hint: swap $c$ with some $i\in I$ to get $A$ to inject, and swap $c$ with some $j\in J$ to get $B$ to inject).

I now claim that $C\setminus\{c\}$ is in fact strictly smaller than $C$, that is, that there is no injection from $C$ to $C\setminus\{c\}$. This is because otherwise there would be an injection of $\omega$ into $C$, and this would pull back to an injection of $\omega$ into one of $A$ or $B$, but this would contradict their Dedekind-finiteness.

$$$$

$^1$If you don't like class-sized po"set"s, we can say this differently: it's consistent with ZF that the set $V_{\omega+2}$ (modulo bijectability) ordered by $A\le B\iff$ there is an injection of $A$ into $B$ is not a semilattice .