Want to take part in these discussions? Sign in if you have an account, or apply for one below
Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.
Spurred by an MO discussion, I added the observation that coproduct inclusions are monic in a distributive category.
I added a bit more to distributive category, including a proof that distribution over binary coproducts implies distribution over nullary coproducts.
I don’t know what the standard proof of that is. The proof I wrote down is a little tricky.
I added a link to extensive category at the bottom, but it might be worth mentioning near the beginning.
Here’s the proof from Carboni-Lack-Walters:
There is only one possible inverse [to $p:A\times 0\to 0$], the unique arrow $!:0\to A$ [sic]. Certainly we have $p \circ ! = 1$. On the other hand, the distributivity axiom establishes $A\times (0+0)$ as the coproduct of $A\times 0$ with itself, the coprojections being equal. But any sum with coprojections equal can have at most one arrow to any other object and so $!\circ p = 1$.
Ah, okay, thanks for that Mike. That seems preferable.
Curiously, distributive category and distributive lattice were not cross-linked, so I fixed that.
Looking over some old Café conversation (round about here and following), I was moved to add some material on alternative (manifestly self-dual) criteria, leading up to Birkhoff’s forbidden sublattice criterion, to distributive lattice.
Nowhere could I find online arguments for some of this stuff, such as the cancellation criterion, that are cost-free, clear, and constructively valid. So putting this in is my good deed for the nLab this day. :-) There is more to be added to modular lattice as well.
In Indiscrete Thoughts, Rota tells a story about some illustrious mathematician who came up to him and shouted, “Admit it! All lattice theory is trivial!” Yeah, I really don’t think so. I’ve just come to learn in the past day or two of one problem in lattice theory that was open for more than 4 decades (1904-1945), due to E.V. Huntington; it asks whether a lattice with unique complementation has to be distributive. It sounds at first like it might not be so bad. But it’s a bear. And to this day no example in the wild is known (the answer to the question is negative, but Dilworth’s 1945 solution which came as a complete surprise is a grueling syntactic analysis, based on Whitman’s seminal work on free lattices, and even today the proof is pretty hard work).
Neat; thanks!
Do we have a page about “forbidden subobjects”? In addition to Birkhoff’s sublattices blocking distributivity, and the classical $K_{5}$ and $K_{3,3}$ blocking planarity of a graph, there is the “pinwheel configuration” that blocks composability of a brick diagram in a double category; and what others?
I don’t know that we have such a page; it’s certainly worth considering. There is however a major theorem in graph theory, the graph minor theorem of Robertson and Seymour, that says that for any class $C$ of finite graphs that is closed under taking graph minors, there is a finite collection of “forbidden graphs” that cannot appear as a minor of any element of $C$. The best known special case might be Kruskal’s theorem, on the class of finite forests, where the triangle $K_3$ is the forbidden graph. We have a smidgen about this in the nLab, here.
Thanks for the pointer. I wonder whether the forbidden sublattices and pinwheels can be seen as cases of the forbidden minor theorem?
i added to distributive lattice the following section and modified the finite distributive section to note that such lattices are bi-Heyting. I probably made some minor errors or may be even wronger.
I haven’t modified or cross linked any of the related pages: Heyting algebra, co-Heyting algebra, frame, locale, completely distributive lattice.
It seems somewhat strange that Heyting algebra and co-Heyting algebra don’t mention infinite distribution or give formulas for the exponentials.
A distributive lattice that is complete (not necessarily completely distributive) may be infinitely distributive or said to satisfiy the infinite distributive law :
$x \wedge (\bigvee_i y_i) = \bigvee_i (x\wedge y_i)$This property is sufficient to give the lattice Heyting algebra stucture where the implication $a\Rightarrow b$ (or exponential object $b^a$) is:
$(u \Rightarrow v) = \bigvee_{x \wedge u \leq v} x$Note that this property does not imply the dual co-infinitely distributive property:
$x \vee (\bigwedge_i y_i) = \bigwedge_i (x\vee y_i)$Instead this dual gives the lattice co-Heyting structure where the co-implication or “subtraction” ($\backslash$) is
$(u \backslash v) = \bigwedge_{u \leq v \vee x} x$If a lattice has both properties, as in a completely distributive lattice, then it has bi-Heyting structure (both Heyting and co-Heyting) and the two exponentials are equal.
$(u \Rightarrow v) = \bigvee_{x \wedge u \leq v} x \qquad = \qquad (u \backslash v) = \bigwedge_{u \leq v \vee x} x$For future reference, there is no need to copy on the forum the text added – anyone can follow the link and see it for themselves.
Re #12: it looks fine, except that if it were me, I’d be more inclined to put this mostly at frame, with a quick mention and link from distributive lattice. Definitely the calculation of the exponential would improve the article frame, which at present contents itself with a quick glossing mention of adjoint functor theorem.
However, it doesn’t make sense to say those two exponentials agree, not even in the Boolean case. For example $u \backslash 0 = u$, whereas $u \Rightarrow 0$ is the negation of $u$. The variance is also off: $u \Rightarrow v$ is contravariant in $u$ and covariant in $v$; it’s the other way around for $u \backslash v$. In the Boolean case, we actually have $u \Rightarrow 0 = 1 \backslash u$.
It seems somewhat strange that Heyting algebra and co-Heyting algebra don’t mention infinite distribution or give formulas for the exponentials.
Actually, Heyting algebra does both. Look carefully here.
1 to 15 of 15