1.3 Способы задания множеств

Перечислением (списком) элементов

М : = {a₁, a₂,… a_k}

Списком можно задавать только конечные множества. Задание типа N = 1, 2, 3… - это не список, а условное обозначение, допустимое лишь тогда, когда оно заведомо не вызывает разночтений. Список обычно заключается в фигурные скобки. Например, A = {a, b, d, h} означает, что множество A состоит из четырех элементов a, b, d, h.

Порождающей процедурой

М : = {x | x : = f }

Она описывает способ получения элементов множества из уже существующих элементов или из других объектов. Элементами множества считаются все объекты, которые могут быть построены с помощью такой процедуры. Например, описание множества M, для которого исходными объектами для построения являются натуральные числа, а порождающей процедурой – вычисление, описанное формулой /2  k.

Описанием свойств элементов множества (характеристическим предикатом)

М : = {x | P (x)}

Наиболее обычный способ задания множества. Например, N – множество всех натуральных чисел от 1 до 100.

Данное описание множеств должно быть точным и недвусмысленным. Например, множество всех хороших футболистов за всю историю футбольной команды “Динамо” Киев разные люди зададут разными списками (быть может, пустыми), так как сами критерии, по которым производится отбор, при этом будут различны.

Примеры: 1. М₉ : = {1, 2, 3, 4, 5, 6, 7, 8, 9}

2. М₉ : = {n | n  N  n < 10}

3. М₉ : = {n | for n from 1 to 9 yield n}

Примечание 1: оператор yield x означает возврат значения х, но при этом выполнение функции не прекращается, а продолжается со следующего оператора.

Примечание 2: Множество целых чисел в диапазоне от m до n обозначают так: m .. n. Т.е.

m .. n : = {k  Z | 0  k  k  n}

Примечание 3: Перечислением можно задавать только конечные множества. Бесконечные множества задаются характеристическим предикатом или порождающей процедурой.

Пример: N : = {n | n : = 0; while true n : = n + 1 do yield n endwhile}

{ Парадокс РАССЕЛА: Задание множеств характеристическим предикатом может приводить к противоречиям. Например, все рассмотренные в примерах множества не содержат себя в качестве элемента.

Рассмотрим множество всех множеств, не содержащих себя в качестве элемента:

Y = {X | X  X }

Если множество Y существует, то мы должны иметь возможность ответить на следующий вопрос: Y Y ? Пусть Y Y, тогда Y  Y. Пусть

Y  Y, тогда Y Y. Получается неустранимое логическое противоречие, которое известно как парадокс Рассела.

Существует три способа избежать этого противоречия:

1. Ограничить используемые характеристические предикаты видом

P (x) = x A  Q (x),

где А – известное, заведомо существующее множество (универсум). Обычно при этом используют обозначение {x A | Q (x)}. Для Y универсум не указан, а поэтому Y множеством не является.

2. Теория типов. Объекты имеют тип 0, множества имеют тип 1, множества множеств – тип 2 и т.д. Y не имеет типа и множеством не является.

3. Характеристический предикат P(x) задан в виде вычислимой функции (алгоритма). Способ вычисления значения предиката X X не задан, а потому Y множеством не является. }