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

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

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

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

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

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

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

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

Логические операции (связки) над множествами

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

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

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

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

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

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

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

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

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

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

Равносильность есть не что иное, как "двусторонняя импликация", т.е. равносильно . Это означает, что из истинности следует истинность и, наоборот, из истинности следует истинность .

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

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

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

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

Предикаты и кванторы

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

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

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

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

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

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

Связывание переменных предикатов кванторами

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

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

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

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

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

Обсудив особенности употребления логической символики, вернемся к рассмотрению множеств.

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

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

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

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

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

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

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

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

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

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

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

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

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

New Page 1

Математический анализ для чайников. Урок 1. Множества.

Понятие множества

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

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

Каждое множество задается правилом, которое однозначно определяет, принадлежит элемент к этому множеству или нет. Какие могут быть эти правила? Например, если множество конечное, можно тупо перечислить все его объекты. Можно задать диапазон. Например, все целые числа от 1 до 10. Это будет тоже конечное множество, но тут мы не перечисляем его элементы, а формулируем правило. Или неравенство, к примеру, все числа, больше 10. Это будет уже бесконечное множество, поскольку нельзя назвать самое большое число - какие бы число мы не называли, всегда есть это число плюс 1.

Как правило, множества обозначаются прописными буквами латинского алфавита A, B, C и так далее. Если множество состоит из конкретных элементов и мы хотим задать его списком этих элементов, то мы можем заключить этот список в фигурные скобки, например A={a, b, c, d}. Если a является элемент множества A, то это записывают следующим образом: a Î A . Если же a не является элементом множества A, то пишут a Ï A. Одним из важных множеств является множество N всех натуральных чисел N={1,2,3,...,} . Существует также специальное, так называемое пустое множество, которое не содержит ни одного элемента. Пустое множество обозначается символом Æ .

Определение 1 (определение равенства множеств). Множества А и B равны, если они состоят из одних и тех же элементов, то есть, если из x Î A следует x Î B и обратно, из x Î B следует x Î A.

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

(А=В ) := " x (( x Î A ) Û (x Î B )),

Это означает, что для любого объекта x соотношения x Î A и x Î B равносильны.

Здесь " – квантор всеобщности (" x читается как "для каждого x ").

Определение 2 (определение подмножества). Множество А является подмножеством множества В , если любое х принадлежащее множеству А , принадлежит множеству В. Формальное это можно представить в виде выражения:

(A Ì B ) := " x ((x Î A ) Þ (x Î B ))

Если A Ì B, но A ¹ B, то A – собственное подмножество множества В. В качестве примера можно привести опять же прямую и отрезок. Если отрезок лежит на прямой, то множество его точек являются подмножеством точек этой прямой. Или, другой пример. Множество целых чисел, которые делятся без остатка на 3, является подмножеством множества целых чисел.

Замечание. Пустое множество является подмножеством любого множества.

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

Над множествами возможны следующие операции:

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

C=A È B: = {x:x Î A или x Î B }

Пример. Решим неравенство | 2 x + 3 | > 7.

Из него следует либо неравенство 2x+3 >7, для 2x+3 ≥0, тогда x>2

либо неравенство 2x+3 <-7, для 2x+3 <0, тогда x<-5.

Множеством решений данного неравенство является объединения множеств (-∞,-5) È (2, ∞).

Давайте проверим. Посчитаем значение выражение | 2 x + 3 | для нескольких точек, лежащих и не лежащих в данном диапазоне:

x	| 2 x + 3 |
-10	17
-6	9
-5	7
-4	5
-2	1
0	3
1	5
2	7
3	9
5	13

Как видим, все решено правильно (красным обозначены пограничные диапазоны).

Пересечение. Пересечением называется операция создания нового множества из двух, содержащих элементы, которые входят в оба этих множества. Что бы изобразить это наглядно, давайте представим, что у нас есть два множества точек на плоскости, а именно фигура A и фигура B. Их пересечение обозначает фигуру C - это и есть результа операции пересечения множеств:

Формально операция пересечения множеств записывается так:

C=A Ç B := {x: x Î A и x Î B }

Пример. Пусть у нас есть множество Тогда C=A Ç B = {5,6,7}

Вычитание. Вычитание множеств - это исключение из вычитаемого множества тех элементах, которые содержатся в вычитаемом и вычитателе:

Формально вычитание множества записывается так:

A \ B: = {x:x Î A и x Ï B }

Пример. Пусть у нас есть множество A={1,2,3,4,5,6,7}, B={5,6,7,8,9,10}. Тогда C=A \ B = { 1,2,3,4}

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

A : = {x:x Î U и x Ï A} = U \ A

Графически это можно изобразить в виде:

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

Математически это можно выразить так:

A D B:= (A \ B ) È (B \ A ) = (A È B ) \ (A Ç B )

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

Из определений объединения и пересечения множеств следует, что операции пересечения и объединения обладают следующими свойствами:

1. Коммутативность.

A È B=B È A
A Ç B=B Ç A

1. Ассоциативность.

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

