Как зависит от множества. "элементы теории множеств". II. Отношения между множествами и способы их задания

I. Основные понятия и аксиомы теории множеств

За тысячи лет своего существования от простейших представлений о числе и фигуре математики пришла к образованию многих новых понятий и методов. Она превратилась в мощное средство изучения природы и гибкое орудие практики. XX век принес математике новые идеи, теории, расширилась сфера её применения. Математика занимает особое положение в системе наук - её нельзя отнести ни к гуманитарным, ни к естественным наукам. Но она ввела те основные понятия, которые используются в них. Таким понятием является понятие «множество», которое впервые возникло в математике и в настоящее время является общенаучным.

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

В конце 19 века Георг Кантор, немецкий математик, основоположник теории множеств, дал интуитивное определение понятию «множеству» так: «Множество есть многое, мыслимое как единое целое» . Такое определение множества потребовало введения трех символов .

Первый из них должен представлять множество как нечто «единое», т.е. являться представителем самого множества. В качестве такого символа принято применять любую прописную букву какого-либо алфавита: например, обозначать множества прописными буквами латинского алфавита А, В, …, Х или какого-либо другого по соглашению.

Второй символ должен представлять «многое», то есть рассматриваться как элемент множества. В качестве этого символа принято использовать строчные буквы этого же алфавита: a, b, …, z.

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

Стоит отметить, что такое определение понятия множества приводит к ряду внутренних противоречий теории - так называемым парадоксам.

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

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

На настоящее время существует несколько аксиоматических систем теории множеств:

Система аксиом Цермело. К этой системе аксиом часто добавляют аксиому выбора, и называют системой Цермело — Френкеля с аксиомой выбора (ZFC).

Аксиомы теории NBG. Данная система аксиом, предложенная фон Нейманом, впоследствии пересмотренная и упрощенная Робинсоном, Бернайсом и Геделем.

Система Цермело (Z-система) состоит из 7 аксиом. Опишем данные аксиомы в тех рамках, в которых они используются в школьном курсе математики.

Аксиома объемности (Z1). Если все элементы множества А принадлежат множеству В, а все элементы множества В принадлежат также множеству А, то А=В.

Для пояснения данной аксиомы нам необходимо использовать термин «подмножество»: Если каждый элемент множества A является элементом множества Z, то говорят, что А - подмножество Z, и пишут . Символ именуется «включение». Если не исключается возможность ситуации, когда Z=A, то для того чтобы акцентировать на этом внимание, пишут .

Введя термин «подмножество», сформулируем аксиому 1 в символьном виде: .

Аксиома пары (Z2). Для произвольных a и b существует множество, единственными элементами которого являются {a,b}.

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

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

В символьном виде аксиому Z3 можно записать так: . На основании данной аксиомы и вытекающих из неё теорем указываются свойства операций множеств, описание которых будут изложены в пункте 3. Аксиомы Z1 и Z2 позволяют нам ввести понятие операции объединения, пересечения, дополнение, разности множеств.

Аксиома степени (Z4). Для любого множества Х существует множество всех его подмножеств Р(Х).

Аксиома бесконечности (Z6). Существует, по крайней мере, одно бесконечное множество - натуральный ряд чисел.

Аксиома выбора (Z7) . Для всякого семейства непустых множеств существует функция, которая каждому множеству семейства сопоставляет один из элементов этого множества. Функция называется функцией выбора для заданного семейства.

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

Укажем ещё одно важное открытие в теории множеств - изображение отношений между подмножествами, для наглядного представления . Одним из первых, кто пользовался этим методом, был выдающийся немецкий математик и философ Готфрид Вильгельм Лейбниц. Затем этот метод довольно основательно развил и Леонард Эйлер. После Эйлера этот же метод разрабатывал чешский математик Бернард Больцано. Только в отличие от Эйлера он рисовал не круговые, а прямоугольные схемы. Методом кругов Эйлера пользовался и немецкий математик Эрнест Шредер. Но наибольшего расцвета графические методы достигли в сочинениях английского логика Джона Венна. В честь Венна вместо кругов Эйлера соответствующие рисунки называют иногда диаграммами Венна, а в некоторых книгах их называют также диаграммами Эйлера-Венна . Диаграммы Эйлера-Венна используются не только в математике и логике, но и в менеджменте и других прикладных направлениях.

