📘 Lattices

📘 Lattices#

Elements#

Elements in a lattice can be combined using two primary operations: join(denoted as \(\lor\)) and meet (denoted as \(\land\)). Since elements in a lattice are partially ordered, they can be compared using the classical ordering relations: less than or equal to (\(\leq\)), greater than or equal to (\(\geq\)), less than (\(<\)), and greater than (\(>\)).

In Python, we can represent these operations and tests using the operators | (for join), & (for meet), <=, >=, <, and >.

# import the PrimeFactors lattice element
from galactic.algebras.lattice.examples.arithmetic.core import PrimeFactors

display(PrimeFactors(3), PrimeFactors(18), PrimeFactors(24))
\[3=3\]
\[18=2·3^2\]
\[24=2^3·3\]
# all powers of prime factors of 3 are also powers of prime factors of 24
PrimeFactors(3) <= PrimeFactors(24)

True

# there exists powers of prime factors of 18 that are not powers of prime factors of 3
PrimeFactors(18) <= PrimeFactors(3)

False

# 18 and 24 are not comparable
PrimeFactors(18) <= PrimeFactors(24)

False

PrimeFactors(18) >= PrimeFactors(24)

False

Collections#

Lattices are collections of elements. In Python, a lattice can be represented using internal structures that store only certain special elements: join-irreducible elements, meet-irreducible elements, and, when necessary, the maximum and minimum. These elements suffice to reconstruct the entire lattice using the \(\lor\) (join) and \(\land\) (meet) operations.

Creation of Lattices#

from galactic.algebras.lattice.core import ExtensibleFiniteLattice, FrozenFiniteLattice

Lattices can be created in Python using a sequence of existing lattices and/or an iterable of elements. As being a collection, a lattice can be iterated over to access its elements, its size can be obtained using the len function, and it can be tested using the in operator.

The empty lattice#

lattice = ExtensibleFiniteLattice[PrimeFactors]()
lattice

<galactic.algebras.lattice.core.ExtensibleFiniteLattice object at 0x7cdc28ecab90>

# check its size
len(lattice)

0

# check if an element is in the lattice
PrimeFactors(6) in lattice

False

# iterate over its elements
list(lattice)

[]

From elements#

integers = [
    PrimeFactors(2),
    PrimeFactors(3),
    PrimeFactors(5),
    PrimeFactors(7),
    PrimeFactors(9),
]
lattice = ExtensibleFiniteLattice[PrimeFactors](elements=integers)
lattice

<galactic.algebras.lattice.core.ExtensibleFiniteLattice object at 0x7cdc28ecafb0>

# check its size
len(lattice)

24

# check if an element is in the lattice
PrimeFactors(6) in lattice

True

# iterate over its elements
list(lattice)

[PrimeFactors(630),
 PrimeFactors(210),
 PrimeFactors(90),
 PrimeFactors(126),
 PrimeFactors(315),
 PrimeFactors(70),
 PrimeFactors(30),
 PrimeFactors(42),
 PrimeFactors(105),
 PrimeFactors(18),
 PrimeFactors(45),
 PrimeFactors(63),
 PrimeFactors(10),
 PrimeFactors(14),
 PrimeFactors(35),
 PrimeFactors(6),
 PrimeFactors(15),
 PrimeFactors(21),
 PrimeFactors(9),
 PrimeFactors(2),
 PrimeFactors(5),
 PrimeFactors(7),
 PrimeFactors(3),
 PrimeFactors(1)]

From existing lattices#

integers1 = [
    PrimeFactors(2),
    PrimeFactors(3),
]
integers2 = [
    PrimeFactors(3),
    PrimeFactors(5),
    PrimeFactors(7),
    PrimeFactors(9),
]
lattice1 = ExtensibleFiniteLattice[PrimeFactors](elements=integers1)
lattice2 = ExtensibleFiniteLattice[PrimeFactors](elements=integers2)
lattice = ExtensibleFiniteLattice[PrimeFactors](lattice1, lattice2)
lattice

<galactic.algebras.lattice.core.ExtensibleFiniteLattice object at 0x7cdc28ecb110>

# check its size
len(lattice)

24

# check if an element is in the lattice
PrimeFactors(6) in lattice

True

# iterate over its elements
list(lattice)

