ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ (с) http://karatel.nm.ru

Под множеством S будем понимать любое собрвние определенных и различных между собой объектов мыслимое как единое целое. Эти объекты называются элементами множества S. Для любого объекта можно установить принадлежит он множеству или нет. A={1,2,3..}, A={x|p(x)} – обозначения. Множества A и В считаются равными, если они состоят из одинаковых элементов А=В. {1,2,3}={2,1,3}={2,1,1,1,3}. 1) множество всех множеств содержащих сами себя - множество всех множеств, 2) множества, которые не содержат себя как элемент. Рассмотрим множество второго типа: A={x|x¢x}. Если А себя не содержит, то это одно из таких множеств, значит оно должно содержаться в А – парадокс рассела.

СООТНОШЕНИЕ МНОЖСТВ

AcB, если все элементы А являются элементами множества В (А содержит В), А является подмножеством В. Если 1.АсВ, 2. А≠В, то АсВ, то А является подмножеством В {1,2}c{1,2,3}, {1}c{1,2}. Множество, не содержащее элементов называется пустым и обозначается Ø. Считается, что пустое множество является подмножеством любого множества AøcA. Множество всех подмножеств А называется множеством – степенью или булеаном. А{1,2,3}, B(A)={{Ø},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}} – булеан. УТВЕРЖДЕНИЕ: если множество А состоит из n элементов, то булеан от А состоит из 2(c.n) элементов. Док-во: 1-входит, 0 – не входит, 0..2(c.n) и Ø, всего 2(c.n).

ДЕЙСТВИЯ НАД МНОЖЕСТВАМИ

Объединием AUB называется

множество, все элементы

которого являются

элементами А или В (рис.2).

AUB={x|xЄA или xЄB}. AcAUB, BcAUB. Пересечением множеств A∩B называют множество, все элементы которого являются элементами обоих множеств А и В. A∩B={x|xЄA и xЄB}, A∩BcA, A∩BcB (рис.3). Дополнением множества А называют множество эементов, не принадлежащих множеству А. А={x|x¢A} (рис.4). Симметричная разность – A+B=(A\B)U(B\A) (рис.5). Вычитание – множество принадлежит В и не принадлежит А. B\A={x|xЄB и x¢A}=B∩A(вектор).

СВОЙСТВА

1) AUB=BUA - свойства коммутативности (объединения), 1') A∩B=B∩A - коммутативный перенос, 2) ассоциативность AU(BUC)=(AUB)UC, 2') A∩(B∩C)=(A∩B)∩C, 3) дистрибутивность: AU(B∩C)=(AUB)∩(AUC), 3') A∩(BUC)=(A∩B)U(A∩C) Пример: a(b+c)=ab+ac – алгебра чисел, a+bc≠(a+b)(a+c)… 4) AUØ=A, 4’)A∩U=A, 5)AUA(надчеркнутое)=U, 5’) A∩A(надчеркн)=Ø, 6) AUA=A, 6’) A∩A=A, 7) AUU=U, 7’)A∩Ø=Ø, 8) [AUB](надчеркнутое)=A(надч)UB(надч) – закон де Моргана, 8’) тоже что и прошлое, только ∩. [c+(ab)](надчерк)=c(надч)(a(надч)+b(надч)). 9) закон поглощения: AU(A∩B)=A, 9’) A∩(AUB)=A, a+ab=a(U+b)=aU=a, a(a+b)=aa+ab=a+ab, (a+b)(a+c)=aa+ac+ab+bc=a+ac+ab+bc=…=a+bc.

ОТНОШЕНИЕ ФУНКЦИИ

Упорядоченной парой называется совокупность, состоящая из 2х элементов х и y, расположенные в определенном порядке. 2 пары и считаются равными т. и т.т., к. х=U, y=v. Бинарным или двуместным отношением ρ называется множество упорядоченных пар, элементы пар называются координатами или компонентами отношения ρ. Єρ xρy. ОПРЕДЕЛЕНИЕ 2: обастью определения бинарного отношения ρ называют множество D(инд.ρ){x|существует y: Єρ}. Областью значения ρ называется множество: R(инд.ρ)={y|существует х, Єρ}.

Примеры: 1.{,,,}, D(инд.ρ)={1,2,3,2}={1,2,3}={2,3,1}, R(инд.ρ)={2,4,3,1}={1,2,3,4}. Отношение равенства на множестве действительных чисел: {|x,y – действительные и x=y}, {|x,y – целые и существует z>0: x+z=y}

УПОРЯДОЧЕННАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ

