1
$\begingroup$

Following from this Q+A, I have a family of lattices such that:

  • They are not Distributive in general;
  • They do not include any diamond sub-lattice M3;
  • They do include pentagon sub-lattice N5;
  • Specific sub-lattices are distributive -- Edit: in fact they seem to be Boolean Algebras; except with great difficulty to algebraically express each sub-lattice's least and greatest elements.

To specify those sub-lattices I use (Prover9 format):

x ^ R00 = y ^ R00 & y ^ R00 = z ^ R00 -> x v (y ^ z) = (x v y) ^ (x v z).

Edit: In this case, x ^ R00 is the least element.

In which the RHS of the -> is the usual Distributivity constraint; the LHS constrains the three participating nodes.

Now every diagram I can find of Distributive (sub-)lattices shows a pattern of diamond tiles -- like the 'Young's lattice' shown on that wiki page. But Mace4 is generating a counter-example in which x, y, z meet the LHS constraint in the formula above, but they are the only three nodes in the sub-lattice -- IOW they form a triangle tile.

I've worked through applying that RHS formula, and they obey it whichever way round I assign x, y, z. But this isn't Distributive a Boolean algebra in the sense I want or expect.

What I'm getting is similar to the wiki diagram "M3 (right)" (which is showing this isn't really an M3 sub-lattice), specifically nodes b, e, c; but no dotty line d...b -- that is, d ^ b = c = d ^ e. Also no line a--e -- that is, a, e are not adjacent, b v e = b. In this case d is the specified element R00, so b ^ d = e ^ d = c ^ d = c.

I'm expecting there would be a fourth node (say f) between b--c, thus:

  • Forming a diamond b-f-c; b-e-c; and
  • a pentagon a-d-c; a-b-f-c.

I'm wanting a diamond tile, so that I can get a complement. Without an f, what is the complement of e within the sub-lattice b-e-c?

Edit: I see that for a "sub-lattice (viewed as an interval) [that] is complemented" there is a 'local' complement. Given three elements that I can establish belong to the same sub-lattice, can I express a 'local' least and greatest element from just those three?

$\endgroup$
2
  • $\begingroup$ Note to self: 'sectionally complemented lattice' might be relevant here planetmath.org/…. In which for any element a the 'local' least element is a ^ R00; the interval [a ^ R00, a] is sectionally complemented. Point "1. Every pair of elements have a difference." is exactly what I'm aiming for, even though the overall structure isn't a Boolean algebra. $\endgroup$
    – AntC
    Commented Nov 17, 2023 at 10:25
  • $\begingroup$ The wiki diagram linked in the Q that "contains N5" (left), seems to show a triangle 'tile' b-f-c. Is the lattice overall Distributive? Click on it and see the comments below: (author) " - Own work". Sounds close to 'original research'. $\endgroup$
    – AntC
    Commented Nov 18, 2023 at 9:53

1 Answer 1

1
$\begingroup$

Yes, as your edits hint, what you're aiming for is not merely a sub-lattice that's Distributive, but also a Boolean algebra/lattice. This requires not only Distributivity but also Complementation. Unfortunately, most of the materials for Complements assume the whole Lattice is Complemented, so example formulas use overall least and greatest elements 0, 1. More explanation to follow, but first ...

(Wire-)Framing the question: "triangle 'tile'"

There is no such thing as a triangle tile within a lattice diagram. The "- own work" diagrams on that wikipage are just wrong. You can't select some arbitrary subset of elements and expect the same lattice structure to apply -- indeed the resulting elements might not form a lattice at all.

(Educationally it would help if other learning resources such as PlanetMath/Wolfram showed diagrams, not just formulas. There are a few other sites out there with diagrams -- mostly notes for undergraduate courses -- including even a few with apparently triangles. But I couldn't find explicit 'rules' for how to produce diagrams.)

Take the alleged triangle b-f-c of the "contains N5" (left). The b-f segment shows b ^ f = f; the f-c segment shows f ^ c = c. Then necessarily b ^ c = c (by transitivity of ^); but it is not the convention to show that as a separate line segment. Otherwise, you'd be drawing lines from lattice top a to every other element, and seem to get (for example) two triangles a-b-f, a-c-f.

You'd only get a segment b-c if element f was removed (as shown by the dotty lines b...f, f...c) -- but in that case there'd be no f to form a triangle.

So a line segment in the diagrams mean this is the shortest path between those elements/there's no other element in between.

Answer: Boolean sub-lattice

  • They [the family of lattices] are not Distributive in general;
  • They do include pentagon sub-lattice N5;

Then the lattices are not overall Boolean algebras.

  • Specific sub-lattices are distributive ... they seem to be Boolean Algebras;

Then they must be specified as both Distributive and Complemented. To specify the Complementation, you need to find a least (or dually, most) element within the sub-lattice to 'stand in for' 0 (or dually 1).

the 'local' least element is a ^ R00; [from your 'Note to self' comment]

Then yes 'sectionally complemented lattice' is the applicable tool. (That is, if we take L from that definition to be a sub-lattice and 0 to be the "section"'s least element a ^ R00.) You can express complements using only sub-lattice bottom:

x ^ y = y & y ^ (x ^ R00) = (x ^ R00) -> exists z (z ^ y = x ^ R00 & z v y = x).

This says: for all elements x, for all y between x and its 'local' sub-lattice bottom x ^ R00, there exists z the complement of y within the sub-lattice interval [x ^ R00, x].

IOW this treats x as 'local' lattice top; you don't need to find three distinct elements as with the Distributivity formula. And if any arbitrary element x of the sub-lattice is required to exhibit Complementarity, the whole sub-lattice must; and is therefore a Boolean sub-lattice.

With that formula included in the model you're working with, Mace4 doesn't generate non-Boolean counter-sub-lattices.

$\endgroup$
1
  • $\begingroup$ "Then necessarily b ^ c = c" so we don't get a triangle, but three-in-a-row. And that sub-lattice is Distributive but not Complemented (there's no complement for the middle node), so not a Boolean lattice. $\endgroup$
    – AntC
    Commented Nov 19, 2023 at 0:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .