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

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

До второй половины 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), тогда:

- xÎA;

- yÏA и yÏB;

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

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

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

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

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

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

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

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

- характеристическое свойство, когда среди элементов какого-либо множества выделяются с помощью высказывания, элементы, обладающие некоторым свойством (характеризующим это множество). Пусть 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 | x>12 и x<3} = Æ;

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

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

Y = {X | XÏX}

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

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

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

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

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

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

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

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

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

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

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

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

Свойства:

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

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

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

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

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

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

Свойства

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

· Для бесконечных множеств мощность множества может совпадать с мощностью его собственного подмножества, например $|{\mathbb N}|=|\mathbb Z|$

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, или | 2^A | > | A | .

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

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

Мощность множества натуральных чисел ${\mathbb N}$ обозначается символом $\aleph_0$ («алеф-нуль»). Множество называется бесконечным, если его мощность $\ge \aleph_0$ , таким образом, счётные множества — это «самые маленькие» из бесконечных множеств. Следующие кардинальные числа в порядке возрастания обозначаются $\aleph_1, \aleph_2,\dots$ .

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

Для мощностей, как и в случае конечных множеств, имеются понятия: равенство, больше, меньше. Т.е. для любых множеств 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 | < | B | , невозможна по теореме Кантора — Бернштейна.

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

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

Глава 2. Операции над множествами

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

2.1 Сравнение множеств

множество элемент аксиоматический принадлежность

Множество A содержится во множестве B (множество B включает множество A), если каждый элемент A есть элемент B:

$A \subset B :\Leftrightarrow x \in A \Rightarrow x \in B$ .

Если $A \subset B$ и $A \ne B$ , то A называется собственным подмножеством В. Заметим, что $\forall M \quad M \subset M$ . По определению $\forall M \quad \varnothing \subset M$ .

Два множества называются равными, если они являются подмножествами друг друга: $A = B :\Leftrightarrow A \subset B \land B \subset A$

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

2.2 Основные операции над множествами

Ниже перечислены основные операции над множествами:

· объединение:

$A\cup B := \left\{x| x \in A \lor x \in B\right\}$

· пересечение:

$A\cap B := \left\{x| x\in A\land x\in B\right\}$

· разность:

$A\setminus B := \left\{x| x\in A \land x\notin B\right\}$

· симметрическая разность:

$A\triangle B \equiv A \dot - B := \left(A\cup B\right)\setminus\left(A\cap B\right) = \left\{x|(x\in A \land x\notin B)\lor(x\notin A \land x\in B)\right\}$

· дополнение:

$\overline A := \left\{x|x\notin A\right\}$

Операция дополнения подразумевает некоторый универсум (множество U, которое содержит A): $\overline A = U \setminus A$

Для лучшего понимания смысла этих операций используются диаграммы Эйлера — Венна, на которых представлены результаты операций над геометрическими фигурами как множествами точек.

Объединением двух множеств A È B (рис. 2.2.1) – называется третье множество, каждый элемент которого принадлежит хотя бы одному из множеств A и B

Рис. 2.2.1

Пересечением множеств А∩В (рис 2.2.2), является множество, состоящее из всех тех элементов, которые принадлежат одновременно всем данным множествам.

Рис 2.2.2

Разностью множеств A \ B = A – B (рис. 2.2.3) – называется такое множество, каждый элемент которого принадлежит множеству A, но не принадлежит множеству B.

Рис. 2.2.3

Симметрическая разность A D B (рис. 2.2.4)

Рис. 2.2.4

Дополнение к множеству A называется множество всех элементов, не входящих в множество A (рис 3.2.5)

Рис. 2.2.5

2.3 Свойства операций над множествами

Пусть задан универсум U. Тогда для всех A,B,CÌ Uвыполняются следующие свойства (табл. 2.3.1):

Свойства операций над множествами

Для объединения ( È )	Для пересечения ( Ç )
Идемпотентность
A È A = A	A Ç A =A
Коммутативность
A È B = B È A	A Ç B = B Ç A
Ассоциативность
A È (B È C) = (A È B) È C	A Ç (B Ç C) = (A Ç B) Ç C
Дистрибутивность
A È (B Ç C) = (A È B) Ç (A È C)	A Ç (B È C) = (A Ç B) È (A Ç C)
Поглощение
(A Ç B) È A = A	(A È B) Ç A = A
Свойства нуля
A È Æ = A	A Ç Æ = Æ
Свойства единицы
A È U = U	A Ç U = U
Инволютивность
= A
Законы де Моргана

