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

Введение

Математическая логика – это наука о возможностях и методах математических рассуждений. Она восходит к фундаментальной работе Аристотеля, ученика Платона, написанной в 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, x₁, x₂, … и отношений Î и =. Значениями переменных служат множества. Кроме множеств, объектов нет. Если множества связаны отношениями 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) должно выражаться из отношений = и Î с помощью логических связок и кванторов, поэтому каждому из рассматриваемых свойств можно поставить в соответствие натуральное число, и все такие свойства содержатся в последовательности: F₀(x), F₁(x), F₂(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)).

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

X₁ ´ X₂ ´ … ´ X_n = (X₁ ´ X₂ ´ … ´ X_n-1) ´ X_n

В случае X₁ = X₂ = … = X_n = X обозначим: X₁ ´ X₂ ´ … ´ X_n через Xⁿ. Определим X⁰ = {Æ} как множество, состоящее из одного элемента.

Отношением между 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

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

Упражнение 5

Для произвольных функций f: X à Y и подмножества A Í X ограничением f|_A функции f на A называется функция A à Y₀, принимающая значения 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 по некоторому правилу сопоставляется множество X_i, то говорят, что задано семейство множеств .

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

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

Положим: , .

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

.

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

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

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

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

Упражнение 7

Доказать, что в предположении аксиомы выбора аксиома регулярности следует из утверждения о том, что не существует бесконечных последовательностей множеств x₀ x₁ x₂ …

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

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

Напомним, что отношением между множествами 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 ° Id_A = Id_B ° R = R,

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