Множества

Теория

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

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

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

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

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

*Т. Кантор (1845-1918) — немецкий математик, основатель теории множеств.

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

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

Обычно константы и переменные, область значений которых есть некоторое числовое множество [1], а именно одно из множеств ℕ,ℤ, ℚ, ℝ и ℂ, называют соответственно натуральными, целыми (или целочисленными), рациональными, действительными и комплексными константами и переменны- переменными. В курсе дискретной математики мы будем использовать различные константы и переменные, область значений которых не всегда является числовым множеством.

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

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

  1. Дизъюнкция ∨: высказывание P ∨ Q (читается: „Р или Q") истинно тогда и только тогда, когда истинно хотя бы одно из высказываний Р и Q.
  2. Конъюнкция ∧: высказывание P ∧ Q (читается: „Р и Q") истинно тогда и только тогда, когда истинны оба высказывания Р и Q.
  3. Отрицание ¬: высказывание с¬Р (читается: „не Р") ис- истинно тогда и только тогда, когда Р ложно.
  4. Импликация ⇒: высказывание Р ⇒ Q (читается: „если Р, то Q" или „Р влечет Q") истинно тогда и только тогда, когда истинно высказывание Q или оба высказывания ложны.
  5. Эквивалентность (или равносильность) ⇔: высказывание P ⇔ Q (читается: „Р, если и только если Q") истинно тогда и только тогда, когда оба высказывания Р и Q либо одновременно истинны, либо одновременно ложны. Любые два высказывания Р и Q, такие, что истинно Р , называют логически эквивалентными или равносильными.

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

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

Например, высказывание

¬ P ∧ Q ∨ ¬ Q ∧ P ⇒ ¬ Q

после расстановки скобок в соответствии с приоритетами примет вид

(((¬ P) ∧ Q) ∨ ((¬ Q) ∧ P)) ⇒ (¬ Q).

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

Равносильность ⇔ есть не что иное, как „двусторонняя импликация", т.е. Р ⇔ Q равносильно (Р ⇒ Q) ∧ (Q ⇒ Р). Это означает, что из истинности Р следует истинность Q и, наоборот, из истинности Q следует истинность Р.

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

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

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

Tабл. 1.1-1.5. Множества

Рассмотрим сложное высказывание

(¬ P ∧ Q) ⇒ (¬ Q ∧ P).

Для удобства вычислений обозначим высказьюание ¬ P ∧ Q через А, высказывание ¬Q ∧ Р через В, а исходное высказывание запишем в виде А ⇒ В. Таблица истинности этого высказывания состоит из столбцов Р, Q, A, В и А ⇒ В (табл. 1.6). #

Tабл. 1.6. Множества

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

Предикат есть высказывание, содержащее одно или несколько индивидных переменных. Например, "х есть четное число или "х есть студент МГТУ им. Баумана, поступивший в 1999 г.". В первом предикате х есть целочисленное переменное, во втором — переменное, пробегающее множество „человеческих индивидов". Примером предиката, содержащего несколько индивидных переменных, может служить: „x есть сын у", „x, у и z учатся в одной и той же группе", „x делится на у", „х меньше у" и т.п. Предикаты будем записывать в виде Р(х), Q(x,y), R(x,у,z), полагая, что в скобках перечислены все переменные, входящие в данный предикат.

Подставляя вместо каждого переменного, входящего в предикат Р(x1,...,хn), конкретное значение, т.е. фиксируя значения х1 = a1,... ,xn = an, где a1,... ,an — некоторые константы с соответствующей областью значений, получаем высказывание, не содержащее переменных. Например, „2 есть четное число", „Исаак Ньютон есть студент МГТУ им. Баумана, поступивший в 1999 г.", „Иванов есть сын Петрова", „5 делится на 7" и т.п. В зависимости от того, истинно или ложно полученное таким образом высказывание, говорят, что предикат Р выполняется или не выполняется на наборе значений переменных х1 = a1,...,хn = аn. Предикат, выполняющийся на любом наборе входящих в него переменных, называют тождественно истинным, а предикат, не выполняющийся ни на одном наборе значений входящих в него переменных, — тождественно ложным.

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

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

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

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

(Q1x1 ∈ A1)(Q2x2 ∈ A2)...(Qnxn ∈ An)Р(х1х2,...,xn),

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

Например, высказывание (∀x ∈ А)(∃у ∈ В)Р{х,у) читается так: „для всякого х∈А существует у ∈ В, такой, что истинно Р(x,y)". Если множества, которые пробегают переменные предикатов, фиксированы (подразумеваются „по умолчанию"), то кванторы записываются в сокращенной форме: (∀x)Р(x) или (∃x)Р(x).

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

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

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

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

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

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

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

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

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

А = {х:Р(х)}.     (1.1)

Например,

А = {х: х есть четное натуральное число}

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

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

G = {х: х есть студент 2-го курса специальности

ИУ5 МГТУ им. Баумана, поступивший в 1999 г.},

в буквальном смысле слова формирует некий „коллектив".

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

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

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

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

Рассмотрим операции над множествами, которые позволяют из уже имеющихся множеств образовывать новые множества [I].

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

А∪В = {х: х ∈ А ∨ х ∈ В},

А∩В = {х: х ∈ А ∧ х ∈ В},

А\В = {х: х ∈ А ∧ х ∉ В},

АΔВ = (A\B)∪(B\A),

т.е. объединение А и В есть множество всех таких х, что х является элементом хотя бы одного из множеств A, B; пересечение А и В — множество всех таких х, что х — одновременно элемент А и элемент B; разность А \ В — множество всех таких х, что х — элемент А, но не элемент B; симметрическая разность АΔВ — множество всех таких х, что х — элемент А, но не элемент В или х — элемент В, но не элемент А.

Кроме того, фиксируя универсальное множество ∪, мы можем определить дополнение А множества А следующим образом: А = ∪\A [I]. Итак, дополнение множества А — это множество всех элементов универсального множества, не принадлежащих А.

Полезно разобраться в том, как операции над множествами, введенные выше, соотносятся с логическими операциями. Пусть А = {х: Р(х)}, В = {х: Q(x;)}, т.е. множество А задано посредством характеристического предиката Р, а множество В — посредством характеристического предиката Q.

Легко показать, что

А∪В = {х: P(x) ∨ Q(x)},

А∩В = {х: P(x) ∧ Q(x)},

А\В = {х: P(x) ∧ ¬Q(x)},

Следующие процедуры получения новых множеств связаны с понятием подмножества. Говорят, что В есть подмножество множества А, если всякий элемент В есть элемент А. Для обозначения используют запись: В С А. Говорят также, что В содержится в А, В включено в А, А включает В (имеет место включение В ⊆ А). Считают, что пустое множество есть подмножество любого множества и, если фиксировано некоторое универсальное множество, каждое рассматриваемое множество есть его подмножество. Нетрудно проверить, что если А = {х: Р(x)}, В = {х: Q(x)}, то В ⊆ А тогда и только тогда, когда высказывание Q(x) ⇒ Р(х) тождественно истинно.

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

А = В⇔((A⊆B)∧(B⊆A)).

Формула (1.2) является основой для построения доказательств о равенстве множеств. Ее применение состоит в следующем. Чтобы доказать равенство двух множеств X и У, т.е. что X = У, достаточно доказать два включения X ⊆ У и У ⊆ X, т.е. доказать, что из предположения х∈ X (для произвольного х) следует, что x ∈ У, и, наоборот, из предположения х∈ У следует, что x ∈ X. Такой метод доказательства множественных равенств называют методом двух включений. Примеры применения этого метода мы дадим позже.

Замечание. Равенство множеств {х: Р(х)} и {х: Q(x)} означает, что предикаты Р(х) и Q(x) эквивалентны, т.е. предикат Р(х) ⇔ Q(x) является тождественно истинным. #

Если В ⊆ А, но В ≠ А, то пишут В ⊂ А и В называют строгим подмножеством (или собственным подмножеством) множества А, а символ ⊂ — символом строгого включения.

Для всякого множества А может быть образовано множество всех подмножеств множества А. Его называют булеаном множества А и обозначают 2A:

2A = {Х:Х ⊆ А}.

Для булеана используют также обозначения P(A), B(A) и ехр(А).

Пример, а. Булеан множества {а, b} состоит из четырех множеств ∅, {а}, {b}, {а, b}, т.е. 2{a,b} = {∅, {а}, {b}, {а, b}}.

б. Булеан 2 состоит из всех возможных, конечных или бесконечных, подмножеств множества ℕ. Так, ∅ ∈ 2, {5} ∈ 2, вообще для любого n множество {n} ∈ 2, множество {1,...,n}∈2, {n: n = 2k, k=1,2,...} ∈2 и т.п. #

Для булеана 2A мы можем рассматривать произвольные его подмножества. Таким подмножеством, например, будет oдноэлементное множество {B}, где В — произвольное подмножество А. Подчеркнем, что единственным элементом множества {В} является, в свою очередь, некоторое множество. Вообще же образование булеана открывает путь для построения множеств, элементами которых являются множества, элементами которых, в свою очередь, являются некоторые множества, и т.д. Так можно определить множества 22A , 222A и т.д.*

*Применяя теорию множеств, часто выстраивают подобные „башни" булеанов, начиная этот процесс с элементов, не рассматриваемых как множества. Такие элементы называют праэлементами. Далее в качестве праэлементов берутся любые числа, а также такие объекты, как константы, переменные, буквы какого-нибудь алфавита и т.п.

Введенные выше операции над множествами обладают следующими свойствами:

  1. A∪B = B∪A
  2. A∩B = B∩A
  3. A∪(B∪C) = (A∪B)∪C
  4. A∩(B∩C) = (∩AB)∩C
  5. A∩(B∪C) = (A∩B)∪(A∩C)
  6. A∪(B∩C) = (A∪B)∩(A∪C)
  7. A∪B = AB
  8. A∩B = AB
  9. A∪∅ = A
  10. A∩∅=∅
  11. A∩∪ = A
  12. A∪∪ = ∪
  13. A∪A = ∪
  14. A∪A =∪
  15. A∪A =A
  16. A∩A =A
  17. A =A
  18. A\B = A∩B
  19. AΔB = (\(A∩B)
  20. (AΔB)ΔC= AΔ(BΔC)
  21. AΔB = BΔA
  22. A∩(BΔC) = (A∩B)Δ(A∩C)

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

Пусть х ∈ АΔВ. Тогда, согласно определению симметрической разности, х ∈ (А\В) ∪ (В\А). Это означает, что х ∈ (А \ В) или х ∈ (В \ А). Если х ∈ (А \ В), то х ∈ А и х ∉ В, т.е. х ∈ A ∪ В и при этом х ∉ А ∩ В. Если же х ∈ (В \ А), то х ∈ В и х ∉ А, откуда х ∈ А ∪ В и х ∉ А ∩ В. Итак, в любом случае из х ∈ (A\B)∪(B\A) следует x∈A∪B и х ∉ А ∩ В, т.е. х ∪ (A ∪ В) \ (А ∩ B). Таким образом, доказано, что

А Δ В ⊆ (A ∪ B)\(A ∩ B).

Покажем обратное включение (A ∪ B)\(A ∩ B) ⊆ А Δ В.

Пусть х ∈ (A ∪ B)\(A ∩ B). Тогда х ∈ A ∪ B и х ∉ A ∩ B. Из х ∈ A ∪ B следует, что х ∈ A или х ∈ B. Если х ∈ A, то с учетом х ∉ A ∩ B имеем х ∉ B, и поэтому х ∈ A \ B. Если же х ∈ B, то опять-таки в силу х ∉ A ∩ B получаем, что х ∉ A и х ∈ B \ A. Итак, х ∈ A \ B или х ∈ B \ A, т.е. х ∈ (A\B) ∪ (B\A).

Следовательно,

(A ∪ B)\(A ∩ B) ⊆ А Δ В.

Оба включения имеют место, и тождество 19 доказано.

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

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

Докажем этим методом тождество 22, пользуясь тождествами 1-19. Преобразуем левую часть к правой:

= ((А∩В)Δ(А∩С))=(А∩В)∪(А∩С) ∩ (А∩В)∩(А∩С) =

= (А∩(В∪С))∩((А∩В)(А∩С)) =

= (A∩(B∪C))∩(AB)∪(AC) =

=(A∩(B∪C))∩(А∪(ВС)) =

= ((А∩(В∪С))∩А)∪((А∩(В∪С))∩(ВС)) =

= ∅∪((А∩(В∪С))∩(A∩(B∩C)) =

= А∩((В∪С))∩(B∩C)) =

= А∩((В∪С))\(B∩C)) =А∩(ВΔС).

Тождество доказано.