x1,x2…,xn называются упорядоченные группы или пары. n-нарным отношением называется множество n-нок. Пусть даны n-множества A1,A2…An. Множество всех n-нок таких, что x1ЄA1…., xnЄAn.

A1xA2x…xAn=П[сверху – i, снизу – i=1]A(инд.i); Ai=A. Обратным отношением для отношения ρ={|Єρ} называется отношение

ρ(c.-1)={|Єρ}. Композицией отношений ρ1 и ρ2 называется отношение ρ=oρ1={|существует z: Єρ1 и Єρ2}

СВОЙСТВА БИНАРНЫХ ОТНОШЕНИЙ

1) (ρ(с.-1))(с.-1)=ρ, 2) (ρ2 o ρ1)(c.-1)=ρ1(c.-1) o ρ2(c.-1); Бинарное отношение f называется функцией, если из того, что Єf, Єf => y=z. 2 функции называются равными, если они состоят из одних и тех же элементов. D(инд.f)=X, R(инд.f)=Y. Говорят, что функция f осуществляет отображение множества f: XY, X(стрелка с перечеркнутым надчеркиванием)Y;

n-местной функцией называют отношение f, если f: x(c.n)Y или Y=f(x1,…,xn(c.n)). ОПРЕДЕЛЕНИЕ1: функция f: XY называется инъективной, если для любого x1,x2ЄX, Y=f(x1), Y=f(x0) =>x1=x2. ОПРЕДЕЛЕНИЕ2: функция f: XY называется сюръективной, если для любого yЄY существует x, f(x)=y. ОПРЕДЕЛЕНИТЕ3: функция называется биективной, если она одновременно и инъективная и сюръективная. СЛЕДСТВИЕ: говорят, что биективная функция f осуществляет однозначное отображение множества Х на множество Y. ПРИМЕРЫ: X=R (действительные R), Y=R, y=e(c.x). Монотонность функции говорит о инъективности – монотонно возрастает. y=x(c.3)-x – сюрьективная, y=x(c.3) – биективная. Композиция 2х функций – это функция gof.

=gof, Єgof} => существует некоторая функция, что существует U: xfu и ugy y=g[f(x)] существует V: xfV =>U=V и Vgz =>y=z, z=g[f(x)].

УТВЕРЖДЕНИЕ: композиция 2х биективных функций – есть биективная функция. ОПРЕДЕЛЕНИЕ: тождественным отображением множества Х в себя называется отображение e(инд.x): Xx, такое, что для любых xЄX существует значение функции e(инд.x)(x)=x, foe(инд.x)=f, e(с.y)of=f. УТВЕРЖДЕНИЕ: отображение f: XY имеет обратное

ОТНОШЕНИЕ ЧАСТИЧНОГО ПОРЯДКА

на множестве х, для которого 2 любые элементы сравнимы называется отношением линейного порядка. Любые x,yЄX либо x≤y либо y≤x.

Определение: говорят, что элемент х покрывает элемент y, если x≤y и существует такое, что x≤z≤y.

ДИАГРАММА ХАССЕ

ПРИМЕРЫ: некое множество A={1,2,3}

и его булеан B(A)={Ø,{1},{2},{3}, {1,2},

{1,3}, {2,3}, {1,2,3}}=X. 1,2,3 покрывают Ø.

Множество Х={1,2,3,5,6,10,15,30}. y делится

нацель на х. Диаграммы ХАССЕ на рисунке.

Если порядок линейный, то просто линия будет.

Определение: 2 частично упорядоченных

множества Х,Y называются изоморфными, если существует биективная функция, φ*ХY, сохраняющая частичный порядок, т.е. для любых x,yЄX, x≤y => φ(x)≤φ(y).

СРАВНЕНИЕ МНОЖЕСТВ