II. Отношения между множествами и способы их задания

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

Считают, что множество определяется своими элементами, то есть множество задано, если о любом объекте можно сказать, принадлежит он этому множеству или не принадлежит. Различают два способа задания множеств.

перечисления элементов .

Например, если множество А состоит из элементов а, b, с, то пишут: А = {a, b, c}.

Не каждое множество можно задать с помощью перечисления элементов. Множества, все элементы которых можно перечислить называют конечными. Множества, все элементы которых нельзя перечислить называют бесконечными. Их нельзя задать с помощью перечисления элементов. Исключение составляют бесконечные множества, в которых ясен порядок образование каждого следующего элемента на основе предыдущего. Например, множество натуральных чисел - бесконечное множество. Но известно, что в нем каждое следующее число, начиная со второго, на 1 больше предыдущего. Поэтому можно задать так N = {1, 2, 3, 4, …}.

Множество можно задать с помощью указания характеристического свойства.

Характеристическим свойством данного множества называется свойство, которым обладают все элементы этого множества и не обладают ни один, не принадлежащий ему элемент. Обозначается: А = {x|…}, где после вертикальной черты записывается характеристическое свойство элементов данного множества.

Например, В={1,2,3}. Нетрудно заметить, что каждый элемент множества В - натуральное число, меньшее 4. Именно это свойство элементов множества В является для него характеристическим. В этом случае пишут: и читают: «Множество В состоит из таких элементов х, что х принадлежит множеству натуральных чисел и х меньше четырех» или множество В состоит из натуральных чисел, меньших 4. Множество В можно задать и по - другому: или , и т.д.

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

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

N = {1, 2, 3, 4, …} - множество натуральных чисел;

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

Q = {x | x=p/q, где p∈Z, q∈N} - множество рациональных чисел (состоит из чисел, допускающих представление в виде обыкновенной дроби);

J - множество иррациональных чисел (множество, состоящее из бесконечных десятичных непериодических дробей, например: 1,23456342 …;, и др.)

R = (-∞; +∞) - множество действительных чисел.

Множество всех действительных чисел Л. Эйлер изобразил с помощью кругов. (Рис. 1)

Cтоит отметить, что все любые числовые множества можно задать с помощью числового промежутка. (Рис. 2)

Типы числовых промежутков

Множество С, рассмотренное выше, это числовое множество и его можно указать с помощью числового промежутка (Рис. 3)

Рисунок 3 - Числовой промежуток

Укажем еще одно важное правило для задания числовых множеств: Конечные числовые множества изображаются на числовой прямой отдельными точками.

В математике иногда приходится рассматривать множества, содержащие только один элемент, и даже множества, не имеющие ни одного элемента. Множество, не содержащее ни одного элемента, называют пустым . Его обозначают знаком ∅. Например, дано множество A={x|x∈N∧-2

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

Множество А включается во множество В, если каждый элемент множества А принадлежит множеству В. Обозначается данное отношение так: A⊂B. Или, по-другому говорят, что множество А является подмножеством множества В.

Множества А и В называются равными , тогда и только тогда, когда каждый элемент множества А принадлежит множеству В и вместе с этим каждый элемент множества В принадлежит множеству А. Обозначается данное отношение так: А=В

Например:

1) A={a,b,c,d} и B={b,d}, эти множества находятся в отношении включения B⊂A, т.к. каждый элемент множества В принадлежит множеству А.

