Revision history [back]

First notice that for $x,y\in P$, if $x\subseteq y$ then $x\cap \overline{y}=\emptyset$ and thus $y\setminus x = \overline{x\cup\overline{y}}\in P$. It follows that each set in $P$ is formed by the union of some minimal elements of $P$, and furthermore $P$ is completely defined by the set of its minimal elements.

We can search for the set of minimal elements of $P$ among the antichains of the boolean lattice. A candidate antichain $a$ must satisfy the property that the complement of each element of $a$ is the disjoint union of elements of $a$. Here is a sample code that lists such antichains.

def test(n,a):
    u = Set(1..n)
    for s in a:
        c = u.difference(s)
        for t in a:
            if t.issubset(c):
                c = c.difference(t)
                if c.is_empty():
                    break
        if not c.is_empty():
            return False
    return True

def minels(n):
    for a in posets.BooleanLattice(n, use_subsets=True).antichains():
        if test(n,a):
            print(a)

For example, for $n=4$ it lists the following candidate sets of minimal elements of $P$:

[]
[{2}, {1}, {3}, {4}]
[{2}, {1}, {3, 4}]
[{2}, {3}, {1, 4}]
[{2}, {1, 3}, {4}]
[{2}, {1, 3, 4}]
[{1}, {3}, {2, 4}]
[{1}, {2, 3}, {4}]
[{1}, {2, 3, 4}]
[{1, 2}, {3}, {4}]
[{1, 2}, {1, 3}, {2, 3}, {1, 4}, {2, 4}, {3, 4}]
[{1, 2}, {1, 3}, {2, 4}, {3, 4}]
[{1, 2}, {2, 3}, {1, 4}, {3, 4}]
[{1, 2}, {3, 4}]
[{3}, {1, 2, 4}]
[{1, 3}, {2, 3}, {1, 4}, {2, 4}]
[{1, 3}, {2, 4}]
[{2, 3}, {1, 4}]
[{1, 2, 3}, {4}]
[{1, 2, 3, 4}]

First notice that for $x,y\in P$, if $x\subseteq y$ then $x\cap \overline{y}=\emptyset$ and thus $y\setminus x = \overline{x\cup\overline{y}}\in P$. It follows that each set in $P$ is formed by the union of some minimal elements of $P$, and furthermore $P$ is completely defined by the set of its minimal elements.

We can search for the set of minimal elements of $P$ among the antichains of the boolean lattice. $B_n$. A candidate antichain $a$ must satisfy the property that the complement of each element of $a$ is the disjoint union of elements of $a$. Here is a sample code that lists such antichains.

def test(n,a):
    u = Set(1..n)
    for s in a:
        c = u.difference(s)
        for t in a:
            if t.issubset(c):
                c = c.difference(t)
                if c.is_empty():
                    break
        if not c.is_empty():
            return False
    return True

def minels(n):
    for a in posets.BooleanLattice(n, use_subsets=True).antichains():
        if test(n,a):
            print(a)

For example, for $n=4$ it minels(4) lists the following candidate sets of minimal elements of $P$:$P\subseteq B_4$:

[]
[{2}, {1}, {3}, {4}]
[{2}, {1}, {3, 4}]
[{2}, {3}, {1, 4}]
[{2}, {1, 3}, {4}]
[{2}, {1, 3, 4}]
[{1}, {3}, {2, 4}]
[{1}, {2, 3}, {4}]
[{1}, {2, 3, 4}]
[{1, 2}, {3}, {4}]
[{1, 2}, {1, 3}, {2, 3}, {1, 4}, {2, 4}, {3, 4}]
[{1, 2}, {1, 3}, {2, 4}, {3, 4}]
[{1, 2}, {2, 3}, {1, 4}, {3, 4}]
[{1, 2}, {3, 4}]
[{3}, {1, 2, 4}]
[{1, 3}, {2, 3}, {1, 4}, {2, 4}]
[{1, 3}, {2, 4}]
[{2, 3}, {1, 4}]
[{1, 2, 3}, {4}]
[{1, 2, 3, 4}]

First notice that for $x,y\in P$, if $x\subseteq y$ then $x\cap \overline{y}=\emptyset$ and thus $y\setminus x = \overline{x\cup\overline{y}}\in P$. It follows that each set in $P$ is formed by the disjoint union of some minimal elements of $P$, and furthermore $P$ is completely defined by the set of its minimal elements.

We can search for the set of minimal elements of $P$ among the antichains of $B_n$. A candidate antichain $a$ must satisfy the property that the complement of each element of $a$ is the disjoint union of elements of $a$. Here is a sample code that lists such antichains.

def test(n,a):
    u = Set(1..n)
    for s in a:
        c = u.difference(s)
        for t in a:
            if t.issubset(c):
                c = c.difference(t)
                if c.is_empty():
                    break
        if not c.is_empty():
            return False
    return True

def minels(n):
    for a in posets.BooleanLattice(n, use_subsets=True).antichains():
        if test(n,a):
            print(a)

For example, minels(4) lists the following candidate sets of minimal elements of $P\subseteq B_4$:

[]
[{2}, {1}, {3}, {4}]
[{2}, {1}, {3, 4}]
[{2}, {3}, {1, 4}]
[{2}, {1, 3}, {4}]
[{2}, {1, 3, 4}]
[{1}, {3}, {2, 4}]
[{1}, {2, 3}, {4}]
[{1}, {2, 3, 4}]
[{1, 2}, {3}, {4}]
[{1, 2}, {1, 3}, {2, 3}, {1, 4}, {2, 4}, {3, 4}]
[{1, 2}, {1, 3}, {2, 4}, {3, 4}]
[{1, 2}, {2, 3}, {1, 4}, {3, 4}]
[{1, 2}, {3, 4}]
[{3}, {1, 2, 4}]
[{1, 3}, {2, 3}, {1, 4}, {2, 4}]
[{1, 3}, {2, 4}]
[{2, 3}, {1, 4}]
[{1, 2, 3}, {4}]
[{1, 2, 3, 4}]