1
$\begingroup$

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.

How can I 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.

I have posted a similar question: Enumeration of a certain sequence III which may help.

$\endgroup$
2
  • $\begingroup$ Thank you. Did it. $\endgroup$
    – user227351
    Jun 30, 2023 at 13:46
  • 1
    $\begingroup$ 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. $\endgroup$
    – Adam
    Jul 4, 2023 at 2:31

1 Answer 1

1
+50
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ 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). $\endgroup$
    – Adam
    Jun 25, 2023 at 17:57
  • $\begingroup$ This sequence appears to be oeis.org/A334255 which seems to count different closure operators. $\endgroup$
    – user227351
    Jun 25, 2023 at 19:20
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$
    – Adam
    Jun 25, 2023 at 22:59
  • $\begingroup$ 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$? $\endgroup$
    – user227351
    Jul 5, 2023 at 11:58
  • 2
    $\begingroup$ The code could be made more explicit; I'll remove the Withs to make the variables a bit easier to read. $\endgroup$
    – Adam
    Jul 6, 2023 at 23:00

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.