Теория множеств

ЭЛЕМЕНТЫ  ТЕОРИИ МНОЖЕСТВ

Под множеством 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.

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

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

Примеры: 1.{<1,2>,<2,4>,<3,3>,<2,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}, {<x,y>|x,y — целые и существует z>0: x+z=y}

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

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

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

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

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

1) (ρ(с.-1))(с.-1)=ρ, 2) (ρ2 o ρ1)(c.-1)=ρ1(c.-1) o ρ2(c.-1); Бинарное отношение  f называется функцией, если из  того, что <x,y>Єf, <x,z>Є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.

<x,y>=gof, <x,z>Є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<n), где все элементы различны, называются размещениями. Их число=A(c.m)(инд.n)=n!/(n-m)!. Пример: группа из 15ти человек выиграла 3 различных книги. Сколькими способами эти книги можно распределить среди группы? Неупорядоченные выборки объемом m из n элементов (m<n) называются сочетаниями. Их число C(c.m)(инд.n)=n!/m!(n-m)! Пример: группа из 15 человек выигрыла 3 одинаковых книги. Сколькими способами можно распределить эти книги? Размещения с повторениями: упорядоченные выборки объемом m из n элементов, где элементы могут повторяться. Их число A(c.m)(инд.n)(n)=n(c.m). Пример: кодовый замок состояит из 4х разрядов, в каждом разряде независимо от других могут быть выбраны цифры от 0 до 9. Сколько возможных комбинаций (10(c.4))?

СВОЙСТВО  биноминального коэффициента (С[степень, индекс]): 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(инд.n1)(с.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),