Главная > Документ


[1]

РОБЕРТ СТОЛЛ

МНОЖЕСТВА. ЛОГИКА.

АКСИОМАТИЧЕСКИЕ ТЕОРИИ

Перевод с англ. Ю. А. Гастева и И. Х. Шмаина.

Под редакцией Ю. А. Шихановича

М. Просвещение. 1968

ОГЛАВЛЕНИЕ

Предисловие.............................................................................................................6

Глава I. Множества и отношения

1.1. Канторовское понятие множества......................................................11

1.2. Основные принципы интуитивной теории множеств ......................13

1.3. Включение.............................................................................................20

1.4. Операции над множествами................................................................23

1.5. Алгебра множеств................................................................................28

1.6. Отношения............................................................................................37

1.7. Отношения эквивалентности ............................................................ 43

1.8. Функции............................................................................................... 49

1.9. Композиция и обращение функций................................................... 55

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

Глава II. Логика

[3]

2.1. Исчисление высказываний. Сентенциональные связки…….......... 72

2.2. Исчисление высказываний. Истинностные таблицы....................... 76

2.3. Исчисление высказываний. Общезначимость.................................. 81

2.4. Исчисление высказываний. Логическое следствие………............. 93

2.5. Исчисление высказываний. Приложения....................................... 101

2.6. Исчисление предикатов. Символизация обычного языка............. 108

2.7. Исчисление предикатов. Общая формулировка............................. 116

2.8. Исчисление предикатов. Общезначимость..................................... 122

2.9. Исчисление предикатов. Логическое следствие............................ 133

Глава III. Аксиоматические теории

3.1. Понятие аксиоматической теории ……………………...................139

3.2. Неформальная аксиоматика..............................................................145

3.3. Неформальные теории в рамках теории множеств.........................152

3.4. Дальнейшие свойства неформальных теорий.................................155

3.5. Формальные аксиоматические теории………………….................165

3.6. Исчисление высказываний как формальная

аксиоматическая теория…………………………………………………167

3.7. Исчисление предикатов как формальная

аксиоматическая теория .......................................................................... 173

3.8. Аксиоматические теории первого порядка......................................176

3.9. Метаматематика.................................................................................183

Глава IV. Булевы алгебры

4.1. Определение булевой алгебры......................................................... 191

4.2. Некоторые основные свойства булевых алгебр............................. 194

4.3. Другая формулировка теории.......................................................... 198

4.4. Отношения конгруэнтности для булевых алгебр.......................... 203

4.5. Представления булевых алгебр....................................................... 211

4.6. Исчисления высказываний как булевы алгебры ………............... 217

4.7. Свободные булевы алгебры............................................................. 218

Указатель символов…………………………………..............................223

Указатель терминов..................................................................................225

Указатель имен..........................................................................................231

[6]

ПРЕДИСЛОВИЕ

Эта небольшая книжка была задумана как учебник для полугодового курса и как справочное издание. Ее содержание примыкает к той части математики, которую принято называть основаниями. Термин «основания математики» для разных людей имеет различный смысл. Что касается меня, то я понимаю под основаниями математики анализ основных математических понятий, проводимый с целью подготовки к изучению всего основанного на них здания математики с некоторой общей и единой точки зрения. Надеюсь, что материал этой книги сможет оказаться полезным для нескольких групп читателей. К одной из таких групп относятся те, кто желает, будучи студентами старших курсов, изучить некоторые разделы абстрактной математики. Другая группа (если только она отличается от первой) — это будущие преподаватели математики в высшей школе. Еще одна группа читателей — преподаватели математики средней школы. Наконец, я надеюсь, что большая часть этой книги может оказаться небесполезной для способных студентов, начинающих испытывать вкус к математике. Постараюсь подтвердить сказанное.

Во многих опубликованных за последние годы учебниках, вводящих в те или иные абстрактные разделы математики, имеется особая «глава О», посвященная краткому обзору понятий, нужных для понимания дальнейшего материала. Для студентов, впервые сталкивающихся с этими вопросами, такая вводная глава зачастую представляет трудность. Глава I настоящей книги представляет собой расширенный вариант подобной «главы 0», снабженный примерами и упражнениями.1 Эта глава — вместе с первыми четырьмя параграфами главы III, посвященными понятию аксиоматической теории, с которым ежедневно сталкивается каждый математик,— должна способствовать преодолению разрыва между первона-

