Topology, Separation and finite combinatorics

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. :-)

This entry was posted in Numbers are hard on by .

One thought on “Topology, Separation and finite combinatorics

  1. Veky

    > 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

    Yes, it is indeed the case. The trick for reduction of GI to PI is to consider the incidence relation on disjoint union V(G)UE(G) as a partial order.

Comments are closed.