In fact, for any finite topological space [tex]X[/tex] we have that [tex]w(X) = |X|[/tex].

Proof: For any point [tex]x[/tex] define [tex]U_x[/tex] to be the intersection of all open sets containing [tex]x[/tex]. The set [tex]{ U_x : x in X }[/tex] is a basis for the topology of [tex]X[/tex] of cardinality [tex]|X|[/tex].

See here for far more details.

Warning: This post isn’t really of an expository nature. It’s more me rambling for my own benefit about something I find interesting. It isn’t in any especially coherent order. You might find this interesting, or you might not.

A while ago I claimed that all interesting topological spaces were Hausdorff. Even then I knew this wasn’t really the case – for example the algebraic geometers’ Spec is almost never Hausdorff, or even [tex]T_1[/tex] (a prime ideal is closed iff it’s maximal). What I really mean of course is interesting for my purposes – Hausdorff is precisely the requirement that limits are unique (in an appropriate sense), and given that most of the stuff studied in analysis is concerned with limits, this seemed to me to be a fairly compelling argument that Hausdorff was an extremely important condition.

One seperation axiom that really is required in order for a topological space to be ‘interesting’ is that of being [tex]T_0[/tex]. Two points x and y are said to be indistinguishable iff they’re contained in precisely the same open sets. Equivalently they’re indistinguishable iff [tex]overline{ { x } } =overline{ { y } }[/tex]. Topologically speaking, you can’t tell the difference between indistinguishable points. A space is [tex]T_0[/tex] if it has no distinct indistinguishable points.

Of course, one might argue that there are examples of spaces with additional structure which might distinguish these points. So from that perspective there is certainly worth in studying spaces which are [tex]T_0[/tex]. But, from a topological perspective, this is essentially the same as studying their Kolmogorov quotient, which is [tex]T_0[/tex].

The Kolmogorov quotient is defined in an obvious way. Indistinguishability of points is an equivalence relation. Put the quotient topology on the set of equivalence classes. This is the Kolmogorov quotient of the space. It is universal in the sense that if [tex]X[/tex] is a topological space and [tex]kX[/tex] is its Kolmogorov quotient then any map [tex]f : X to Y[/tex], where Y is [tex]T_0[/tex], factors uniquely through the quotient map [tex] pi : X to kX [/tex].
Usually if we have some algebraic structure compatible with the topology then the Kolmogorov quotient will inherit this.

For example, suppose we have a topological group [tex]G[/tex] which may not be [tex]T_0[/tex]. Some minor faffing will show that x and y are equivalent iff [tex]x y^{-1} in overline{ { e } }[/tex]. In particular the group is [tex]T_0[/tex] iff the identity (and so every point) is closed.

The closure of the identity is a closed normal subgroup of [tex]G[/tex], and so we can quotient by it to get a topological group in which the identity is closed. Further, this quotient is precisely the Kolmogorov quotient of [tex]G[/tex]. So, as promised, the Kolmogorov quotient inherits a natural algebraic structure.

As an aside note, if a topological group is [tex]T_1[/tex] then it is Hausdorff, as the diagonal is the preimage of the identity under the map [tex](x, y) to x y^{-1}[/tex] and so is closed. Another reason why I thought Hausdorff spaces were really the appropriate setting for what I was doing (and while I still maintain that Hausdorff is part of the definition of topological group).

One thing that seems to be the case is that the theories of Hausdorff and non-Hausdorff topological spaces seem to be very different – definitions important in one either don’t work or become essentially trivial in the other. Almost everything you’d normally file under ‘point-set topology’ is a bit uninteresting or downright wrong when you start weakening separation conditions.

All that being said, some rather cool stuff does happen in the case where your spaces fail to be [tex]T_1[/tex].

Let [tex]X[/tex] be some topological space. For [tex]x, y in X[/tex] define [tex]x prec y[/tex] if [tex]x in overline{ { y } }[/tex]. Then this is a preorder on [tex]X[/tex], and it’s a partial order precisely when [tex]X[/tex] is [tex]T_0[/tex].

Now, in the familiar cases where the spaces are [tex]T_1[/tex] this tells you precisely bugger all about your underlying topologies – the resulting partial order is just a great big antichain.

But in the case where [tex]X[/tex] is finite, this tells you everything about the topological space. Remember that there’s only one [tex]T_1[/tex] topology on a finite set – the discrete topology.

