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.
I have added (here) the (small) list of examples as grabbed form rig category.
But really some counter-examples should be mentioned…
Thanks!!
Should we make a page for your example of “rectangular bands”? I had never heard of these before.
Just on formatting: Where you had
$xx= x$ for all $x\in X$ and $xyx=x$
I have inserted whitespace
$x x = x$ for all $x\in X$ and $x y x=x$
because otherwise Instiki renders the products as variable names typeset in mathrm
rectangular bands
They cropped up before as algebras for some version of the reader monad.
They are definitely worth an entry. A look at the old catlist-dicussion shows that they pop up as example for a lot of different things like affine theories, collapsed toposes, in Barr’s “point of the empty set”-paper, they also share the associativity-for-free-property with graphic monoids. For the terminology I don’t know, I used the name suggested by Peter Johnstone there and apparently taken from semigroup theory.
Okay, so I made rectangular band a hyperlink. Will create an annoyingly empty stub for it now, hoping to prompt you to add some content…
Thanks, Yemon. As per the other thread (here), now both band and rectangular band point to the same entry, containing essentially the material you provided. Any further disambiguation can be written there. Or if the entries should be split, in two (or more) please do (or let me know if I should do it).
There should probably also be some disambiguation to the band of a gerbe.
Re #22, oh, I see I didn’t put the link in properly in #19 to Sam Staton’s comment.
If I recall correctly, when $E=2$ then the algebras are precisely the rectangular bands.
Added to related concepts, completely distributive category and totally distributive category.
1 to 29 of 29