From: diamanto (John C.D. Diamantopoulos) Subject: Math 550 HELP !!! To: rusin (Dave Rusin) Date: Wed, 9 Feb 1994 20:31:31 -0600 (CST) Dr. Rusin, I am sorry to bother you (being on leave and all) but I had a question about topology... We were given, in math 550, the problem of PROVING that the MAXIMUM number of sets you can obtain from complements and closures is 14; i.e. the Kuratowski 14 set problem! I am having many difficulties in attempting to prove this argument, is there any "hint" you might be able to give me which would start me along the "solution" path??? [deletia - djr] ============================================================================== Date: Thu, 10 Feb 94 15:48:17 CST From: rusin (Dave Rusin) To: diamanto Subject: Re: Math 550 HELP !!! In the monoid of all functions on the power set of a toplogical space (under composition), we have s=complementation and t=closure. You need to know how big is the submonoid generated by s and t. You have the relations s^2=id and t^2=t. Thus the submonoid is the set of words (id), (st), (st)^2, etc., optionally preceded by t or followed by s. To get this set to be finite, you need another relation. I think it's (st)^7=(st)^3, or something like that. To find it, you need to know (st)^7(A) = (st)^3(A) for all subsets A (or whatever the correct relation is). As usual in topology DONT try to manipulate points -- you'll go nuts thinking about a point in the closure of the complement of the closure of... Instead what always (ahem) works better is to look at subsets. You could prove the above relation, for example, by proving (st)^7(A) is both contained in and contains (st)^3(A). So here's the deal. Introduce a partial order on this monoid by stating w1 < w2 iff for every subset A of every topological space you have w1(A) \subseteq w2(A). Work with progressivelyl longer words w1 and w2 until you can prove w1=w2 for some pair of apparently different words w1 and w2 (as above, you do this by proving both w1w2). Here's how you establish the partial order: (1) (id) < t (2) if w1 < w2 then t.w1 < t.w2 (3) if w1 < w2 then s.w1 > s.w2 (4) if w1 < w2 then w1.w < w2.w for any word w I think these are the only facts you need. (1) and (2) are standard facts about closure, (3) is obvious about complements, and (4) follows from our definition of "<" ("...for EVERY subset ...") I forget the final result, but you should be able to work out the details (Hint: separate the words into those with even versus odd numbers of s's; the rules above will never make comparable words with different parities of numbers of s's) Let me know if you have any trouble. I assume you are not attempting to obtain something in a manner contrary to the understanding of your instructor. dave r ============================================================================== %What follows is a Plain TeX document which spells out solutions. %rusin June 27 2001 \nopagenumbers \def\implies{\longrightarrow} \def\R{\hbox{\bf R}} \def\Q{\hbox{\bf Q}} \def\s{\sigma} \def\t{\tau} \def\a#1{(#1)} What is the largest number of sets one can form from a single subset of a topological space, taking only closures and complements? This is Kuratowski's problem. Let us write $\s(A)$ for the closure of $A$ and $\t(A)$ for the complement of $A$ (in the larger space $X$). Note that $\s$ and $\t$ may be viewed as functions from the power set of $X$ to itself, and viewing them as functions we may take their composites (with the associative law satisfied). As in a group theory discussion, say, we may denote composition by juxtaposition, that is, $fg$ means ``first do $g$, then do $f$.'' Clearly $\s^2=\s$ and $\t^2=1$ (the identity function) so the only iterates of interest are alternating products of $\s$'s and $\t$'s. We use just a few other basic facts about $\s$ and $\t$. First, whenever applied to any subsets $B,C$ of $X$, we have $$\eqalignno{ \a1\ & B\subseteq C \implies \s(B)\subseteq \s(C)\cr \a2\ & B\subseteq C \implies \t(C)\subseteq \t(B)\cr \noalign{\hbox{which together tell us that}} \a3\ & B\subseteq C \implies \s\t(C)\subseteq \s\t(B)}$$ The other basic fact is that for any set $B$, $$\eqalignno{ \a4\ B&\subseteq \s(B)\cr \noalign{\hbox{to which we apply \a3 once to get}} \a5\ \s\t\s(B)&\subseteq\s\t(B)\cr \noalign{\hbox{and then again to get}} \a6\ \s\t\s\t(B)&\subseteq\s\t\s\t\s(B).}$$ Here's the trick, though: these statements apply to {\it any\/} subset $B$ of $X$. Given a single subset $Y$ of $X$ we simply apply \a6 to $B= \t\s(Y)$ and \a5 to $B=\t\s\t\s(Y)$ to conclude $$\s\t\s\t\t\s(Y) \subseteq \s\t\s\t\s\t\s(Y) \subseteq \s\t\t\s\t\s(Y).$$ But both ends of these inclusions equal $\s\t\s(Y)$, so that $\s\t\s\t\s\t\s(Y)=\s\t\s(Y)$. That is, $\s\t\s\t\s\t\s$ and $\s\t\s$ have the same effect on any subset $Y$ in the power set of $X$. That means the functions $\s\t\s\t\s\t\s$ and $\s\t\s$ are equal, so that the complete set (actually semigroup) of functions generated by $\s$ and $\t$ is $$\matrix{ 1, \s, \t\s, \s\t\s, \t\s\t\s, \s\t\s\t\s, \t\s\t\s\t\s,\cr \t, \s\t, \t\s\t, \s\t\s\t, \t\s\t\s\t, \s\t\s\t\s\t, \t\s\t\s\t\s\t\cr}$$ since all longer strings of composites involve $\s\s=\s$, $\t\t=1$, or $\s\t\s\t\s\t\s=\s\t\s$. \bigskip One might think that possibly others among these fourteen operations are equal, but this is not true even for subsets of $X=\R$. Consider, for example, the set $Y=(0,1)\cup(1,2)\cup\{3\}\cup((5,7)\cap\Q)$. For each of the fourteen sets we may create a vector of 0's and 1's indicating whether the points 1, 2, 3, 4, and 6 lie in the set; the fourteen vectors are distinct (observe the conversion from binary, below), showing that the fourteen sets are distinct: $$\matrix{ \hfill Y&=[0, 0, 1, 0, 1]:&\hfill 5&\ \ &\hfill \t(Y)&= [1, 1, 0, 1, 0]:&\hfill 26\cr \hfill \s(Y)&=[1, 1, 1, 0, 1]:&\hfill 29&\ \ &\hfill \s\t(Y)&= [1, 1, 1, 1, 1]:&\hfill 31\cr \hfill \t\s(Y)&=[0, 0, 0, 1, 0]:&\hfill 2&\ \ &\hfill \t\s\t(Y)&= [0, 0, 0, 0, 0]:&\hfill 0\cr \hfill \s\t\s(Y)&=[0, 1, 1, 1, 0]:&\hfill 14&\ \ &\hfill \s\t\s\t(Y)&= [1, 1, 0, 0, 0]:&\hfill 24\cr \hfill \t\s\t\s(Y)&=[1, 0, 0, 0, 1]:&\hfill 17&\ \ &\hfill \t\s\t\s\t(Y)&= [0, 0, 1, 1, 1]:&\hfill 7\cr \hfill \s\t\s\t\s(Y)&=[1, 1, 0, 0, 1]:&\hfill 25&\ \ &\hfill \s\t\s\t\s\t(Y)&= [0, 1, 1, 1, 1]:&\hfill 15\cr \hfill \t\s\t\s\t\s(Y)&=[0, 0, 1, 1, 0]:&\hfill 6&\ \ &\hfill \t\s\t\s\t\s\t(Y)&= [1, 0, 0, 0, 0]:&\hfill 16 }$$ Although $14 < 2^4$, no set of four test points suffices here, and I believe one can show that in any space~$X$, given any subset $Y$ and any list of four points in $X$, the number of distinct 4-tuples which can arise is at most 12. \end