86314 (Элементы теории множеств)

Федеральное агентство по образованию

ФГОУ ВПО

Чувашский государственный университет им. И.Н. Ульянова

Алатырский филиал

Факультет управления и экономики

Кафедра высшей математики и информационных технологий

Курсовая работа

по дисциплине: Математическая логика

Элементы теории множеств

Выполнил студент

1 курса

группы - АФТ 61-06

Научный руководитель

проф. Мерлин А.В.

Алатырь

Введение

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

До второй половины XIX века понятие «множества» не рассматривалось в качестве математического (множество книг на полке, множество человеческих добродетелей и т. д. — всё это чисто бытовые обороты речи). Положение изменилось, когда немецкий математик Георг Кантор (рис. 1) разработал свою программу стандартизации математики, в рамках которой любой математический объект должен был оказываться тем или иным «множеством».

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

Программа Кантора вызвала резкие протесты со стороны многих современных ему крупных математиков. Особенно выделялся своим непримиримым к ней отношением Леопольд Кронекер, полагавший, что математическими объектами могут считаться лишь натуральные числа и то, что к ним непосредственно сводится (известна его фраза о том, что «бог создал натуральные числа, а всё прочее — дело рук человеческих»). Тем не менее, некоторые другие математики — в частности, Готлоб Фреге и Давид Гильберт — поддержали Кантора в его намерении перевести всю математику на теоретико-множественный язык.

Однако вскоре выяснилось, что установка Кантора на неограниченный произвол при оперировании с множествами (выраженный им самим в принципе «сущность математики состоит в её свободе») является изначально порочной. А именно, был обнаружен ряд теоретико-множественных антиномий: оказалось, что при использовании теоретико-множественных представлений некоторые утверждения могут быть доказаны вместе со своими отрицаниями (а тогда, согласно правилам классической логики высказываний, может быть «доказано» абсолютно любое утверждение!). Антиномии ознаменовали собой полный провал программы Кантора.

И всё же Кантор считается основателем теории множеств, и сделал большой вклад в современную математику. Ему принадлежит следующая характеристика понятия «множество»: Множество — это объединение определённых, различных объектов, называемых элементами множества, в единое целое.

Глава 1. Множества

1.1 Элементы и множества

Понятия множества и элемента множества относятся к понятиям, не определимым явно, таким, как, например, точка и прямая. Слова «совокупность», «семейство», «система», «набор» и т.п. – синонимы слова «множество». Это связано с тем, что некоторые понятия в математике должны быть исходными, служить теми "кирпичиками", из которых складывается общая теория. Мы определяем только, как соотносятся эти исходные понятия, не говоря о природе рассматриваемых объектов. Человеческое мышление устроено так, что мир представляется состоящим из отдельных «объектов». Философам давно ясно, что мир — единое неразрывное целое, и выделение в нем объектов — это не более чем произвольный акт нашего мышления, позволяющий сформировать доступную для рационального анализа картину мира. Но как бы там ни было, выделение объектов и их совокупностей — естественный (или даже единственно возможный) способ организации нашего мышления, поэтому неудивительно, что он лежит в основе главного инструмента описания точного знания — математики.

Можно сказать, что множество — это любая определенная совокупность объектов. Объекты, из которых составлено множество, называются его элементами. Элементы множества различны и отличимые друг от друга. Примерами множеств могут быть: множество людей, животных, растений на нашей планете, а также множество N натуральных чисел 1, 2, 3, ..., множество Р простых чисел 2, 3, 5, 7, 11, ... Множество Z целых чисел: ... , -2, -1, 0, 1, 2, ..., множество R вещественных чисел и т.д. Множество, не содержащее элементов, называется пустым. Обозначение: . Пустое множество является подмножеством любого множества. Мощность пустого множества равна нулю. Понятие пустого множества (подобно понятию «нуль») возникает из потребности, чтобы результат всякой операции над множествами был также множеством.

Обычно в конкретных рассуждениях элементы всех множеств берутся из некоторого одного, достаточно широкого множества U, которое называется универсальным множеством (или универсумом).

Если объект х является элементом множества М, то говорят, что х принадлежит М. Обозначение: хМ. В противном случае говорят, что х не принадлежит М. Обозначение: хМ. Заметим, что элементы множества сами могут являться множествами. Например, множество групп студентов состоит из элементов (групп), которые, в свою очередь, состоят из студентов.

Рис 1.1.1

Пусть даны два множества А и В (рис 1.1.1), тогда:

• xA;

• yA и yB;

Подмножество – понятие части в теории множеств. Множество C является подмножеством множества B (рис. 1.1.1, обозначается CB) в случае, если каждый элемент множества C является также и элементом множества B. Например, множество всех чётных чисел является подмножеством множества всех целых чисел. Если C является подмножеством B, то B называется надмножеством C.

