7
$\begingroup$

I've seen that there is currently no known formula for the amount of distinct topologies on a finite set. However I was wondering there are some rough estimates, aside from the trivial ones on the amount.

Given a finite set $X$ of cardinality $n$ we have the trivial upper bound of $2^{2^n}$. I was wondering whether there are some stronger estimates. In particular, I was wondering whether one can show there are less topologies on $X$ then there are relations on $X\times X$? i.e:

Can we say that it is larger than $2^{n^2}$ or smaller than $2^{n^2}$?

I would also welcome any help in estimates for an infinite set $X$.

$\endgroup$
1

2 Answers 2

10
$\begingroup$

See The number of finite topologies by Kleitman and Rothschild. If $T_n$ is the number of topologies on a set with $n$ elements, they show that $$\log_2 T_n\sim n^2/4$$ This is quite an old paper and there may be a better asymptotic formula at this point. Asymptotically, the logarithm of the number of topologies is also equal to the logarithm of the number of partial orders on the set. The same authors have a sequel to the paper that gives a better formula for the number of partial orders, but without the logarithm I believe they cease to be asymptotically equal.

$\endgroup$
4
  • $\begingroup$ Are you referring to this article? researchgate.net/publication/… $\endgroup$ Jul 7, 2019 at 17:57
  • $\begingroup$ @Keen Yes. I guess I was remembering the wrong title. $\endgroup$ Jul 7, 2019 at 18:01
  • $\begingroup$ The paper shows that asymptotically the number of relations on $[n]\times [n]$ is larger than the number of topologies on $[n]$, but can we also say that this holds true always? $\endgroup$ Jul 9, 2019 at 12:03
  • 2
    $\begingroup$ @Keen yes, according to the other answer. $\endgroup$ Jul 9, 2019 at 12:06
5
$\begingroup$

On a finite set $S$, the topology is uniquely determined by the closures of singletons: A subset of $S$ is closed iff it contains the closure of all its elements. Given a topology, we can define $$\tag1a\le b\iff \overline{\{a\}}\subseteq \overline{\{b\}}$$ (or equivalently, $a\in \overline{\{b\}}$). This need not be a partial order because we can have $a\le b$ and $b\le a$ with $a\ne b$. But it is a reflexive and transitive relation on $S$.

On the other hand, from a a reflexive and transitive relation $\le$ on $S$, we can define a topology by declaring $$\tag2 A\text{ closed}\iff\forall a\in A\colon \forall x\in S\colon x\le a\to x\in A.$$ One verifies that the union or intersection of two closed sets is closed and trivially $\emptyset$ and $S$ are closed.

Moreover, the associations topology $\leftrightarrow$ reflexive transitive relation in $(1)$ and $(2)$ are inverse of each other, hence

On a finite set, there are as many topologies as there are reflexive transitive binary relations.

The relation to partial orders is that a reflexive transitive binary relation on $S$ is the same as a partial order on a partition of $S$. In particular, if the counts of topologies and partial orders are $T_n$ and $P_n$, respectively, we have $$ T_n=P_n+{n\choose 2}P_{n-1}+\left({n\choose 3}+\frac12{n\choose 2}{n-2\choose 2}\right)P_{n-2}+\ldots+2^{n-1}P_2+P_1.$$

$\endgroup$
2
  • $\begingroup$ Is the highlighted result not also true for infinite sets? Or does (2) not describe a general topology. $\endgroup$ Jul 10, 2019 at 14:09
  • 1
    $\begingroup$ @Keen This fails for infinite sets because the union of infinitely many closed sets might not be closed. $\endgroup$ Jul 10, 2019 at 20:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .