This page is about starting with a finite labeled set and trying to find all possible topologies on that set.
(A related task I would like to pursue, discussed on the page here, would be to work with an unlabeled set to try to list all inequivalent topologies)
I am trying to write a FriCAS program to list all possible topologies of a set. More details about how this program is coded on the page here.
I think I have worked out a suitable algorithm. I think its correct but I don't know how to check for sure. The results look correct and it produces the correct number of topologies as you can see here:
(1) -> #allTopologiesOnSet [1,2,3]
(1) 29
Type: PositiveInteger
(2) -> #allTopologiesOnSet [1,2,3,4]
(2) 355
Type: PositiveInteger
(3) -> #allTopologiesOnSet [1,2,3,4,5]
(3) 6942
Type: PositiveInteger
(4) -> #allTopologiesOnSet [1,2,3,4,5,6]
(in this case a thread ran 100% for 4 hours until I gave up and pressed ^C)
These results agree with the table at the bottom of the Wiki page here: https://en.wikipedia.org/wiki/Finite_topological_space
My code is here: https://github.com/martinbaker/fricasAlgTop/blob/topology/topology.spad
This Wiki page says "There is no known simple formula to compute T(n) for arbitrary n" and forums like this: https://mathoverflow.net/questions/8970/number-of-valid-topologies-on-a-finite-set-of-n-elements seem to suggest that an efficient algorithm is an open problem.
So what am I missing here? Why do they say its so difficult?
The code seems to be efficient (Of course my spad code can be improved but I cant see how the underlying algorithm could be made more efficient). It doesn't generate a lattice of lattices and then filter out valid topologies, instead it recurses directly to the required topologies.
On this page I will first mention a method that would take all possible combinations of open sets and then filter out the combinations that are valid topologies. Then go on to a much more efficient method.
Brute-Force Method
One method would be to:
|
 |
So if we had a lattice of lattices (with the top and bottom elements removed as they all have top and bottom elements) we would need to check 2^(2^n-2)-2 potential topologies.
The number of topologies is massive, even on a small set. The number of invalid topologies will be even larger (we are taking a power set of a power set !) so this method is a very inefficient brute-force algorithm. I looked this up on wikipedia It suggests that finding an efficient algorithm to do this is an unsolved problem.
Birkhoff's representation theorem says that finite distributive lattices can always be represented by sets of sets.
The following diagram attempts to show all the valid topologies that can be made from a 3 element set {A,B,C}. On a 3 element set there are 29 possible topologies. Non-topologies are shown as 'X' (not all of these are shown to keep the diagram simple).
Note that meet is taken to be the intersection of the open sets and join is taken to be the union of the open sets. Such set operations may not produce a valid topology so, for instance,
- The join of two valid topologies may produce an invalid topology.
- The join of two invalid topologies may produce an valid topology.
At the bottom, in red, are all the open sets. Then we generate all combinations of these to get a lattice of lattices. It is drawn in the form of a Hasse diagram (if a line is drawn for x<y and another for y<z then we don't need to draw a line for x<z). Perhaps I should call it a partial lattice of a lattice (or, if we show all invalid lattices, a lattice of partial lattices). I don't think 'partial lattice' is accepted terminology, I just mean a lattice with some meets and joins missing - really a poset.
In this diagram we can see that all the topologies can be generated from the join of lower degree topologies. This may not necessarily be the case for sets bigger than 3 elements? We may need to include invalid topologies.
Alternative More Efficient Method
This code grades the power set and then takes the power set of each grade separately (which is a lot less than the elements traversed on the previous method) and it does not recurse to the next grade for cases where the required meets and joins don't exist so it cuts out the invalid cases at an early stage.
In this algorithm we build up potential topologies from open sets with only one element. In this way we do not have to traverse the whole powerset because the lower degree open sets put restrictions on what the
| Start with the singletons, these potential topologies are made up of open sets with just one element. Each of the boxes on the right is intended to represent a potential topology. |  |
Now we can try to add higher degree open sets. So now try to add open sets with 2 elements. There are restrictions on which open sets we can add. If our potential topology has open sets {A} and {B} then the topology must have {A,B} due to the 'join' requirement. |
 |
 |
Also there are restrictions on the combinations of 2 element open sets, for example, we can only have both {A,B} and {B,C} if we have a singleton {B} due to the 'meet' requirement. |
 |
I am therefore looking for a different method for generating all topologies. Here I start with all combinations of the singletons {A},{B} and {C}. For a given combinations of these we can work out which 2-element sets: {A,B}, {B,C} and {A,C} can be included.
|
 |
From wikipedia page this is how many topologies for each size of set.
| cardinality of set | Distinct topologies | Distinct T0 topologies | Inequivalent topologies | Inequivalent T0 topologies |
|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 |
| 2 | 4 | 3 | 3 | 2 |
| 3 | 29 | 19 | 9 | 5 |
| 4 | 355 | 219 | 33 | 16 |
| 5 | 6942 | 4231 | 139 | 63 |
| 6 | 209527 | 130023 | 718 | 318 |
| 7 | 9535241 | 6129859 | 4535 | 2045 |
| 8 | 642779354 | 431723379 | 35979 | 16999 |
| 9 | 63260289423 | 44511042511 | 363083 | 183231 |
| 10 | 8977053873043 | 6611065248783 | 4717687 | 2567284 |
The papers about enumeration of finite topologies seem to use different representations.
- For example this one uses transitive digraphs: https://dl.acm.org/doi/pdf/10.1145/363282.363311
- and this one uses semi-tensor products of matrices: https://www.mdpi.com/2227-7390/10/7/1143
- https://en.wikipedia.org/wiki/Finite_topological_space
- https://www.amazon.com/Algebraic-Topology-Topological-Applications-Mathematics/dp/3642220029/ref=sr_1_1