2) M={x|x∈R∧x<6}=(-∞;6) и K{x|x∈R∧x≤8}=(-∞;8], эти множества находятся в отношении включения M⊂K, т.к. каждый элемент множества M принадлежит множеству K (Рис. 4)

Рисунок 4 - Числовой промежуток

3) A={x|x∈N∧x:2}={2,4,6,8,10,...} и B={x|x∈N∧x:3}={3,6,9,12,...}, эти два множества не находятся ни в каких отношениях A⊄B, так как во множестве А есть элемент 2, не принадлежащий множеству В

и B⊄A, т.к. во множестве В есть элемент 3, не принадлежащий множеству А.

Следовательно, данные множества не находятся ни в каких отношениях.

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

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

A∩B={x|x∈A∧x∈B}

Опр.2. Объединением множеств А и В называется операция, результатом которой является множество, состоящее из тех и только тех элементов, которые принадлежат множеству А или множеству В (т.е. хотя бы одному из этих множеств).

A∪B={x|x∈A∨x∈B}

Опр.3. Разностью множеств А и В называется операция, результатом которой является множество, состоящее из тех и только тех элементов, которые принадлежат А и не принадлежат В одновременно.

А\ В ={x∈A∧x∉B}

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

Выражения с множествами

Из множеств, знаков операций над ними и, может быть, скобок можно составлять выражения. Например, А∩В\С.

Необходимо знать порядок выполнения операций в таких выражениях и уметь их читать.

Порядок выполнения операций

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

если в выражении есть скобки, то сначала выполняют операции в скобках по порядку, приведенному в пункте 1), а затем все операции за скобками.

Например, а) А∩В\С; б) А∩(В\С); в) А∩(В\С)" .

Чтение выражения начинается с результата последней операции. Например, выражение а) читается так: разность двух множеств, первое из которых пересечение множеств А и В, а второе - множество С.

Круги Эйлера

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

Задача. Изобразить с помощью кругов Эйлера множество (А∪В)"∩С.

Решение. Расставим порядок выполнения операций в данном выражении: (А∪В)"∩С. Заштрихуем результаты операций согласно порядку их выполнения

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

Свойства I - 8 и 1 0 - 8 0 связаны между собой гак называемым принципом двойственности:

если в любом из двух столбиков свойств поменять знаки ∩→∪, ∪→∩, ∅→U, U→∅, то получится другой столбик свойств.

IV. Разбиение множества на классы

Считают, что множество Х разбито на попарно непересекающиеся подмножества или классы, если выполнены следующие условия:

1) пересечение любых двух подмножеств пусто;

2) объединение всех подмножеств совпадает с множеством Х.

Разбиение множества на классы называют классификацией.

V. Декартово произведение множеств

Декартовым произведением множеств А и В называется множество пар, первая компонента каждой из которых принадлежит множеству А, а вторая — множеству В Декартово произведение множеств А и В обозначают А х В. Таким образом, А×В={(x,y)|x∈A˄y∈B}. Операцию нахождения декартова произведения множеств А и В называют декартовым умножением этих множеств. Если А и В — числовые множества, то элементами декартова произведения этих множеств будут упорядоченные пары чисел.

VI. Правила суммы и произведения

Обозначим число элементов конечного множества A символом n(A). Если множества А и В не пересекаются, то n(AUВ)= n(А) +n (В). Если множества А и В пересекаются, то n(А U В) = n (A) + n (В) — n (A ∩ В).

Число элементов декартова произведения множеств A и В подсчитывается по формуле n (А X В) = n (A) . n (В).

Правило подсчета числа элементов объединения непересекающихся конечных множеств в комбинаторике носит название прави-ла суммы, если элемент х можно выбрать k способами, а элемент у — m способами, причем ни один из способов выбора элемента х не совпадает со способом выбора элемента у, то выбор «х или у» можно осуществить k + m способами.

Правило подсчета числа элементов декартова произведения конечных множеств в комбинаторике носит название правила произведения: если элемент х можно выбрать k способами, а элемент y - m способами, то пару (х,y) можно выбрать km способами.

