Ask Your Question

# 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?

edit retag close merge delete

## Comments

1

Like this

sage: posets.SetPartitions(4)
Finite lattice containing 15 elements

( 2021-05-24 18:58:06 +0200 )edit

## 1 Answer

Sort by » oldest newest most voted

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

more

## Your Answer

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

Add Answer

## Stats

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

Seen: 6,449 times

Last updated: May 24 '21