Loading [MathJax]/jax/output/HTML-CSS/jax.js

First time here? Check out the FAQ!

Ask Your Question
2

Obtaining the lattice of equivalence relations

asked 3 years ago

klaaa gravatar image

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

Preview: (hide)

Comments

1

Like this

sage: posets.SetPartitions(4)                                                   
Finite lattice containing 15 elements
FrédéricC gravatar imageFrédéricC ( 3 years ago )

1 Answer

Sort by » oldest newest most voted
2

answered 3 years ago

tmonteil gravatar image

updated 3 years ago

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()
Preview: (hide)
link

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

Stats

Asked: 3 years ago

Seen: 6,990 times

Last updated: May 24 '21