Suppose you know the preorder [tex]prec[/tex] on [tex]X[/tex]. Then for each point [tex]x[/tex] you know what [tex]overline{ { x } }[/tex] is. So for any [tex]A subseteq X[/tex] you have that [tex]overline{A} = bigcuplimits_{x in A} overline{ {x} }[/tex]. So you know the closure operator, and so the topology, precisely.

Another way of looking at this is that given a preorder on a set [tex]X[/tex] you can form a topology on [tex]X[/tex] by taking [tex]A subseteq X[/tex] to be closed iff it is downward closed (i.e. if [tex]x in A[/tex] and [tex]y prec x[/tex] then [tex]y in A[/tex]), or the open sets to be the upwards closed sets. In the finite case composing this with the above construction gives you back the original topology on [tex]X[/tex].

Note that both of these constructions are functorial. I suspect they form an adjoint pair of some sort, but have yet to work out the details. In the finite case they are an isomorphism of categories.

This is cool. Finite topological spaces are precisely the same thing as finite preorders (and finite [tex]T_0[/tex] spaces precisely the same as finite partial orders). This is related to why we have such a hard time of enumerating the finite topological spaces – because enumerating the finite partial orders is hard (and I think determining if two of them are isomorphic is NP-complete – it is after all essentially a not very special case of graph isomorphism).

Note that this construction, in the infinite case, gives us a topology whose open sets are closed under arbitrary intersection, as a consequence of which [tex]overline{A} = bigcuplimits_{x in A} overline{ {x} }[/tex] holds in general. These are called Alexandroff topologies. They are of course [tex]T_1[/tex] iff they’re discrete. (Compact examples of?) these are supposed to be the natural infinite generalisation of finite topological spaces.

One thing we do in point-set topology is look at cardinal invariants of topological spaces. These don’t behave all that well when they’re finite, so we often redefine them to take [tex]aleph_0[/tex] as their minimum value. That way we can avoid inconvenient nonsenses like numbers for which we have [tex]x^2 > x[/tex] or [tex]x+1 not= x[/tex]. Silly things like those. On the other hand, the basic definitions more or less work and I was curious as to how they look in the finite example.

Two important ones are the density [tex]d(X)[/tex], the smallest cardinality of a dense subset, and the cellularity [tex]c(X)[/tex], the sup of the cardinalities of a pairwise disjoint collection of open sets (In the finite case I’m going to require the sets to be non-empty. In the infinite case this is irrelevant because [tex]x + 1 = x [/tex]).

For any topological space we have [tex]c(X) leq d(X)[/tex] – every non-empty open set contains an element of any given dense set, and if two sets are disjoint they can’t contain the same element. For metric spaces they are always equal, but in general they can be arbitrarily far apart.

Curiously, it turns out for finite topological spaces they’re also always equal. The reason is as follows.

In a finite topological space, every element is covered by some maximal element of the space – an [tex]x[/tex] such that [tex]x prec y implies x = y[/tex]. Thus the set of maximal [tex]x[/tex] is dense in [tex]X[/tex]. Now, any dense set [tex]A subseteq X[/tex] must contain this set, because for each maximal [tex]x[/tex] there is [tex]y in A[/tex] with [tex]x prec y[/tex], and so [tex]x = y[/tex]. Thus the collection of maximal elements of [tex]X[/tex] is a dense set of minimal cardinality.
Now, for [tex]x[/tex] maximal we have [tex]x notin overline{{ y }}[/tex] for [tex]y not= x[/tex]. Thus the complement of [tex]{ x }[/tex] is closed, and [tex]{ x }[/tex] is open. Thus the set of singletons of maximal elements of [tex]X[/tex] is a pairwise disjoint collection of open subsets of [tex]X[/tex]. Hence we have [tex]c(X) geq d(X)[/tex] and so [tex]c(X) = d(X)[/tex].

Another important cardinal invariant is the weight. The weight of [tex]X[/tex] is the smallest cardinality of a basis of [tex]X[/tex]. I originally thought there wasn’t much interesting to say about this in the finite case, but on the tube home today I noticed I was wrong.

For finite [tex]T_0[/tex] spaces the weight satisfies [tex]w(X) geq |X|[/tex].

The proof of this is a fairly trivial induction. Suppose [tex]|X| = n + 1[/tex] and the result holds for every space of cardinality [tex]n[/tex]. Let [tex]B[/tex] be a basis for [tex]X[/tex]. By our previous observation, [tex]X[/tex] contains an open point [tex]x[/tex]. Because the singleton [tex]{ x }[/tex] is open it must contain a basis element, and so must in fact be a basis element. Let [tex]C= {U setminus { x } : U in (B setminus { { x } } ) }[/tex]. Then [tex]C[/tex] is a basis for [tex]X setminus { x }[/tex], which is a space of cardinality [tex]n – 1[/tex]. Hence by our inductive hypothesis we have [tex]|C| geq n – 1[/tex] and so [tex]|B| geq |C| + 1 geq n[/tex].