Обычно множества обозначают прописными буквами латинского алфавита, а элементы множеств — строчными буквами.

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

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

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

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

Иррациональность чисел поставила нас перед необходимостью работать с бесконечными множествами. Но на самом деле с бесконечностью приходится сталкиваться постоянно, например любая геометрическая фигура – множество точек: отрезок, окружность, трапеция, конус… – все эти фигуры содержат бесконечное количество точек. Исходя из этого, возникает необходимость задания множеств, для удобства работы с ними. Чтобы задать множество, нужно указать, какие элементы ему принадлежат. Это можно сделать различными способами. Укажем две наиболее употребительные формы задания (определения) множеств

• перечисление элементов, то есть указание всех элементов множества, которые принято заключать в фигурные скобки. Если элементы: , , , , - принадлежат множеству М, то записывается М=, , , , ;

• характеристическое свойство, когда среди элементов какого-либо множества выделяются с помощью высказывания, элементы, обладающие некоторым свойством (характеризующим это множество). Пусть P(x) – какое-то свойство числа x. Тогда запись x P(x) означает множество всех таких чисел, которые обладают свойством P(x). Например, множество x x² – 3x + 2=0 есть совокупность корней уравнения x² – 3x + 2=0, то есть это множество состоит из двух элементов: 2 и 1; x 3 x 7 – множество всех чисел, удовлетворяющих неравенствам 3 x 7; x x12 и x3 = ;

Однако при задании множеств как одним, так и другим способом могут возникнуть проблемы. Например, пусть множество А состоит из русских слов «стол», «мир» и символа «$» в стандартной символике, то есть А= стол, мир, $. Множество А^{^}, состоящее из таких же символов, но на английском языке, будет другим А^{^}= table, peace, $. Так что нужно быть точным в перечислении (то есть задании множеств путём перечисления). И ещё один пример, связанный с каким-либо учебником или книгой. Существует много экземпляров какой-то книги, если имеется в виду конкретная книга (например, принадлежащая определённому человеку), получим один вариант, если имелись ввиду все экземпляры, вышедшие из типографии (например, тираж 100 тыс. книг) – другой вариант, если же иметь ввиду только сохранившиеся к настоящему моменту – третий вариант. Поэтому необходимо быть точным при задании множеств перечислением.

Но и способ задания множества с помощью характеристических свойств элементов таит некоторые опасности, поскольку "неправильно" заданные свойства могут привести к противоречию. Приведем один из наиболее типичных теоретико-множественных парадоксов – парадокс Рассела. Рассмотрим множество всех множеств, не содержащих себя в качестве элемента:

Y = X XX

Если множество Y существует, то мы должны иметь возможность ответить на следующий вопрос: YY? Пусть YY, тогда должно выполняться свойство, задающее множество Y, то есть YY. Пусть YY, то, поскольку выполняется свойство, задающее Y, приходим к тому, что YY, а это противоречит предположению. Получается неустранимое логическое противоречие. Вот три способа избежать этого парадокса.

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

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

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

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

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

Последний из перечисленных способов лежит в основе так называемого конструктивизма — направления в математике, в рамках которого рассматриваются только такие объекты, для которых известны процедуры (алгоритмы) их порождения. В конструктивной математике исключаются из рассмотрения некоторые понятия и методы классической математики, чреватые возможными парадоксами.

1.3 Количество элементов в множестве

Мощность множества – это обобщение понятия количества (числа элементов множества), которое имеет смысл для всех множеств, включая бесконечные.

Существуют большие, есть меньшие бесконечные множества, среди них счётное множество является самым маленьким.

В теории множеств счётное множество есть бесконечное множество, элементы которого возможно занумеровать натуральными числами. Более формально: множество X является счётным, если существует биекция , где обозначает множество всех натуральных чисел. Другими словами, счётное множество — это множество, равномощное множеству натуральных чисел.

Счётное множество является «наименьшим» бесконечным множеством, т. е. в любом бесконечном множестве найдётся счётное подмножество.

Свойства:

1. Любое подмножество счётного множества конечно или счётно;

2. Объединение конечного или счётного числа счётных множеств счётно;

3. Прямое произведение конечного числа счётных множеств счётно;

4. Множество всех конечных подмножеств счётного множества счётно;

5. Множество всех подмножеств счётного множества континуально и, в частности, не является счётным.

Несчётное множество – такое бесконечное множество, которое не является счётным. Таким образом, любое множество является либо конечным, либо счётным, либо несчётным. Множество рациональных чисел и множество алгебраических чисел счётны, однако множество вещественных чисел континуально и, следовательно, несчётно. Два множества называются равномощными, если между ними существует биекция. Существование биекции между множествами есть отношение эквивалентности, а мощность множества — это соответствующий ему класс эквивалентности.