Свойства дополнения

Выражение для разности

Выражение для симметрической разности

В справедливости перечисленных свойств можно убедиться различными способами. Например, нарисовать диаграммы Эйлера для левой и правой частей равенства и убедиться, что они совпадают, или же провести формальное рассуждение для каждого равенства. Рассмотрим для примера первое равенство: AÈA = А. Возьмем произвольный элемент х, принадлежащий левой части равенства, х ÎAÈA. По определению операции объединения È имеем хÎAÈ хÎA.В любом случае хÎA. Взяв произвольный элемент из множества в левой части равенства, обнаружили, что он принадлежит множеству в правой части. Отсюда по определению включения множеств получаем, что AÈAÌ А. Пусть теперь хÎA. Тогда, очевидно, верно хÎAÈ хÎA. Отсюда по определению операции объединения имеем х ÎAÈA. Таким образом, А ÌAÈA. Следовательно, по определению равенства множеств, AÈA = А. Аналогичные рассуждения нетрудно провести и для остальных равенств.

Докажем свойство дистрибутивности для операции объединения на диаграммах Эйлера-Венна (рис 2.3.1):

A È (B Ç C) = (A È B) Ç (A È C)

Рис. 2.3.1

Глава 3. Аксиоматическая теория множеств

3.1 Наивная теория множеств

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

После обнаружения антиномии Рассела часть математиков (например, Л. Э. Я. Брауэр и его школа) решила полностью отказаться от использования теоретико-множественных представлений. Другая же часть математиков, возглавленная Д. Гильбертом, предприняла ряд попыток обосновать ту часть теоретико-множественных представлений, которая казалась им наименее ответственной за возникновение антиномий, на основе заведомо надёжной финитной математики. С этой целью были разработаны различные аксиоматизации теории множеств.

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

В настоящее время наиболее распространённой аксиоматической теорией множеств является ZFC — теория Цермело — Френкеля с аксиомой выбора. Вопрос о непротиворечивости этой теории (а тем более — о существовании модели для неё) остаётся нерешенным.

3.2 Аксиомы теории множеств

Сейчас у нас имеются все средства, чтобы сформулировать систему аксиом теории множеств ZFC, в рамках которой можно изложить все общепринятые в современной математике способы рассуждений и не проходит ни один из известных теоретико-множественных парадоксов. Эта система позволяет строить все математические объекты исходя из пустого множества. Представим систему аксиом, Цермело — Френкеля (ZF).

1. Аксиома существования пустого множества: Существует пустое множество Æ;

2. Аксиома существования пары: Если существуют множества а и b, то существует множество { a, b };

3. Аксиома суммы: Если существует множество X, то существует множество ÈX={a | a Î b для некоторого b Î X};

4. Аксиома бесконечности: Существует множество w = { 0, 1,…,n,… }, где 0 = Æ, n + 1 = n È { n };

5. Аксиома множества всех подмножеств: Если существует множество А, то существует множество:

Р(А) = { B | B Í A};

6. Аксиома замены: Если P(x, у) — некоторое условие на множества x, у, такое, что для любого множества x существует не более одного множества у, удовлетворяющего Р(х, у), то для любого множества а существует множество {b | P(c,b) для некоторого с Î а};

7. Аксиома экстенсиональности:

Два множества, имеющие одинаковые элементы, равны, любое множество определяется своими элементами:

;

8. Аксиома регулярности:

Всякое непустое множество x имеет элемент а Î х, для которого

a Ç x = Æ.

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

Покажем, как аксиоматика ZF позволяет определять теоретико-множественные операции.

1. Определим множество A È В, исходя из множеств А к В. По аксиоме существования пары образуется множество {А, В}. С помощью аксиомы суммы получаем множество È{A, B}, которое по определению совпадает с множеством A È B.

2. Пересечение А Ç В множеств А и В определяется по аксиоме замены с помощью следующего свойства Р(х, у): х = у и х Î А. Имеем множество {b | P(c,b) и с Î В} = {b | с = b и с Î А и с ÎВ} = {c | с Î А и с ÎВ}.

3. Покажем, что из аксиом 5 и 6 следует существование множества А² = {(a, b) | a, b Î А} для любого множества А. Так как (a, b) = {{a}, {a, b}}, то А² Í P(Р(А)). Пусть свойство Р(х, у) означает, что существуют такие a, b Î А, что x = {{а}, {а, b}} и y = х. Тогда множество А² равно {b | P(c,b), c Î Р(Р(А))} и по аксиоме 6 оно существует.

