Оглавление:
Главная страница djvu-student.narod.ru
Электрический привод
Математическая логика
Биология
Бжд
История
Психология
Литература
Экономика
Химия
Информатика
Юриспруденция
Высшая математика
Школьная математика
Сопротивление материалов
Теоретическая механика
Теоретические основы электротехники
Физика
Программы, бесплатный софт
Обратная связь
Наша кнопка


Скачать эту страницу
в формате PDF, 188 КБ

Математическая логика, учебник

Учебник, часть 1

Введение

Математическая логика – это наука о возможностях и методах математических рассуждений. Она восходит к фундаментальной работе Аристотеля, ученика Платона, написанной в 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.

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

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

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

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

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

A = {a, b, c, …}

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

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

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

A = {x : (x)}.

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

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

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

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

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

A = {x : x x}.

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

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

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

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

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

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

Аксиомы формулируются с помощью символов переменных 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, ) = ((u, v), ). Аналогично определяются упорядоченные четверки, пятерки и т.д.

Аксиома объединения. Для каждого множества 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}.

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

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

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

Обозначим это множество через {x  A : (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  Y, принимающая значения f|A(a) = f(a) при
a  A. Пусть fA = Im (f|A). Доказать, что fA – множество.

Упражнение 6

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

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

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

x + 0 = x,

x + 1 = x  {x},

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

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

для любых x, n  .

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

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

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

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

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

Положим: , .

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

.

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

Иными словами, из каждого 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, …

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

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

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

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

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

Для произвольного отношения R  A  B обратным называется отношение , состоящее из пар (b, a), для которых (a, b)  R. Например, для отношения < на , обратное отношение <-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, и отношений равенств
Id
A = {(a, a): a A} на A, IdB = {(b, b): b B} на B.


1.4. Отношение эквивалентности и фактор-множество

Пусть R – бинарное отношение на множестве X. Отношение R называется рефлексивным, если (x, x)  R для всех x  X; симметричным – если из (x, y)  R следует (y, x)  R; транзитивным – если (x, y)  R и (y, z)  R влекут (x, z)  R.

Пример 1

Будем говорить, что x  X имеет общее с элементом y  X, если множество
x  y не пусто. Отношение иметь общее будет рефлексивным и симметричным, но не транзитивным.

Отношением эквивалентности на X называется рефлексивное, транзитивное и симметричное отношение. Легко видеть, что R  X  X будет отношением эквивалентности тогда и только тогда, когда имеют место включения:

IdX  R (рефлексивность),

R-1  R (симметричность),

R  R  R (транзитивность).

В действительности эти три условия равносильны следующим:

IdX R, R-1 = R, R R = R.

Разбиением множества X называется множество А попарно непересекающихся подмножеств a  X таких, что UA = X. С каждым разбиением А можно связать отношение эквивалентности ~ на X, полагая x ~ y, если x и y являются элементами некоторого a  A.

Каждому отношению эквивалентности ~ на X соответствует разбиение А, элементами которого являются подмножества, каждое из которых состоит из находящихся в отношении ~. Эти подмножества называются классами эквивалентности. Это разбиение А называется фактор-множеством множества X по отношению ~ и обозначается: X/~.

Пример 2

Определим отношение ~ на множестве  натуральных чисел, полагая x ~ y, если остатки от деления x и y на 3 равны между собой. Тогда /~ состоит из трёх классов эквивалентности, соответствующих остаткам 0, 1 и 2.

1.5. Отношение порядка

Бинарное отношение R на множестве X называется антисимметричным, если из x R y и y R x следует: x = y. Бинарное отношение R на множестве X называется отношением порядка, если оно рефлексивно, антисимметрично и транзитивно. Легко видеть, что это равносильно выполнению следующих условий:

1) IdX  R (рефлексивность),

2) R  R-1 = IdX (антисимметричность),

3) R  R  R (транзитивность).

Упорядоченная пара (X, R), состоящая из множества X и отношения порядка R на X, называется частично упорядоченным множеством.

Пример 1

