|ЭЛЕМЕНТЫ ТЕОРИИ |СЧЕТНОЕ МНОЖЕСТВО | |
|МНОЖЕСТВ |- множество | |
|(с) |равномощное множеству| |
|http://karatel.nm.ru |натуральных чисел. | |
|Под множеством S |A={0, ±1, ±2,…}. | |
|будем понимать любое |f: A(N (должно быть | |
|собрвние определенных|взаимно однозначное | |
|и различных между |соответствие), | |
|собой объектов |a={i/2, i четное; | |
|мыслимое как единое |(1-i)/2. |A|=|N|. | |
|целое. Эти объекты |ТЕОРЕМА О СЧЕТНЫХ | |
|называются элементами|МНОЖЕСТВАХ: | |
|множества S. Для |1) любое бесконечное | |
|любого объекта можно |множество содержит | |
|установить |счетное подмножество.| |
|принадлежит он |Док-во: А?Ш, т.к. оно| |
|множеству или нет. |бесконечно. Можно | |
|A={1,2,3..}, |выбрать произвольный | |
|A=p(x) – |элемент a1, берем | |
|обозначения. |остаток Aa1?Ш, | |
|Множества A и В |выбираем a2, | |
|считаются равными, |повторяем операцию | |
|если они состоят из |сколько-то раз | |
|одинаковых элементов |Aa1a2?0 ( a3… | |
|А=В. |Получаем | |
|{1,2,3}={2,1,3}=1,1,3. 1) множество |счетное множество. | |
|всех множеств |2) любое бесконечное | |
|содержащих сами себя |подмножество B | |
|- множество всех |множества А счетно. | |
|множеств, 2) |Док-во: BcA, мощность| |
|множества, которые не||B|?|A|. По теореме 1| |
|содержат себя как |=> CcBcA, | |
|элемент. Рассмотрим ||N|?|B|?|A|, |C|=|N|.| |
|множество второго |По условию | |
|типа: A=x. Если||N|?|B|?|A|=|N|, | |
|А себя не содержит, ||B|=|N|. | |
|то это одно из таких |3) объединением | |
|множеств, значит оно |конечного или | |
|должно содержаться в |счетного семейства | |
|А – парадокс рассела.|счетных множеств – | |
| |есть счетное | |
| |множество. A(инд.i) | |
|СООТНОШЕНИЕ МНОЖСТВ |U[сверху ?, снизу | |
|AcB, если все |i=1] A. A1 счетно, | |
|элементы А являются |A1=
. 1 индекс – | |
|В (А содержит В), А |номер множества, 2 | |
|является |индекс – номер | |
|подмножеством В. Если|элемента.Берем значит| |
|1.АсВ, 2. А?В, то |матрицу бесконечную | |
|АсВ, то А является |двумерную и соединяем| |
|подмножеством В |линиями элементы в | |
|{1,2}c{1,2,3}, |следующем порядке | |
|{1}c{1,2}. Множество,|B= т.к. удалось | |
|элементов называется |перегруппировать, то | |
|пустым и обозначается|теорема доказана. | |
|Ш. Считается, что |4) мощность булеана | |
|пустое множество |множества больше | |
|является |мощности самого | |
|подмножеством любого |множества. | |
|множества AшcA. ||M| существует | |
|,{1,2},{1,3},{2,3},,2,3} – булеан. |M(B(M). Рассматриваем| |
|УТВЕРЖДЕНИЕ: если |2 ситуации: а) | |
|множество А состоит |xЄf(X), б) xўf(x), | |
|из n элементов, то |xЄM, f(x)ЄB(M). | |
|булеан от А состоит |Остановимся на б) – | |
|из 2(c.n) элементов. |рассмотрим множество | |
|Док-во: 1-входит, 0 –|P=xЄf(x), ШЄB(M) | |
|не входит, 0..2(c.n) |булеану. Существует | |
|и Ш, всего 2(c.n). |х: Ш=f(x), xўШ. P – | |
| |подмножество | |
|ДЕЙСТВИЯ НАД |множества M => | |
|МНОЖЕСТВАМИ |PЄB(M), существует y:| |
|Объединием AUB |P=f(y). Разберемся | |
|называется |yЄP или yўP => | |
|множество, все |yЄf(y)=P | |
|элементы |противоречие, а | |
|которого являются |оттуда => yўf(y)=P | |
|элементами А или В |противоречие => | |
|(рис.2). |допущение неверно. | |
|AUB=x. |5) мощность булеана | |
|AcAUB, BcAUB. |счетного множества | |
|Пересечением множеств|равна мощности | |
|A?B называют |континиума. | |
|множество, все ||B(N)|=|[0,1]|. | |
|элементы которого |A=[0,1] – все | |
|являются элементами |действительные числа | |
|обоих множеств А и В.|0-1, B=[0,2], | |
|A?B=xЄA и xЄB, ||A|=|B|, y=2x. | |
|A?BcA, A?BcB (рис.3).| | |
|Дополнением множества|ОСНОВНЫЕ СООТНОШЕНИЯ | |
|А называют множество |КОМБИНАТОРИКИ | |
|эементов, не |Упорядоченные выборки| |
|принадлежащих |n из n элементов, где| |
|множеству А. |все элементы различны| |
|А=x (рис.4). |называются | |
|Симметричная разность|перестановками из n | |
|– A+B=(AB)U(BA) |элементов Pn=n!. | |
|(рис.5). Вычитание – |Упорядоченные выборки| |
|множество принадлежит|объемом m из n | |
|В и не принадлежит А.|элементов (m |начало, w – конец. | |
|y=z. 2 функции |ОПРЕДЕЛЕНИЕ: если | |
|называются равными, |вершина v является | |
|если они состоят из |концом ребра х | |
|одних и тех же |неорграфа (началом | |
|элементов. |или концом дуги х | |
|D(инд.f)=X, |орграфа), то v и х | |
|R(инд.f)=Y. Говорят, |называется | |
|что функция f |инцидентными. | |
|осуществляет |Вершины v,w | |
|отображение множества|называются смежными, | |
|f: X(Y, X((стрелка с |если есть ребро | |
|перечеркнутым |{v,w}=x, соединяющее | |
|надчеркиванием)Y; |эти вершины. Степенью| |
| |вершины v графа g – | |
|n-местной функцией |число ?(v) ребер | |
|называют отношение f,|графа G, инцедентных | |
|если f: x(c.n)(Y или |вершине v. Вершина | |
|Y=f(x1,…,xn(c.n)). |графа имеет степень | |
|ОПРЕДЕЛЕНИЕ1: функция|0, называется | |
|f: X(Y называется |изолированной, а | |
|инъективной, если для|степень 1 висячей. В | |
|любого x1,x2ЄX, |неориентированном | |
|Y=f(x1), Y=f(x0) |псевдографе вклад | |
|=>x1=x2. |каждой петли | |
|ОПРЕДЕЛЕНИЕ2: функция|инцидентной вершины v| |
|f: X(Y называется |в степень этой | |
|сюръективной, если |вершины =2. Для | |
|для любого yЄY |орграфа: полустепенью| |
|существует x, f(x)=y.|исхода (захода) | |
|ОПРЕДЕЛЕНИТЕ3: |вершины v орграфа D | |
|функция называется |называется число | |
|биективной, если она |?(с.+)(v) – исход, | |
|одновременно и |?(с. -)(v) – заход. | |
|инъективная и |В случае псевдографа | |
|сюръективная. |вклад каждой петли | |
|СЛЕДСТВИЕ: говорят, |смежной вершины v | |
|что биективная |равен 1. | |
|функция f |n(G) – количество | |
|осуществляет |вершин неорграфа, | |
|однозначное |m(G) – количество | |
|отображение множества|ребер неорграфа, n(D)| |
|Х на множество Y. |для орграфа, m(D) – | |
|ПРИМЕРЫ: X=R |количество дуг | |
|(действительные R), |орграфа. Для каждого | |
|Y=R, y=e(c.x). |псевдографа D | |
|Монотонность функции |выполняется следующее| |
|говорит о |равенство S[vЄV] | |
|инъективности – |?(v)=2m(G), | |
|монотонно возрастает.|S[vЄV] | |
|y=x(c.3)-x – |?(с.+)(v)=S[vЄV] | |
|сюрьективная, |?(с.-)(v)=m(D). | |
|y=x(c.3) – | | |
|биективная. |ИЗОМОРФИЗМ. | |
|Композиция 2х функций|ГОМЕОМОРФИЗМ. | |
|– это функция gof. |G1(V1,X1), G2(V2,X2) | |
| |называются | |
|=gof, Єgof}|изоморфными, если | |
|=> существует |существует | |
|некоторая функция, |биективное | |
|что существует U: xfu|(взаимооднозначное) | |
|и ugy |отображение ?:V1(V2, | |
|y=g[f(x)] |сохраняющее | |
|существует V: xfV |смежность, т.е. если | |
|=>U=V и Vgz =>y=z, |{v,w}ЄX1 | |
|z=g[f(x)]. |{?(v),?(w)}ЄX2. | |
|УТВЕРЖДЕНИЕ: |Орграфы D1(V1,X1), | |
|композиция 2х |D2=(V2,X2) называются| |
|биективных функций – |изоморфными, если | |
|есть биективная |существует | |
|функция. ОПРЕДЕЛЕНИЕ:|отображение ?:V1(V2, | |
|тождественным |(v,w)ЄX1 | |
|отображением |(?(v),?(w))ЄX2. | |
|множества Х в себя |Свойства изоморфных | |
|называется |графов: - если G1,G2 | |
|отображение e(инд.x):|– изоморфны и ?:V1(V2| |
|X(x, такое, что для |– для любого vЄV1, | |
|любых xЄX существует |?(v)=?(?(v)), - | |
|значение функции |m(G1)=m(G2), | |
|e(инд.x)(x)=x, |n(G1)=n(G2). Для | |
|foe(инд.x)=f, |орграфа свойства | |
|e(с.y)of=f. |аналогичны, для | |
|УТВЕРЖДЕНИЕ: |любого vЄV1, | |
|отображение f: X(Y |?(с.-)(v)=?(инд.-)(?(| |
|имеет обратное |v)) | |
| |, | |
|ОТНОШЕНИЕ ЧАСТИЧНОГО |?(с.+)(v)=?(с.+)(?(v)| |
|ПОРЯДКА |), m(D1)=m(D2), | |
|на множестве х, для |n(D1)=n(D2). Примеры | |
|которого 2 любые |изоморфных графов см.| |
|элементы сравнимы |на рисунке. | |
|называется отношением|УТВЕРЖДЕНИЕ: | |
|линейного порядка. |изоморфизм групп | |
|Любые x,yЄX либо x?y |является отношением | |
|либо y?x. |эквивалентности на | |
|Определение: говорят,|множестве | |
|что элемент х |графов или орграфов. | |
|покрывает элемент y, |ОПРЕДЕЛЕНИЕ: | |
|если x?y и |операцией по | |
|существует такое, что|разбиению дуги (u,v) | |
|x?z?y. |в орграфе D(v,x) | |
| |называется | |
|ДИАГРАММА ХАССЕ |операция, которая | |
|ПРИМЕРЫ: некое |состоит из удаления | |
|множество A={1,2,3} |добавления к V | |
|и его булеан |вешины w. Орграф D2 | |
|B(A)={Ш,{1},{2},{3}, |называется разбиением| |
|{1,2}, |орграфа D1 | |
|{1,3}, {2,3}, |, если D2 получается | |
|{1,2,3}}=X. 1,2,3 |из D1 путем | |
|покрывают Ш. |последовательного | |
|Множество |применения интеграции| |
|Х=. y делится |D1,D2(G1,G2) | |
|нацель на х. |называются | |
|Диаграммы ХАССЕ на |гомеоморфными, если | |
|рисунке. |существует их | |
|Если порядок |подразделение, | |
|линейный, то просто |которое является | |
|линия будет. |изоморным. Если | |
|Определение: 2 |степени всех вершин | |
|частично |равны k, то граф | |
|упорядоченных |называется регулярным| |
|множества Х,Y |в степени k. Граф | |
|называются |исходящий из 1 | |
|изоморфными, если |вершины называется | |
|существует биективная|тривиальным. | |
|функция, ?*Х(Y, |Двудольным называется| |
|сохраняющая частичный|граф G(V,X), | |
|порядок, т.е. для |такой, что он разбит | |
|любых x,yЄX, x?y => |V1,V2(v1Uv2=v, | |
|?(x)??(y). |v1?v2?Ш), | |
| |каждое ребро | |
|СРАВНЕНИЕ МНОЖЕСТВ |инцедентно вершине из| |
|ОПРЕДЕЛЕНИЕ: |v1 и v2. | |
|множества А и В | | |
|называются | | |
|равномощными, если | | |
|между АиВ существуют | | |
|взаимно однозначные | | |
|соответствия. 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|