VII. Список использованных источников

Асеев Г.Г. Абрамов О.М., Ситников Д.Э. Дискретная математика: Учебное пособие. - Ростов н/Д: «Феникс», Харьков: «Торсинг», 2003, -144с.

Виленкин Н. Я. Алгебра. Учебное пособие для IX - X классов средних школ с математической специализацией, 1968

Виленкин Н.Я. Рассказы о множествах. М.: Изд-во «Наука». - 1965. - 128с

Диаграммы Эйлера - Венна.URL:http://studopedia.net/1_5573_diagrammi-eylera-venna.html

Киреенко С.Г., Гриншпон И. Э. Элементы теории множеств (учебное пособие). - Томск, 2003. - 42 с.

Куратовский К., Мостовский А. Теория множеств. - М.: Мир, 1970, - 416с.

Содержание статьи
МНОЖЕСТВ ТЕОРИЯ. Под множеством понимается совокупность каких-либо объектов, называемых элементами множества. Теория множеств занимается изучением свойств как произвольных множеств, так и множеств специального вида независимо от природы образующих их элементов. Терминология и многие результаты этой теории широко используются в математике, например в математическом анализе, геометрии и теории вероятностей.

Терминология.

Если каждый элемент множества B является элементом множества A , то множество B называется подмножеством множества A . Например, если множество A состоит из чисел 1, 2 и 3, то у него существует 8 подмножеств (три из них содержат по 1 элементу, три – содержат по 2 элемента, одно подмножество, по определению, есть само множество A и восьмое подмножество – это пустое множество, не содержащее ни одного элемента). Запись x О A означает, что x – элемент множества A , а B М A – что B является подмножеством множества A . Если универсальное множество, из которого мы берем элементы всех множеств, обозначить через I , то элементы, принадлежащие I , но не входящие в A , образуют множество, называемое дополнением множества A и обозначаемое C (A ) или A ў. Множество, не содержащее ни одного элемента, называется пустым множеством.

Над множествами можно производить операции, напоминающие операции, производимые в арифметике над числами. Объединением A B множеств A и B называется множество, состоящее из всех элементов, принадлежащих хотя бы одному из множеств A и B (элемент, принадлежащий множествам A и B одновременно засчитывается при включении в A B только один раз). Пересечением A B множеств A и B называется множество, состоящее из всех элементов, принадлежащих как A , так и B . Предположим, например, что множество I состоит из всех букв русского алфавита, A – из всех согласных, а множество B – из букв, встречающихся в слове «энциклопедия». Тогда объединение A B состоит из всех букв алфавита, кроме а , ё , у , ъ , ь , ы , ю , пересечение A B – из букв д , к , л , н , п , ц , а дополнение C (A ) – из всех гласных. Раздел теории множеств, который занимается исследованием операций над множествами, называется алгеброй множеств. Пустое множество играет в алгебре множеств роль нуля, и поэтому его часто обозначают символом О ; например, A O = A , A O = O .

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

Алгебра множеств является подразделом булевых алгебр, впервые возникших в трудах Дж.Буля (1815–1864). В аксиомах булевой алгебры отражена аналогия между понятиями «множества», «событие» и «высказывания». Логические высказывания можно записать с помощью множеств и проанализировать с помощью булевой алгебры.

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

2831. Не бывает котенка, который любит рыбу и которого нельзя научить всяким забавным штукам;

2. Не бывает котенка без хвоста, который будет играть с гориллой;

3. Котята с усами всегда любят рыбу;

4. Не бывает котенка с зелеными глазами, которого можно научить забавным штукам;

5. Не бывает котят с хвостами, но без усов.

Какое заключение можно вывести из этих утверждений?

