8
$\begingroup$

Kuratowski's 14 set theorem says that there are at most 14 sets one can obtain from a given set $A\subseteq X$ in a topological space $X$ by repeatedly applying the interior and complement operations. He also showed that if you add intersection to that list (and thus all the Boolean operations) there are potentially infinitely many sets one can obtain.

My question is the following:

  1. For each $n$, what is the maximum number of sets one can obtain from a given set by using complement, intersection, and at most $n$ applications of the interior operation?

It is certainly finite. For example, the number of sets one can make from the Boolean operations and one application of the interior operation is not more than the Boolean algebra freely generated by $A$ and its formal interior $int(A)$ -- i.e. 16. And, more generally, the number of sets one can make from n+1 applications of the interior operation will not exceed the size of the Boolean algebra freely generated by the elements generated by $n$ applications, and the formal interiors of those elements.

As a means of answering this, it's natural to look for an analogue of disjunctive normal form in propositional logic. Each combination of Boolean operations that potentially produces different results when applied to $k$ distinct sets $A_1...A_k$ is equivalent to a combination that has the form of a union of intersections, where each intersection consists of either $A_i$ or its complement for each $i \in 1...k$. So my second question is:

  1. Is there a (pretty) canonical way of expressing the combinations of operations from $\{int, \cdot^c, \cap, \cup\}$, in $k$ variables, that potentially produce different sets?

More precisely, we may define the formal expressions over variables $A_1...A_k$ as follows: $A_1...A_k$ are expressions, and $int(B)$, $B^c$, $B\cap C$ and $B\cup C$ are expressions if $B$ and $C$ are (and, moreover, the expressions are the smallest set of strings closed under these rules). Say that two expressions are equivalent if they evaluate to the same thing in every topological space, for every assignment of sets to the variables. A satisfactory answer to 2 must then deliver a collection of canonical expressions such that no two canonical expressions are equivalent, and such that every expression is equivalent to a canonical expression. Of course, to answer question 1 we only need the case where k=1.

(Any pointers to relevant literature also appreciated.)

EDIT:

Incidentally, I'm particularly interested in the case where $X$ is extremally disconnected, so if imposing that condition makes the question simpler I'd also be very interested.

$\endgroup$
  • $\begingroup$ Your questions are interesting but they look very difficult. Problem 5349 from the Monthly is mildly related: it asks readers to prove that the field of subsets generated by Kuratowski's 14 sets can contain at most $2^{14}$ sets, and to find an example where this bound is attained. Also noteworthy is an unpublished result of Luke Pebody which states that for a given positive integer $n$, there is a topological space and set in the space such that exactly $n$ sets can be generated under intersection, complement and interior if and only if $n=2^k$ for some $k$. $\endgroup$ – mathematrucker Jan 3 '18 at 6:32
  • $\begingroup$ @mathematrucker Thanks. What is the full title of the "Monthly"? (If I'm understanding the first question correctly, surely the first part is well known (the field of sets generated by $n$ sets has a cardinality of at most $2^n$), and I'd be surprised if the second part was open since it looks like the sort of thing that, if all else failed, a computer could verify.) $\endgroup$ – Andrew Bacon Jan 3 '18 at 18:47
  • 1
    $\begingroup$ American Mathematical Monthly Vol. 72, No. 10, Dec., 1965 $\endgroup$ – Cheerful Parsnip Jan 4 '18 at 17:44
  • 1
    $\begingroup$ A complete bibliography related to the Kuratowski’s 14-set theorem is collected by Mark Bowron. $\endgroup$ – Alex Ravsky Jan 5 '18 at 4:45
  • 1
    $\begingroup$ @AndrewBacon if you haven't seen it before let me recommend The Algebra of Topology by McKinsey and Tarski (jstor.org/stable/1969080). It launched the subject of closure (or interior) algebras, which seem relevant to your question 2. $\endgroup$ – mathematrucker Jan 5 '18 at 5:24
0
+50
$\begingroup$

