FiniteTop: The Naive Approach

January 26, 2010

FiniteTop is a short program I wrote in C++ to calculate the number of topologies on a finite set. Compile with:

g++ main.cpp Binvector.cpp

And use with

./a.out x

where x is the size of the set for which you wish to calculate the number of topologies. I have compiled and tested it under Linux, but it should compile under any system with a reasonable C++ compiler.

It has many limitations, but the most practical of which is that it will only work reasonably for x = 0,1,2,3,4,5 and for x = 5 it will probably take an hour or so. For x = 6 there really is no hope; certainly it its state it will take longer than ten times your lifetime unless you have some crazy computer.

It's slow because it goes through each possible subset of P(X) and checks whether it satisfies the axioms for a topological space. Note that in the finite case we need only check for closure under finite unions, and thus we need only check whether the union of two elements is again an element. Practically, there is no gain since the sequence from n = 0,...,18 can already be found here, where the first few terms are 1, 1, 4, 29, 355, 6942, 209527, 9535241, 642779354, 63260289423, 8977053873043, 1816846038736192, 519355571065774021,207881393656668953041.

However, the program is reasonably readable and uses a small vector data structure, and so you might like to take a look if you're interested in representing finite topological spaces in a computer, and taking unions and intersections of open sets. If anyone is interested in the source, send me an email and I will write a short explanation about it.

FiniteTop is licensed under the GPLv3.

Known bugs

Won't check more than 2^31-1 cases. It's a bit strange because integer values (seemingly) aren't needed to keep track of all the cases, but I must have a hidden dependence on an int somewhere.