[7]

чальньми представлениями студентов о математике как о вычислительной теории и абстрактной природой более глубоких и более современных ее разделов. Так, я полагаю, овладение материалом главы I и первой половины главы III позволит студенту, приступающему к изучению курса топологии, начать прямо с топологических понятий, а слушающему начальный курс абстрактной алгебры — с алгебраических понятий, не тратя времени на предварительное обсуждение понятий множества, функции, отношения порядка и т. п. Конечно, тот, кто преподает математику в высшей школе, хорошо знаком с этими понятиями. Но вполне может оказаться, что современное состояние предмета и современная терминология знакомы такому преподавателю уже не столь хорошо. Насколько такое близкое знакомство может оказаться важным, известно тем, кому приходится читать статьи в современных математических журналах, хотя бы в Mathematics Teacher, или готовиться к чтению какого-нибудь курса повышенного типа, или только разбираться в уже существующих новых разделах математической программы.

Глава II посвящена символической логике. В ней подробно излагается простейшая часть традиционной проблематики этой дисциплины — исчисление высказываний. Узкое исчисление предикатов, небольшим фрагментом которого служит исчисление высказываний, рассматривается уже довольно бегло. Однако достаточно основательное рассмотрение исчисления высказываний позволит читателю, который при изучении исчисления предикатов будет следовать образцам рассуждений, характерных для исчисления высказываний, добиться удовлетворительного понимания даже бегло освещаемых вопросов исчисления предикатов. Такая степень обстоятельности изложения символической логики, по-видимому, для большинства читателей будет достаточна. В то же время излагаемый минимум сведений не выходит за пределы того, чем должен владеть образованный человек. Относящимися к этой области проблемами занимались некоторые из величайших мыслителей, и полученные ими результаты — после надлежащего их осмысления — вошли в число наиболее впечатляющих творений человеческого интеллекта. Любой серьезный студент-математик должен знать элементы символической логики; удобства этого символизма он легко сможет оценить, пытаясь точно сформулировать отрицание утверждения «f непрерывна при х = а»2.

[8]

Заключительная часть главы III предназначена для читателя, желающего ознакомиться с той ролью, которую играет символическая логика в современных исследованиях проблем, относящихся к формальным аксиоматическим теориям3.

В главе IV излагается теория булевых алгебр4. Она предлагается в качестве награды тем, кто справился с главами I и II и первой половиной главы III. Многие из введенных в этих главах понятий способствуют созданию на немногих страницах полной картины элементарной части теории, представляющей не только исторический интерес, но и значение для современной математики. Для достойного завершения ";книги я избрал теорию, буквально ошеломляющую богатством своих возможностей.

Эта книга содержит заимствования из готовящегося к изданию учебника, являющегося более исчерпывающим изложением проблем оснований современной абстрактной математики. Приношу благодарность всем, кто помог мне в написании этой книги. Национальное общество оснований науки предоставило мне годичный отпуск за счет фонда Оберлинского колледжа, позволивший мне целиком посвятить это время своей работе. Калифорнийский технологический институт создал мне обстановку, чрезвычайно благоприятствующую работе. Я весьма обязан также своему бывшему коллеге профессору Angelo Margaris, способствовавшему моему логическому образованию. Профессор Margaris и издательский рецензент прочли всю рукопись, отметили мои ошибки и внесли многочисленные предложения, способствовавшие улучшению книги. Наконец—то не в последнюю очередь — я выражаю благодарность моей жене за перепечатку последовательно исправляемых вариантов текста и за терпение, проявленное ею, пока я преодолевал трудности писания.

3 сентября I960 г. Роберт Р. Столл

[9]

ГЛАВА I

МНОЖЕСТВА И ОТНОШЕНИЯ

Теория множеств как математическая дисциплина создана немецким математиком Г. Кантором (1845—1918). Исчерпывающее освещение проблем, связанных с ее возникновением и развитием, выходит за рамки наших задач, поскольку это потребовало бы довольно серьезных предварительных математических сведений. Вместо этого мы вынуждены, в порядке неудобного компромисса, дать поверхностный очерк этих вопросов. Не беда, если этот очерк не сможет в полной мере удовлетворить читателя; даже частичное понимание этих вопросов может оказаться полезным.

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

[10]

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