ОПРЕДЕЛЕНИЕ: множества А и В называются равномощными, если между АиВ существуют взаимно однозначные соответствия. 1. AB, |A|=|B|. УТВЕРЖДЕНИЕ: отношение равномощности множеств является отношением эквивалентности. Реплексивность – можно установить соответствие – сам с собой. Симметрия – хоть так, хоть эдак. СЛУЧАЙ 1: АиВ конечное множество: утверждение: множества А и В равномощны т. и т.т., к. количество элементов в А равно количеству элементов в В. Докажем: допустим 2 множества имеют одинаковые элементы, имеют одинаковые индексы соответствующих друг другу значений. Множества равномощны. Обратно: допустим множества равномощны => существуют взаимно однозначные соответствия. Мощность равна количеству элементов, для конечных множеств. СЛУЧАЙ2: бесконечное множество: N={1,2,3..}. Пример: множество всех натуральных чисел. И множество всех четных чисел: M={2,3,4..}. Теперь установим равномощность m(инд.i)=2n(инд.i). Говорят, что мощность множества А не превосходит мощность множества В. |A|≤|B|, если существует множество B1cB, что |A|=|B1|. Мощность А < мощности В, при 1) |A|≤|B|, 2. |A|≠|B|. ТЕОРЕМА: отношения |A|≤|B|, |A|<|B| являются отношениями линейного порядка. УТВЕРЖДЕНИЕ: ТЕОРЕМА КОНТОрА: пусть N={1,2..} множество всех натуральных чисел, а А=[0,1] множество всех чисел ближайших отрезку [0,1], тогда |N|≤|A| и докажем: 1) докажем |N|≤|A|, берем действительные числа a(инд.i)=(1/i), i=1,2,3.. все они лежат на отрезке [0,1] значит |N|≤|A|. 2) допустим, что |N|=|A|, то f:NA, тогда f(1)=0.a11a12a13, f(2)=0.a21a22a23,… f(n)=0.an1an2an3. Число b=0.b1b2b3, b(инд.i)={1, aij≠1; 2, aij=1.

СЧЕТНОЕ МНОЖЕСТВО

- множество равномощное множеству натуральных чисел. A={0, ±1, ±2,…}.

f: AN (должно быть взаимно однозначное соответствие),

a={i/2, i четное; (1-i)/2. |A|=|N|. ТЕОРЕМА О СЧЕТНЫХ МНОЖЕСТВАХ:

1) любое бесконечное множество содержит счетное подмножество. Док-во: А≠Ø, т.к. оно бесконечно. Можно выбрать произвольный элемент a1, берем остаток A\a1≠Ø, выбираем a2, повторяем операцию сколько-то раз A\a1\a2≠0  a3… Получаем бесконечность и т.д., счетное множество.

2) любое бесконечное подмножество B множества А счетно. Док-во: BcA, мощность |B|≤|A|. По теореме 1 => CcBcA, |N|≤|B|≤|A|, |C|=|N|. По условию |N|≤|B|≤|A|=|N|, |B|=|N|.

3) объединением конечного или счетного семейства счетных множеств – есть счетное множество. A(инд.i) U[сверху ∞, снизу i=1] A. A1 счетно, A1={a11, a12, a13, a14…}. 1 индекс – номер множества, 2 индекс – номер элемента.Берем значит матрицу бесконечную двумерную и соединяем линиями элементы в следующем порядке B={a11, a21, a12, a13….} т.к. удалось перегруппировать, то теорема доказана.

4) мощность булеана множества больше мощности самого множества. |M|<|B(M)|. Док-во: надо доказать, что 1. |M|≤|B(M)| McB(M).

2. |M|≠|B(M)|. допустим |M|=|B(M)| => существует некоторая функция f: MB(M). Рассматриваем 2 ситуации: а) xЄf(X), б) x¢f(x), xЄM, f(x)ЄB(M). Остановимся на б) – рассмотрим множество P={x|xЄf(x)}, ØЄB(M) булеану. Существует х: Ø=f(x), x¢Ø. P – подмножество множества M => PЄB(M), существует y: P=f(y). Разберемся yЄP или y¢P => yЄf(y)=P противоречие, а оттуда => y¢f(y)=P противоречие => допущение неверно.

5) мощность булеана счетного множества равна мощности континиума.

|B(N)|=|[0,1]|. A=[0,1] – все действительные числа 0-1, B=[0,2], |A|=|B|, y=2x.

ОСНОВНЫЕ СООТНОШЕНИЯ КОМБИНАТОРИКИ

Упорядоченные выборки n из n элементов, где все элементы различны называются перестановками из n элементов Pn=n!.

Упорядоченные выборки объемом m из n элементов (m

СВОЙСТВО биноминального коэффициента (С[степень, индекс]): 1) 0!=1, 2) C[0;m]=C[m;m]=1, 3) C[m-n; m]=C[n;m], C[m-n; m]=m!/(m-n)!(m-(m-n))!=

=m!/(m-n)!n!=C[r;m], 4) C[n;m]=C[n;m-1] + C[n-1;m-1], C[i;n]C[i;m]=

=C[m;n]C[i-m;n-m]. БИНОМ НЬЮТОНА: (x+y)(c.m)=∑[m;n=0]C[n;m] *

*x(c.n)*y(c.m-n). Док-во: методом математической индукции: m=1, x+y=1x’+1y’, m-1, покажем, что соотношение верно и для m.

