Понятие множества и антиномии

Введение

Математическая логика – это наука о возможностях и методах математических рассуждений. Она восходит к фундаментальной работе Аристотеля, ученика Платона, написанной в IV веке до н.э. Основное положение Аристотеля заключается в том, что всякое правильное рассуждение можно свести к дедуктивному применению правил, не зависящих от природы объектов. Особое внимание он уделил «силлогизму», состоящему из соотношений вида A ® B и A & B, и способа соединения этих соотношений и их отрицаний:

.

Несмотря на то, что Аристотелю принадлежит заслуга выделения кванторов и идея модальной оценки высказываний, развитая им система описывалась громоздко и в словесной форме. Она превратилась в математическую логику лишь в XIX веке, когда Лейбниц высказал идею описания логики в символах. Создателем современной символьной логики считается Дж. Буль.

С работ Г. Фрёге (1848 – 1925 гг.) началось применение логики для исследований оснований математики. Значительный вклад в развитие математической логики внесли
Б. Рассел (1872 – 1970 гг.), А.Н. Уайтхед (1861 – 1947 гг.), Д. Гильберт (1862 – 1943 гг.), К. Гёдель (1906 – 1978 гг.), А. Тарский (1901 – 1983 гг.), А. Чёрч (р. 1903 г.),
А.И. Мальцев (1909 – 1967 гг.).

При решении математических проблем было обнаружено, что некоторые из них неразрешимы, как, например, проблема равенства слов в полугруппах. Обнаружилось, что если достаточно богатая теория непротиворечива, то существует неразрешимое в этой теории предложение (К. Гёдель). Эти глубокие результаты были получены на основе теории алгоритмов, машин Тьюринга и рекурсивных функций.

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

Цель данного учебного пособия – дать введение в математическую логику и теорию алгоритмов. Для понимания не требуется математических знаний. Учебное пособие, помимо стандартного материала, включает главу, посвящённую нечёткой пропозициональной логике и главу о модальной и темпоральной логике.

Приводятся обязательные задания для контроля знаний студентов. Авторы надеются, что студенты не только сделают эти задания, но и смогут применить полученные знания при программировании прикладных задач.

В рамках дисциплины «Математическая логика и теория алгоритмов» выполняется два расчетно-графических задания. Номер варианта определяется двумя последними цифрами номера зачётной книжки следующим образом:

если 2 последние цифры номера зачётной книжки находятся в диапазоне 00 – 29, то им соответствуют номера вариантов с 01 по 30, например, числу 23 соответствует вариант 24;

в других случаях к остатку от деления числа, состоящего из двух последних цифр номера зачётной книжки, на 30 прибавляется 1. Если последние цифры зачётной книжки, например, 56, то номер варианта – 27.

Отчёт по каждому расчётно-графическому заданию сдаётся в письменном виде. После изучения курса сдаётся письменный экзамен. Экзаменационный билет составляется из экзаменационных вопросов и задач, приведённых в пособии.


Множества и отношения

Объекты, с которыми работает математика: числа, функции, последовательности, уравнения, геометрические фигуры – все представляются с помощью множеств. В данной главе обсуждаются логические проблемы, связанные с понятием множества, и предлагается способ разрешения этих проблем на основе системы аксиом Цермело и Френкеля, позволяющей дать конструктивное определение множества. Вводятся основные определения, необходимые для изложения математической логики.

Понятие множества и антиномии

Интуитивно множество представляется как собрание или совокупность объектов произвольной природы. Оно может быть задано перечислением этих объектов:

A = {a, b, c, …}

Объекты a, b, c, … называются элементами множества A, а тот факт, что объект является элементом множества A, записывается как a Î A и читается: «a принадлежит A».

Если каждому объекту x ставится в соответствие либо 1 (истина), либо 0 (ложь), то говорят, что задано свойство F(x).

Множество может быть задано как совокупность объектов, для которых F(x) = 1, в этом случае пишут:

A = {x : F(x)}.

Например, положительные действительные числа задаются формулой:

A = {x : x – действительное число и x > 0}.

Теория множеств была создана Георгом Кантором примерно в 1873 году, в работах, связанных со сходимостью рядов Фурье. Вначале она была встречена с недоверием, но с начала девяностых годов стала широко применяться в анализе и геометрии.

Противоречия, связанные с определением множества как совокупности произвольных объектов, называются антиномиями или парадоксами теории множеств. Первая из антиномий была обнаружена в 1895 году Бурали и Форти. В 1899 году Кантор установил с помощью другой антиномии, что совокупность всех множеств не является множеством. Тем не менее, ситуация не казалась слишком серьёзной. В 1902 году Бертран Рассел нашел антиномию, относящуюся к самым началам теории множеств и показывающую, что в основаниях этой дисциплины не все благополучно.

Антиномия Рассела.Пусть А – множество, элементами которого являются все множества, не содержащие себя в качестве элемента

