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 w1<w2 and w1>w2). 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