Настойчивое требование Кантора рассматривать бесконечность как нечто актуально данное (он рассматривал бесконечные множества и трансфинитные числа наравне с конечными множествами и натуральными числами) было для того времени большой новостью. Предубеждение по отношению к такой точке зрения обусловило непризнание работ Кантора со стороны некоторых математиков, реакция других была более благоприятна, тем более что новая теория давала доказательство существования трансцендентных чисел. Были получены также приложения теории множеств к анализу и геометрии, так что к 1890 году канторовская теория множеств получила признание в качестве самостоятельного раздела математики. В самом конце прошлого столетия обнаружилось, что позиция эта связана с определенными опасностями—оказалось, что в теории множеств могут возникнуть противоречия. Но это обстоятельство не воспринималось как очень серьезный дефект теории5 — на это указывает и то, что эти противоречия стали именоваться парадоксами, т. е. такого рода дефектами теории, для устранения которых достаточно лишь как следует разобраться в сути дела.

Идеи канторовской теории не только оказались полезными для существовавшей математики; они постепенно привели к созданию самостоятельной дисциплины — общей теории абстрактных множеств. Этой общей теории множеств и посвящена в основном данная глава.

В частности, в этой главе обсуждаются в рамках теории множеств три важных математических понятия: функция, отношение эквивалентности и отношение порядка. Параграфы 1.3—1.6 содержат необходимые предварительные сведения; в §§ 1.1 —1.2 описывается наша исходная точка зрения на теорию Кантора.

Можно было бы усомниться в разумности такой точки зрения — известно, к каким неприятным последствиям она в конце концов приводит6. Мы полагаем, однако, что важнейшие выводы, которые делаются в этой главе, не зависят от тех особенностей, которые характерны для канторовского (или «наивного») подхода к теории множеств. В самом деле, любая теория множеств, предназначенная для того, чтобы служить основой математики, должна включать основные определения и теоремы, содержащиеся в этой главе. Наивными являются лишь методы, с помощью

[11]

которых мы получим некоторые из этих результатов. В пользовании такого рода методами нет ничего особенно страшного — это обычное орудие математики7.

В этой главе мы будем предполагать, что читателю хорошо известны системы целых, рациональных, действительных и комплексных чисел. Знание этих систем расширяет возможности построения примеров, способствующих усвоению определений, теорем и т. д. Для обозначения множеств целых, рациональных, действительных и комплексных чисел мы будем использовать, соответственно, буквы Z, Q, R и С; для обозначения множеств положительных целых, положительных рациональных и положительных действительных чисел — соответственно, символы Z + , Q+ и R + .

1.1. Канторовское понятие множества

Рассмотрим, как Кантор понимает термин «множество», и разберемся вкратце, из чего складывается это понимание. Согласно канторовскому определению, множество S есть любое собрание определенных и различимых между собой объектов нашей интуиции или интеллекта, мыслимое как единое целое. Эти объекты называются элементами, или членами, множества S.

Существенным пунктом канторовского понимания является то, что собрание предметов само рассматривается как один предмет (мыслится как единое целое). Нет нужды еще раз подчеркивать, что внимание, здесь переносится с отдельных предметов на их собрания, в свою очередь понимаемые как предметы — это обстоятельство очевидным образом отражено в таких словах нашего языка, как «компания», «стая», «стадо».

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

[12]

указать. В этой связи стоит вспомнить, что элементы любого бесконечного множества даже теоретически нельзя собрать в законченную совокупность.8 Примерами могут служить, скажем, множество всех простых чисел или множество точек евклидовой плоскости, координаты которых (в некоторой фиксированной системе координат) рациональны. Имеются и конечные множества, обладающие в этом отношении той же степенью неопределенности, что и любое бесконечное множество.9

В основе известного примера, подтверждающего это последнее обстоятельство, лежит допущение, что линотипная машина, имеющая 10000 различных литер (среди которых имеются строчные и прописные буквы всех существующих на Земле алфавитов различных размеров и фасонов, цифры, знаки препинания, всевозможные специальные знаки и пустая литера для пропуска между словами), пригодна для печатания на любом языке. (Точный объем этого множества литер не играет никакой роли; читатель может заменить в этом рассуждении 10 000 любым целым числом, превышающим 1.) Условимся теперь под «книгой» понимать любую последовательность, состоящую из 1000 000 знаков, напечатанных с помощью имеющихся литер (включая пустую литеру и соответствующий ей «пустой знак» — пропуск). Таким образом, книга может содержать от 0 до 1000000 непустых знаков. Рассмотрим теперь множество всех книг. Поскольку для каждого из 1 000000 мест, которые в книге могут быть заняты знаками, имеется 10 000 различных возможностей, общее число книг оказывается равным 10 0001000000. Число это очень велико (но конечно!). Кроме всяческой тарабарщины, в это множество будут входить все учебники, когда-либо написанные или задуманные, все когда-либо напечатанные газеты, все противоправительственные памфлеты, все железнодорожные расписания, все таблицы логарифмов и т. д. и т. п. Совокупность эта столь же необъятна, как и бесконечное множество.

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