В математике понятие множества является одним из основных, фундаментальным, однако единого определения множества не существует. Одним из наиболее устоявшихся определений множества является следующее: под множеством понимают любое собрание определённых и отличных друг от друга объектов, мыслимых как единое целое. Создатель теории множеств немецкий математик Георг Кантор (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 -я компонента которых принадлежит .

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

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

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

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

Множества обозначим А, В, С…, а элементы множеств а, b, с…, используя латинский алфавит.

Можно сделать такую запись определения множества:

“” – принадлежит;
“=>“ – следовательно;
“ø” – пустое множество, т.е. не содержащее ни одного элемента.

Два множества будем называть равными, если они состоят из одних и тех же элементов

Например:

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

Графически это выглядит так (рис.1):

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

Рассмотрим операции над множествами и их графическую иллюстрацию (рис.2).

Объединением множеств А и В называется множество С, образованное всеми элементами, которые принадлежат хотя бы одному из множеств А или В. Слова “или ” ключевое в понимании элементов входящих в объединение множеств.

Это определение можно записать с помощью обозначений:

А υ В, где

где “ υ ” – знак объединения,

“ / ” – заменяет слова ”таких что“

Пресечение двух множеств А и В называется множество С, образованное всеми элементами, которые принадлежат и множеству А, и множеству В. Здесь уже ключевое слово “и”. Запишем коротко:

А ∩ В = С, где

“∩“ – знак пересечения. (рис.3)

Обозначим буквой Е основное или универсальное множество, где A С Е (“”- любо число), т.е. А Е = Е; АЕ =А

Множество всех элементов универсального множества Е, не принадлежащих множеству А называется дополнением множества А до Е и обозначается ĀЕ или Ā (рис.4)

Е

Примерами для понимания этих понятий являются свойства:

А Ā=Е Ø = Е Е Ā=Ā

А ∩ Ā= Ø Ē = Ø (Ā)=А

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

Введем еще одно понятие – это мощность множества.

Для конечного множества А через m (A) обозначим число элементов в множестве А.

Из определение следуют свойства:

m (A) + m (Ā) = m (E)

А = В => m(A) = m(B)

Для любых конечных множеств справедливы так же утверждения:

m (AB) =m (A) + m (В) – m (А∩В)

m (A∩B) = m (A) + m (В) – m (АВ)

m (ABC) = m (A) + m (В) + m (С)– m (А∩В) - m (А∩С) – m (В∩С) – m (А∩В∩С).

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

Задача №1

В олимпиаде по математике для абитуриентов приняло участие 40 учащихся, им было предложено решить одну задачу по алгебре, одну по геометрии и одну по тригонометрии. По алгебре решили задачу 20 человек, по геометрии – 18 человек, по тригонометрии – 18 человек.

По алгебре и геометрии решили 7 человек, по алгебре и тригонометрии – 9 человек. Ни одной задачи не решили 3 человека.

1. Сколько учащихся решили все задачи?
2. Сколько учащихся решили только две задачи?
3. Сколько учащихся решили только одну задачу?

Задача № 2

Первую или вторую контрольные работы по математике успешно написали 33 студента, первую или третью – 31 студент, вторую или третью – 32 студента. Не менее двух контрольных работ выполнили 20 студентов.

Сколько студентов успешно решили только одну контрольную работу?

Задача № 3

В классе 35 учеников. Каждый из них пользуется хотя бы одним из видов городского транспорта: метро, автобусом и троллейбусом. Всеми тремя видами транспорта пользуются 6 учеников, метро и автобусом – 15 учеников, метро и троллейбусом – 13 учеников, троллейбусом и автобусом – 9 учеников.

Сколько учеников пользуются только одним видом транспорта?

Решение задачи № 1

Запишем коротко условие и покажем решение:

• m (Е) = 40
• m (А) = 20
• m (В) = 18
• m (С) = 18
• m (А∩В) = 7
• m (А∩С) = 8
• m (В∩С) = 9

m (АВС) = 3 => m (АВС) = 40 – 3 = 37

Обозначим разбиение универсального множества Е множествами А, В, С (рис.5).

К1 – множество учеников, решивших только одну задачу по алгебре;

К2 – множество учеников, решивших только две задачи по алгебре и геометрии;

К3 – множество учеников, решивших только задачу по геометрии;

К4 – множество учеников, решивших только две задачи по алгебре и тригонометрии;

К5 – множество всех учеников, решивших все три задачи;

К6 – множество всех учеников, решивших только две задачи, по геометрии и тригонометрии;

К7 – множество всех учеников, решивших только задачу по тригонометрии;

К8 – множество всех учеников, не решивших ни одной задачи.

Используя свойство мощности множеств и рисунок можно выполнить вычисления:

Ответ:

5 учеников решили три задачи;

9 учеников решили только по две задачи;

23 ученика решили только по одной задаче.

С помощью этого метода можно записать решения второй и третьей задачи так:

Решение задачи № 2

Найти m (К1 ) + m (К3 ) + m (К7 )

Ответ:

Только одну контрольную работу решили 18 учеников.

Решение задачи № 3

• m (Е) = 35
• m (А∩В∩С)= m (К5 ) = 6
• m (А∩В)= 15
• m (А∩С)= 13
• m (В∩С)= 9

Найти m (К1) + m (К3) + m (К7 )

• m (К2 ) = m (А∩В) - m (К5 ) = 15-6=9
• m (К4 ) = m (А∩С) - m (К5 ) = 13-6=7
• m (К6 ) = m (В∩С) - m (К5 ) = 9-6=3
• m (К1 ) + m (К3 ) + m (К7 ) = m (Е) - m (К4 ) - m (К2 ) - m (К6 ) - m (К5 ) = 35-7-9-3-6=10

Ответ:

Только одним видом транспорта пользуется 10 учеников.

Литература: А.Х. Шахмейстер «Множества. Функции. Последовательности»

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

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

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

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

Итак, считается, что определения у множества нет и, что мы интуитивно понимаем, что это такое. Кантор говорил так: «Под «множеством» мы понимаем соединение в некое целое 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 нет.

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

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

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