Раздел 1. Основы теории множеств.

1.1. Основные определения

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

А={₁,₂,…,_n},

где А – множество, ₁, ₂,…, _n - его элементы. Например, множество А может состоять из натуральных чисел 1, 2,…,6 при этом его элементами будут ₁=1, ₂=2, …, ₆=6.

Любой набор, каждый элемент которого принадлежит множеству А, является его подмножеством, так В={1, 2, 3} – подмножество А={1, 2, 3, 4, 5, 6} обозначается ВА. Любое множество по этому определению является собственным подмножеством.

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

Пример. Пусть S={1, 2, …, 6}. Рассмотрим формирование подмножеств множества S. С учетом пустого подмножества  в рассматриваемом множестве S может быть выделено в общей сложности 2⁶=64 подмножества:

, {1}, …, {6}, {1, 2},……,{1,2,6},…, S.

В общем случае если множество S содержит n элементов, в нем можно выделить 2ⁿ подмножеств.

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

С  В  А

S

А

С

В

Обычно каждое натуральное число воспринимается как то общее, что присуще любой совокупности М, состоящей из m предметов ; об этом делают запись вида m = |М|. Если все m предметов из совокупности М попарно различны, то совокупность эту именуют множеством, а также m-элементным множеством, при этом число m называют кардинальным числом, а также мощностью множества М.

Если |М| = 0, то говорят, что М - пустое множество, и пишут М = . Если среди предметов, входящих в совокупность М, имеются одинаковые, то такую совокупность называют мультимножеством.

Говоря о множестве М, подразумевают, что М состоит из элементов. Множество, состоящие из конечного числа элементов, т.е. имеющие конечную мощность называют конечным. Множество, не являющееся конечным, называют бесконечным. Если x есть элемент множества М, то этот факт записывают в виде x М и говорят « принадлежит М». Запись означает, что рассматривается множество, состоящее из элементов, обладающим свойством Р, а запись М₁ =x М: P(x)  и аналогичная запись М₁ = x  М | P(x) означают, что рассматривается часть множества М, причем x  М₁  (x  М  Р(x)). (Обозначения: АВ - из утверждения А следует утверждение В; АВ - из А следует В и наоборот ).

Возможно, что М₁ = 0, либо М₁ = М. В любом случае о множестве М₁ говорят, что оно суть подмножество множества М, и пишут М₁  М. Если М₁  М и М  М₁, то пишут М₁ = М и называют М₁ и М равными множествами. Если М₁  М, но М₁  М, то пишут М₁  М, т.е. М₁ строго включено в М. Если же просто М₁  М, то говорят о включении М₁ в М.

Пусть А  R . Тогда в дальнейшем А⁺ =  x  А : x  0 , так что R⁺ =  x  R : x  0, Z⁺ = x  Z : x  0 = 1,2,..., = N⁺.

Если хотя бы одним способом можно пронумеровать (пересчитать) с помощью всех натуральных чисел n  N все элементы бесконечного множества М, то говорят, что М имеет счетную мощность или является счетным множеством, и пишут |М| = |N| . Вместо |N| пишут иногда одну букву a (готическое а). Например, множество Z счетно, ибо это легко усматривается в следующей записи чисел друг под другом :

Z = ...,-3,-2,-1,0,1,2,3,...,

N = ...,6,4,2,0,1,3,5,....

В общем случае если между элементами множеств X и Y можно установить взаимно однозначное соответствие (т.е. каждому элементу x  X поставить в соответствие один и только один элемент y  Y, но так, чтобы при этом каждому y  Y также будет поставлен в соответствие некоторый элемент x  X), то говорят, что множества X и Y имеют одно и то же кардинальное число, или имеют одинаковую мощность, или равномощны, и пишут |X| = |Y|. Запись |X|  |Y| означает, что |X|  |Y|, но для некоторого подмножества Y₁  Y выполнятся |X| = =|Y₁|. Например, множество Q имеет счетную мощность, а множество R имеет более высокую мощность (континуальную мощность c ), так что а = |N| = |Q|  |R| = c, где c - готическое С. Итак, 0,1,2,... - все конечные кардинальные числа, а, с - два бесконечных кардинальных числа ; отметим, что бесконечных кардинальных чисел существует сколь угодно много.