[13]

ность решить, различны они или одинаковы. Эпитет «определенный» понимается в том смысле, что если дано какое-либо множество и некоторый предмет, то можно определить, является этот предмет элементом данного множества или нет. Отсюда вытекает, что множество полностью определяется своими элементами.

1.2. Основные принципы интуитивной теории множеств

Согласно Кантору, всякое множество состоит из некоторых предметов, называемых его членами, или элементами (мы будем пользоваться обоими терминами как синонимами). Требование согласно которому для любого конкретного предмета и любого конкретного множества можно определить, является ли этот предмет элементом данного множества, означает следующее: если первое пустое место выражения «__есть элемент__» заполнено названием предмета, а второе—названием множества,

то предполагается, что о получающемся в результате предложении можно решить, является оно истинным или ложным. Таким образом, принадлежность, или членство, есть отношение между предметами и множествами. Мы будем обозначать это отношение символом Є и писать:

XA

если предмет х является элементом множества А. Если же х не есть элемент множества А, то мы будем писать:

XA

Записью

X1, X2, ….., Xn A

мы будем пользоваться в качестве сокращения для «X1A и X2A и …. XnA»

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

Интуитивный принцип объемности10. Два множества равны в том и только в том случае, когда они состоят из одних и тех же элементов. Равенство двух множеств X и Y будет обозначаться через

X = Y,

[14]

а неравенство множеств X и Y через

XY

Следует уяснить, что принцип объемности есть нетривиальное допущение об отношении принадлежности. Доказательство равенства каких-либо двух конкретных множеств А и В состоит, вообще говоря, из двух частей: в первой части доказывается, что если XA, то XB; во второй — что если XB, то XA. Пример такого доказательства приводится ниже.

То (однозначно определенное) множество, элементами которого являются предметы,X1, X2, ….., Xn , будет обозначаться

{X1, X2, ….., Xn}

В частности, {х} — так называемое единичное множество — есть одноэлементное множество, единственным элементом которого является х.

Примеры А

1. Докажем, что множество А всех положительных четных целых чисел равно множеству В положительных целых чисел, представимых в виде суммы двух положительных нечетных целых чисел. Допустим вначале, что XA, и докажем, что XB. Если XA, то х = 2m, так что х = (2m—1)+1. Это и означает, что XB. Предположим теперь, что XB, и выведем отсюда, что XA. Если XB, то х = (2р—1)+ +(2q—1), откуда X = 2(p + q—1), из чего следует, что XA. Таким образом, мы доказали, что множества А и В состоят из одних и тех же элементов.

2. {2, 4, 6} есть множество, состоящее из первых трех положительных четных целых чисел. Поскольку {2, 4, 6} и {2, 6, 4} состоят из одних и тех же элементов, они являются равными множествами. Кроме того, по той же причине {2, 4, 6} = {2, 4, 4, 6}.

3. Элементы какого-либо множества сами могут быть множествами. Например, географическая область, известная как Соединенные Штаты Америки, есть множество из 50 элементов — штатов, каждый из которых, в свою очередь, есть множество округов. Далее, {{1, 3}, {2, 4}, {5, 6}} есть множество из трех элементов, а именно: {1, 3}, {2, 4} и {5, 6}. Множества {{1, 2}, {2, 3}} и {1, 2, 3} не равны, так как элементами первого являются {1, 2} и {2, 3}, а элементами второго — 1, 2 и 3.

4. Множества {{1,2}} и {1,2} не равны, так как первое — одноэлементное множество, имеющее единственным своим элементом {1,2}, а второе имеет своими элементами 1 и 2. Это иллюстрирует то общее замечание, со-

[15]

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

