Classification of topologies on finite sets using graphs
With the use of digraphs, topologies on finite sets are studied. On this basis, a new classification of such topologies is proposed. Some properties of T0-topologies on finite sets are proved. In particular, it is proved that, in T0-topologies, there exist open sets containing arbitrary number of...
Збережено в:
| Дата: | 2008 |
|---|---|
| Автори: | , , , |
| Формат: | Стаття |
| Мова: | Російська Англійська |
| Опубліковано: |
Institute of Mathematics, NAS of Ukraine
2008
|
| Онлайн доступ: | https://umj.imath.kiev.ua/index.php/umj/article/view/3215 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Ukrains’kyi Matematychnyi Zhurnal |
| Завантажити файл: |  |
Репозитарії
Ukrains’kyi Matematychnyi Zhurnal| _version_ | 1860509264991223808 |
|---|---|
| author | Adamenko, N. P. Velichko, I. G. Адаменко, Н. П. Величко, И. Г. Адаменко, Н. П. Величко, И. Г. |
| author_facet | Adamenko, N. P. Velichko, I. G. Адаменко, Н. П. Величко, И. Г. Адаменко, Н. П. Величко, И. Г. |
| author_sort | Adamenko, N. P. |
| baseUrl_str | https://umj.imath.kiev.ua/index.php/umj/oai |
| collection | OJS |
| datestamp_date | 2020-03-18T19:48:23Z |
| description | With the use of digraphs, topologies on finite sets are studied. On this basis, a new classification of such topologies is proposed.
Some properties of T0-topologies on finite sets are proved.
In particular, it is proved that, in T0-topologies, there exist open sets containing arbitrary number of
elements that does not exceed the cardinality of the set itself. |
| first_indexed | 2026-03-24T02:38:21Z |
| format | Article |
| fulltext |
К О Р О Т К I П О В I Д О М Л Е Н Н Я
УДК 517.5
Н. П. Адаменко, И. Г. Величко (Запорож. нац. ун-т)
КЛАССИФИКАЦИЯ ТОПОЛОГИЙ
НА КОНЕЧНЫХ МНОЖЕСТВАХ С ПОМОЩЬЮ ГРАФОВ
With the use of digraphs, topologies on finite sets are studied. On this basis, a new classification of such
topologies is proposed. Some properties of T0-topologies on finite sets are proved. In particular, it is
proved that, in T0-topologies, there exist open sets containing arbitrary number of elements that does not
exceed the cardinality of the set itself.
З допомогою орграфiв вивчаються топологiї на скiнченних множинах. На цiй основi запропоно-
вано нову класифiкацiю таких топологiй. Доведено деякi властивостi T0-топологiй на скiнченних
множинах i, зокрема, iснування в T0-топологiях вiдкритих множин, що мiстять будь-яку кiлькiсть
елементiв, яка не перевищує потужностi самої множини.
Идея использования графов для изучения топологий на конечных множествах при-
менялась неоднократно. В работах [1, 2] решались задачи перечисления всех топо-
логий на конечных множествах с помощью транзитивных графов. В данной работе
топологии на конечных множествах исследуются и классифицируются с помощью
орграфов особого вида.
Пусть τX — топология на конечном множестве X (носителе топологии). Будем
говорить, что множество A ∈ τX является максимальным в X, если A не содержит-
ся ни в каком другом множестве из τX , кроме самого X. При этом множество X
будем называть объемлющим для A.
Предположим, что заданы множества A, X, A ⊂ X, и топология τA. Вы-
ясним, как можно восстановить все топологии на множестве X такие, что τA
есть индуцированная ими топология и множество A является максимальным в со-
ответствующей топологии на X (в этом случае топологию τA и соответствующие
топологии на X будем называть согласованными).
Лемма 1. Если A максимально в X и B = X \A, то для любого открытого
множества V ∈ τX пересечение V ∩B равно или пустому множеству, или самому
множеству B.
Доказательство. Предположим противное: пусть существует множество V ∈
∈ τX такое, что пересечение V ∩ B = C, где C 6= ∅, C 6= B. Очевидно, что
A ⊂ A ∪ V ⊂ X. То, что эти включения строгие, следует из того, что A ∩ B = ∅,
(A ∪ V ) ∩ B = C, X ∩ B = B. Значит, в этом случае множество A не является
максимальным.
Лемма доказана.
Теорема 1 [о топологиях на объемлющем множестве]. Пусть X — конечное
множество, A ⊂ X, B = X \ A и τA — топология на A. Предположим, что
L ∈ τA, а набор
∑
L
состоит из всех элементов топологии τA и всевозможных
множеств вида
{
Wi ∪ B | L ⊂ Wi ⊂ A,Wi ∈ τA
}
. Набор τX подмножеств
c© Н. П. АДАМЕНКО, И. Г. ВЕЛИЧКО, 2008
992 ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 7
КЛАССИФИКАЦИЯ ТОПОЛОГИЙ НА КОНЕЧНЫХ МНОЖЕСТВАХ ... 993
множества X является топологией в X, согласованной с τA, тогда и только
тогда, когда он есть набор
∑
L
для некоторого L.
Доказательство. Покажем, что если τX — топология на X, согласованная с
τA, то существует L ∈ τA такое, что τX =
∑
L
. Выберем множество L следующим
образом: L =
( ⋂
W∈τX ,W⊃B
W
)
∩ A. Очевидно, что таким образом определенное
множество L принадлежит τA. Рассмотрим произвольное множество M из τX .
Если M ⊂ A, то оно является элементом τA и, следовательно, M ∈
∑
L
. Если
M 6⊂ A, то по лемме оно обязательно содержит в себе множество B. Поскольку
множество M \B = M ∩A открыто в τA и содержит в себе L, то и в этом случае
M ∈
∑
L
. Значит, τX ⊂
∑
L
.
Покажем, что для выбранного L имеет место включение
∑
L
⊂ τX . Пусть
множество M ∈
∑
L
. Если M ∈ τA, то M ∈ τX . Если же M 6∈ τA, то по
определению набора
∑
L
получим M = W ∪ B, где L ⊂ W ⊂ A и W ∈ τA. Так
как L ⊂ W, то и в этом случае M = W ∪ B = (W ∪ L) ∪ B = W ∪ (L ∪ B) =
= W ∪
( ⋂
U∈τX ,U⊃B
U
)
принадлежит τX . Таким образом, топология τX совпадает
с набором
∑
L
для некоторого L.
Легко проверяется, что для любого L ∈ τA набор
∑
L
есть топология на X,
согласованная с топологией τA.
Теорема доказана.
Следствие 1. Если задана топология на множестве A, то любая топология
на объемлющем множестве X (согласованная с топологией на A) получается
следующим образом: выбираем любое открытое множество L ∈ τA, каждый
элемент из τA, содержащий в себе L, объединяем с B = X \ A и к полученной
системе множеств добавляем все элементы τA. Этот набор является топологией
на множестве X.
Каждой топологии на конечном множестве будем ставить в соответствие ори-
ентированный конечный граф (колчан) Q [3]. При этом вершинам колчана со-
ответствуют открытые в заданной топологии τX множества. Из вершины vi в
вершину vj ведет стрелка, если множество, соответствующее вершине vi, вложено
во множество, соответствующее вершине vj , и между ними нет промежуточных
открытых множеств. Колчан, который соответствует некоторой топологии на ко-
нечном множестве X, будем называть T -колчаном. При этом пустое множество
и X соответствуют вершинам T -колчана, которые являются истоком и стоком со-
ответственно.
Перейдем к выяснению того, когда произвольный колчан будет T -колчаном. Из
теоремы 1 следует такое утверждение.
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 7
994 Н. П. АДАМЕНКО, И. Г. ВЕЛИЧКО
Теорема 2. 1. Колчан, изображенный на рисунке, является T -колчаном.
2. Пусть есть T -колчан на множестве A и B ∩ A = ∅. Из любой вершины L
колчана QA достраивается стрелка в новую вершину, соответствующую L ∪ B.
Из этой новой вершины достраивается подграф, изоморфный подграфу T -колчана
QA с истоком в вершине L. Все соответствующие вершины обоих подграфов
соединяются стрелками. Этот колчан будет изображать топологию на мно-
жестве X = A ∪ B, согласованную с топологией на множестве A, т. е. будет
T -колчаном.
Покажем, что способом, описанным в данной теореме, можно получить все
T -колчаны топологий на произвольном конечном множестве.
Напомним, что топология называется T0-топологией, если для любых двух ее
различных точек хотя бы одна имеет окрестность, не содержащую другую точку.
Лемма 2. Если топология τ является T0-топологией на n-элементном мно-
жестве X, то существует хотя бы одно (n − 1)-элементное открытое мно-
жество в τ.
Доказательство будем проводить от противного. Предположим, что не су-
ществует (n− 1)-элементного открытого множества и максимальное по мощности
открытое множество V ∈ τ состоит из n − k, 2 ≤ k < n, элементов. Рассмотрим
произвольные точки x1 и x2 из X \V. Поскольку τ является T0-топологией, хотя бы
одна из этих точек имеет окрестность, не содержащую другую точку. Пусть, для
определенности, Ux1 — окрестность точки x1, не содержащая x2. Тогда множество
W = V ∪ Ux1 является открытым в τ и его мощность больше чем n − k, а это
противоречит максимальности V. Таким образом, k = 1.
Лемма доказана.
Теорема 3. Все T -колчаны T0-топологий могут быть получены описанным в
теореме 2 способом.
Доказательство. Пусть τAn
является T0-топологией на n-элементном мно-
жестве An. Выберем (n−1)-элементное открытое множество An−1 (оно существует
по лемме 2) и рассмотрим на нем индуцированную топологию τAn−1 . В силу со-
гласованности топологий T -колчан, соответствующий топологии τAn
, получается
из T -колчана, соответствующего топологии τAn−1 , описанным в п. 2 теоремы 2
способом. Далее в τAn−1 выберем (n − 2)-элементное открытое множество An−2
и рассмотрим на нем индуцированную топологию τAn−2 . T -колчан, соответству-
ющий τAn−1 , получается описанным в п. 2 теоремы 2 способом из T -колчана,
соответствующего τAn−2 . Процедуру повторяем до тех пор, пока не придем к топо-
логии τA1 на одноэлементном множестве, T -колчан которой изображен на рисунке.
Таким образом, искомый T -колчан топологии τAn
образуется из T -колчана, изобра-
женного на рисунке, применением n−1 раз п. 2 теоремы 2. В силу произвольности
n получаем утверждение теоремы.
Следствие 2. T -колчаны всех топологий на конечном множестве можно по-
лучить описанным в теореме 2 способом.
Доказательство. Пусть τ — топология на n-элементном множестве X, не
являющаяся T0-топологией. Тогда существуют точки a и b, неотделимые в смысле
аксиомы T0. Переобозначим во множестве X и элементах из τ подмножество
{a, b} через c. Указанную процедуру повторяем до тех пор, пока не придем к
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 7
КЛАССИФИКАЦИЯ ТОПОЛОГИЙ НА КОНЕЧНЫХ МНОЖЕСТВАХ ... 995
T0-топологии. На каждом из шагов (а их конечное число) получаем T -колчан,
изоморфный T -колчану исходной топологии.
Следствие доказано.
Отнесем к одному классу топологии, которые имеют изоморфные T -колчаны.
Поскольку изоморфизм орграфов есть отношение эквивалентности, получаем клас-
сификацию топологий на конечных множествах.
Рассмотрим T -колчан T0-топологий. По теореме 3 T -колчан T0-топологии на
n-элементном множестве может быть построен из T -колчана, изображенного на
рисунке, применением n− 1 раз п. 2 теоремы 2. Так как каждый раз при примене-
нии п. 2 теоремы 2 мощность носителя топологии увеличивается на единицу, по-
строенный T -колчан будет соответствовать топологии на n-элементном множестве.
Рассмотрим произвольный маршрут из истока в сток. Множества, соответствую-
щие вершинам этого маршрута, строго упорядочены по включению. Значит, их
мощности образуют монотонно возрастающую последовательность целых чисел
a0 = 0, a1, . . . , an = n. Отсюда получаем ak = k.
С другой стороны, любой маршрут из истока в фиксированную вершину в T -
колчане T0-топологии соответствует линейно упорядоченному набору элементов из
этой топологии, или, в терминах частично упорядоченных множеств, любой марш-
рут из истока в фиксированную вершину в T -колчане T0-топологии соответствует
некоторой цепи. Одной из важных числовых характеристик цепи является ее длина
l, равная |n|, где |n| — мощность носителя линейно упорядоченного множества
[3]. Итак, имеет место следующий факт: в T -колчане T0-топологии длины всех
маршрутов из истока в некоторую фиксированную вершину одинаковы. А так как
T -колчан произвольной топологии является T -колчаном некоторой T0-топологии,
этот факт справедлив и для T -колчана произвольной топологии.
Будем говорить, что вершина T -колчана является вершиной k-го уровня, если
маршруты из истока к ней имеет длину k. Вершина, соответствующая пустому
множеству, будет вершиной нулевого уровня.
Приведенные выше рассуждения можно сформулировать в виде теоремы.
Теорема 4. На k-м уровне произвольного T -колчана T0-топологии находятся
вершины, соответствующие k-элементным открытым множествам.
В заключение докажем несколько свойств T0-топологий с использованием T -
колчанов.
Следствие 3. Если τ — T0-топология на n-элементном множестве, то для
любого k, 0 ≤ k ≤ n, в ней существует k-элементное множество.
Доказательство. Построим T -колчан, соответствующий данной T0-топологии.
Он будет n-уровневым. Вершины k-го уровня соответствуют k-элементным откры-
тым множествам.
Следствие 4. Для любого нетривиального открытого k-элементного множе-
ства в n-элементном топологическом T0-пространстве существуют содержащее
его (k + 1)-элементное открытое множество и содержащееся в нем (k − 1)-
элементное открытое множество.
Доказательство. Построим T -колчан, соответствующий T0-топологии. За-
данному k-элементному открытому множеству, согласно теореме 4, соответствует
вершина k-го уровня. Стрелка с началом в данной вершине ведет в вершину (k+1)-
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 7
996 Н. П. АДАМЕНКО, И. Г. ВЕЛИЧКО
го уровня. Эта вершина соответствует (k + 1)-элементному открытому множеству,
содержащему данное. Вторая часть следствия доказывается аналогично.
Следствие 5 (критерий T0-пространства). Топология на n-элементном мно-
жестве является T0-топологией тогда и только тогда, когда ей соответствует
n-уровневый T -колчан.
Доказательство. Если топология является T0-топологией, то, согласно тео-
реме 4, ей соответствует n-уровневый T -колчан. Если топология не является
T0-топологией, то, используя метод доказательства следствия 2, получаем, что
ее T -колчан изоморфен T -колчану T0-топологии на k-элементном множестве, где
k < n.
1. Evans J. W., Harary F., Lynn M. S. Оn the computer enumeration of finite topologies // Communs
ASM. – 1967. – 10. – P. 295 – 298.
2. Козырев В. П. Перечисление транзитивных ориентированных графов и вложение транзитив-
ных графов // Вопросы кибернетики. – 1975. – Вып. 15. – С. 44 – 60.
3. Горбатов В. А. Основы дискретной математики: Уч. пос. для студентов вузов. – М.: Высш.
шк., 1986. – 18 с.
Получено 15.10.07
ISSN 1027-3190. Укр. мат. журн., 2008, т. 60, № 7
|
| id | umjimathkievua-article-3215 |
| institution | Ukrains’kyi Matematychnyi Zhurnal |
| keywords_txt_mv | keywords |
| language | rus English |
| last_indexed | 2026-03-24T02:38:21Z |
| publishDate | 2008 |
| publisher | Institute of Mathematics, NAS of Ukraine |
| record_format | ojs |
| resource_txt_mv | umjimathkievua/6c/cc9a4c6d3e1e4736c3346d6467fd816c.pdf |
| spelling | umjimathkievua-article-32152020-03-18T19:48:23Z Classification of topologies on finite sets using graphs Классификация топологий на конечных множествах с помощью графов Adamenko, N. P. Velichko, I. G. Адаменко, Н. П. Величко, И. Г. Адаменко, Н. П. Величко, И. Г. With the use of digraphs, topologies on finite sets are studied. On this basis, a new classification of such topologies is proposed. Some properties of T0-topologies on finite sets are proved. In particular, it is proved that, in T0-topologies, there exist open sets containing arbitrary number of elements that does not exceed the cardinality of the set itself. З допомогою орграфiв вивчаються топології на скінченних множинах. На цій основі запропоновано нову класифікацію таких топологій. Доведено деякі властивості T0-топологій на скінченних множинах і, зокрема, існування в T0-топологіях відкритих множин, що містять будь-яку кількість елементів, яка не перевищує потужності самої множини. Institute of Mathematics, NAS of Ukraine 2008-07-25 Article Article application/pdf https://umj.imath.kiev.ua/index.php/umj/article/view/3215 Ukrains’kyi Matematychnyi Zhurnal; Vol. 60 No. 7 (2008); 992–996 Український математичний журнал; Том 60 № 7 (2008); 992–996 1027-3190 rus en https://umj.imath.kiev.ua/index.php/umj/article/view/3215/3176 https://umj.imath.kiev.ua/index.php/umj/article/view/3215/3177 Copyright (c) 2008 Adamenko N. P.; Velichko I. G. |
| spellingShingle | Adamenko, N. P. Velichko, I. G. Адаменко, Н. П. Величко, И. Г. Адаменко, Н. П. Величко, И. Г. Classification of topologies on finite sets using graphs |
| title | Classification of topologies on finite sets using graphs |
| title_alt | Классификация топологий на конечных множествах с помощью графов |
| title_full | Classification of topologies on finite sets using graphs |
| title_fullStr | Classification of topologies on finite sets using graphs |
| title_full_unstemmed | Classification of topologies on finite sets using graphs |
| title_short | Classification of topologies on finite sets using graphs |
| title_sort | classification of topologies on finite sets using graphs |
| url | https://umj.imath.kiev.ua/index.php/umj/article/view/3215 |
| work_keys_str_mv | AT adamenkonp classificationoftopologiesonfinitesetsusinggraphs AT velichkoig classificationoftopologiesonfinitesetsusinggraphs AT adamenkonp classificationoftopologiesonfinitesetsusinggraphs AT veličkoig classificationoftopologiesonfinitesetsusinggraphs AT adamenkonp classificationoftopologiesonfinitesetsusinggraphs AT veličkoig classificationoftopologiesonfinitesetsusinggraphs AT adamenkonp klassifikaciâtopologijnakonečnyhmnožestvahspomoŝʹûgrafov AT velichkoig klassifikaciâtopologijnakonečnyhmnožestvahspomoŝʹûgrafov AT adamenkonp klassifikaciâtopologijnakonečnyhmnožestvahspomoŝʹûgrafov AT veličkoig klassifikaciâtopologijnakonečnyhmnožestvahspomoŝʹûgrafov AT adamenkonp klassifikaciâtopologijnakonečnyhmnožestvahspomoŝʹûgrafov AT veličkoig klassifikaciâtopologijnakonečnyhmnožestvahspomoŝʹûgrafov |