A = {x : x Ï x}.

Тогда в случае A Ï A множество A будет элементом множества А. Если же А – элемент множества А, то A Ï A. Ни A Î A, ни A Ï A не справедливо.

Полученное противоречие показывает, что А – не множество.

Противоречия возникают и при определении множеств, число элементов которых конечно.

Антиномия Греллинга.Некоторые русские прилагательные, например, «русское», «многосложное», «неодносложное», обладают свойством, которое они называют: прилагательное «русское» само является русским, а «многосложное» – многосложным. Прилагательные «французское», «односложное», «душистое» таким свойством не обладают, и мы назовём их гетерологическими. Прилагательное «гетерологическое» является гетерологическим, если и только если оно негетерологическое.

Полученное противоречие показывает, что множество гетерологических прилагательных не существует. На эту антиномию обратили внимание Греллинг и Нельсон в 1908 году.

Аксиомы Цермело-Френкеля

Аксиомы формулируются с помощью символов переменных x, y, A, B, X, Y, x1, x2, … и отношений Î и =. Значениями переменных служат множества. Кроме множеств, объектов нет. Если множества связаны отношениями x Î y, то говорят, что x является элементом множества y, или y содержит элемент x. Каждая аксиома утверждает о существовании некоторого множества. Таким образом, множества строятся с помощью аксиом.

Аксиома пустого множества. Существует множество, не содержащее элементов. Это множество обозначается Æ.

Аксиома экстенсиональности. Два множества равны, если и только если они состоят из одних и тех же элементов. Иными словами, x = y тогда и только тогда, когда z Î x влечет
z Î y, и наоборот, из z Î y следует z Î x.

Упражнение 1

Доказать, что пустое множество является единственным.

Аксиома (неупорядоченной) пары. Для любых множеств x и y существует множество, состоящее из элементов x и y.

Это множество обозначается {x, y}. Положим {x} = {x, x}.

Упражнение 2

Доказать единственность множества {x, y}.

Указание. Для решения упражнений 1 и 2 воспользуемся аксиомой экстенсиональности.

Определим упорядоченную пару как (u, v) = {{u},{u, v}}, упорядоченную тройку (u, v, w) = ((u, v), w). Аналогично определяются упорядоченные четверки, пятерки и т.д.

Аксиома объединения. Для каждого множества x существует множество Èx, элементами которого служат элементы элементов множества x. Таким образом,
z Î Èx означает существование u Î x такого, что z Î U.

Положим, что AÈB = È{A, B}.

Будем говорить, что x – подмножество множества y и будем писать: x Í y, если каждый элемент z Î x является элементом множества y.

Аксиома множества подмножеств. Для каждого множества x существует множество P(x), элементами которого служат все подмножества множества x.

Для любого множества x положим: x + 1 = x È{x}. Определим натуральные числа по индукции:

0 = Æ, 1 = {Æ}, 2 = 1 + 1, 3 = 2 + 1, … . Таким образом, n = {0, 1, 2, …, n-1}.

Аксиома бесконечности. Натуральные числа составляют множество, которое будет далее обозначаться через w = {0, 1, 2, 3, …}; это множество w является наименьшим среди множеств, содержащих все натуральные числа.

Если каждому множеству x сопоставляется F(x) = 1, или F(x) = 0, то будем говорить, что задано свойство множеств F(x). В дальнейшем понятие свойства будет уточнено. В действительности свойство F(x) должно выражаться из отношений = и Î с помощью логических связок и кванторов, поэтому каждому из рассматриваемых свойств можно поставить в соответствие натуральное число, и все такие свойства содержатся в последовательности: F0(x), F1(x), F2(x), …

Схема аксиом выделения. Пусть F(x) – свойство множеств. Тогда для каждого множества А элементы x Î A, для которых F(x) = 1, составляют множество.

Обозначим это множество через {x Î A : F(x)}.

Определим: A Ç B = {a Î A : a Î B}, A \ B = {a Î A : a Ï B}. Здесь a Ï B означает, что a не является элементом множества B.

Декартово произведение A ´ B определяется как

A ´ B = {(a, b) : a Î A и b Î B}.

Упражнение 3

Доказать, что A ´ B – множество.

Указание. Воспользуемся схемой аксиом выделения, аксиомами объединения и множества подмножеств, и включением A ´ B Í P(P(A È B)).

Определим по индукции декартово произведение множеств:

X1 ´ X2 ´ … ´ Xn = (X1 ´ X2 ´ … ´ Xn-1) ´ Xn

В случае X1 = X2 = … = Xn = X обозначим: X1 ´ X2 ´ … ´ Xn через Xn. Определим X0 = {Æ} как множество, состоящее из одного элемента.