Сделаем небольшое отступление, чтобы пояснить символику, используемую нами при обсуждении теории множеств. Как правило, мы будем пользоваться строчными курсивными латинскими буквами для обозначения элементов, а для обозначения содержащих их множеств будем употреблять (пока) прописные курсивные латинские буквы. Далее, для обозначения множеств некоторых определенных видов мы будем использовать строчные греческие буквы. Если элементы какого-либо множества в свою очередь являются множествами и если мы желаем подчеркнуть это обстоятельство в обсуждении, мы будем употреблять для обозначения таких множеств, содержащих множества, прописные рукописные латинские буквы и будем называть их системами множеств. Например, мы можем в случае необходимости говорить о системе ¥ всех конечных множеств А целых чисел х. Можно сказать в качестве мнемонического правила, что уровень, занимаемый множеством в рассматриваемой иерархии множеств, определяется размером и фасоном буквы, используемой для его обозначения.

Обозначение множества с помощью фигурных скобок, употребительное для явного задания множеств, составленных из небольшого числа элементов, слишком громоздко, чтобы его использовать для задания множеств, имеющих хотя и конечное, но большое число элементов, и вовсе неприменимо для бесконечных множеств (множеств, имеющих бесконечно много элементов). Как можно задать множество, состоящее из большого числа элементов? Имеется инстинктивная тенденция различать конечные и бесконечные множества, исходящая из того, что конечное множествоможно фактически представить в виде некоторой полностью составленной совокупности, а бесконечное — нельзя. Однако обширные конечные множества (например, описанное в § 1.1 множество книг) в той же мере «неисчерпаемы», как и любое бесконечное множество. Такого рода примеры приводят нас к заключению, что проблемы эффективного описания какого-либо обширного конечного множества и описания бесконечного множества практически представляют собой одну и ту же проблему.

Обычное решение этой проблемы, исходящее от Кантора, основано на понятии «формы от х»11. Пока мы ограничимся следующим интуитивным описанием. Будем понимать под высказыванием повествовательное



Скачать документ

Похожие документы:

  1. Роберт столл множества логика аксиоматические теории

    Документ
    [1] РОБЕРТСТОЛЛМНОЖЕСТВА. ЛОГИКА. АКСИОМАТИЧЕСКИЕТЕОРИИ Перевод с англ. Ю. А. Гастева и И. Х. Шмаина. Под ... трудности писания. 3 сентября I960 г. Роберт Р. Столл [9] ГЛАВА I МНОЖЕСТВА И ОТНОШЕНИЯ Теориямножеств как математическая дисциплина создана ...
  2. Математическая логика часть 1 Логика высказываний Логика предикатов Калининград 2001г

    Учебное пособие
    ... Лавров И.А., Максимова Л.Л. Задачи по теориимножеств, матeмaтичecкoй логике и теории алгоритмов 240с. 7. ЛихтарниковЛ.М., ... Калининград: КГТУ, 1992г.. 10. Роберт P. Столл. Множества. Логика. Аксиоматическиетеории.- М.: Просвещение, 1968. – 231 ...
  3. Математическая логика часть 1 Логика высказываний Логика предикатов Калининград 2001г

    Учебное пособие
    ... Лавров И.А., Максимова Л.Л. Задачи по теориимножеств, матeмaтичecкoй логике и теории алгоритмов 240с. 7. ЛихтарниковЛ.М., ... Калининград: КГТУ, 1992г.. 10. Роберт P. Столл. Множества. Логика. Аксиоматическиетеории.- М.: Просвещение, 1968. – 231 ...
  4. Программа дисциплины «дискретная математика»

    Программа дисциплины
    ... гл.7, 8. Дополнительная литература: СтоллРоберт Р. Множества. Логика. Аксиоматическиетеории. М.: Просвещение, 1968. ... Комбинаторные алгоритмы. Теория и практика. М., Мир, 1980. 11. СтоллРоберт Р. Множества. Логика. Аксиоматическиетеории. М.: ...
  5. Программа дисциплины «дискретная математика»

    Программа дисциплины
    ... гл.7, 8. Дополнительная литература: СтоллРоберт Р. Множества. Логика. Аксиоматическиетеории. М.: Просвещение, 1968. ... Комбинаторные алгоритмы. Теория и практика. М., Мир, 1980. 11. СтоллРоберт Р. Множества. Логика. Аксиоматическиетеории. М.: ...

Другие похожие документы..