Since the relationship between interior and union, namely $int(A)\cup int(B)\subseteq int(A\cup B),$ falls short of equality, it seems doubtful that any good canonical form will ever be found.

Question 1 is unusual because it restricts the number of times an operation can be applied; no such variation of Kuratowski's theorem has appeared previously to my knowledge. A list of (closure or interior)-complement-intersection references can be found here.

Let $f(n)$ denote the maximum in Question 1. As the OP said, the value of $f(n+1)$ “will not exceed the size of the Boolean algebra freely generated by the elements generated by $n$ applications, and the formal interiors of those elements.” Since the Boolean algebra freely generated by $0$ applications has two nontrivial elements $A$ and $cA,$ the bound for $f(1)$ based on this reasoning is $2^{2^4},$ with the generators being $A,$ $cA,$ $int(A),$ $int(cA).$ Removing $cA$ reduces this to $2^{2^3}=256.$

The actual value of $f(1)$ turns out to be $12$:

1.  A
2.  cA
3.  iA
4.  ciA
5.  icA
6.  cicA
7.  A ∩ cA = ∅
8.  c(A ∩ cA) = X
9.  ciA ∩ A
10. cicA ∩ cA
11. c(ciA ∩ A)
12. c(cicA ∩ cA)

Proof. The only (nontrivial) candidates for applying interior we can ever have are sets 1 and 2, which when interior is applied to them produce sets 3 and 5; we need not worry about ever applying interior again. It is obvious that sets 1-12 are closed under complement. Sets 9 and 10 are the only nontrivial intersections (of any number of sets) among sets 1-8 that do not violate the condition; note that cicA ∩ ciA is also nontrivial, but it violates the restriction on interior. The intersection of 9 and 10 is trivial, hence sets 1-10 are “closed under” intersection (subject to the restriction). Thus the only remaining way to get any new sets from 1-12 is to intersect either 11 or 12 with either 1 or 2.

But c(ciA ∩ A) ∩ A = iA and c(ciA ∩ A) ∩ cA = cA. By duality the intersections of 12 with 1 and 2 are similarly trivial. $\blacksquare$

Again we note that sets 1-12 are generated by applying the Boolean operations to these three sets:

1.  A
3.  iA
5.  icA

Noting that interior distributes across intersection, when we apply interior to sets 1-12 we only get four additional generators for $f(2)$:

13. iciA
14. icicA
15. ic(ciA ∩ A)
16. ic(cicA ∩ cA)

Thus our initial crude bound on $f(2)$ is $2^{128}.$ Based on computer experiments the value of $f(2)$ is probably 40, with (one representation of) the remaining possible sets being:

17. ciciA
18. cicicA
19. iciA ∩ A
20. iciA ∩ cA
21. ciciA ∩ A
22. ciciA ∩ cA
23. icicA ∩ A
24. icicA ∩ cA
25. cicicA ∩ A
26. cicicA ∩ cA
27. cicA ∩ ciA
28. c(iciA ∩ A)
29. c(iciA ∩ cA)
30. c(ciciA ∩ A)
31. c(ciciA ∩ cA)
32. c(icicA ∩ A)
33. c(icicA ∩ cA)
34. c(cicicA ∩ A)
35. c(cicicA ∩ cA)
    c(cicA ∩ ciA) = ic(cicA ∩ cA)
36. cic(ciA ∩ A)
37. c(ciA ∩ A) ∩ cicA
38. c(cicA ∩ cA) ∩ ciA
39. cic(ciA ∩ A) ∩ cA
40. c(cic(ciA ∩ A) ∩ cA)

To find the above sets I used a $7$-point seed set in a $14$-point space that generates the maximum possible number of distinct intersections of Kuratowski’s 14 sets ($14+72=86;$ note that this cannot be done in a space with fewer than 14 points) to generate lots of sets ($2^{11}$ to be exact), then filtered out the ones with two or fewer applications of interior in their representations.

Admittedly all I have “shown” here is that $40\leq f(2)\leq2^{128},$ but it would probably be fairly easy (if a little time-consuming...) to prove that $f(2)=40.$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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