A couple of notes on this: Obviously the [tex]T_0[/tex] hypothesis is neccesary, as the indiscrete topology on any set shows. This inequality is the best possible, as the discrete topology shows (there are other examples. e.g. the sierpinski space).
This latter inequality is very much a special property of finite topologies. In general there are no good inequalities between [tex]|X|[/tex] and [tex]w(X)[/tex]. For compact Hausdorff spaces we have [tex]w(X) leq |X|[/tex].

Finally, I am of course probably reinventing the wheel with all of this. I’ve no illusions that any of this is remotely new, but equally I’ve got no relevant sources except a couple random posts on the web about finite topological spaces. :-)

I seem to be undergoing a bit of a blog diaspora at the moment.

The latest instance of this is that, thanks to the generosity of my friends David Jao and Mikael Johansson, A Mathematician’s Scratchpad can now be found here, where I’ll be using wordpress 2.0 and – most importantly – LaTeXRender. This way the formulae in my posts can actually be readable.

I’ve got a copy of the pressing down lemma post up at the moment, but it still needs a bit more editing. Converting this crappy ascii mathematics into LaTeX turns out to bea lot of work.

The pressing down lemma is a ridiculously useful technical lemma from combinatorial set theory. It’s amazing how often you can just set up some machinery, apply the pressing down lemma, and poof. A solution pops out. I’m going to give a simplified version of the lemma and show two nice applications of it to general topology. There are various almost immediate generalisations of the version I’m going to give, but they require me to introduce more new ideas than I want to, and this version will suffice.

Let \(\omega_1\) be the first uncountable ordinal. A function \(f : \omega_1 \to \omega_1 \) is said to be regressive if for every \(x > 0\) we have \(f(x) < x\).

The pressing down lemma: Every regressive \(f : \omega_1 \to \omega_1\) is constant on some unbounded set.
Proof:

Suppose for every \(t < \omega_1\) we had that \(f^{-1}( {t} )\) was bounded. Let \(g(t) = \sup f^{-1} ( { t } )\). Note that if \(x \neq 0 \) and \( x \in f^{-1} ( { t } )\) then \(t = f(x) < g(t)\) (and trivially \(g(0) \neq 0\), so we have \( \forall t t < g(t) \) ). We define a sequence \(x_n\) as follows. Let \(x_0 = 0\). Let \(x_{n+1} = \sup { g(t) : t \leq x_n }\) (there are only countably many \(t \leq x_n\), so this set is bounded above). Now, in particular we have \(x_{n+1} \geq g(x_n) > x_n\)

Now, let \(x = \sup x_n\). We have that \(f(x) < x\), and so that\( f(x) < x_k\) for some k. But then\( x \in g(f(x))\) and so \( x_{k+1} \geq x \) and thus \( x_{k+2} > x \), contradicting that \(x = \sup x_n\).

QED

Note that there’s something special going on here. If we define \(f : \omega \to \omega\) by \(f(0) = 0\) and \(f(n) = n – 1\) for \(n > 0\) then this is a regressive function for which the largest set it is constant on is \({0, 1}\). The pressing down lemma is a genuinely new property of the uncountable case.

Now, let’s give an application of this:

Theorem: Give \(\omega_1\) the order topology and let \(f : \omega_1 \to \mathbb{R}\) be continuous. Then \(f\) is eventually constant (i.e. there is some \(t \in \omega_1\)) such that \(f\) is constant on \([t, \infty)\) ).

Proof:

\(f\) is continuous, so for every t there is some neighbourhood of t such that for s in this neighbourhood we have \(|f(s) – f(t)| < 2^{-(n+1)}\). In particular if \(t > 0\) there is some \(k < t\) such that whenever \(k < s < t\) we have \(|f(s) – f(t)| < 2^{-(n+1)}\). Let \(f(t)\) be the least such \(k\). (and \(f(0) = 0\)). Now, f is regressive, so it’s constant on some unbounded set.

