Ask Your Question

Obtaining the lattice of equivalence relations

asked 2021-05-24 13:18:33 +0100

klaaa gravatar image

Is there an easy method to obtain the lattice of all equivalence relations $L_n$ of a set with $n$ elements in Sage?

edit retag flag offensive close merge delete



Like this

sage: posets.SetPartitions(4)                                                   
Finite lattice containing 15 elements
FrédéricC gravatar imageFrédéricC ( 2021-05-24 18:58:06 +0100 )edit

1 Answer

Sort by » oldest newest most voted

answered 2021-05-24 15:06:55 +0100

tmonteil gravatar image

updated 2021-05-24 18:25:27 +0100

I 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,)))
sage: refine(((1,), (2,), (3,)), ((1,), (2, 3)))

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()

sage: P.plot()
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2021-05-24 13:18:33 +0100

Seen: 6,613 times

Last updated: May 24 '21