Рассмотрим следующие множества (универсальное множество I включает в себя всех котят): A – котята, любящие рыбу; B – котята, обучаемые забавным штукам; D – котята с хвостами; E – котята, которые будут играть с гориллой; F – котята с зелеными глазами и G – котята с усами. Первое утверждение гласит, что множество котят, которые любят рыбу, и дополнение множества котят, обучаемых забавным штукам, не имеют общих элементов. Символически это записывается как

Не помню, когда я впервые узнал про топологию, но меня эта наука сразу заинтересовала. Чайник превращается в бублик, сфера выворачивается наизнанку. Многие слышали про это. Но у тех, кто хочет углубиться в эту тему на более серьёзном уровне, часто возникают трудности. Особенно это относится к освоению самых начальных понятий, которые по своей сути очень абстрактны. Более того, многие источники, как будто специально стремятся запутать читателя. Скажем русская вики даёт весьма туманную формулировку того, чем занимается топология. Там говорится, что это наука изучающая топологические пространства . В статье про топологические пространства читатель может узнать, что топологические пространства - это пространства снабжённые топологией . Такие объяснения в стиле лемовских сепулек не очень проясняют суть предмета. Я попробую далее изложить основные базовые понятия в более ясной форме. В моей заметке не будет превращающихся чайников и бубликов, но будут сделаны первые шаги, которые позволят в конце концов научиться этой магии.

Впрочем, так как я не математик, а стопроцентный гуманитарий, то вполне возможно, что написанное ниже - враньё! Ну, или по крайней мере часть.

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

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

Итак, считается, что определения у множества нет и, что мы интуитивно понимаем, что это такое. Кантор говорил так: «Под «множеством» мы понимаем соединение в некое целое M определённых хорошо различимых предметов m нашего созерцания или нашего мышления (которые будут называться «элементами» множества M)». Конечно, это просто иносказательное описание, а не математическое определение.
Теория множеств известна (прошу простить за каламбур) множеством удивительных парадоксов. Например . С ней также связан кризис математики в начале XX-го века.

Теория множеств существует в нескольких вариантах, таких как ZFC или NBG и других. Вариантом теории являетсятеория типов , которая весьма важна для программистов. Наконец, некоторые математики предлагает вместо теории множеств в качестве фундамента математики использовать теорию категорий, о которой много написано на Хабре. Теория типов и теория множеств описывают математические объекты как бы «изнутри», а теория категорий не интересуется их внутренним строением, а только как они взаимодействуют, т.е. даёт их «внешнюю» характеристику.
Для нас важны только самые начальные основы теории множеств.

Множества бывают конечными.

Бывают бесконечными. Например, множество целых чисел, которое обозначается буквой ℤ (или просто Z, если у вас на клавиатуре нет фигурных букв).

Наконец, есть пустое множество. Оно ровно одно во всей Вселенной. Имеется простое доказательство этого факта, но я не буду его здесь приводить.

Если множество бесконечно, оно бывает счетным . Счетные - те множества, элементы которых можно перенумеровать натуральными числами. Само множество натуральных чисел, как вы догадались, тоже счетно. А вот как можно пронумеровать целые числа.

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

Мы зигзагом движемся по рациональным числам, начиная с 1. При этом каждому числу, которое у нас получается, присваиваем четный номер. Отрицательные рациональные числа считаются тем же способом, только номера нечетные, начиная с 3. Ноль традиционно получает первый номер. Таким образом видно, что все рациональные числа можно пронумеровать. Все числа вроде 4,87592692976340586068 или 1,00000000000001, или -9092, или даже 42 получают свой номер в этой таблице. Тем не менее, сюда попадают не все числа. Например, √2 не получит номера. Когда-то это очень огорчило греков. Говорят, того парня, который открыл иррациональные числа, утопили.

