Вступ в топологічні простору. Програмування кінцевих топологій на Java

Введення

Я довго думав про те, щоб вибрати який-небудь математичний об'єкт, цікавий не тільки з точки зору дискретної математики, але і функціонального аналізу, і спробувати запрограмувати його.

Цим об'єктом стали так звані топологічні простору. Природно, кінцевий об'єм представлення об'єктів у пам'яті комп'ютера не дозволяє з абсолютною точністю змоделювати наявні в математиці топологічні простору, а отже, залишається задовольнятися кінцевими топологіями.

На щастя, це один з тих об'єктів, для яких кінцівку не тільки дозволяє оперувати стандартними математичними поняттями, але і спрощує деякі з них. Тим більше досить цікаво дослідити об'єкти, для яких у нас немає ніякої можливості поміряти відстань між точками. Так, так, ви не помилилися. У загальній топології такої можливості у нас немає.

Але про все по порядку.



Визначення

Спершу дамо класичне визначення топологічного простору.

Нехай X — довільна безліч. Система τ його підмножин називається топологією, якщо виконані наступні умови:
  1. Пусте безліч і безліч X належать топології
  2. Об'єднання довільного числа множин, які належать топології, належить топології.

  3. Перетин кінцевого числа множин, що належать топології, належить топології.


Довільне число множин в даному випадку означає, що ми можемо брати також об'єднання рахункового або навіть незліченної кількості множин. Природно, це має сенс тільки у випадку нескінченних множин.

Як я вже говорив, в комп'ютері всі звичайно. Як зміниться наше визначення топології, якщо ми припустимо, що X — кінцеве безліч.

Неважко бачити, що визначення звучатиме наступним чином:
Нехай X — довільна безліч кінцевої. Система τ його підмножин називається кінцевою топологією, якщо виконані наступні умови:
  1. Пусте безліч і безліч X належать топології
  2. Якщо дві множини належать топології, то їх об'єднання належить топології

  3. Якщо дві множини належать топології, то їх перетин належить топології


Слово «кінцева» надалі для зручності будемо опускати. Зауважимо, що топологія представляє собою множину множин. На жаль, стандартні класи для безлічі, представлені в мові 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 (a Node = 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 (a Node = 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 (a Node = 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 (a Node = 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 — ні відкрите, ні замкнутий безліч, оскільки ні він, ні його доповнення не входять в топологію.


Далі, треба ввести поняття околиці.

Околицею точки 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}, {1,2,4},{1,2,3,4}
  2. Околі точки 2: {2,4}, {1,2,4},{1,2,3,4}

  3. Околі точки 3: {1,2,3,4}
  4. Околі точки 4: {2,4}. {1,2,4}, {1,2,3,4}
  5. Околиці безлічі{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


Тепер у нас є все для того, щоб визначити важливе в математиці поняття: замикання множини.

Замикання множини 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. У наступній частині я планую трохи розповісти про базу топології, однак у випадку кінцевих топологій це поняття досить сильно спрощується, оскільки кінцеві топологічні простору мають рахункової базою, а що буде далі, побачимо. Цілком імовірно, що ми поговоримо про безперервних отображениях одного топологічного простору в інше. Було б непогано спробувати запрограмувати такий об'єкт, чи не так?

Спасибі за увагу!

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.