On the number of topologies on a finite set
We denote the number of distinct topologies which can be defined on a set X with n elements by T(n). Similarly, T0(n) denotes the number of distinct T₀ topologies on the set X. In the present paper, we prove that for any prime p, T(pᵏ) ≡ k + 1 (mod p), and that for each natural number n there exists...
Gespeichert in:
| Veröffentlicht in: | Algebra and Discrete Mathematics |
|---|---|
| Datum: | 2019 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Englisch |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2019
|
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/188421 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | On the number of topologies on a finite set / M.Y. Kizmaz // Algebra and Discrete Mathematics. — 2019. — Vol. 27, № 1. — С. 50–57. — Бібліогр.: 8 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859937058909323264 |
|---|---|
| author | Kizmaz, M.Y. |
| author_facet | Kizmaz, M.Y. |
| citation_txt | On the number of topologies on a finite set / M.Y. Kizmaz // Algebra and Discrete Mathematics. — 2019. — Vol. 27, № 1. — С. 50–57. — Бібліогр.: 8 назв. — англ. |
| collection | DSpace DC |
| container_title | Algebra and Discrete Mathematics |
| description | We denote the number of distinct topologies which can be defined on a set X with n elements by T(n). Similarly, T0(n) denotes the number of distinct T₀ topologies on the set X. In the present paper, we prove that for any prime p, T(pᵏ) ≡ k + 1 (mod p), and that for each natural number n there exists a unique k such that T(p + n) ≡ k (mod p). We calculate k for n = 0, 1, 2, 3, 4. We give an alternative proof for a result of Z. I. Borevich to the effect that T₀(p + n) ≡ T₀(n + 1) (mod p).
|
| first_indexed | 2025-12-07T16:09:39Z |
| format | Article |
| fulltext |
“adm-n1” — 2019/3/22 — 12:03 — page 50 — #58
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 27 (2019). Number 1, pp. 50–57
c© Journal “Algebra and Discrete Mathematics”
On the number of topologies on a finite set
M. Yasir Kizmaz
Communicated by V. Lyubashenko
Abstract. We denote the number of distinct topologies
which can be defined on a set X with n elements by T (n). Similarly,
T0(n) denotes the number of distinct T0 topologies on the set X.
In the present paper, we prove that for any prime p, T (pk) ≡ k +
1 (mod p), and that for each natural number n there exists a unique k
such that T (p+ n) ≡ k (mod p). We calculate k for n = 0, 1, 2, 3, 4.
We give an alternative proof for a result of Z. I. Borevich to the
effect that T0(p+ n) ≡ T0(n+ 1) (mod p).
1. Introduction
Given a finite set X with n elements, let T(X) and T0(X) be the family
of all topologies on X and the family of all T0 topologies on X, respectively.
We denote the cardinality of T(X) by T (n) and the cardinality of T0(X)
by T0(n). There is no simple formula giving T (n) and T0(n).
Calculation of these sequences by hand becomes very hard for n > 4.
The online encyclopedia of N. J. A. Sloane [1] gives the values of T (n)
and T0(n) for n 6 18. For a more detailed discussion of results in the
literature, we refer to the article by Borevich [4].
In the present paper, we prove that for any prime p, T (pk) ≡ k +
1 (mod p), and that for each natural number n there exists a unique k
such that T (p+ n) ≡ k (mod p). We calculate k for n = 0, 1, 2, 3, 4. We
give an alternative proof for a result of Z. I. Borevich [5] to the effect that
T0(p+ n) ≡ T0(n+ 1) (mod p). Our results depend on basic properties
of group action, which is the first time used in this problem as far as the
author is aware.
2010 MSC: Primary 11B50, Secondary 11B05.
Key words and phrases: topology, finite sets, T0 topology.
“adm-n1” — 2019/3/22 — 12:03 — page 51 — #59
M. Y. Kizmaz 51
2. Main results
Let G be a group acting on the finite set X. Then the action of
G on X can be extended to the action of G on T(X) by setting gτ =
{gU | U ∈ τ} where τ ∈ T(X) and gU = {gu | u ∈ U}. Now set
Fix(T(X)) = {τ ∈ T(X) | gτ = τ for all g ∈ G}. Notice that if G is
a p-group, |T(X)| ≡ |Fix(T(X))| (mod p) as every non-fixed element
of T(X) has orbit of length a positive power of p. For a given topology
τ ∈ T(X) and x ∈ X, we denote the intersection of all open sets of τ
including x by Ox. Note that Ox ∈ τ as we are in the finite case.
Definition 1. A base B of a topology τ is called a minimal base if any
base of the topology contains B.
Example. Let X = {a, b, c} be a set and let τ be a topology on X
with τ = {∅, {a}, {a, b}, {a, c}, {a, b, c}}. Now if B is an arbitrary base
for τ then we have U =
⋃
x∈U Bx where U ∈ τ and Bx ∈ B such that
x ∈ Bx ⊆ U . Thus, we observe that B′ = {{a}, {a, b}, {a, c}} ⊆ B.
Moreover, B′ is also a base for τ which implies that B′ is a minimal base
for τ .
Proposition 1. Let τ ∈ T(X) and Mτ be the set of all distinct Ox for
x ∈ X. A base B of τ is a minimal base if and only if B = Mτ .
By the proposition, we extend the definition: a base B on X is minimal
if B = Mτ where τ is the topology generated by B.
Lemma 1. τ ∈ Fix(T(X)) if and only if Mτ is G-invariant.
Proof. Let τ ∈ Fix(T(X)) and Ox ∈ Mτ . We need to show that gOx ∈ Mτ .
Let gx = y for g ∈ G. As gτ = τ , gOx ∈ τ . Thus, gOx is an open set
containing the element gx = y. Hence, Oy ⊆ gOx. Since g−1y = x,
we can show that Ox ⊆ g−1Oy which forces gOx = Oy. So, gOx ∈
Mτ ∀g ∈ G. Now assume that Mτ is G-invariant. For each U ∈ τ , we
have U =
⋃
x∈U Ox. Then gU ∈ τ as gOx ∈ Mτ for all g ∈ G, and hence
τ ∈ Fix(T(X)).
Theorem 1. Let p be a prime and let k be a natural number. Then
T (pk) ≡ k + 1 (mod p).
Proof. Without loss of generality, let X be the cyclic group of order pk,
that is, X = Cpk . Clearly X acts on X by left multiplication. By extending
“adm-n1” — 2019/3/22 — 12:03 — page 52 — #60
52 On the number of topologies on a finite set
this action, X acts on T(X). Notice that |T(X)| ≡ |Fix(T(X))| (mod p)
as X is a p-group. It is left to show that Fix(T(X)) has k + 1 elements.
Let τ ∈ Fix(T(X)) and let Ox, Oy ∈ Mτ for x, y ∈ X. Then (yx−1)Ox
is an open set including y. Hence,Oy ⊆ (yx−1)Ox which means |Oy| 6 |Ox|.
The other inclusion can be done similarly so |Ox| = |Oy| for all x, y ∈ X.
Now if m ∈ Ox ∩ Oy, then Om ⊆ Ox ∩ Oy. As their orders are equal,
we must have Ox = Oy or Ox ∩ Oy = ∅. Thus, X is a disjoint union of
elements of Mτ , that is, X =
⋃·Ox∈Mτ
Ox. It follows that |X| = |Mτ ||Ox|
for any x ∈ X.
Note that X also acts on Mτ by Lemma 1. Let e be the identity
element of X and Stab(Oe) be the stabilizer of Oe in the action of X
on Mτ . Then we obtain that |X : Stab(Oe)| = |Mτ | as the action is
transitive. It follows that | Stab(Oe)| = |Oe| as |X| = |Mτ ||Oe| also holds.
Since our action is induced from left multiplication in the group X, the
product Stab(Oe)Oe is exactly set multiplication in the group X. Then we
obtain that Oe = Stab(Oe)Oe ⊇ Stab(Oe)e = Stab(Oe). But the equality
|Oe| = | Stab(Oe)| forces that Oe = Stab(Oe).
Hence, the set Mτ is the set of left cosets of a subgroup of X. Since
the chosen topology τ from Fix(T(X)) uniquely determines Mτ and Mτ
uniquely determines a subgroup Oe of X, we have an injection from
Fix(T(X)) to the set of all subgroups of X. Conversely, for a subgroup
H of X, the set of left cosets of H forms an X-invariant minimal base
for a topology. The topology τ generated by this base is an element of
Fix(T(X)) by Lemma 1. Hence, the cardinality of Fix(T(X)) is equal to
the number of the subgroups of X, which is k + 1.
By applying the same method in the above proof, we can also show
that T0(p
k) ≡ 1 (mod p). Actually, Z. I. Borevich proved a more general
result about T0(n). Now we establish an alternative proof for the theorem
of Z. I. Borevich.
Theorem 2 (Z. I. Borevich). Let p be a prime. If k ≡ l (mod p−1), then
T0(k) ≡ T0(l) (mod p).
Proof. It is equivalent to show that T0(n+ p) ≡ T0(n+ 1) (mod p) for an
integer n > 0. Let C = Cp be the cyclic group of order p and N be a set
with n elements. Without loss of generality, let X be the disjoint union of
C and N so that the cardinality of X is p+ n. We define the action of C
on X in the following way: for c ∈ C and for x ∈ X, c ∗ x = cx if x ∈ C
and c ∗ x = x if x ∈ N . Then the action of C on X can be extended to
“adm-n1” — 2019/3/22 — 12:03 — page 53 — #61
M. Y. Kizmaz 53
the action of C on T0(X). As |T0(X)| ≡ |Fix(T0(X))| (mod p), it is left
to show that |Fix(T0(X))| = T0(n+ 1).
Let τ ∈ Fix(T0(X)). Pick x, y ∈ C and a ∈ N where x 6= y. We know
that yx−1Ox = Oy. Then we can observe that Ox ∩N = Oy ∩N as N is
fixed by C. Similarly, Ox∩C and Oy ∩C are disjoint or equal. But we can
not have Ox = Oy as it is a T0 topology. Hence, (Ox ∩C)∩ (Oy ∩C) = ∅.
Then we obtain that Ox ∩C = {x}, and hence Ox = {x} ∪ S for a subset
S of N . On the other hand, x(C ∩Oa) = C ∩Oa, which forces that C ∩Oa
is either C or ∅, and hence Oa is either C ∪ T or T for a subset T of
N . Set Y = {x} ∪ N then for each τ ∈ Fix(T0(X)), we have subspace
topology τY = {U ∩ Y | U ∈ τ} on Y . Note that τY is a T0 topology as it
is the subspace topology on Y induced from τ .
Now our aim is to show that the mapping τ 7→ τY is a bijection from
Fix(T0(X)) to T0(Y ). Let π, τ ∈ Fix(T0(X)) such that τY = πY . Then
we have Ot ∩ Y = O′
t ∩ Y for all t ∈ Y where Ot ∈ Mτ and O′
t ∈ Mπ.
Note that Ox ⊆ Y by the properties deduced in previous paragraph, and
hence we obtain Ox = O′
x. We also have the equality Oa ∩Y = O′
a ∩Y for
a ∈ N , which forces that Oa ∩ C = O′
a ∩ C is either C or ∅ by previous
paragraph. Since Oa ∩ N = O′
a ∩ N , we get Oa = O′
a for a ∈ N . Then
it follows that Ot = O′
t for all t ∈ Y . Since Oz = zx−1Ox for z ∈ C, we
obtain that Ot = O′
t for all t ∈ X, which implies the equality τ = π. Thus,
our map is one to one.
Now, let π ∈ T0(Y ) and let Mπ be the minimal base of π. Set
Ot =
tx−1O′
x if t ∈ C
O′
t if t ∈ N and x /∈ O′
t
C ∪O′
t if t ∈ N and x ∈ O′
t
for each O′
t ∈ Mπ. We need to show that B = {Ot | t ∈ X} is a minimal
base and the topology τ generated by B is a T0 topology. To show that
it is a minimal base, we need to show that if a ∈ Ot then Oa ⊆ Ot for
any a, t ∈ X. In fact, we will observe that Oa ⊂ Ot which shows that τ
is a T0 topology. It can be done case by case but here we present only
nontrivial cases. Fix a ∈ N and let a ∈ Ox. Note that a ∈ O′
x as O′
x = Ox,
and hence we obtain O′
a ⊆ O′
x. If x ∈ O′
a then we have O′
a = O′
x which is
not possible as π is a T0 topology. Thus, x /∈ O′
a which implies Oa = O′
a
by our setting. Then we obtain that Oa ⊂ Ox. Now assume that x ∈ Oa.
Then we get that x ∈ O′
a otherwise x /∈ Oa by our setting. Thus, we
obtain O′
x ⊂ O′
a in a similar way. It follows that Ox ⊂ Oa as Ox = O′
x. As
a result τ ∈ Fix(T0(X)) as B is a C-invariant minimal base. Moreover,
“adm-n1” — 2019/3/22 — 12:03 — page 54 — #62
54 On the number of topologies on a finite set
the equality τY = π holds, which concludes that the mapping τ 7→ τY
from Fix(T0(X)) to T0(Y ) is a bijection, which completes the proof.
Corollary 1. T0(p
k) ≡ 1 (mod p) where k is a natural number and p is
a prime number.
The proof of next theorem is similar to the proof of Theorem 2 in
the sense that both use the same technique. For clarity, we repeat some
arguments.
Theorem 3. For each natural number n, there exists a unique integer k
such that T (p+ n) ≡ k (mod p) for all primes p.
Proof. If n = 0, T (p) ≡ 2 (mod p) by Theorem 1. Now we can assume
that n > 0. Let C = Cp be the cyclic group of order p and N be a set with
n elements. We define the action of C on X as in the proof the previous
theorem. Then the action of C on X can be extended to the action of
C on T(X). As |T(X)| ≡ |Fix(T(X))| (mod p), it is left to show that
|Fix(T(X))| does not depend on the choice of prime p.
Due to Lemma 1, |Fix(T(X))| is equal to the number of C-invariant
minimal bases on X. Let x, y ∈ C. Notice that Ox completely determines
Oy as (yx−1)Ox = Oy. Then |Ox∩C| = |Oy∩C| as yx−1(Ox∩C) = Oy∩C.
Now it is easy to see that Ox ∩ C and Oy ∩ C are either disjoint or equal.
As cardinality of C is prime, Ox ∩ C is either {x} or C. If a ∈ N then
we must have gOa = Oa for all g ∈ C as ga = a. Hence, Oa ∩ C is either
∅ or C. Thus, the elements of C have no contribution to the number of
possible minimal bases. Now we know that such k exists. If k′ is also such
an integer then k ≡ k′ (mod p) for all primes p. Hence k − k′ is divisible
by all primes which forces k − k′ = 0.
By the previous theorem, we see that k is uniquely determined by n,
which leads the following definition.
Definition 2. We define the integer sequence k(n) for n > 0 to be the
unique number such that k(n) ≡ T (p+ n) (mod p) for all primes p.
The sequence k(n) has appeared in the online encyclopedia of N. J. A.
Sloane [2] with reference number (A265042) after this article appeared in
arxiv. The proof of the theorem also gives an algorithm to calculate k(n)
for a given n.
Corollary 2. T (p+ 1) ≡ 7 (mod p) for all primes p, that is, k(1) = 7.
“adm-n1” — 2019/3/22 — 12:03 — page 55 — #63
M. Y. Kizmaz 55
Proof. By following the proof the Theorem 3, it can be easily counted
that there are exactly seven C-invariant minimal bases. Then the result
follows.
However, it is difficult to count C-invariant minimal bases for larger n
to determine k(n). We develop a new method to calculate k(n) for larger
n. But the method requires knowing values of T (s) for some s.
Theorem 4. The sequence k(n) satisfies the following inequality
T (n+ 1) + T0(n+ 1) 6 k(n) < 2T (n+ 1)
for n > 1.
Proof. We follow the proof of Theorem 3. We have k(n) = |Fix(T(X))|
where |X| = n + p and |C| = p. Thus, we need to count C-invariant
minimal bases. According to the proof, we have two main cases.
Case 1: Ox ∩ C = C for x ∈ C. Then Oy ∩ C = C for all y ∈ C and
Ox = Oy for all x, y ∈ C. If a ∈ N then Oa∩C is either C or ∅. Hence we
can see the whole C as one element, that is, pass to the quotient X = X/ ∼
where x ∼ y if x, y ∈ C then there is a one to one correspondence between
C-invariant topologies and quotient topologies. It follows that we have
exactly T (n+ 1) possible sub-cases.
Case 2: Ox ∩ C = {x} for x ∈ C. Let x, y ∈ C then when we define
Ox, Oy is completely determined as Oy = yx−1Ox. Moreover, we have
Ox ∩ N = Oy ∩ N as C acts trivially on N . We also have Oa ∩ C is
either C or ∅. Now set Y = N ∪ {x} then the mapping τ → τY is one
to one from Fix(T(X)) to T(Y ). Hence we can have at most T (n + 1)
possible sub-cases. But we can not have exactly T (n + 1) possible sub-
cases as the given map is not onto. To see this, set O′
x = {x, a} for
a ∈ N and O′
a = {x, a} for a topology π ∈ T(Y ). Let τ ∈ Fix(T(X))
such that τY = π. Note that O′
a = Oa ∩ Y and Oa must be fixed by the
action of C. Thus, we have C ∪ {a} ⊆ Oa. Since Ox = O′
x = {x, a}, we
obtain that Oa ⊆ {x, a}. Then we obtain that Oa = {a} as it must be
fixed by C, which is a contradiction. Thus, the map is not onto. Then
we get that k(n) < 2T (n + 1). Moreover, the mapping is onto from
Fix(T0(X)) ⊆ Fix(T(X)) to T0(Y ) ⊆ T(Y ).(See the proof of Theorem 2
for details of how the map τ → τY is one to one. It also shows why this
map is onto when the target set is T0(Y ).) Thus, we have at least T0(n+1)
sub-cases, and hence T (n+ 1) + T0(n+ 1) 6 k(n) < 2T (n+ 1).
“adm-n1” — 2019/3/22 — 12:03 — page 56 — #64
56 On the number of topologies on a finite set
Corollary 3. lim
n→∞
k(n)
T (n+ 1)
= 2.
Proof. We have 1 + T0(n+1)
T (n+1) 6
k(n)
T (n+1) < 2 by Theorem 4. In [6], it is
proved that limn→∞
T0(n)
T (n) = 1, and hence the result follows.
Theorem 5. The sequence k(n) = 2, 7, 51, 634, 12623 for n = 0, 1, 2, 3, 4
respectively.
Proof. If n = 0, the result follows from Theorem 1. Now assume that
n > 1. We only show the calculation of k(2) and rest of them follow in a
similar way. By previous theorem, we have T (3) + T0(3) 6 k(2) < 2T (3)
so 48 6 k(2) < 58. Clearly, we have
T (5) ≡ k(2) (mod 3)
T (7) ≡ k(2) (mod 5)
It follows that k(2) ≡ 6 (mod 15) by solving the above congruence
relation. We obtain that k(2) = 51 as 48 6 k(2) < 58. For n = 3, 4, we
have the same procedure.
We should note that for n > 5, there is no unique solution satisfying
the inequality. For example, k(5) ∈ {357593, 387623, 417653}. The closed
form of k(n) seems to be another open problem. Hence calculation of k(n)
for specific n or some better lower and upper bounds can be seen as new
problems arising from this article.
Acknowledgement
The author would like to thank an anonymous referee for many in-
valuable suggestions on the original manuscript.
References
[1] N. J. A. Sloane, Online Encyclopedia of Integer Sequences(Concerned with se-
quences A000798,A001035 )
[2] N. J. A. Sloane, Online Encyclopedia of Integer Sequences(A265042)
[3] M. Benoumhani, The number of topologies on a finite set, J. Integer Seq. 9 (2006),
no. 2, Article 06.2.6, 9 pp.
[4] Z. I. Borevich, Periodicity Of Residues of The number Of Finite Labeled Topologies,
Journal of Soviet Mathematics, 24, No. 4, 391-395 (1984)
“adm-n1” — 2019/3/22 — 12:03 — page 57 — #65
M. Y. Kizmaz 57
[5] Z. I. Borevich, Periodicity of residues of the number of finite labeled T0-topologies,
(Russian) Modules and algebraic groups. Zap. Nauchn. Sem. Leningrad. Otdel.
Mat. Inst. Steklov. (LOMI) 114 (1982), 32-36, 217.
[6] M. Erné, Struktur- und Anzahlformeln für Topologien auf endlichen Mengen,
Manuscr. Math.,11, No. 3, 221-259 (1974).
[7] A. S. Mashhour, M. E. Abd El-Monsef and A. S. Farrag, On the number of
topologies on a finite set, Delta J. Sci. 10 (1986), no. 1, 41-65.
[8] R. Stanley, On the number of open sets of finite topologies, J. Combinatorial
Theory 10 (1971) 74-79.
Contact information
M. Y. Kizmaz Department of Mathematics, Middle East
Technical University, Ankara 06531, Turkey
E-Mail(s): yasir@metu.edu.tr
Received by the editors: 31.03.2017
and in final form 06.10.2017.
|
| id | nasplib_isofts_kiev_ua-123456789-188421 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1726-3255 |
| language | English |
| last_indexed | 2025-12-07T16:09:39Z |
| publishDate | 2019 |
| publisher | Інститут прикладної математики і механіки НАН України |
| record_format | dspace |
| spelling | Kizmaz, M.Y. 2023-02-28T18:51:11Z 2023-02-28T18:51:11Z 2019 On the number of topologies on a finite set / M.Y. Kizmaz // Algebra and Discrete Mathematics. — 2019. — Vol. 27, № 1. — С. 50–57. — Бібліогр.: 8 назв. — англ. 1726-3255 2010 MSC: Primary 11B50, Secondary 11B05. https://nasplib.isofts.kiev.ua/handle/123456789/188421 We denote the number of distinct topologies which can be defined on a set X with n elements by T(n). Similarly, T0(n) denotes the number of distinct T₀ topologies on the set X. In the present paper, we prove that for any prime p, T(pᵏ) ≡ k + 1 (mod p), and that for each natural number n there exists a unique k such that T(p + n) ≡ k (mod p). We calculate k for n = 0, 1, 2, 3, 4. We give an alternative proof for a result of Z. I. Borevich to the effect that T₀(p + n) ≡ T₀(n + 1) (mod p). en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics On the number of topologies on a finite set Article published earlier |
| spellingShingle | On the number of topologies on a finite set Kizmaz, M.Y. |
| title | On the number of topologies on a finite set |
| title_full | On the number of topologies on a finite set |
| title_fullStr | On the number of topologies on a finite set |
| title_full_unstemmed | On the number of topologies on a finite set |
| title_short | On the number of topologies on a finite set |
| title_sort | on the number of topologies on a finite set |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/188421 |
| work_keys_str_mv | AT kizmazmy onthenumberoftopologiesonafiniteset |