Введение
Я долго думал о том, чтобы выбрать какой-либо математический объект, интересный не только с точки зрения дискретной математики, но и функционального анализа, и попытаться запрограммировать его.
Этим объектом стали так называемые топологические пространства. Естественно, конечный объём представления объектов в памяти компьютера не позволяет с абсолютной точностью смоделировать имеющиеся в математике топологические пространства, а значит, остаётся довольствоваться конечными топологиями.
К счастью, это один из тех объектов, для которых конечность не только позволяет оперировать стандартными математическими понятиями, но и упрощает некоторые из них. Тем более довольно интересно исследовать объекты, для которых у нас нет никакой возможности померить расстояние между точками. Да, да, вы не ослышались. В общей топологии такой возможности у нас нет.
Но обо всём по порядку.
Определение
Сперва дадим классическое определение топологического пространства.
Пусть X — произвольное множество. Система τ его подмножеств называется топологией, если выполнены следующие условия:
- Пустое множество и множество X принадлежат топологии
- Объединение произвольного числа множеств, которые принадлежат топологии, принадлежит топологии.
- Пересечение конечного числа множеств, принадлежащих топологии, принадлежит топологии.
Произвольное число множеств в данном случае означает, что мы можем брать также объединения счётного или даже несчётного числа множеств. Естественно, это имеет смысл только в случае бесконечных множеств.
Как я уже говорил, в компьютере всё конечно. Как изменится наше определение топологии, если мы предположим, что X — конечное множество.
Нетрудно видеть, что определение будет звучать следующим образом:
Пусть X — произвольное множество конечной мощности. Система τ его подмножеств называется конечной топологией, если выполнены следующие условия:
- Пустое множество и множество X принадлежат топологии
- Если два множества принадлежат топологии, то их объединение принадлежит топологии
- Если два множества принадлежат топологии, то их пересечение принадлежит топологии
Слово «конечная» в дальнейшем для удобства будем опускать. Заметим, что топология представляет собой множество множеств. К сожалению, стандартные классы для множества, представленные в языке Java, меня не устроили, главным образом тем, что операции объединения и пересечения в интерфейсе Set меняют объект множества, а мне необходимо. чтобы объект менялся только тогда, когда к нему добавляют элементы.
Поэтому я создал следующий класс для представления множеств на основе связного списка.
Класс FSet<T>
package generaltopology;
public class FSet<T> {
protected class Node {
T elem;
Node next;
public Node(T a)
{
elem = a;
next = null;
}
}
Node first;
public FSet() {
first = null;
}
public boolean contains(T a)
{
boolean flag= false;
Node x = first;
while (x != null && !flag)
{
if (x.elem.equals(a))
flag = true;
x = x.next;
}
return flag;
}
public boolean subset(FSet<T> b)
{
boolean flag = true;
Node x = first;
while (x != null && flag)
{
if (!b.contains(x.elem))
flag = false;
x = x.next;
}
return flag;
}
public void add(T a)
{
Node x = new Node(a);
if (!contains(a))
{
x.next = first;
first = x;
}
}
public FSet<T> union(FSet<T> b)
{
FSet<T> c = new FSet<>();
for (Node a = first; a != null; a = a.next)
c.add(a.elem);
for (Node a = b.first; a != null; a = a.next)
c.add(a.elem);
return c;
}
public FSet<T> intersection(FSet<T> b)
{
FSet<T> c = new FSet<>();
for (Node a = first; a != null; a = a.next)
if (b.contains(a.elem))
c.add(a.elem);
return c;
}
public FSet<T> complement(FSet<T> b)
{
FSet<T> c = new FSet<>();
for (Node a = first; a != null; a = a.next)
if (!b.contains(a.elem))
c.add(a.elem);
return c;
}
@Override
public boolean equals(Object b)
{
FSet<T> bb = (FSet<T>)b;
return subset(bb) && bb.subset(this);
}
@Override
public String toString()
{
String s = "[";
for (Node a = first; a != null; a = a.next)
if (a.next != null)
s += a.elem + ",";
else
s += a.elem;
s += ']';
return s;
}
}
Этот класс является основным кирпичом для построения конечной топологии. Теперь перейдём к самой топологии. До сих пор я говорил только о ней, но не сказал, что такое топологическое пространство. Это пара (X,τ) множества и его топологии.
Поэтому задаток класса выглядит следующим образом (Я хочу, чтобы множество состояло из целых чисел, но благодаря использованию родовых классов вы легко подправите ко�� под произвольный тип).
public class Topology extends FSet<FSet<Integer>>
{
static final FSet<Integer> EmptySet = new FSet<>();
FSet<Integer> X;
}
Теперь возникает вопрос, как должен выглядеть конструктор топологии. Заметим, что топология — это всегда система подмножеств множества X.
Итак, а вот и первое самостоятельное задание Вам, уважаемый читатель. Докажите следующее утверждение:
Пусть X — произвольное множество. Тогда система τ, состоящая из пустого множества и множества X образует топологию.
Это было несложно, верно? Данная топология называется тривиальной. Так что давайте всегда создавать тривиальную топологию в начале использования, добавляя нужные множества позднее с помощью метода add суперкласса.
public Topology(FSet<Integer> X)
{
add(X);
add(EmptySet);
this.X = X;
}
Но это ещё не всё. Добавили мы какой-то элемент в топологию. А осталась ли она топологией от добавления элемента или нет? Проверку на выполнение второго и третьего свойств написать несложно, но вопрос состоит в том, где её написать. Мы не можем вызывать её при добавлении элемента, поскольку тогда мы не сможем получить хорошую топологию из-за вывода ошибки «Ай-ай, это не топология». Значит, на этапе создания надо на время «простить» эту ошибку, а уже потом устроить ей хороший пинок: добавим в класс флажок и метод проверки
private boolean _isTopology;
public boolean isTopology()
{
boolean flag = true;
Node x = first;
while (x != null && flag)
{
Node y = x.next;
while (y != null && flag)
{
FSet<Integer> a = x.elem;
FSet<Integer> b = y.elem;
FSet<Integer> u = a.union(b);
FSet<Integer> i = a.intersection(b);
if (!contains(u))
flag = false;
if (!contains(i))
flag = false;
y = y.next;
}
x = x.next;
}
_isTopology = flag;
return flag;
Но это была всего лишь разминка. Теперь дадим ещё несколько определений.
Множества, входящие в топологию τ называются открытыми.
Множества, дополнительные к открытым, называются замкнутым.
Большинство студентов на этом путаются. Вот вам следующее задание:
Пусть X={1,2,3,4}, а τ={∅,{1},{2,4},{1,2,4},{1,2,3,4}}. Определить, являются ли следующие множества открытыми или замкнутыми?
A={1}
B={1,3}
C={1,2,3,4}
D={2,3}
Естественно, проверка этих двух свойств осуществляется следующими методами:
public boolean isOpen(FSet<Integer> a)
{
if (!_isTopology)
throw new IllegalArgumentException("Данная система не образует топологию");
if (!a.subset(X))
throw new IllegalArgumentException("Данное множество не является подмножеством всего пространства");
return contains(a);
}
public boolean isClosed(FSet<Integer> a)
{
if (!_isTopology)
throw new IllegalArgumentException("Данная система не образует топологию");
if (!a.subset(X))
throw new IllegalArgumentException("Данное множество не является подмножеством всего пространства");
return contains(X.complement(a));
}
Исключения выбрасываются, если система не образует топологию, либо переданное множество не является подмножеством X топологического пространства.
Если вы проскочили через прошлую задачу, не попытавшись её решить, то вы удивитесь, почему второй метод не вызывается через первый. А если решили, то поймёте.
Ответ к предыдущей задаче
A — открытое множество. Оно входит в топологию.
B — замкнутое множество. Оно является дополнением множества {2,4}, входящего в топологию.
С — открытое и замкнутое множество. Оно открыто, т. к. входит в топологию. Но оно же и замкнуто, т. к. является дополнением пустого множества, которое входит в топологию.
D — ни открытое, ни замкнутое множество, т. к. ни оно, ни его дополнение не входят в топологию.
B — замкнутое множество. Оно является дополнением множества {2,4}, входящего в топологию.
С — открытое и замкнутое множество. Оно открыто, т. к. входит в топологию. Но оно же и замкнуто, т. к. является дополнением пустого множества, которое входит в топологию.
D — ни открытое, ни замкнутое множество, т. к. ни оно, ни его дополнение не входят в топологию.
Далее, надо ввести понятие окрестности.
Окрестностью точки x называется любое открытое множество, содержащее x
Окрестностью множества M называется любое открытое множество G, содержащее M
Задача 3. Пусть дано топологическое пространство из предыдущей задачи. Найти все окрестности точек множества X, а также окрестности множества {1,2}
Заметим, что окрестностей как у точки, так и у множества может быть несколько. Здесь я уже нашёл удовлетворяющий меня класс: ArrayList. Соответственно, я просто вывожу список найденных окрестностей.
public ArrayList<FSet<Integer>> getNeighbourhoods(Integer x)
{
if (!_isTopology)
throw new IllegalArgumentException("Данная система не образует топологию");
ArrayList<FSet<Integer>> neighbourhoods = new ArrayList<>();
Node a = first;
while (a != null)
{
FSet<Integer> open = a.elem;
if (open.contains(x))
neighbourhoods.add(open);
a = a.next;
}
return neighbourhoods;
}
public ArrayList<FSet<Integer>> getNeighbourhoods(FSet<Integer> M)
{
if (!_isTopology)
throw new IllegalArgumentException("Данная система не образует топологию");
if (!M.subset(X))
throw new IllegalArgumentException("Данное множество не является подмножеством всего пространства");
ArrayList<FSet<Integer>> neighbourhoods = new ArrayList<>();
Node a = first;
while (a != null)
{
FSet<Integer> open = a.elem;
if (M.subset(open))
neighbourhoods.add(open);
a = a.next;
}
return neighbourhoods;
}
Ответ к задаче 3
- Окрестности точки 1: {1}, {1,2,4},{1,2,3,4}
- Окрестности точки 2: {2,4}, {1,2,4},{1,2,3,4}
- Окрестности точки 3: {1,2,3,4}
- Окрестности точки 4: {2,4}. {1,2,4}, {1,2,3,4}
- Окрестности множества {1,2}: {1,2,4}, {1,2,3,4}
В топологическом пространстве, где отсутствуют такие привычные для нас термины как расстояние, метрика или норма, окрестность представляет собой базовый фундамент для построения геометрии в таких пространствах.
Итак, ещё немного определений.
Точка x из множества X называется точкой прикосновения множества M, лежащего в X, если каждая окрестность точки x содержит хотя бы одну точку из M
Точка x из множества X называется предельной точкой множества M, лежащего в X, если каждая окрестность точки x содержит хотя бы одну точку из M, отличную от X
Итак, как всегда, пока знания свежи, я предлагаю вам простые задачи после определения, за ними последует код, а далее решение.
Задача 4. В предыдущем топологическом пространстве найти точки прикосновения и предельные точки множества M={2,3}.
Заметьте, что в определении не требуется принадлежность множества топологии.
Код для соответствующих точек:
boolean isAdherencePoint(Integer x, FSet<Integer> M)
{
if (!_isTopology)
throw new IllegalArgumentException("Данная система не образует топологию");
if (!M.subset(X))
throw new IllegalArgumentException("Данное множество не является подмножеством всего пространства");
boolean flag = true;
if (M.equals(EmptySet))
return false;
ArrayList<FSet<Integer>> neighbourhoods = getNeighbourhoods(x);
int i = 0;
while (i < neighbourhoods.size() && flag) {
FSet<Integer> a = neighbourhoods.get(i);
FSet<Integer>.Node t = M.first;
boolean containsM = false;
while (t != null && !containsM)
{
if (a.contains(t.elem))
containsM = true;
t = t.next;
}
if (!containsM)
flag = false;
i++;
}
return flag;
}
boolean isLimitPoint(Integer x, FSet<Integer> M)
{
if (!_isTopology)
throw new IllegalArgumentException("Данная система не образует топологию");
if (!M.subset(X))
throw new IllegalArgumentException("Данное множество не является подмножеством всего пространства");
boolean flag = true;
if (M.equals(EmptySet))
return false;
ArrayList<FSet<Integer>> neighbourhoods = getNeighbourhoods(x);
int i = 0;
while (i < neighbourhoods.size() && flag) {
FSet<Integer> a = neighbourhoods.get(i);
FSet<Integer>.Node t = M.first;
boolean containsM = false;
while (t != null && !containsM)
{
if (!t.elem.equals(x) && a.contains(t.elem))
containsM = true;
t = t.next;
}
if (!containsM)
flag = false;
i++;
}
return flag;
}
Ответ
Точки прикосновения: 2,3,4
Предельные точки: 3
Предельные точки: 3
Теперь у нас есть всё для того, чтобы определить важное в математике понятие: замыкание множества.
Замыкание множества M — это множество всех его точек прикосновения. Обычно оно обозначается как [M].
FSet<Integer> getClosure(FSet<Integer> M) {
if (!_isTopology)
throw new IllegalArgumentException("Данная система не образует топологию");
if (!M.subset(X))
throw new IllegalArgumentException("Данное множество не является подмножеством всего пространства");
FSet<Integer> c = new FSet<>();
FSet<Integer>.Node a = X.first;
while (a != null) {
if (isAdherencePoint(a.elem,M))
c.add(a.elem);
a = a.next;
}
return c;
}
Опять продолжая работу с нашим топологическим пространством, мы можем увидеть, что [{2,3}]={2,3,4}, при этом мы получили замкнутое множество.
Ещё одним важным понятием является понятие изолированной точки.
Точка x называется изолированной точкой множества M, если существует её окрестность, не содержащая других точек из M.
Задача 5. Доказать, что x=2 является изолированной точкой множества M={2,3}
boolean isIsolated(Integer x, FSet<Integer> M)
{
if (!_isTopology)
throw new IllegalArgumentException("Данная система не образует топологию");
if (!M.subset(X))
throw new IllegalArgumentException("Данное множество не является подмножеством всего пространства");
boolean flag = false;
ArrayList<FSet<Integer>> neighbourhoods = getNeighbourhoods(x);
int i = 0;
while (i < neighbourhoods.size() && !flag) {
FSet<Integer> a = neighbourhoods.get(i);
FSet<Integer>.Node t = M.first;
boolean containsothers = false;
while (t != null && !containsothers)
{
if (!t.elem.equals(x) && a.contains(t.elem))
containsothers = true;
t = t.next;
}
if (!containsothers)
flag =true;
i++;
}
return flag;
}
Далее, надо понимать, что на одном и том же множестве можно ввести разные топологии, получив тем самым разные пространства. Но между топологиями можно установить частичный порядок.
Говорят, что топология т1 слабее топологии т2, если т1 целиком содержится в т2, и сильнее в противном случае.
Очевидно, что самая слабая топология — это тривиальная топология.
Задача 6. Пусть дано произвольное множество X. Ввести на нём самую сильную топологию. Указать все открытые и замкнутые множества.
@Override
public int compareTo(Topology o)
{
int a;
if (!_isTopology || !o._isTopology)
throw new IllegalArgumentException("Данная система не образует топологию");
if (subset(o))
a = -1;
else if (equals(o))
a = 0;
else if (o.subset(this))
a = 1;
else throw new IllegalArgumentException("Топологии не сравнимы");
return a;
}
Ответ
Самая сильная топология, которую можно ввести на множестве X, — так называемая дискретная топология, состоящая из всех подмножеств множества X. В ней все подмножества множества X одновременно и открытые, и замкнутые.
И последнее понятие, о котором я хочу рассказать в этой статье, это след топологии.
Следом топологии т на множестве A, лежащем в X, называется топология тA, состоящая из всех множеств вида B ∩ A, где B принадлежит топологии.
Задача 7. Доказать, что след топологии т на множестве A, образует топологию на множестве A
Topology getTrace(FSet<Integer> A)
{
if (!_isTopology)
throw new IllegalArgumentException("Данная система не образует топологию");
if (!A.subset(X))
throw new IllegalArgumentException("Данное множество не является подмножеством всего пространства");
FSet<Integer> AX = A.intersection(X);
Topology c = new Topology(AX);
Node f = first;
while (f != null)
{
c.add(f.elem.intersection(A));
f = f.next;
}
return c;
}
Заключение
На этом подходит к концу первая часть моего цикла статей о топологических пространствах и программировании их подкласса: конечных топологий — на языке Java. В следующей части я планирую немного рассказать о базе топологии, однако в случае конечных топологий это понятие довольно сильно упрощается, поскольку конечные топологические пространства по умолчанию обладают счётной базой, а что будет дальше, ещё увидим. Вполне вероятно, что мы поговорим о непрерывных отображениях одного топологического пространства в другое. Было бы неплохо попытаться запрограммировать такой объект, не так ли?
Спасибо за внимание!