Элементы теории множеств - Курсовая работа

Например, натуральное число, по Кантору, следовало рассматривать как множество, состоящее из единственного элемента другого множества, называемого «натуральным рядом» - который, в свою очередь, сам представляет собой множество, удовлетворяющее так называемым аксиомам Пеано . При этом общему понятию «множества», рассматривавшемуся им в качестве центрального для математики, Кантор давал мало что определяющие определения вроде «множество есть многое, мыслимое как единое», и т. д. Ему принадлежит следующая характеристика понятия «множество» : Множество - это объединение определенных, различных объектов, называемых элементами множества, в единое целое. Понятие пустого множества (подобно понятию «нуль») возникает из потребности, чтобы результат всякой операции над множествами был также множеством. Множество, элементами которого являются множества, обычно называется классом или семейством.A содержится во множестве B (множество B включает множество Ниже перечислены основные операции над множествами: · объединение : · пересечение : · разность : · симметрическая разность : · дополнение : Операция дополнения подразумевает некоторый универсум (множество U, которое содержит 2.2.1) - называется третье множество, каждый элемент которого принадлежит хотя бы одному из множеств Пересечением множеств А?В (рис 2.2.2), является множество , состоящее из всех тех элементов , которые принадлежат одновременно всем данным множествам. 2.2.3) - называется такое множество, каждый элемент которого принадлежит множествуАксиома существования пары: Если существуют множества а и b, то существует множество {a, b }; Аксиома суммы: Если существует множество X, то существует множество EX={a | a I b для некоторого b I X}; Аксиома множества всех подмножеств: Если существует множество А, то существует множество: Р(А) = {B | B I Аксиома замены: Если P(x, у) - некоторое условие на множества x, у, такое, что для любого множества x существует не более одного множества у, удовлетворяющего Р(х, у), то для любого множества а существует множество {b | P(c,b) для некоторого с I а}; Аксиома экстенсиональности: Два множества, имеющие одинаковые элементы, равны, любое множество определяется своими элементами: ;Курсовой проект выполнен на тему «Элементы теории множеств».

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

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

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

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

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

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

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

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

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

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

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

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

Рис 1.1.1

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

- YIA и YIB;

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

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

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

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

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

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

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

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

- характеристическое свойство, когда среди элементов какого-либо множества выделяются с помощью высказывания, элементы, обладающие некоторым свойством (характеризующим это множество). Пусть P(x) - какое-то свойство числа x. Тогда запись {x | P(x)} означает множество всех таких чисел, которые обладают свойством P(x). Например, множество {x | x2 - 3x 2=0} есть совокупность корней уравнения x2 - 3x 2=0, то есть это множество состоит из двух элементов: 2 и 1; {x | 3 12 и x<3} = ?;

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

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

Y = {X | XIX}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Свойства

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

· Для бесконечных множеств мощность множества может совпадать с мощностью его собственного подмножества, например

Z (множество целых чисел) = {-3,-2,-1,0,1,2,3…};

N (множество натуральных чисел) = {1,2,3,4,5,6,7...};

0,1,-1,2,-2,3,-3… целых чисел столько же, сколько и натуральных

1,2, 3,4, 5, 6, 7…

· Теорема Кантора гарантирует существование более мощного множества для любого данного: Множество всех подмножеств множества A мощнее A, или | 2A | > | A | .

· С помощью канторова квадрата можно также доказать следующее полезное утверждение: Декартово произведение бесконечного множества A с самим собой равномощно A.

Следуя Кантору , мощность множества называется кардинальным числом и обозначается мощность такого множества A через | A | (сам Кантор использовал обозначение ). Иногда встречается обозначение .

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

Про множества, равномощные множеству всех вещественных чисел , говорят, что они имеют мощность континуума , и мощность таких множеств обозначается символом c (continuum). Континуум-гипотеза утверждает, что .

Для мощностей, как и в случае конечных множеств, имеются понятия: равенство, больше, меньше. Т.е. для любых множеств A и B возможно только одно из трех: 1. | A | = | B | или A и B равномощны;

2. | A | > | B | или A мощнее B, т. е. A содержит подмножество, равномощное B, но A и B не равномощны;

3. | A | < | B | или B мощнее A, в этом случае B содержит подмножество, равномощное A, но A и B не равномощны.

Ситуация, в которой A и B не равномощны и ни в одном из них нет части, равномощной другому, невозможна. Это следует из теоремы Цермело. Иначе это означало бы существование несравнимых между собой мощностей (что в принципе возможно, если не принимать аксиому выбора ).

Ситуация, в которой | A | > | B | и | A | .

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

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

Курсовой проект выполнен на тему «Элементы теории множеств». В нем рассмотрены вопросы: § Множества: элементы и множества, способы задания множеств, количество элементов в множестве;

§ Операции над множествами: сравнение множеств, основные операции над множествами, свойства операций над множествами;

§ Аксиоматическая теория множеств: наивная теория множеств, аксиомы теории множеств;

§ Представление множеств в ЭВМ: Реализация операций над подмножествами заданного универсума U, Генерация всех подмножеств универсума, Представление множеств упорядоченными списками;

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

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

1. Дискретная математика для программистов / Ф.А.Новиков. - СПБ.: Питер, 2002. - 304 с.

2. Жолков С.Ю. Математика и информатика для гуманитариев: Учебник. - М.: Гардарики, 2002. - 531 с.

3. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики: Учебник. - М.: ИНФРА-М, Новосибирск: Изд-во НГТУ, 2002. - 280 с. - (Серия «Высшее образование»)

4. Шипачев В.С. Высшая математика. Учеб. Для вузов. - 4-е изд., стер. - М.: Высшая школа. 1998. - 479 с.

5. Материал из Википедии - свободной энциклопедии. Георг Кантор (http://www.peoples.ru/science/mathematics/kantor/)

Размещено на .ru