- •Раздел I. Теория множеств и бинарные отношения
- •Тема 1. Основные понятия теории множеств
- •1. Множества и их элементы
- •2. Операции над множествами
- •3. Представление множеств в эвм
- •4. Отображения
- •Тема 2. Мощность множества
- •1. Понятие мощности
- •0/1 1/1 2/1 3/1 . . .
- •1/2 2/2 3/2 4/2 . . .
- •2. Свойства счетных множеств
- •3. Примеры несчетных множеств
- •4. Множества мощности континуума и выше
- •Тема 3. Нечеткие множества
- •1. Понятие нечеткого множества
- •Примеры записи нечеткого множества
- •Основные характеристики нечетких множеств.
- •Примеры нечетких множеств
- •Методы построения функций принадлежности нечетких множеств
- •2. Операции над нечеткими множествами
- •Свойства операций. Пусть а, в, с – нечеткие множества, тогда выполняются следующие соотношения:
- •Тема 4. Бинарные отношения
- •1. Бинарные отношения и операции над ними
- •2. Свойства операций над отношениями
- •3. Способы задания отношений
- •4. Применение отношений в информационных технологиях
- •5. Свойства бинарных отношений
- •Тема 5. Специальные бинарные отношения.
- •1. Упорядочение и безразличие
- •2. Слабый порядок
- •XIслy ( (X, y) Pсл и (y, X) Pсл )
- •XIслy ( (y, X)Pсл и (X, y)Pсл ).
- •3. Разбиение и эквивалентность
- •4. Качественный порядок
- •5. Описание и организация выбора
4. Множества мощности континуума и выше
Для мощности множества вещественных чисел R есть специальное обозначение – с. Любое множество, имеющее такую мощность называется континуумом (от английского continue – продолжаться).
Введение понятия мощность континуума порождает два вопроса.
1. Существует ли множество мощностью больше чем с?
2. Существует ли множество промежуточной мощности между счетным и континуумом?
На первый взгляд, если отрезок прямой имеет мощность континуума, то множеством мощности больше с является любая плоская фигура, например, квадрат. Однако, это не так и справедлива
Теорема 2.2. Открытый единичный квадрат на плоскости имеет мощность равную с.
Доказательство. Построим отображение f точек квадрата на его сторону. Возьмем любую точку внутри квадрата с координатами (x, y). Пусть в десятичном представлении x = 0,a1a2a3..., а y = 0,b1b2b3... . Образуем число z = f(x, y) = = 0,a1b1a2b2a3b3..., которое является координатой точки на стороне квадрата. Таким образом, мы отобразим точки квадрата на его сторону.
Возьмем две различные точки квадрата А = (x1, y1) и B = (x2, y2) и определим zA = f(A), zB = f(B). Ясно, что при А ≠ В либо x1 x2 либо y1 y2, А раз так, то эти числа отличаются хотя бы одним десятичным знаком, и значит zA zB. Значит, две разные точки A и B квадрата отображаются в две разные точки на отрезке прямой. Поэтому отображение f инъективно.
Инъективность означает, что точек в квадрате не больше, чем на отрезке. С другой стороны, их не может быть меньше, поскольку отрезок является подмножеством квадрата. Следовательно, построенное отображение f взаимно однозначно.
Тем не менее, множества мощности выше континуума существуют, более того, справедлива
Теорема 2.3. Для любого множества А существует множество В большей мощности.
Доказательство. Пусть имеется множество А. Рассмотрим множество В, являющееся множеством всех функций, определенных в точках множества А и равных 0 или 1в этих точках. Покажем, что мощность множества В больше мощности А.
Рассмотрим на множестве А функцию из B, определенную по правилу
где aА. Поставим каждой точке аА в соответствие функцию fa(x)В и рассмотрим полученное множество
B1 = { fa(x)B | aA } B.
Очевидно, что нами установлено взаимно однозначное отображение А В1. Следовательно, | A | = | B1 |, а значит | A | | B |. Покажем, что | A | | B|. Это эквивалентно тому, что не существует взаимно однозначного отображения А на все В.
Предположим противное, что существует биективное отображение : А В, которое каждому аА ставит в соответствие элемент bВ и обратно, каждой функции из B – элемент множества A. Обозначим (a) = f(a)(x), и рассмотрим функцию
g(x) = 1 – f(а)(x).
По свойствам элементов множества В имеем, что значение f(а)(x) равно 0 или 1, тогда это свойством обладает и функция g(x). Следовательно, g(x)В. Значит, по предположению, существует такая точка bА, что ей однозначно соответствует g(x), т.е. g(x) = f(b)(x). Возьмем х = b, тогда получим
g(b) = 1 – f(b)(b) = f(b)(b).
Отсюда f(b)(b)=1/2, что противоречит условию принадлежности функции f(b)(x) множеству В.
Поэтому, такого отображения не существует. Значит, | A | | B | и | A | | B|, т.е. мощность В строго больше мощности А.
Из теоремы следует, что множества самой большой мощности не существует.
Эквивалентный способ построения множества большей мощности, чем А получим, если определим B как множество, элементами которого являются всевозможные подмножества множества A. Множество всех подмножеств некоторого множества A называется булеаном и обозначается 2A (2A={ C | C A}). Тогда m(2A) = 2|A|.
Множество, мощность которого равна 2c, называется множеством мощности гиперконтинуума.
Что касается проблемы существования множества промежуточной мощности, то оказалось, что это утверждение невозможно доказать на основе аксиом теории множеств, но оно и не противоречит им.