i.e. we can find \(k < \omega_1\) and an unbounded set of \(x\) such that for \(k < s < x\) we have \(|f(s) – f(x)| < 2^{-(n+1)}\). In particular this works for \(k^+\), so we have that \(|f(s) – f(k^+)| \leq 2^{-(n+1)} + 2^{-(n+1)} = 2^{-n}\). Now, because the set of \(x\) for which this works is unbounded, for any s > k we can find x > s for which this works, and so \(|f(s) – f(k^+)| \leq 2^{-n}\)

So, we can find \(t_n\) such that for any \(s \geq x\) we have \(|f(s) – f(t_n)| \leq 2^{-n}\). Let \(t = \sup t_n\).

Now, we have from the above that \(f( [t, \infty) )\) has diameter \(\leq 2^{-n}\) for every \(n\), and so has diameter 0. i.e. it consists of a single point. Hence \(f\) is eventually constant.

QED

Neat, huh? There was essentially no work in there other than trying to figure out how to apply the pressing down lemma.

The next bit is a tiny bit more work, and won’t apply the pressing down lemma directly. Instead we’ll procede via another cool and important lemma in combinatorial set theory.

A collection of sets F is said to be a \(\Delta\)-system with root I if for every distinct \(A, B \in F\) we have \(A \cap B = I\). Note that \(I\) is allowed to be empty.

The \(\Delta\)-system lemma:

Let F be an uncountable collection of finite sets. F contains an uncountable \(\Delta\)-system.

Proof:

By passing to a subset we may assume that |F| = aleph_1. Further we then have that \(|\bigcup F| = \aleph_1\), so by taking an appropriate bijection we may assume that \(\bigcup F \subseteq \omega_1\) and contains no finite ordinals.

Now, enumerate F as \({ U_t : t < \omega_1 }\)

For each \(t < \omega_1\) define \(f(t) = \max ( \{0\} \cup (U_t \cap t ) )\) (this set is finite, so has a maximum). Then \(f\) is regressive. (When \(t\) is finite you need the fact that we choose the \(U_t\) so that they contained no finite ordinals, else you might have \(t \subseteq U_t\)). So, by the pressing down lemma, is constant on some unbounded set. So, we have an ordinal s and an unbounded set A such that for \(t \in A\) we have \(\max { U_t \cap t } = s\). In particular \(U_t \cap t \leq s\). Now, \(s\) is countable, and for every \(t\) we have that \(U_t \cap t\) is a finite subset of \(s\). There are only countably many finite subsets of \(s\), and A is uncountable, so for some finite \(R \subseteq s\) we must have that \(U_t \cap t = R\) for uncountably many \(t \in A\). Fix some such R and let A’ be the set of \(t \in A\) such that \(U_t \cap t = R\). Now, by transfinite induction we pick an \(\omega_1\) sequence x_t such that \(x_t\) is in A’ and \(x_t > \sup \bigcup\limits_{s \in A ‘, s < t} F_t\). Let \(D\) be the image of this sequence. Now for \(s, t \in D\) if \(s < t\) we have that \(\max U_s < t\).

Now, let \(s, t \in D\). Say \(s < t\). Then \(U_s \cap U_t = (U_s \cap t) \cap U_t\), because \(U_s \subseteq t\). Thus \(U_s \cap U_t \subseteq U_s \cap (U_t \cap t) = U_s \cap R \subseteq R\). But we know that \(R \subseteq U_s \cap U_t\), because we have that \(R \subseteq U_s \cap s \subseteq U_s\) and \(R \subseteq U_t \cap t \subseteq U_t\).

Hence \(\{ U_t : t \in D \}\) is our desired \(\Delta\)-system, and has root \(R\).

QED

Phew. I have to admit, I don’t think this proof is substantially easier than the proof without the pressing down lemma. However it’s not any harder, and the use of the pressing down lemma clears away a lot of the ugly details.

So. Why do we care about these things? A number of reasons actually, but I don’t know many of them. I’m going to use it to prove the following topological result.

First a definition. A topological space is said to be ccc (countable chain condition) if every pairwise disjoint collection of open sets is countable.

Why do we care about this? Well, it has important connections to the theory of Boolean algebras, and it’s often a good way to test if something is separable – any separable space is ccc, and it’s often easy to see if a space is not ccc. Seeing if it *is* ccc can sometimes be a bit more subtle, and that’s something this theorem will help with. Additionally, it is just a special case of one of the many cardinal invariants we can use to study topological spaces, and it’s one which is remarkably well behaved.

Theorem: Let \({ A_t : t \in I }\) be a collection of topological spaces such that every finite product of them is ccc. Then \(\prod A_t\) is ccc. In particular a product of separable spaces is ccc.

