# Enumeration of a sequence involving closure operators

Let us call a collection $$\mathcal{F} \subseteq \mathcal{P}(X)$$ special if it satisfies the following two conditions:

1. $$\emptyset, X \in \mathcal{F}$$
2. For all $$U, V \in \mathcal{F}$$, it holds that $$U \cap V \in \mathcal{F}$$.

We can list and evaluate the number of special collections on a finite labeled set of $$n$$ elements with the following code:

Table[Length[
Select[Subsets[Subsets[Range[n]]],
And[MemberQ[#, {}], MemberQ[#, Range[n]],
SubsetQ[#, Intersection @@@ Tuples[#, 2]]] &]], {n, 0, 4}]


Let us introduce another condition that special collections may satisfy:

1. For all $$S \subseteq X$$, the statement $$\forall x,y \in S : \mathrm{cl}(\left \{ x,y \right \})\subseteq S$$ implies $$S \in \mathcal{F}$$,

where the closure $$\mathrm{cl}(A)$$ is defined as $$\mathrm{cl}(A)=\bigcap \left \{ U : U\supseteq A \wedge U \in \mathcal{F} \right \}$$ for all $$A \subseteq X$$. In the condition 3, it may also be that $$x=y$$.

Let $$a(n)$$ denote the number of special collections on a finite labeled set of $$n$$ elements that also satisfy condition 3.

Can someone help me write a code to list all such collections and calculate $$a(n)$$ for $$n \leq 4$$?

For example, $$a(2)=4$$ since all of the collections;

{{}, {1,2}}

{{}, {1}, {1,2}}

{{}, {2}, {1,2}}

{{}, {1}, {2}, {1,2}}

satisfy conditions 1, 2 and 3.

• Thank you. Did it. Commented Jun 30, 2023 at 13:46
• I missed this in your definition: it could be $\forall_S\forall_{\{x,y\}}(\text{abc}\implies\text{xyz})$ or $\forall_S(\forall_{\{x,y\}}\text{abc})\implies\text{xyz}$. The latter is correct.
Commented Jul 4, 2023 at 2:31

Condition 3 is equivalent to $$\forall_{S\not\in\mathcal F}\neg\forall_{\{x,y\}\subseteq S}\mathrm{cl}(\{x,y\})\subseteq S$$. This can be seen by expanding the logical operators.

This code is a straightforward implementation. It isn't fast, I'm curious if a solution involving ForAll and Exists is faster.

Remove[singletonsAndPairs, n, P, closure, condition1Q, condition2Q, condition3Q, P123]
singletonsAndPairs[A_List] := Subsets[A, {1, 2}]
n = 4;
P = Subsets@Range@n;
closure[𝓕_, A_] := Intersection @@ Select[𝓕, SubsetQ[#, A] &](*\!$$\*SubscriptBox[\(\[Intersection]$$, $$A \[SubsetEqual] # \[SubsetEqual] 𝓕$$]#\)*)
condition1Q[𝓕_] := SubsetQ[𝓕, {{}, Range@n}]
condition2Q[𝓕_] := SubsetQ[𝓕, Intersection @@@ singletonsAndPairs@𝓕](*{U\[Intersection]V:U,V\[Element]𝓕}\[SubsetEqual]𝓕*)
condition3Q[𝓕_] := AllTrue[Complement[P, 𝓕], S \[Function] \[Not] AllTrue[singletonsAndPairs@S, SubsetQ[S, closure[𝓕, #]] &]]
P123 = Select[Subsets@P, condition1Q@# \[And] condition2Q@# \[And] condition3Q@# &];
Length@P123


We get $$a(1)=1$$, $$a(2)=4$$, $$a(3)=45$$ and $$a(4)=2062$$.

A smarter method is needed for $$a(5)$$; my notebook runs out of memory.

• Replace //Length with //Column[#,Frame->All]&, or delete the //... entirely (the result is a List, and you can find its length, or frame it in a column, or anything else).
• Thank you very much! What if we replaced condition 3 with: For all $S \subseteq X$, the statement $\forall x_1, x_2, ..., x_k \in S : \mathrm{cl}(\left \{ x_1, x_2, ..., x_k \right \})\subseteq S$ implies $S \in \mathcal{F}$ for arbitrary $k$? Commented Jul 5, 2023 at 11:58
• The code could be made more explicit; I'll remove the Withs to make the variables a bit easier to read.