Обобщением понятия размера для множеств является мощность . Мощность конечных множеств равна числу их элементов. Мощность бесконечных множеств обозначается еврейской буквой алеф с индексом. Самая маленькая бесконечная мощность-это мощность ℵ 0 . Она равна мощности счетных множеств. Как видим, таким образом, натуральных чисел, так же много, как и целых или рациональных. Странно, но факт. Следующая - мощность континуума . Она обозначается ℵ 1 . Это мощность множества вещественных чисел ℝ, например. Существует гипотеза о том, что мощность континуума и мощность алеф-один - одно и то же. Т.е. что нет никакой промежуточной мощности меду счетными множествами и континуумом.

Над множествами можно проводить различные операции и получать новые множества.

1. Множества можно объединять.

3. Можно искать пересечение множеств.

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

1. Само S и ∅ принадлежат T.
2. Любое объединение произвольных семейств элементов T принадлежит T.
3. Пересечение произвольного конечного семейства элементов T принадлежит T.

Если эти три пункта выполняются, то наша структура является топологией T на множестве S. Элементы множества T называются открытыми множествами на S в топологии T. Дополнением к открытым множествам являются замкнутые множества. Важно отметить, что если множество открыто, это еще не означает, что оно не замкнуто и наоборот. Кроме того в данном множестве относительно некоторой топологии могут быть подмножества, которые не являются ни открытыми, ни замкнутыми.

Приведем пример. Пусть у нас есть множество, состоящее из трех цветных треугольников.

Самая простая топология на нем называется антидискретной топологией . Вот она.

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

На одном множестве можно задать несколько топологий. Вот еще одна очень примитивная топология, которая бывает. Она называется дискретной. Это топология, которая состоит из всех подмножеств данного множества.

А вот еще топология. Она задана на множестве из 7 разноцветных звезд S, которые я обозначил буквами. Убедитесь, что это топология. Я в этом не уверен, вдруг я пропустил, какое-то объединение или пересечение. На этой картинке должно быть само множество S, пустое множество, пересечения и объединения всех остальных элементов топологии также должны быть на картинке.

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

Если в множестве много точек (не говоря уже о том, что их может быть бесконечно много), то перечислить все открытые множества может быть проблематично. Например, для дискретной топологии на множестве из трех элементов, надо составить список из 8 множеств. А для 4-элементного множества дискретная топология будет насчитывать уже 16, для 5 - 32, для 6 -64 и так далее. Для того, чтобы не перечислять все открытые множества используется как бы сокращенная запись - выписываются те элементы, объединения которых могут дать, все открытые множества. Это называется базой топологии. Например, для дискретной топологии пространства из трех треугольников - это будут три треугольника взятые в отдельности, потому, что объединяя их, можно получить все остальные открытые множества в данной топологии. Говорят, что база генерирует топологию. Множества, элементы которого генерируют базу, называют предбазой.

Ниже пример базы для дискретной топологии на множестве из пяти звезд. Как видите, в данном случае база состоит всего из пяти элементов, в то время как в топологии целых 32 подмножества. Согласитесь, использовать базу для описания топологии - гораздо удобнее.

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

С понятием открытого множества неразрывно связано понятие окрестности . Некоторые авторы дают определение топологии не через открытые множества, а через окрестности. Окрестность точки p - это множество, которое содержит открытый шар с центром в этой точке. Например, на рисунке ниже показаны окрестности и не окрестности точек. Множество S 1 является окрестностью точки p, а множество S 2 нет.

Связь между открытым множеством и октестностью можно сформулировать так. Открытое множество - такое множество, каждый элемент которого имеет некоторую окрестность. Или наоборот можно сказать, что множество открыто, если оно является окрестностью любой своей точки.

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

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

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

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

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

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

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

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

Для сокращения записи мы будем пользоваться логической символикой, позволяющей коротко, наподобие формул, записывать высказывания. Понятие высказывания не определяется. Указывается только, что всякое высказывание может быть истинным или ложным (разумеется, не одновременно!).
Логические операции (связки) над множествами
Для образования из уже имеющихся высказываний новых высказываний используются следующие логические операции (или логические связки).

