Введение в топологические пространства. Программирование конечных топологий на Java24.01.2015 03:48
Я долго думал о том, чтобы выбрать какой-либо математический объект, интересный не только с точки зрения дискретной математики, но и функционального анализа, и попытаться запрограммировать его.Этим объектом стали так называемые топологические пространства. Естественно, конечный объём представления объектов в памяти компьютера не позволяет с абсолютной точностью смоделировать имеющиеся в математике топологические пространства, а значит, остаётся довольствоваться конечными топологиями.
К счастью, это один из тех объектов, для которых конечность не только позволяет оперировать стандартными математическими понятиями, но и упрощает некоторые из них. Тем более довольно интересно исследовать объекты, для которых у нас нет никакой возможности померить расстояние между точками. Да, да, вы не ослышались. В общей топологии такой возможности у нас нет.
Но обо всём по порядку.
Сперва дадим классическое определение топологического пространства.Пусть X — произвольное множество. Система τ его подмножеств называется топологией, если выполнены следующие условия:
Пустое множество и множество X принадлежат топологии
Объединение произвольного числа множеств, которые принадлежат топологии, принадлежит топологии.
Пересечение конечного числа множеств, принадлежащих топологии, принадлежит топологии.
Произвольное число множеств в данном случае означает, что мы можем брать также объединения счётного или даже несчётного числа множеств. Естественно, это имеет смысл только в случае бесконечных множеств.
Как я уже говорил, в компьютере всё конечно. Как изменится наше определение топологии, если мы предположим, что X — конечное множество.
Нетрудно видеть, что определение будет звучать следующим образом: Пусть X — произвольное множество конечной мощности. Система τ его подмножеств называется конечной топологией, если выполнены следующие условия:
Пустое множество и множество X принадлежат топологии
Если два множества принадлежат топологии, то их объединение принадлежит топологии
Если два множества принадлежат топологии, то их пересечение принадлежит топологии
Слово «конечная» в дальнейшем для удобства будем опускать. Заметим, что топология представляет собой множество множеств. К сожалению, стандартные классы для множества, представленные в языке Java, меня не устроили, главным образом тем, что операции объединения и пересечения в интерфейсе Set меняют объект множества, а мне необходимо. чтобы объект менялся только тогда, когда к нему добавляют элементы.
Поэтому я создал следующий класс для представления множеств на основе связного списка.
Класс FSet
package generaltopology;
public class FSet {
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 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 union (FSet b)
{
FSet 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 intersection (FSet b)
{
FSet 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 complement (FSet b)
{
FSet 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 bb = (FSet)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>
{
static final FSet EmptySet = new FSet<>();
FSet X;
}
Теперь возникает вопрос, как должен выглядеть конструктор топологии. Заметим, что топология — это всегда система подмножеств множества X.
Итак, а вот и первое самостоятельное задание Вам, уважаемый читатель. Докажите следующее утверждение:
Пусть X — произвольное множество. Тогда система τ, состоящая из пустого множества и множества X образует топологию.
Это было несложно, верно? Данная топология называется тривиальной. Так что давайте всегда создавать тривиальную топологию в начале использования, добавляя нужные множества позднее с помощью метода add суперкласса.
public Topology (FSet 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 a = x.elem;
FSet b = y.elem;
FSet u = a.union (b);
FSet 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 a)
{
if (!_isTopology)
throw new IllegalArgumentException («Данная система не образует топологию»);
if (! a.subset (X))
throw new IllegalArgumentException («Данное множество не является подмножеством всего пространства»);
return contains (a);
}
public boolean isClosed (FSet a)
{
if (!_isTopology)
throw new IllegalArgumentException («Данная система не образует топологию»);
if (! a.subset (X))
throw new IllegalArgumentException («Данное множество не является подмножеством всего пространства»);
return contains (X.complement (a));
}
Исключения выбрасываются, если система не образует топологию, либо переданное множество не является подмножеством X топологического пространства.Если вы проскочили через прошлую задачу, не попытавшись её решить, то вы удивитесь, почему второй метод не вызывается через первый. А если решили, то поймёте.
Ответ к предыдущей задаче
A — открытое множество. Оно входит в топологию.B — замкнутое множество. Оно является дополнением множества {2,4}, входящего в топологию.С — открытое и замкнутое множество. Оно открыто, т. к. входит в топологию. Но оно же и замкнуто, т. к. является дополнением пустого множества, которое входит в топологию.D — ни открытое, ни замкнутое множество, т. к. ни оно, ни его дополнение не входят в топологию.
Далее, надо ввести понятие окрестности.
Окрестностью точки x называется любое открытое множество, содержащее xОкрестностью множества M называется любое открытое множество G, содержащее M
Задача 3. Пусть дано топологическое пространство из предыдущей задачи. Найти все окрестности точек множества X, а также окрестности множества {1,2}
Заметим, что окрестностей как у точки, так и у множества может быть несколько. Здесь я уже нашёл удовлетворяющий меня класс: ArrayList. Соответственно, я просто вывожу список найденных окрестностей.
public ArrayList> getNeighbourhoods (Integer x)
{
if (!_isTopology)
throw new IllegalArgumentException («Данная система не образует топологию»);
ArrayList> neighbourhoods = new ArrayList<>();
Node a = first;
while (a!= null)
{
FSet open = a.elem;
if (open.contains (x))
neighbourhoods.add (open);
a = a.next;
}
return neighbourhoods;
}
public ArrayList> getNeighbourhoods (FSet M)
{
if (!_isTopology)
throw new IllegalArgumentException («Данная система не образует топологию»);
if (! M.subset (X))
throw new IllegalArgumentException («Данное множество не является подмножеством всего пространства»);
ArrayList> neighbourhoods = new ArrayList<>();
Node a = first;
while (a!= null)
{
FSet 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 M)
{
if (!_isTopology)
throw new IllegalArgumentException («Данная система не образует топологию»);
if (! M.subset (X))
throw new IllegalArgumentException («Данное множество не является подмножеством всего пространства»);
boolean flag = true;
if (M.equals (EmptySet))
return false;
ArrayList> neighbourhoods = getNeighbourhoods (x);
int i = 0;
while (i < neighbourhoods.size() && flag) {
FSet a = neighbourhoods.get (i);
FSet.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 M)
{
if (!_isTopology)
throw new IllegalArgumentException («Данная система не образует топологию»);
if (! M.subset (X))
throw new IllegalArgumentException («Данное множество не является подмножеством всего пространства»);
boolean flag = true;
if (M.equals (EmptySet))
return false;
ArrayList> neighbourhoods = getNeighbourhoods (x);
int i = 0;
while (i < neighbourhoods.size() && flag) {
FSet a = neighbourhoods.get (i);
FSet.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
Теперь у нас есть всё для того, чтобы определить важное в математике понятие: замыкание множества.
Замыкание множества M — это множество всех его точек прикосновения. Обычно оно обозначается как [M].
FSet getClosure (FSet M) {
if (!_isTopology)
throw new IllegalArgumentException («Данная система не образует топологию»);
if (! M.subset (X))
throw new IllegalArgumentException («Данное множество не является подмножеством всего пространства»);
FSet c = new FSet<>();
FSet.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 M)
{
if (!_isTopology)
throw new IllegalArgumentException («Данная система не образует топологию»);
if (! M.subset (X))
throw new IllegalArgumentException («Данное множество не является подмножеством всего пространства»);
boolean flag = false;
ArrayList> neighbourhoods = getNeighbourhoods (x);
int i = 0;
while (i < neighbourhoods.size() && !flag) {
FSet a = neighbourhoods.get (i);
FSet.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 A)
{
if (!_isTopology)
throw new IllegalArgumentException («Данная система не образует топологию»);
if (! A.subset (X))
throw new IllegalArgumentException («Данное множество не является подмножеством всего пространства»);
FSet 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. В следующей части я планирую немного рассказать о базе топологии, однако в случае конечных топологий это понятие довольно сильно упрощается, поскольку конечные топологические пространства по умолчанию обладают счётной базой, а что будет дальше, ещё увидим. Вполне вероятно, что мы поговорим о непрерывных отображениях одного топологического пространства в другое. Было бы неплохо попытаться запрограммировать такой объект, не так ли? Спасибо за внимание!
© Habrahabr.ru
