馃摌 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 >.

In the galactic.algebras.lattice.examples.arithmetic.core module, the PrimeFactors class implements a lattice structure based on the prime factorization of positive integers.

# 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\]
# compute the join of powers of prime factors of 6 and powers of prime factors of 8
PrimeFactors(6) | PrimeFactors(8)
\[24=2^3路3\]
# compute the meet of powers of prime factors of 6 and powers of prime factors of 8
PrimeFactors(6) & PrimeFactors(8)
\[2=2\]
# 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#

In the galactic.algebras.lattice.core module, the ExtensibleLattice class represents mutable lattices, while the FrozenLattice class represents immutable lattices.

Both classes are generic and can be used with any element type that implements the necessary lattice operations and comparisons.

from galactic.algebras.lattice.core import ExtensibleLattice, FrozenLattice

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 = ExtensibleLattice[PrimeFactors]()
lattice

<galactic.algebras.lattice.core.ExtensibleLattice object at 0x759d741b7740>

# 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 = ExtensibleLattice[PrimeFactors](integers)
lattice

<galactic.algebras.lattice.core.ExtensibleLattice object at 0x759d5ef0e350>

# 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(1),
 PrimeFactors(3),
 PrimeFactors(9),
 PrimeFactors(63),
 PrimeFactors(126),
 PrimeFactors(630),
 PrimeFactors(315),
 PrimeFactors(18),
 PrimeFactors(90),
 PrimeFactors(45),
 PrimeFactors(21),
 PrimeFactors(42),
 PrimeFactors(210),
 PrimeFactors(105),
 PrimeFactors(6),
 PrimeFactors(30),
 PrimeFactors(15),
 PrimeFactors(7),
 PrimeFactors(14),
 PrimeFactors(70),
 PrimeFactors(35),
 PrimeFactors(2),
 PrimeFactors(10),
 PrimeFactors(5)]

From existing lattices#

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

<galactic.algebras.lattice.core.ExtensibleLattice object at 0x759d5ef0e4b0>

# 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(1),
 PrimeFactors(3),
 PrimeFactors(21),
 PrimeFactors(63),
 PrimeFactors(315),
 PrimeFactors(630),
 PrimeFactors(126),
 PrimeFactors(105),
 PrimeFactors(210),
 PrimeFactors(42),
 PrimeFactors(9),
 PrimeFactors(45),
 PrimeFactors(90),
 PrimeFactors(18),
 PrimeFactors(15),
 PrimeFactors(30),
 PrimeFactors(6),
 PrimeFactors(7),
 PrimeFactors(35),
 PrimeFactors(70),
 PrimeFactors(14),
 PrimeFactors(5),
 PrimeFactors(10),
 PrimeFactors(2)]

Combining both approaches#

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

<galactic.algebras.lattice.core.ExtensibleLattice object at 0x759d5ef0e6c0>

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

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 = ExtensibleLattice[PrimeFactors](integers1)
lattice2 = ExtensibleLattice[PrimeFactors](integers2)
lattice = ExtensibleLattice[PrimeFactors](
    lattice1,
    lattice2,
    [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

Special elements in a lattice#

If not empty, a lattice can have a maximum and a minimum element. These elements can be accessed using the corresponding properties: maximum and minimum.

display(lattice.maximum, lattice.minimum)
\[6930=2路3^2路5路7路11\]
\[1\]

Collections of elements in a lattice#

A lattice handle four special collections:

  • join_irreducible elements: elements that cannot be expressed as the join of other elements in the lattice.

  • meet_irreducible elements: elements that cannot be expressed as the meet of other elements in the lattice.

  • co_atoms: the predecessors of the maximum element in the lattice, if it exists.

  • atoms: the successors of the minimum element in the lattice, if it exists.

These collections can be accessed using the corresponding properties:

display(lattice.join_irreducible, list(lattice.join_irreducible))

<galactic...Collection object at 0x759d5e459330>

[PrimeFactors(3),
 PrimeFactors(11),
 PrimeFactors(7),
 PrimeFactors(9),
 PrimeFactors(5),
 PrimeFactors(2)]

display(lattice.meet_irreducible, list(lattice.meet_irreducible))

<galactic...Collection object at 0x759d5e459bd0>

[PrimeFactors(770),
 PrimeFactors(630),
 PrimeFactors(2310),
 PrimeFactors(990),
 PrimeFactors(3465),
 PrimeFactors(1386)]

display(lattice.co_atoms, list(lattice.co_atoms))

<galactic...Collection object at 0x759d5e45bb30>

[PrimeFactors(1386),
 PrimeFactors(3465),
 PrimeFactors(990),
 PrimeFactors(2310),
 PrimeFactors(630)]

display(lattice.atoms, list(lattice.atoms))

<galactic...Collection object at 0x759d5e45b0e0>

[PrimeFactors(3),
 PrimeFactors(11),
 PrimeFactors(7),
 PrimeFactors(5),
 PrimeFactors(2)]
Contents