1. Дизъюнкция : высказывание (читается: " или ") истинно тогда и только тогда, когда истинно хотя бы одно из высказываний и .

2. Конъюнкция : высказывание (читается: " и ") истинно тогда и только тогда, когда истинны оба высказывания и .

3. Отрицание : высказывание (читается: "не ") истинно тогда и только тогда, когда ложно.

4. Импликация : высказывание (читается: "если , то " или " влечет ") истинно тогда и только тогда, когда истинно высказывание или оба высказывания ложны.

5. Эквивалентность (или равносильность) : высказывание (читается: ", если и только если ") истинно тогда и только тогда, когда оба высказывания и либо одновременно истинны, либо одновременно ложны. Любые два высказывания и , такие, что истинно , называют логически эквивалентными или равносильными.

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

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

Например, высказывание после расстановки скобок в соответствии с приоритетами примет вид

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

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

В первых двух столбцах таблицы записывают все возможные наборы значений, которые могут принимать высказывания и . Истинность высказывания обозначают буквой "И" или цифрой 1, а ложность - буквой "Л" или цифрой 0. Остальные столбцы заполняют слева направо. Так для каждого набора значений и находят соответствующие значения высказываний.

Наиболее простой вид имеют таблицы истинности логических операций (табл. 1.1-1.5).

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

Предикат есть высказывание, содержащее одно или несколько индивидных переменных. Например, " есть четное число" или " есть студент МГТУ им. Баумана, поступивший в 1999 г.". В первом предикате есть целочисленное переменное, во втором - переменное, пробегающее множество "человеческих индивидов". Примером предиката, содержащего несколько индивидных переменных, может служить: " есть сын ", " и учатся в одной и той же группе", " делится на ", " меньше " и т.п. Предикаты будем записывать в виде , полагая, что в скобках перечислены все переменные, входящие в данный предикат.

Подставляя вместо каждого переменного, входящего в предикат , конкретное значение, т.е. фиксируя значения , где - некоторые константы с соответствующей областью значений, получаем высказывание, не содержащее переменных. Например, "2 есть четное число", "Исаак Ньютон есть студент МГТУ им. Баумана, поступивший в 1999 г.", "Иванов есть сын Петрова", "5 делится на 7" и т.п. В зависимости от того, истинно или ложно полученное таким образом высказывание, говорят, что предикат выполняется или не выполняется на наборе значений переменных . Предикат, выполняющийся на любом наборе входящих в него переменных, называют тождественно истинным, а предикат, не выполняющийся ни на одном наборе значений входящих в него переменных, - тождественно ложным.

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

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

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

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

Например, высказывание читается так: "для всякого существует , такой, что истинно ". Если множества, которые пробегают переменные предикатов, фиксированы (подразумеваются "по умолчанию"), то кванторы записываются в сокращенной форме: или .

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

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

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

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

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

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

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

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

Например, означает, что " есть множество, состоящее из всех таких элементов , что каждое из них есть четное натуральное число".

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

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

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

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

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

В математике понятие множества является одним из основных, фундаментальным, однако единого определения множества не существует. Одним из наиболее устоявшихся определений множества является следующее: под множеством понимают любое собрание определённых и отличных друг от друга объектов, мыслимых как единое целое. Создатель теории множеств немецкий математик Георг Кантор (1845-1918) говорил так: "Множество есть многое, мыслимое нами как целое".

Множества как тип данных оказались очень удобными для программирования сложных жизненных ситуаций, так как с их помощью можно точно моделировать объекты реального мира и компактно отображать сложные логические взаимоотношения. Множества применяются в языке программирования Паскаль и один из примеров решения мы ниже разберём. Кроме того, на основе теории множества создана концепция реляционных баз данных, а на основе операций над множествами - реляционная алгебра и её операции - используемые в языках запросов к базам данных, в частности, SQL.

