ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 24 May 2021 18:58:06 +0200Obtaining the lattice of equivalence relationshttps://ask.sagemath.org/question/57255/obtaining-the-lattice-of-equivalence-relations/ Is there an easy method to obtain the lattice of all equivalence relations $L_n$ of a set with $n$ elements in Sage?Mon, 24 May 2021 13:18:33 +0200https://ask.sagemath.org/question/57255/obtaining-the-lattice-of-equivalence-relations/Comment by FrédéricC for <p>Is there an easy method to obtain the lattice of all equivalence relations $L_n$ of a set with $n$ elements in Sage?</p>
https://ask.sagemath.org/question/57255/obtaining-the-lattice-of-equivalence-relations/?comment=57259#post-id-57259Like this
sage: posets.SetPartitions(4)
Finite lattice containing 15 elementsMon, 24 May 2021 18:58:06 +0200https://ask.sagemath.org/question/57255/obtaining-the-lattice-of-equivalence-relations/?comment=57259#post-id-57259Answer by tmonteil for <p>Is there an easy method to obtain the lattice of all equivalence relations $L_n$ of a set with $n$ elements in Sage?</p>
https://ask.sagemath.org/question/57255/obtaining-the-lattice-of-equivalence-relations/?answer=57258#post-id-57258I do not know whether there is such a builtin construction in Sage, so here is a possible construction.
Let `S` be a set, e.g.:
sage: S = {'a','b','c','d'}
First, we define the list of partitions over `S`:
sage: list(SetPartitions(S))
[{{'a', 'b', 'c', 'd'}},
{{'a', 'b', 'c'}, {'d'}},
{{'a', 'b', 'd'}, {'c'}},
{{'a', 'b'}, {'c', 'd'}},
{{'a', 'b'}, {'c'}, {'d'}},
{{'a', 'c', 'd'}, {'b'}},
{{'a', 'c'}, {'b', 'd'}},
{{'a', 'c'}, {'b'}, {'d'}},
{{'a', 'd'}, {'b', 'c'}},
{{'a'}, {'b', 'c', 'd'}},
{{'a'}, {'b', 'c'}, {'d'}},
{{'a', 'd'}, {'b'}, {'c'}},
{{'a'}, {'b', 'd'}, {'c'}},
{{'a'}, {'b'}, {'c', 'd'}},
{{'a'}, {'b'}, {'c'}, {'d'}}]
Second, we define a function that decides whether a partition refines another one:
sage: refine = lambda p,q : all(any(set(i).issubset(set(j)) for j in q) for i in p)
sage: refine(((1,), (2, 3)), ((1,), (2,), (3,)))
False
sage: refine(((1,), (2,), (3,)), ((1,), (2, 3)))
True
With both the list of partitions and the refinment order, we can construct the poset:
sage: P = Poset((list(SetPartitions(S)), refine))
sage: P
Finite poset containing 15 elements
sage: P.is_lattice()
True
sage: P.plot()Mon, 24 May 2021 15:06:55 +0200https://ask.sagemath.org/question/57255/obtaining-the-lattice-of-equivalence-relations/?answer=57258#post-id-57258