Пусть X = {0, 1, 2, 3}, R = {(0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (2, 2), (3, 3)}.

Поскольку R удовлетворяет условиям 1 – 3, то (X, R) – частично упорядоченное множество. Для элементов x = 2, y = 3, неверно ни x R y, ни y R x. Такие элементы называют несравнимыми. Обычно отношение порядка обозначают . В приведенном примере 0  1 и 2  2, но неверно, что 2  3.

Пример 2

Пусть < – бинарное отношение строгого неравенства на множестве  натуральных чисел, рассмотренное в разд. 1.2. Тогда объединение отношений = и < является отношением порядка  на  и превращает  в частично упорядоченное множество.

Элементы x, y  X частично упорядоченного множества (X, ) называются сравнимыми, если x  y либо y  x.

Частично упорядоченное множество (X, ) называется линейно упорядоченным или цепью, если любые два его элемента сравнимы. Множество из примера 2 будет линейно упорядоченным, а из примера 1 – нет.

Подмножество A  X частично упорядоченного множества (X, ) называется ограниченным сверху, если существует такой элемент x  X, что a  x для всех a  A. Элемент x  X называется наибольшим в X, если y  x для всех y  X. Элемент x  X называется максимальным, если нет отличных от x элементов y  X, для которых x  y. В примере 1 элементы 2 и 3 будут максимальными, но не наибольшими. Аналогично определяются ограничение снизу подмножества, наименьший и минимальный элементы. В примере 1 элемент 0 будет и наименьшим и минимальным. В примере 2 этими свойствами также обладает 0, но в (, ) нет ни наибольшего, ни максимального элемента.

Пусть (X, ) – частично упорядоченное множество, A  X – подмножество. Отношение на А, состоящее из пар (a, b) элементов a, b  A, для которых a  b, будет отношением порядка на А. Это отношение обозначают тем же символом: . Таким образом, (A, ) – частично упорядоченное множество. Если оно является линейно упорядоченным, то будем говорить, что А – цепь в (X, ).

1.6. Принцип максимальности

Некоторые математические утверждения невозможно доказать без аксиомы выбора. Про эти утверждения говорят, что они зависят от аксиомы выбора или справедливы в теории ZFC, на практике вместо аксиомы выбора для доказательства используют обычно либо аксиому Цермело, либо лемму Куратовского-Цорна, либо любое другое утверждение, равносильное аксиоме выбора.

Лемма Куратовского-Цорна. Если каждая цепь в частично упорядоченном множестве (X, ) ограничена сверху, то в X есть по крайней мере один максимальный элемент.

Эта лемма равносильна аксиоме выбора, и поэтому её можно принять в качестве аксиомы.

Теорема. Для любого частично упорядоченного множества (X, ) существует отношение, содержащее отношение и превращающее X в линейно упорядоченное множество.

Доказательство. Множество всех отношений порядка, содержащих отношение , упорядочено отношением включения . Поскольку объединение цепи отношений порядка будет отношением порядка, то по лемме Куратовского-Цорна существует максимальное отношение R, такое, что x  y влечет x R y. Докажем, что R – отношение, линейно упорядочивающее X. Предположим противное: пусть существуют a, b  X такие, что ни (a, b), ни (b, a) не принадлежат R. Рассмотрим отношение:

R = R {(x, y): x R a и b R y}.

Оно получается добавлением пары (a, b) к R и пар (x, y), которые должны быть добавлены к R из условия, что R – отношение порядка. Легко видеть, что R рефлексивно, антисимметрично и транзитивно. Получаем R  R, противоречащее максимальности R, следовательно, R – искомое отношение линейного порядка.

Линейно упорядоченное множество X называется вполне упорядоченным, если всякое его непустое подмножество A  X содержит наименьший элемент a  A. Лемма Куратовского-Цорна и аксиома выбора эквивалентны также следующему утверждению:

Аксиома Цермело. Для каждого множества существует отношение порядка, превращающее его во вполне упорядоченное множество.

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

Трансфинитная индукция. Если (X, ) – вполне упорядоченное множество и (x) – свойство его элементов, верное для наименьшего элемента x0  X и такое, что из истинности (y) для всех y < z следует истинность (z), то (x) верно для всех x  X.

Здесь y < z означает, что у  z, но y  z. Действительно, в противном случае среди x  X, не обладающих свойством (x), можно выбрать наименьший элемент x1, и выполнение (y) для всех y < x1 приводит к выполнению (x1), противоречащему предположению.

1.7. Понятие мощности

Пусть f: X  Y и g: Y  Z – отображения множеств. Поскольку f и g – отношения, то определена их композиция g  f(x) = g(f(x)). Если h: Z  T – отображение множеств, то h  (g  f) = (h  g)  f. Отношения IdX и IdY – функции, стало быть, определены композиции IdY  f = f  Idx = f. При X = Y определим f2 = f  f, f3 = f2  f, …, fn+1 = fn  f.

Отображение f: X Y называется инъекцей, если для любых элементов x1  x2 множества X справедливо f(x1)  f(x2). Отображение f называется сюръекцией, если для каждого y Y существует такой x  X, что f(x) = y. Если f является и сюръекцией, и инъекцией, то f называется биекцией. Легко видеть, что f – биекция тогда и только тогда, когда обратное отношение f-1  Y  X является функцией.

Будем говорить, что справедливо равенство |X| = |Y|, если существует биекция между X и Y. Положим |X|  |Y|, если существует инъекция f: X  Y.

Теорема Кантора-Шредера-Бернштейна. Если |X|  |Y| и |Y|  |X| , то |X| = |Y|.

Доказательство. По условию, существуют инъекции f: X  Y и g: Y  X. Пусть A = gY = Img – образ множества Y относительно отображения g. Тогда

(X \ A) (gf)(X \ A) = ,

(gf)(X \ A) (gf)2(X \ A) = , …,

(gf)n(X \ A) (gf)n+1(X \ A) = , …

Рассмотрим отображение : X  A, заданное как (x) = gf(x), при

x  (X \ A)  (gf)(X \ A)  (gf)2(X \ A)  …, и (x) = x в остальных случаях. Легко видеть, что  – биекция. Искомая биекция между X и Y будет равна g-1  .

1.8. Антиномия Кантора

Положим |X| < |Y|, если |X|  |Y| и не существует биекции между X и Y.

Теорема Кантора. Для любого множества X справедливо |X| < |P(X)|, где P(X) – множество всех подмножеств множества X.

Доказательство. Ясно, что |X|  |P(X)|. Предположим, что существует биекция f: X  P(X). Рассмотрим подмножество:

A = {x  X : x  f(x)}.

Если существует y  X, для которого f(y) = A, то из y  A будет следовать: y  f(y) = A; а из y  A = f(y) следует: y  A. Отсюда нет элементов y  X, таких, что f(y) = A, и, стало быть, f – не биекция. Теорема доказана. Эта теорема показывает, что необходимость уточнения понятия множества была известна Георгу Кантору:

Антиномия Кантора. Предположим, что все множества составляют некоторое множество U. Тогда каждое подмножество A  U принадлежит U. Стало быть, P(U)  U и имеет место |P(U)|  |U|, что противоречит теореме Кантора. Следовательно, собрание всех множеств не является множеством.

1.9. Аксиома выбора и сравнения мощностей

Следующее утверждение справедливо в предположении аксиомы выбора и вместе с теоремой Кантора-Шредера-Бернштейна (разд. 1.7) позволяет установить, что для любых множеств X и Y имеет место одно из соотношений:

|X| < |Y|, |X| = |Y|, |X| > |Y|.

Теорема. Пусть X и Y – множества. Тогда |X|  |Y| или |Y|  |X|.

Доказательство. Пусть T – множество пар (A. f), состоящее из подмножеств
A  X и инъекций f : A  Y. Определим на T отношение порядка, полагая для
(A1, f1) и (A2. f2) из T выполненным отношение (A1, f1)  (A2. f2), если A1  A2 и . Для произвольной цепи C  T существует пара (B, g), состоящая из и отображения g : B  Y, заданного как g(x) = f(x), если (A, f) – такая пара из T, что x  A. Эта пара (B, g) будет ограничивать сверху цепь С. Значит, любая цепь С ограничена сверху в Т, и в Т существует, по крайней мере, один максимальный элемент, который мы обозначим через (A, f). Если A  X и Im f  Y, то инъекцию f можно доопределить на некотором x  X \ A и получить таким образом элемент из T, больший чем (A, f). Это противоречие показывает, что либо A  X и Im f = Y, либо A = X. В первом случае f осуществляет биекцию некоторого подмножества из X с множеством Y, и, значит, имеет место |Y|  |X|. Во втором случае |X|  |Y|. Теорема доказана.

Замечание. В действительности эта теорема равносильна аксиоме выбора и, стало быть, может быть принята в качестве аксиомы.

1.10. Счетные множества

Мощностью множества X будем называть совокупность всех множеств Y таких, что |X| = |Y|. Обозначим мощность тем же символом |X|. Эта совокупность не является множеством, тем не менее, можно доказать, что из неё можно выбрать канонический представитель и взять его за определение мощности.

Множество X называется конечным, если существует n   такое, что |X| = |n|. Множество X называется счетным, если |X| = ||. Например, множество {0, 3, 5} конечно, а множество всех четных натуральных чисел {0, 2, 4, …} счётно.

Упражнение 1

Доказать, что множество положительных рациональных чисел Q+ – счётно.

Указание. Каждое положительное рациональное число можно представить как несократимую дробь m/n. Отсюда существует инъекция Q+    , сопоставляющая дроби m/n пару (m, n), и, значит, |Q+|  |  |. Счётность множества    доказывается стандартным способом:

Пары (m, n) располагаем в таблицу:

(0, 0) (1, 0) (2, 0) (3, 0) …

(0, 1) (1, 1) (2, 1) (3, 1) …

(0, 2) (1, 2) (2, 2) (3, 2) …

Затем их выстраиваем в последовательность: (0, 0), (1, 0), (0, 1), (0, 2), (1, 1), (2, 0), (3, 0), (2,1), (1,2), … Сопоставляя каждому n  n-й член этой последовательности, получаем биекцию между  и   . Поскольку каждое бесконечное подмножество из  счётно, отсюда получаем счётность Q+.

Упражнение 2

Доказать, что объединение двух счётных множеств счётно.

Упражнение 3

Пользуясь решениями предыдущих упражнений 2 и 1, доказать счётность всех рациональных чисел.

По теореме Кантора, || < |P()|, поэтому P() – несчётно.

Упражнение 4

Доказать, что множество действительных чисел 0 < x < 1 несчётно.

Доказательство провести методом диагонализации. Каждое число представляем в виде бесконечной десятичной дроби: 0.a1a2a3,… состоящей из цифр и не имеющей в периоде 9. Предположим, что множество таких дробей счётно. Тогда их можно расположить в виде списка строк:

0 . a11 a12 a13 a14

0 . a21 a22 a23 a24

0 . a31 a32 a33 a34

Рассмотрим последовательность цифр: b1  a11, b2  a22, b3  a33, …, не равных 9. Тогда число 0.b1b2b3 … не содержится в списке, хотя находится в интервале (0, 1). Значит, все действительные числа из этого интервала невозможно занумеровать с помощью натуральных чисел.

1.11. Булевы алгебры

Бинарной операцией на множестве A называется произвольное отображение Значения (a, b) на (a,b)  A  A обычно записываются в инфиксной форме: a  b.

Пример 1

Операция сложения +:      является бинарной операцией на множестве натуральных чисел.

Унарной операцией на множестве A называется произвольное отображение A  A.

Булевой алгеброй называется непустое множество A, на котором определены две бинарные операции ,  и одна унарная операция , удовлетворяющие для всех a, b, c  A следующим аксиомам:

  1. a b = b a, a b = b a;

  2. a (b c) = (a b) c, a (b c) = (a b) c;

  3. (a b) b = b, (a b) b = b;

  4. a (b c) = (a b) (a c), a (b c) = (a b) (a c);

  5. (a a) b = b, (a a) b = b.

Таким образом, булева алгебра – это непустое множество и операции, обладающие теми же свойствами, что и операции пересечения, объединения и дополнения подмножеств фиксированного множества.


Пример 2

Под полем множеств понимается непустое множество U подмножеств фиксированного множества X, содержащее вместе с любыми A, B  U их объединение A  B и пересечение A  B, и вместе с любым A  U – его дополнение X\A. Легко видеть, что U будет булевой алгеброй относительно операций: A  B, A  B и –A = X\A.

Пусть (A, , , ) – булева алгебра. Можно доказать, что для любых a, b  A верно a  -a = b  b и a  -a = b  b, и, значит, элементы x  x, x  x не зависят от x. Обозначим x  x через 1, а x  x через 0. Имеют место тождества:

  1. a a = a, a a = a;

  2. a 1 = 1, a 0 = 0;

  3. a 0 = a, a 1 = a;

  4. ( a) = a;

  5. (a b) = ( a) ( b), (a b) = ( a) ( b).

Докажем, например, свойство 6.

В силу симметричности определения булевой алгебры относительно операций  и , достаточно доказать: a  a = a. Применим аксиомы булевой алгебры:

a = (b a) a (по аксиоме 3)

= a (b a) (по аксиоме 1)

= a (a b) (по аксиоме 1)

= (a a) (a a) (по аксиоме 4)

= (a (a b)) (a (a b)) (по аксиоме 4)

= ((b a) a) ((b a) a) (по аксиоме 1)

= aa, что и требовалось доказать.

Для каждой булевой алгебры существует поле подмножеств некоторого множества и сохраняющая операции объединения, пересечения и дополнения биекция между элементами булевой алгебры и элементами поля подмножеств. Поэтому операции булевой алгебры обладают свойствами, аналогичными свойствам теоретико-множест­венных операций.

 Вверх...
Заметки:
» Тепловое оборудование, выбор и расчёт мощности
» Электропривод с двигателем постоянного тока приводит в движение лебедку
» Электротехника, решение задач это просто

Обучение за рубежём:
» Учеба в Великобритании
» Образование в Германии
» Образование в США
» Обучение во Франции

На этом сайте размещены ссылки на найденные в интернете книги, учебную литературу, интересный софт. Мы никак не связаны с сайтами, которые хранят научные труды на своих серверах. Все права принадлежат их авторам. Если у Вас есть авторские права на файлы и Вы не желаете чтобы они были доступны для поиска у нас, напишите нам.

Hosted by uCoz