Пример 0 (Паскаль). Существует набор продуктов, продаваемых в нескольких магазинах города. Определить: какие продукты есть во всех магазинах города; полный набор продуктов в городе.

Решение. Определяем базовый тип данных Food (продукты), он может принимать значения, соответствующие названиями продуктов (например, hleb). Объявляем тип множества, он определяет все подмножества, составленные из комбинаций значений базового типа, то есть Food (продукты). И формируем подмножества: магазины "Солнышко", "Ветерок", "Огонёк", а также производные подмножества: MinFood (продукты, которые есть во всех магазинах), MaxFood (полный набор продуктов в городе). Далее прописываем операции для получения производных подмножеств. Подмножество MinFood получается в результате пересечения подмножеств Solnyshko, Veterok и Ogonyok и включает те и только те элементы этих подмножеств, которые включены в каждое их этих подмножеств (в Паскале операция пересечения множеств обозначается звёздочкой: A * B * C, математическое обозначение пересечения множеств дано далее). Подмножество MaxFood получается в результате объединения тех же подмножеств и включает элементы, которые включены во все подмножества (в Паскале операция объединения множеств обозначается знаком "плюс": A + B + C, математическое обозначение объединения множеств дано далее).

Код PASCAL

Program Shops; type Food=(hleb, moloko, myaso, syr, sol, sahar, maslo, ryba); Shop = set of Food; var Solnyshko, Veterok, Ogonyok, MinFood, MaxFood: Shop; Begin Solnyshko:=; Veterok:=; Ogonyok:=; ... MinFood:=Solnyshko * Veterok * Ogonyok; MaxFood:=Solnyshko + Veterok + Ogonyok; End.

Какие бывают множества

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

Натуральных чисел 0, 1, 2, 3, 4, ...

Простых чисел

Чётных целых чисел

и т.п. (основные числовые множества рассмотрены в этого материала).

Объекты, составляющие множество, называются его элементами. Можно сказать, что множество - это "мешок с элементами". Очень важно: в множестве не бывает одинаковых элементов.

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

Если M - множество, а a - его элемент, то пишут: a ∈M , что означает "a принадлежит множеству M ".

Из первого (нулевого) примера на Паскале с продуктами, которые есть в тех или иных магазинах:

hleb ∈VETEROK ,

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

Существуют два основных способа задания множеств: перечисление и описание.

Множество можно задать, перечислив все его элементы, например:

VETEROK = {hleb , syr , maslo } ,

A = {7 , 14 , 28 } .

Перечислением можно задать только конечное множество. Хотя можно сделать это и описанием. Но бесконечные множества можно задать только описанием.

Для описания множеств используется следующий способ. Пусть p (x ) - некоторое высказывание, которое описывает свойства переменной x , областью значений которых является множество M . Тогда через M = {x | p (x )} обозначаентся множество, состоящее из всех тех и только тех элементов, для которых высказывание p (x ) истинно. Это выражение читается так: "Множество M , состоящее из всех таких x , что p (x ) ".

Например, запись

M = {x | x ² - 3x + 2 = 0}

Пример 6. Согласно опросу 100 покупателей рынка, купивших цитрусовые, апельсины купили 29 покупателей, лимоны - 30 покупателей, мандарины - 9, только мандарины - 1, апельсины и лимоны - 10, лимоны и мандарины - 4, все три вида фруктов - 3 покупателя. Сколько покупателей не купили ни одного вида перечисленных здесь цитрусовых? Сколько покупателей купили только лимоны?

Операция декартова произведения множеств

Для определения ещё одной важной операции над множествами - декартова произведения множеств введём понятие упорядоченного набора длины n .

Длиной набора называется число n его компонент. Набор, составленный из элементов , взятых именно в этом порядке, обозначается . При этом i я () компонента набора есть .

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

Декартовым (прямым) произведением множеств называется множество, обозначаемое и состоящее из всех тех и только тех наборов длины n , i -я компонента которых принадлежит .

Например, если , , ,