Алгебра и топология (стр. 3 из 8)

Замыканием [A] множества А в {C,

} называется множество всех точек из C, абсолютно близких к А. Однозначно отвечающая этой операции топология на множестве C и называется топологией, порожденной на Cметрикой .

Различные варианты метрик приведены в примере 5.3.

Важным подклассом метрических пространств, связанным с теорией алгоритмов, являются эффективно метрические пространства. Это метрические пространства, рассматриваемые вместе с некоторой своей нумерацией, причем требуется, чтобы расстояние между любыми двумя точками этого пространства были вычисленными дистрибутивными числами и существовал алгоритм, дающий программу вычисления такого числа по номерам точек (отсюда и термин вычислимые числа).

Числовой нумерацией множества А называется произвольное отображение f произвольного множества QÌN; если при этом f(q)=a, то q называется f-номером, или просто номером, элемента а (aÎA и qÎQ).

Множество Q-основание или номерное множество нумерации f. Если Q=N, нумерация является натуральной (простой).

Нумерация называется разрешимой, если существует алгоритм, который применим к любой паре элементов из Q и дает ответ на вопрос, являются ли они или нет номерами одного и того же элемента из А.

Если каждый элемент А имеет только один номер (то есть f – взаимно однозначное соответствие), нумерация называется однозначной (без повторений) нумерацией.

Пример 5.4. Рассмотрим множество V'u слов русского языка на основе русского алфавита А={Æ, а, б, в, …, ю, я} (|A|=32 буквы, включая пробел, обозначенный знаком Æ).

Один из примитивных методов кодирования слов uÎV является нумерация множества А букв алфавита числами натурального ряда N. Нетрудно увидеть, что в этом случае QÌN, если Q есть множество из каких-то тридцати двух чисел. Например, отображение на рисунке 5.1.

4.1. Рис. 5.1.

Если будут нумероваться не только буквы алфавита, но и все образованные слова в каком-то порядке, считая в этом случае и буквы как однобуквенные слова, то Q=N. Номер очередного слова может определяться в соответствии с лексикографическим порядком (см. §1.2, п. 2). Очевидно, что в этом случае будем иметь соответствие g(q)=u, где u некоторое слово из множества слов V, и однозначную нумерацию.

Такого рода процедуру называют иногда арифметизацией. Введенные какие-либо достаточно простые отображения f или g позволяют перевести отношения и операции, определенные на словах, в отношения и операции на номерах. Требование «достаточной простоты» отображения сводятся к тому, чтобы некоторые основные отношения (такие, как отношение вхождения одного слова в другое, – например, вхождение слова «уда», – приспособление для ужения, – в слово на|уда|чу, и т. п.) и операции (такие, как операции соединения слов и т. п.) переходили в отношения и операции, имеющие простую алгоритмическую природу (см. дополнительно §3.3).

2. Линейные (векторные) и нормированные (банаховы) пространства в контексте теории дискретных структур представляют наибольший интерес.

Векторное (линейное) пространство над полем F – аддитивно записанная абелева группа V, в которой определено умножение на скаляр, то есть отображение F´V®V:(l,x)®lx, удовлетворяющее следующим аксиомам (x, yÎV; l, m, 1ÎF):

1)

l(x+y) = lx+ly,

2)

(l+m)x = lx+mx,

3) (lm)x = l(mx),

4) 1×x = x

Элементы векторного пространства называются точками этого пространства либо векторами, а элементы поля F – скалярами.

Векторное пространство V есть частный случай модуля над кольцом, а именно, V есть унитарный модуль (модуль с единицей) над полем. Унитарный модуль над некоммутативным телом также называют векторным пространством над телом.

Аксиомы (4.48) отражают аддитивность и однородность линейного пространства.

Пример5.5. К числу линейных пространств относятся:

1. Множество вещественных чисел R с обычно определенными операциями сложения и умножения.

2. Множество всех упорядоченных n-к вещественных чисел, если операции сложения и умножения на число определены следующим образом.

Если x=(x₁, …, x_n), y=( y₁, …, y_n), то x+y=(x₁+y₁, …, x_n+y_n);

при x, yÎR.

3. Пространство функций

.Если для любых f(x), g(x)Î под f(x)+g(x) понимается сумма значений f и g, взятые при одних и тех же значениях x. То под lf(x) нужно понимать новую функцию, полученную из f(x) умножением всех ее значений на l. Нулевой функцией будет f(x)=0 на всем отрезке [a,b].

Линейное пространство получает законченное описание тогда, когда свойства аддитивности и однородности дополнены возможностью измерения величин самих элементов (векторов). Введение к понятию линейного нормированного пространства (банахова пространства), если для каждого xÎX существует неотрицательное число

, называемое нормойx. Норма должна удовлетворять следующим условиям:

1)

=0 тогда и только тогда, когда x=0;

2)

;

3)

– неравенство треугольника.

В этом случае величина

обладает всеми свойствами меры (x, y). Действительно:

1)

=0, если x-y=0, то есть x=y;

2)

=;

3) учитывая, что y-x=-(x-y), находим

.

Следовательно, линейное нормированное пространство является метрическим пространством с метрикой

(5.3).

Все рассмотренные ранее метрические пространства дополненные свойствами аддитивности и однородности, превращаются в нормированные линейные пространства. Для этих пространств обычно используют специальные обозначения.

Пример 5.6.

1. Пространство

или с нормой при n=1 ;

2. Пространство

с нормой ;

3. Пространство

с нормой ;

4. Пространство

непрерывных функций f(t), определенных на промежутке [a,b], с нормой .

3. Дискретные пространства и пространства близости. Тривиальное замыкание, определенное ранее, удовлетворяет всем пяти условиям (см. §5.1, п. 2) и, следовательно, является топологией. Эта топология называется дискретной. Все подмножества множества X будут в этой топологии и замкнутыми, и открытыми. Всякое множество может рассматриваться как дискретное топологическое пространство, причем в конечных множествах, где всякое подмножество является объединением конечного числа элементов, возможна лишь дискретная топология.

Пример 5.7.

1. Если семейство Uсовпадает с множеством B(X) всех подмножеств X (см. §1.1, п.3), то имеет место дискретная топология.