[PrimeFactors(630),
 PrimeFactors(315),
 PrimeFactors(210),
 PrimeFactors(90),
 PrimeFactors(126),
 PrimeFactors(105),
 PrimeFactors(45),
 PrimeFactors(63),
 PrimeFactors(70),
 PrimeFactors(30),
 PrimeFactors(42),
 PrimeFactors(18),
 PrimeFactors(35),
 PrimeFactors(15),
 PrimeFactors(21),
 PrimeFactors(9),
 PrimeFactors(10),
 PrimeFactors(14),
 PrimeFactors(6),
 PrimeFactors(5),
 PrimeFactors(7),
 PrimeFactors(3),
 PrimeFactors(2),
 PrimeFactors(1)]

Combining both approaches#

integers1 = [
    PrimeFactors(2),
    PrimeFactors(3),
]
integers2 = [
    PrimeFactors(3),
    PrimeFactors(5),
    PrimeFactors(7),
    PrimeFactors(9),
]
lattice1 = ExtensibleFiniteLattice[PrimeFactors](elements=integers1)
lattice2 = ExtensibleFiniteLattice[PrimeFactors](elements=integers2)
lattice = ExtensibleFiniteLattice[PrimeFactors](
    lattice1,
    lattice2,
    elements=[PrimeFactors(2), PrimeFactors(5), PrimeFactors(11)],
)
lattice

<galactic.algebras.lattice.core.ExtensibleFiniteLattice object at 0x7cdc28ecb270>

# check its size
len(lattice)

48

# check if an element is in the lattice
PrimeFactors(6) in lattice

True

# iterate over its elements
list(lattice)

[PrimeFactors(6930),
 PrimeFactors(630),
 PrimeFactors(3465),
 PrimeFactors(2310),
 PrimeFactors(990),
 PrimeFactors(1386),
 PrimeFactors(315),
 PrimeFactors(210),
 PrimeFactors(90),
 PrimeFactors(126),
 PrimeFactors(1155),
 PrimeFactors(495),
 PrimeFactors(693),
 PrimeFactors(770),
 PrimeFactors(330),
 PrimeFactors(462),
 PrimeFactors(198),
 PrimeFactors(105),
 PrimeFactors(45),
 PrimeFactors(63),
 PrimeFactors(70),
 PrimeFactors(30),
 PrimeFactors(42),
 PrimeFactors(18),
 PrimeFactors(385),
 PrimeFactors(165),
 PrimeFactors(231),
 PrimeFactors(99),
 PrimeFactors(110),
 PrimeFactors(154),
 PrimeFactors(66),
 PrimeFactors(35),
 PrimeFactors(15),
 PrimeFactors(21),
 PrimeFactors(9),
 PrimeFactors(10),
 PrimeFactors(14),
 PrimeFactors(6),
 PrimeFactors(55),
 PrimeFactors(77),
 PrimeFactors(33),
 PrimeFactors(22),
 PrimeFactors(5),
 PrimeFactors(7),
 PrimeFactors(3),
 PrimeFactors(2),
 PrimeFactors(11),
 PrimeFactors(1)]

Comparison of Lattices#

Lattices can be compared since they are partially ordered sets (posets). In Python, this comparison can be performed using the same operators as for elements: <=, >=, <, and > or the issubset and issuperset methods.

integers1 = [
    PrimeFactors(2),
    PrimeFactors(3),
]
integers2 = [
    PrimeFactors(3),
    PrimeFactors(5),
    PrimeFactors(7),
    PrimeFactors(9),
]
lattice1 = ExtensibleFiniteLattice[PrimeFactors](elements=integers1)
lattice2 = ExtensibleFiniteLattice[PrimeFactors](elements=integers2)
lattice = ExtensibleFiniteLattice[PrimeFactors](
    lattice1,
    lattice2,
    elements=[PrimeFactors(2), PrimeFactors(5), PrimeFactors(11)],
)

# lattice1 is less than or equal to lattice
display(lattice1 <= lattice, lattice1.issubset(lattice))

True

True

# lattice2 is less than or equal to lattice
display(lattice2 <= lattice, lattice.issuperset(lattice2))

True

True

# lattice1 and lattice2 are incomparable
display(lattice1 <= lattice2, lattice2 <= lattice1)

False

False
Contents