What is Kuratowski’s 14 set theorem?Duncan Clark, 1 July 2014
Introduction
In 1920, Kazimierz Kuratowski (1896–1980) published the following theorem as part of his dissertation.
Theorem 1 (Kuratowski). Let X be a topological space and E ⊂ X. Then, at most 14 distinct subsets ofX can be formed from E by taking closures and complements.
This theorem is fairly well known today and shows up as a (difficult) exercise in many general topologybooks (such as Munkre’s Topology), perhaps due to the mystique of the number 14. In this paper wewill present a proof of the theorem, and in addition, investigate how the number 14 changes if we includeintersections, unions and interior operators.
1 Background knowledge
Let us begin by recalling some basic definitions. Let X be a set, a set T ⊂ P(X) is called a topology on Xif the following hold:
1. ∅, X ∈ T .
2. If {Eα} is a collection of sets in T , then⋃αEα ∈ T .
3. If E1, . . . , En ∈ T , then⋂ni=1Ei ∈ T .
Given a pair (X, T ), we call an element E ∈ T an open set of X, the complement of an open set is calleda closed set. The closure of a set E ⊂ X, denoted cl(E), is the intersection of all closed sets containing Eand the interior of E, denoted int(E), is the union of all open sets contained in E.
Moreover, for each E the closure and interior of E are uniquely determined. So, we can view E 7→cl(E), E 7→ int(E) as functions from P(X) to itself. In general, we denote by End(P(X)) the set of allfunctions ϕ : P(X)→ P(X). A general element ϕ ∈ End(P(X)) is called an endomorphism of P(X). Forconvenience sake, we will drop the ◦ generally used when composing functions, and denote the closure of Eby kE, the interior by iE and complement by cE. Functions will be applied to the left, so that, for example,the closure of the complement of E can be succinctly written kcE.
We say a function k ∈ End(P(X)) is a Kuratowski closure operator if for all sets E,F ⊂ X thefollowing hold:
1. k∅ = ∅.2. kkE = kE.
3. E ⊂ kE.
4. kE ∪ kF = k(E ∪ F ).
One can verify that the Kuratowski closure operator is indeed the closure operator from topology if weinsist that X be given the topology consisting of sets {ckE : E ⊂ X}.
Let I ∈ End(P(X)) represent the identity function, then one can verify that:
k2 = k, c2 = I, i = ckc, i2 = i, ic = ck, kc = ci. (1)
We leave it as an exercise to prove that these relations indeed hold.Let us recall that a set P is a poset (or partially-ordered set) if there is a relation binary relation ≤ on
P such that:
1. a ≤ a for all a ∈ P (reflexivity).
2. If a ≤ b and b ≤ a, then a = b (antisymmetry).
3. If a ≤ b and b ≤ c, then a ≤ c (transitivity).
1
We will create a poset on End(P(X)) by asserting
ϕ ≤ ψ iff ϕ(E) ⊆ ψ(E), ∀E ⊂ X.
We leave it to the reader as an exercise to prove that this is indeed a poset. Note that in addition to beinga poset, our End(P(X)) is also a monoid. That is, a set together with a binary operation (in our case ◦)that is associative and has a neutral element.
2 Main theorem
In this section we will present a proof of Theorem 1. To begin, we will make use of the following lemma.
Lemma 1. The following relations hold (ϕ,ψ ∈ End(P(X))).
1. i ≤ I ≤ k.2. If ϕ ≤ ψ then cϕ ≥ cψ that is, c switches the order.
3. If ϕ ≤ ψ then kϕ ≤ kψ and iϕ ≤ iψ, that is k, i do not switch order.
4. If ϕ ≤ ψ then ϕσ ≤ ψσ for any σ ∈ End(P(X)).
Proof. Left as an exercise to the reader.
We will make use of one more lemma in our proof of Theorem 1.
Lemma 2. Let k, i ∈ End(P(X)) be closure and interior operators respectively. Then, the cardinality of themonoid generated by k, i is at most 7.
For convenience sake let the monoid be represented by (k, i), and in general agree to represent our monoidsin such a way.
Proof. From Lemma 1, we know I ≤ k. So that i = Ii ≤ ki. Applying i on the left, we find that ii ≤ iki.Since ii = i, we then have i ≤ iki. Similarly, i ≤ I. So that ik ≤ Ik = k. Therefore, kik ≤ kk = k. So thatkik ≤ k.
Now since i ≤ iki we have ik ≤ (iki)k = i(kik). But kik ≤ k, so that i(kik) ≤ ik. Thus, ik ≤ ikik ≤ ikand so ik = ikik. Similarly, ki ≤ k(iki) = (kik)i ≤ ki. So that ki = kiki.
Thus, given any word on symbols k, i we can apply k2 = k, i2 = i to reduce to a string of alternating k, i.But, using ki = kiki, ik = ikik, we know the string can be at most 3 terms long. Therefore, we may onlyproduce the following strings (some may be equal, but we know that this is the largest collection that hasthe ability not be equal)
I, i, ik, iki, k, ki, kik. (2)
Since there are 7 terms it follows that |(k, i)| ≤ 7.
Below, we provide the Hasse diagram illustrating the structure of the poset generated by (k, i).
k
kik
I ki ik
iki
i
Figure 1: Hasse diagram for (k, i).
We are now prepared to prove Theorem 1, which we restate below.
2
Theorem 1 (Kuratowski). Let X be a topological space and E ⊂ X. Then, at most 14 distinct subsets ofX can be formed from E by taking closures and complements.
Proof. Recall from (1) that i = ckc. So, the monoids generated by k, i, c and k, c are the same. Now, from(1) as well we know that ic = ck, kc = ci. So, given a word on symbols k, i, c we can assume without loss ofgenerality that all the c’s appear on the left. Last, we use the relation that c2 = I and find that any wordcan be reduced to one with either one or zero c’s at the leftmost position. Thus, |(k, i, c)| ≤ 2|(k, i)| (sincewe cannot guarantee that each be unique). To the right, then, are simply the words generated by k, i. But|(k, i)| ≤ 7. So that
|(k, c)| = |(k, i, c)| ≤ 2|(k, i)| ≤ 14.
So, given E ⊂ X we can produce no more than 14 distinct sets from E by taking closures and complements.
Let’s agree to call a set E ⊂ X that produces 14 distinct sets from closure and complements a Kura-towski 14 set. Perhaps unsurprisingly, there is a Kuratowski set in R. The following set does the trick (weleave the computation as an exercise to the reader, or refer to [3] for the solution)
S = {0} ∪ (1, 2) ∪ (2, 3) ∪ (Q ∩ (4, 5)). (3)
However, we have given no intuition as to why such a set is indeed a 14-set. The site in [6] featuresan interective applet where the user can pick various subsets of the real line to observe how the number ofdistinct sets produced by (k, c) changes. There are many other interesting questions to ask about Kuratowskisets. For example: Does every space have a Kuratowski set? How many Kuratowski sets in R are there?and, are they all measurable? Can a Kuratowski set be countable?
It turns out the lower bound for the cardinality of a Kuratowski set is 3 [7]. A 3 element Kuratowski setcan be found in the 7 point space X = {1, . . . , 7}. Let T be a topology on X with basis
B = {∅, X, {1}, {6}, {1, 2}, {3, 4}, {5, 6}}.
Then the set A = {1, 3, 5} is a Kuratowski set, as the reader may verify.
3 Generalizations
In this section, we will offer a generalized approach to the Kuratowski problem. To do so, we will make useof End(P(X)) not just as a poset, but as a lattice.
Recall that a poset P is called a lattice if any two elements x, y ∈ P have a least upper bound and agreatest lower bound. The least upper bound is called the join of x and y and is written x∨ y, similarly thegreatest lower bound is called the meet and is written x ∧ y. A lattice is distributive if for any x, y, z wehave x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z).
Given a lattice, P , we say that P is Boolean if:
1. It contains a least element, 0, and a greatest element, 1.
2. For any a ∈ P there is a b ∈ P , called the complement of a, such that a ∧ b = 1 and a ∨ b = 0.
On our space End(P(X)) there is a very natural Boolean lattice structure. We simply assert that forϕ,ψ ∈ End(P(X)) and E ⊂ X
(ϕ ∨ ψ)(E) = ϕ(E) ∪ ψ(E), (ϕ ∧ ψ)(E) = ϕ(E) ∩ ψ(E).
Given E ⊂ X, the complement of E (in terms of Boolean lattice structure) is naturally the complementof E in the topological sense (we leave it to the reader to verify that End(P(X)) is indeed a distributive,Boolean lattice). Thus, each of k, i, c,∧,∨ are unary operations in End(P(X)). We now propose the follow-ing question:
Question. Given E ⊂ X, and O ⊂ {k, c, i,∧,∨}, what is the maximal number of distinct subsets of X thatcan be formed by repeatedly applying operations from O on the set E?
3
It is clear that when O = {k, c} this reduces to Kuratowski’s problem. We will now answer this questionfor the case O = {k, i,∧}. We will first need the following lemma (the proof of which we leave to the reader).
Lemma 3. For any ϕ,ψ ∈ End(P(X)) the following hold:
1. i(ϕ ∧ ψ) = iϕ ∧ iψ, k(ϕ ∨ ψ) = kϕ ∨ kψ.2. iϕ ∨ iψ ≤ i(ϕ ∨ ψ), k(ϕ ∧ ψ) ≤ kϕ ∧ kψ.
Theorem 2. Given a topological space X and E ⊂ X. Then, the maximal number of distinct subsets of Xthan can be formed by repeating operations from {k, i,∧} is 13.
Proof. We begin with the diagram found in figure 1. Add ik ∧ ki and notice that iki ≤ ik ∧ ki sinceiki = iki ∧ iki ≤ ik ∧ ki. Now, add the meet of I to any σ ∈ {I, i, ik, iki, k, ki, kik, ik ∧ ki}. Three of theseare obviously redundant since I ∧ I = I, I ∧ i = i, I ∧ k = k. We claim the 13 element set
S = {I, i, ik, iki, k, ki, kik, ki ∧ ik, I ∧ ik, I ∧ ki, I ∧ ik ∧ ki, I ∧ iki, I ∧ kik}
is maximal, that is, closed under the operations k, i,∧.First, i distributes across ∧, so applying i to any σ ∈ S and reducing gives another element of S. Second,
S is closed under ∧ by construction.Third, we show that kS = S. For any σ not of the form I ∧ τ , kσ is clearly in S.So, let σ be any of ki ∧ ik, I ∧ iki, I ∧ ik ∧ ki, I ∧ ki. We have kσ ≤ ki since each has either a iki or ki
term and k(iki) = k(ki) = ki. Also, i ≤ σ so that ki ≤ kσ. Thus, kσ = ki.Consider last k(I ∧ ik), k(I ∧ kik). We see,
k(I ∧ ik) ≤ kI ∧ kik ≤ k ∧ kik = kik,
k(I ∧ kik) ≤ kI ∧ kkik ≤ k ∧ kik = kik.
We claim k(I ∧ ik) = k(I ∧ kik) = kik. Indeed,
ik = ik ∧ k = ik ∧ k((I ∧ ik) ∨ (I ∧ cik))
= ik ∧ (k(I ∧ ik) ∨ k(I ∧ cik)) = (ik ∧ k(I ∧ ik)) ∨ (ik ∧ k(I ∧ cik)).
But ik∧k(I ∧ cik) ≤ ik∧k(cik) = ik∧ ciik = ik∧ cik = 0. Where 0 is the endomorphism such that 0(E) = ∅for all E ⊂ X. Thus, ik ≤ ik ∧ k(I ∧ ik) and so ik ≤ k(I ∧ ik). Therefore, since I ∧ ik ≤ I ∧ kik,
kik ≤ k2(I ∧ ik) ≤ k(I ∧ kik).
Thus, k(I ∧ ik) = k(I ∧ kik) = kik. So S is closed under k and the proof is complete.
i
I ∧ iki
I ∧ ik ∧ ki
I ∧ ki I ∧ ik
I ∧ kik
I
iki
ik ∧ ki
ki ik
kik
k
Figure 2: Hasse diagram for (k, i,∧).
4
Remark. The following set T ⊂ R generates 13 distinct subsets of R by repeated application of k, i,∧ (weleave it to the the reader to verify at his or her own risk).
T =
{1
n: n ∈ N
}⋃([2, 4] \
{3 +
1
n: n ∈ N
})⋃((5, 7] ∩
(Q ∪
∞⋃n=1
(6 +
1
2nπ, 6 +
1
(2n− 1)π
))). (4)
A similar question with ∨ instead of ∧ was posed as Problem 5996 in the Nov. 1974 edition of TheAmerican Mathematical Monthly [4]. C. Y. Yu affirmed that at most 13 distinct sets can be produced withoperations k, i,∨ and published a solution four years later, in 1978 [5]. The reader may verify that thefollowing set does the trick:
U ={
1/n : n ∈ N}∪{x ∈ (2, 3) : x /∈ Q
}∪ (3, 4) ∪ (4, 5). (5)
In figure 3, we present a table with the answers to our question posited earlier. A more thorough overview,including a proof of the k, i,∧,∨ case can be found in [2]. Indeed the number for the k, i,∧,∨ case is 35, andthe severely dedicated reader may verify that the set T from (4) produces thirty five distinct sets.
{I} {∧} {∨} {∧,∨}{I} 1 1 1 1{i} 2 2 2 2{k} 2 2 2 2{c} 2 4 4 4{i, k} 7 13 13 35{i, c} = {i, k, c} = {k, c} 14 ∞ ∞ ∞
Figure 3: Table providing Kuratowski numbers for O ⊂ {k, i, c,∧,∨}.
We last provide as an example of a set which generates an infinite (countably) number of distinct sets fromthe operations k, i, c,∧,∨. Let T be the topology on N generated by the open sets {[1, a) : a ∈ N}. Given anonempty set E ⊂ N, one can verify that the kE = [minE,∞). Now, let ϕ ∈ End(P(N)), ϕ = I∧ (k(k∧c)).Take E = 2N. Then, ϕj(E) = E ∩ [2j + 2,∞), as the reader may verify.
Acknowledgments
This paper was prepared for a presentation during the Summer 2014 What is ... ? seminar at The OhioState University. Many ideas, definitions and proofs are directly copied from [2], and are not my own work.
References
[1] Munkres, J. Topology (2nd edition). Pearson. 2000.[2] Sherman, D. Variations on Kuratowski’s 14-set theorem. people.virginia.edu/∼des5e/papers/14-sets.pdf.
29 Jun. 2014[3] Strabel, G. The Kuratowski closure-complement theorem. 29 Jun. 2014.[4] The American Mathematical Monthly, Vol. 81, No. 9 (Nov., 1974), pp. 1034[5] The American Mathematical Monthly, Vol. 85, No. 4 (Apr., 1978), pp. 283-284[6] http://www.maa.org/sites/default/files/images/upload library/60/bowron/k14.html[7] http://math.stackexchange.com/a/186428/48746, 21 Jun. 2014
5