(x+y)(c.m)=(x+y)(x+y)(c.m-1)=(x+y)∑[n=0;m-1] x(c.n)y(c.m-n-1)=

=x∑[n=0;m-1]C[n;m-1] x(c.n)y(c.m-n-1)+y∑[n=0;m-1]C[n;m-n]x(c.n)y(c.m-n-

-1)=…пиздец…=C[0;m]x(c.0)y(c.m)+∑[n=1;m-1]C[n;m]x(c.n)y(c.m-n).

РАЗБИЕНИЕ МНОЖЕСТВА

n-элементов множества. Надо разбить r1,r2…,r (инд.m) элементов. n! – количество перестановок. n!/r1!…r (инд.n)!

– количество вариантов подмножеств.

Сочетания с повторениями: C(инд.n+r-1)(с.n).

Множество всех вершин V={v1,v2…}.

Ребра: X={x1,x2…}. Ребро такое может быть

обозначено x1={v1,v2}. Если в графе есть петли и/или кратные ребра, то это псевдограф. Псевдограф без петель – мультиграф. Мультиграф, в котором не одно ребро не имеет кратность больше 1 называется графом. Если упорядоченная пара v1,v2, если все пары являются упорядоченными, то граф называется ориентированным (орграф). Ребра орграфов называются дугами и обозначаются круглыми скобками. Неорграф G1,G2… Орграф D1,D2…

ПОНЯТИЕ СМЕЖНОСТИ, ИНЦЕНДЕНТНОСТИ

x={v,w} – ребро неорграфа, тогда v,w – концы ребра. Пусть x(v,w) орграф, v – начало, w – конец. ОПРЕДЕЛЕНИЕ: если вершина v является концом ребра х неорграфа (началом или концом дуги х орграфа), то v и х называется инцидентными.

Вершины v,w называются смежными, если есть ребро {v,w}=x, соединяющее эти вершины. Степенью вершины v графа g – число δ(v) ребер графа G, инцедентных вершине v. Вершина графа имеет степень 0, называется изолированной, а степень 1 висячей. В неориентированном псевдографе вклад каждой петли инцидентной вершины v в степень этой вершины =2. Для орграфа: полустепенью исхода (захода) вершины v орграфа D называется число δ(с.+)(v) – исход, δ(с. -)(v) – заход.

В случае псевдографа вклад каждой петли смежной вершины v равен 1.

n(G) – количество вершин неорграфа, m(G) – количество ребер неорграфа, n(D) для орграфа, m(D) – количество дуг орграфа. Для каждого псевдографа D выполняется следующее равенство ∑[vЄV] δ(v)=2m(G),

∑[vЄV] δ(с.+)(v)=∑[vЄV] δ(с.-)(v)=m(D).

ИЗОМОРФИЗМ. ГОМЕОМОРФИЗМ.

G1(V1,X1), G2(V2,X2) называются

изоморфными, если существует

биективное (взаимооднозначное)

отображение φ:V1V2, сохраняющее смежность, т.е. если {v,w}ЄX1 {φ(v),φ(w)}ЄX2. Орграфы D1(V1,X1), D2=(V2,X2) называются изоморфными, если существует отображение φ:V1V2, (v,w)ЄX1 (φ(v),φ(w))ЄX2. Свойства изоморфных графов: - если G1,G2 – изоморфны и φ:V1V2 – для любого vЄV1, δ(v)=δ(φ(v)), - m(G1)=m(G2), n(G1)=n(G2). Для орграфа свойства аналогичны, для любого vЄV1, δ(с.-)(v)=δ(инд.-)(φ(v))

, δ(с.+)(v)=δ(с.+)(φ(v)), m(D1)=m(D2), n(D1)=n(D2). Примеры изоморфных графов см. на рисунке. УТВЕРЖДЕНИЕ: изоморфизм групп

является отношением эквивалентности на множестве

графов или орграфов. ОПРЕДЕЛЕНИЕ: операцией по

разбиению дуги (u,v) в орграфе D(v,x) называется

операция, которая состоит из удаления добавления к V

вешины w. Орграф D2 называется разбиением орграфа D1

, если D2 получается из D1 путем последовательного

применения интеграции дуг. Орграфы D1,D2(G1,G2) называются гомеоморфными, если существует их подразделение, которое является изоморным. Если степени всех вершин равны k, то граф называется регулярным в степени k. Граф исходящий из 1 вершины называется тривиальным. Двудольным называется граф G(V,X),

такой, что он разбит V1,V2(v1Uv2=v, v1∩v2≈Ø),

каждое ребро инцедентно вершине из v1 и v2.