Proof:

This is almost an immediate consequence of the \(\Delta\)-system lemma. Suppose F was an uncountable set pairwise disjoint open subsets of \(A = \prod A_t\). Then we can replace each element of F with some basis element contained in it. Each of these basis elements is a product of open sets \(U_t\) such that for all but finitely many t we have \(U_t = A_t\). Let G be the collection of sets of the form \({ t : U_t \neq A_t }\) for \(\prod U_t \in F\). Then this is an uncountable collection of finite sets, so it contains a \(\Delta\)- system. Say \(D \subseteq G\) is a \(\Delta\)-system with root R.

Now, R is some finite subset of I. So consider \(\prod_{t \in R} U_t\), where the \(U_t\) are chosen from F such that \({ t : U_t \neq A_t }\) is in D. Then because we have that \(\prod U_t \cap \prod V_t = \prod (U_t \cap V_t)\) we have that the products \(\prod_{t \in R} U_t\) are pairwise disjoint (since \(U_t \cap U_t’ \neq \emptyset\) for \(t \not\in R\), as at least one of \(U_t, U_t’\) is equal to \(A_t\)). So we’ve got an uncountable collection of pairwise disjoint open subsets of \(\prod_{t \in R} A_t\), contradicting the hypothesis that all finite products of the \(A_t\) are ccc.

The ‘in particular’ then follows from the fact that separable spaces are ccc, and finite products of separable spaces are separable.

QED

Neat, huh?

As a quick application of this result, recall that every second countable compact Hausdorff space is the continuous image of \(\{0, 1\}^{\mathbb{N}}\) – the Cantor set. This shows that we can’t directly generalise this, because the theorem proves that for any \(A\) we have that \(\{0, 1\}^A\) is ccc. Easy check: The continuous image of a ccc space is ccc. Thus, for example, \(\omega_1 + 1\) with the order topology is not the continuous image of \(\{0, 1\}^A\) for any A, because it is not ccc (this is also easy to check).

There is a generalisation of this result about the Cantor set, but that’s a story for another day.

I swear this was supposed to be Silly proofs three, but obviously my memories of having done two silly proofs are misleading.

This proof isn’t actually that silly. It’s a proof of the L^2 version of the Fourier inversion theorem.

We start by noting the following important result:

Int_{-inf}^{inf} e^{itx} e^{-x^2/2} = sqrt{2 pi} e^{-t^2/2}

Thus if we let h_0 = e^{-x^2}/2 then we have h_0^ = h_0 (where ^ denotes the fourier transform)

Let h_n(x) = (-1)^n e^{x^2/2} d^n/dx^n (e^{-x^2})

This satisfies:

h_n’ – xh_n = -h_{n+1}

So taking the Fourier transform we get

ix h_n^ – i (h_n^)’ = -h_{n+1}^

So, h_n and (-i)^n h_n^ satisfy the same recurrence relation. Further h_0^ = h_0.

Hence we have that h_n^ = (-i)^n h_n

Now, the functions h_n are orthogonal members of L^2, and so form an orthonormal basis for their span.

On this span we have the map h -> h^ is a linear map with each h_n an eigenvector. Further h_n^^ = (-1)^n h_n. Thus the fourier transform is a linear isometry from this space to itself.

Now, h_n is odd iff n is odd and even iff n is even. i.e. h_n(-x) = (-1)^n h_n

Thus h_n^^(x) = (-1)^n h_n(-x)

And hence h^^(x) = (-1)^n h(-x) for any h in the span. As both sides are continuous, it will thus suffice to show that the span of the h_n is dense.

Exercise: The span of the h_n is precisely the set of functions of the form p(x) e^{-x^2 / 2}

It will thus suffice to prove the following: Suppose f is in L^2 and Int x^n e^{-x^2 / 2} f(x) dx = 0 for every x. Then f = 0.

But this is just an easy application of the density of the polynomial functions in L^2[a, b] (pick a big enough interval so that the integral of |f(x)|^2 over that interval is within epsilon^2 of ||f||^2, and this shows that the integral of |f(x)|^2 over that interval is 0. Thus ||f||_2 < epsilon, which was arbitrary, hence ||f||_2 = 0). I’ve dodged numerous details here, like how the L^2 Fourier transform is actually defined, but this really can be turned into a fully rigorous proof – nothing in this is wrong, just a little fudged. The problem as I see it is that – while the L^2 Fourier theory is very pretty and cool – this doesn’t really convert well to a proof of the L^1 case, which is the more important one.