Отношением между X и Y называется произвольное подмножество R Í X ´ Y. Множество Dom R = {x Î X : существует y Î Y такой, что (x, y) Î R} называется областью определения отношения R. Множество Im R = {y Î Y : существует x Î X такой, что (x, y) Î R } называется образом отношения R.

Отображением или функцией f: X à Y называется такое отношение f Í X ´ Y, что Dom f = X и для любых (x, y) Î f, (x, z) Î f верно равенство y = z. Если f – функция, то f(x) обозначает элемент, для которого (x, f(x)) Î f.

Упражнение 4

Пусть YX состоит из всех функций f: X à Y. Доказать, что YX – множество.

Упражнение 5

Для произвольных функций f: X à Y и подмножества A Í X ограничением f|A функции f на A называется функция A à Y0, принимающая значения f|A(a) = f(a) при
a Î A. Пусть f¢¢A = Im (f|A). Доказать, что – f¢¢A множество.

Упражнение 6

Доказать, что если f: w à {0, 1} – функция, для которой f(0) = 1, и из f(x) = 1 следует f(x + 1) = 1, то f(x) = 1 для всех x Î w.

Бинарной операцией на множестве X называется произвольная функция: a:X´XàX. Значения этой функции a(x, y) записываются в инфиксной форме x a y.

Определим операцию сложения + : w x w ® w натуральных чисел по индукции:

x + 0 = x,

x + 1 = x È {x},

x + 2 = (x + 1) +1,

x + (n + 1) = (x + n) + 1,

для любых x, n Î w.

Будем говорить, что натуральное число x строго меньше, чем y, и будем писать: x < y, если существует неравное нулю n Î w, такое, что x + n = y.

Множество пар (x, y), удовлетворяющих соотношению x < y, будет отношением между w и w.

Пусть I – множество. Если каждому i Î I по некоторому правилу сопоставляется множество Xi, то говорят, что задано семейство множеств .

Например, X0 = w, X1 = P(w), …, Xn = P(Xn-1), …, задает семейство . С помощью рассмотренных аксиом невозможно доказать, что {X0, X1, X2, …} – множество.

Схема аксиом подстановки. Для любого семейства множеств существует множество {Xi : i Î I}, элементами которого служат все множества Xi.

Положим: , .

Декартовым произведением семейства называется множество:

.

Аксиома выбора. Для произвольного семейства непустых множеств декартово произведение не пусто.

Иными словами, из каждого Xi можно выбрать по одному элементу. Аксиома выбора не зависит от других аксиом. Поэтому различают теорию множеств ZF без аксиомы выбора и теорию множеств ZFC с аксиомой выбора.

Аксиома регулярности. Всякое непустое множество A содержит элемент
x Î A такой, что A Ç x = Æ.

Эта аксиома принадлежит фон Нейману. Она была названа им аксиомой фундирования, поскольку эта аксиома не допускает существования бесконечной последовательности множеств x0 x1 x2 … В самом деле, в противном случае множество A={x0, x1, x2, …} не удовлетворяет аксиоме.

Упражнение 7

Доказать, что в предположении аксиомы выбора аксиома регулярности следует из утверждения о том, что не существует бесконечных последовательностей множеств x0 x1 x2

Указание. Если A не удовлетворяет аксиоме регулярности, то существует последовательность x0 Î A, x1 Î A Ç x0, x2 Î A Ç x1, …

Операции над отношениями

Напомним, что отношением между множествами A и B называется произвольное подмножество R Í A ´ B. Поскольку отношения являются подмножествами множества A ´ B, то для них определены операции объединения, пересечения и дополнения . Вместо (x, y) Î R обычно пишут x R y и говорят, что x находится в отношении R с y. Бинарным отношением на A называется подмножество R Í A ´ A.

Например, отношение равенства =, на множестве w натуральных чисел можно понимать как множество пар {(0, 0), (1, 1), (2, 2), …}.

Дополнением этого отношения будет отношение ¹. Отношение < будет множеством пар (x, y), для которых x < y. Объединением отношений < и = будет равно отношению £, а пересечение будет пустым отношением.

Большое значение имеют также операции обращения и композиции отношений.

Для произвольного отношения R Í A ´ B обратным называется отношение , состоящее из пар (b, a), для которых (a, b) Î R. Например, для отношения < на w, обратное отношение <-1 состоит из пар (y, x) таких, что x < y. Следовательно, .

Пусть заданы отношения R Í A ´ B и S Í B ´ C. Композицией называется отношение:

S ° R = {(a, c) Î A ´ C: существует b Î B такой, что (a, b) Î R и (b, c) Î S}

Имеют место соотношения:

(T ° S) ° R = T ° (S ° R),

R ° IdA = IdB ° R = R,

для любых отношений R Í A ´ B, S Í B ´ C, T Í C ´ D, и отношений равенств
IdA = {(a, a): a Î A} на A, IdB = {(b, b): b Î B} на B.