# Start a new discussion

## Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

## Site Tag Cloud

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

• CommentRowNumber1.
• CommentAuthorTodd_Trimble
• CommentTimeJun 8th 2015
• (edited Jun 8th 2015)

Spurred by an MO discussion, I added the observation that coproduct inclusions are monic in a distributive category.

• CommentRowNumber2.
• CommentAuthorTodd_Trimble
• CommentTimeJun 11th 2015

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.

• CommentRowNumber3.
• CommentAuthorDavidRoberts
• CommentTimeJun 11th 2015

I added a link to extensive category at the bottom, but it might be worth mentioning near the beginning.

• CommentRowNumber4.
• CommentAuthorMike Shulman
• CommentTimeJun 12th 2015

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$.

• CommentRowNumber5.
• CommentAuthorTodd_Trimble
• CommentTimeJun 12th 2015

Ah, okay, thanks for that Mike. That seems preferable.

• CommentRowNumber6.
• CommentAuthorMike Shulman
• CommentTimeMay 3rd 2016

Curiously, distributive category and distributive lattice were not cross-linked, so I fixed that.

• CommentRowNumber7.
• CommentAuthorTodd_Trimble
• CommentTimeOct 12th 2016
• (edited Oct 12th 2016)

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).

• CommentRowNumber8.
• CommentAuthorMike Shulman
• CommentTimeOct 12th 2016

Neat; thanks!

• CommentRowNumber9.
• CommentAuthorMike Shulman
• CommentTimeOct 12th 2016

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?

• CommentRowNumber10.
• CommentAuthorTodd_Trimble
• CommentTimeOct 12th 2016

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.

• CommentRowNumber11.
• CommentAuthorMike Shulman
• CommentTimeOct 13th 2016

Thanks for the pointer. I wonder whether the forbidden sublattices and pinwheels can be seen as cases of the forbidden minor theorem?

• CommentRowNumber12.
• CommentAuthorRodMcGuire
• CommentTimeOct 14th 2016

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.

## Infinitely distributive property

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$
• CommentRowNumber13.
• CommentAuthorMike Shulman
• CommentTimeOct 14th 2016

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.

• CommentRowNumber14.
• CommentAuthorTodd_Trimble
• CommentTimeOct 14th 2016

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$.

• CommentRowNumber15.
• CommentAuthorTodd_Trimble
• CommentTimeOct 16th 2016

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.