Система аксиом ZFC образуется из ZF добавлением одной из следующих двух эквивалентных аксиом, которые, с одной стороны, являются наименее "очевидными", а с другой — наиболее содержательными,

1. Аксиома выбора.

Для любого непустого множества А существует такое отображение j: Р(А) \ {Æ} ®A, что j (Х) Î X |для всех X Í А, X ¹ Æ.

2. Принцип полного упорядочения. Для любого непустого множества А существует бинарное отношение £ на А, для которого {A, £} вполне упорядоченное множество.

В системе ZFC справедлив принцип трансфинитной индукции, являющийся обобщением принципа полной индукции: если {A, £} - вполне упорядоченное множество, Р(х) — некоторое свойство, то справедливость свойства Р(х) на всех элементах х Î А следует из того, что для любого z Î А выполнимость свойства Р на элементах у, где у < z, влечет выполнимость P(z):

Глава 4. Представление множеств в ЭВМ

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

Следует подчеркнуть, что, как правило, один и тот же объект может быть представлен многими разными способами, причем нельзя указать способ, который является наилучшим для всех возможных случаев. В одних случаях выгодно использовать одно представление, а в других — другое. Выбор представления зависит от целого ряда факторов: особенностей представляемого объекта, состава и относительной частоты использования операций в конкретной задаче и т. д. Умение выбрать наиболее подходящее для данного случая представление является основой искусства практического программирования. Хороший программист отличается тем, что он знает много разных способов представления и умело выбирает наиболее подходящий.

4.1 Реализация операций над подмножествами заданного универсума U

Пусть универсум U – конечный, и число элементов в нём превосходит разрядности ЭВМ: |U | < n. Элементы универсума нумеруются: U = {u₁… u_n}. Подмножество А универсума Uпредставляется кодом (машинным словом или битовой шкалой) С, в котором

1, если u₁ÎА

С₍_i₎ =

0, если u_nÏА

где С₍_i₎ – это i-й разряд кода С;

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

4.2 Генерация всех подмножеств универсума

Во многих переборных алгоритмах требуется последовательно рассмотреть все подмножества заданного множества. В большинстве компьютеров целые числа представляются кодами в двоичной системе счисления, причём число 2^k – 1 представляется кодом, содержащим k единиц. Таким образом, число 0 является представлением пустого множества Æ, число 1 является представлением подмножества, состоящего из первого элемента, и т.д. Следующий тривиальный алгоритм перечисляет все подмножества n-элементного множества.

Алгоритм генерации всех подмножеств n-элементного множества:

Вход: n ³ 0 – мощность множества;

Выход: последовательность кодов подмножеств i;

for i from 0 to 2ⁿ – 1;

yieldi

endfor

Алгоритм выдаёт 2ⁿ различных целых чисел, следовательно, 2ⁿ различных кодов. С увеличением числа увеличивается количество двоичных разрядов, необходимых для его представления. Самое большое (из генерируемых) число 2ⁿ – 1 требует своего представления ровно n разрядов. Таким образом, все подмножества генерируются, причём ровно по одному разу. Недостаток этого алгоритма состоит в том, что порядок генерации подмножеств никак не связан с их составом. Например, вслед за подмножеством с кодом 0111 будет перечислено подмножество с кодом 1000.

4.3 Представление множеств упорядоченными списками

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

elem = record

i: info {информационное поле};

: {указатель на следующий элемент};

endrecord

При таком представлении трудоёмкость операции Î составит О(n), а трудоёмкость операций Ì, Ç, È составит О(n×m), где n и m – мощности участвующих в операции множеств.

Если элементы в списках упорядочить, например, по возрастанию значения поля i, то трудоёмкость всех операций составит О(n). Эффективная реализация операций над множествами, представленными в виде упорядоченных списков, основана на весьма общем алгоритме, известном как алгоритм слияния. Алгоритм типа слияния параллельно просматривает два множества, представленных упорядоченными списками, причём на каждом шаге продвижение происходит в том множестве, в котором текущий элемент меньше.

Заключение

Курсовой проект выполнен на тему «Элементы теории множеств». В нём рассмотрены вопросы:

- Множества: элементы и множества, способы задания множеств, количество элементов в множестве;

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

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

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

На основании найденной информации (учебная литература, Internet), я выделил основные пункты, которые наиболее полно и точно дают представление о теории множеств. При выполнении работы были приведены примеры множеств, а также и те примеры, которые при