Мощности множеств также иногда называют кардинальными числами.

Дата: 2025-06-02; Просмотры: 12

Оценка:

0.00 из 5.00 — оценок

Скачиваний: 0

Скачать

1. Множества. Основные операции над множествами и их свойства. Диаграммы Венна. Декартово произведение множеств.

Множество – это совокупность объектов, рассматриваемых как единое целое.

Способы задания множеств:

1) Перечисление элементов: М={0,1,2,…,9}

2) Указание свойств Р(х), которым элементы множества должны удовлетворять: М={x | P(x)}.

Неправильное заданные свойства могут привести к противоречию!

Парадокс Рассела:

Рассмотрим множество всех множеств, которые не являются своими собственными элементами: . Является ли тогда множество К своим элементом. Если КєК, то должно выполняться свойство, задающее множество К, т.е. К¢К, что приводит к противоречию. Если же К¢К, то, поскольку выполняется свойство, задающее К, то КєК, а это противоречит предположению. Таким образом, не всякое свойство приводит к осмысленному заданию множества.

Множество А называется подмножеством множества В, если все элементы А принадлежат В, т.е.

Множества А и В называются равными или совпадающими, если они состоят из одних и тех же элементов, т.е.

Совокупность всех подмножеств множества А называется его булеаном или множеством-степенью и обозначается Р(А), т.е. . Если |U|=n (множество U содержит n элементов), то |P(U)|=2ⁿ.

Множество, не содержащее ни одного элемента называется пустым ø.

Множество, содержащее все элементы, находящиеся в рассмотрении, называется универсальным или универсумом U.

Операции над множествами:

1) объединение

2) пересечение

3) вычитание

4) кольцевая сумма (симметрическая разность)

5) дополнение

Свойства основных операций над множествами:

1) Ассоциативность:

2) Коммутативность:

3) Идемпотентность:

4) Дистрибутивность:

5) Поглощение:

6) Законы де Моргана:

7) Законы нуля и единицы: 0=ø, 1=U

8) Закон двойного отрицания:

Упорядоченную последовательность (х₁, х₂,…,х_n) называют кортежем длины n.

Декартовым (прямым) произведением множеств А₁, А₂,…, А_n называется множество {(x₁, x₂,…, x_n) | x₁ є A₁,…, x_n є A_n}.

Если А₁=А₂=…=А_n, то – n-ная декартова степень множества А.

А⁰ = ø

2. Отношения и бинарные отношения, область определения, область значения, обратные отношения. Произведение отношений.

n -местным отношением или n -местным предикатом Р на множествах А₁, А₂,…, А_n называется любое подмножество прямого произведения . Другими словами, элементы х₁, х₂,…, х_n (где х_i є A_i) связаны соотношением Р тогда и только тогда, когда (х₁, х₂,…, х_n) є Р. При n=1 отношение Р является подмножеством множества А₁ и называется унарным отношением или свойством.

При n=2 отношение Р называется бинарным отношением или соответствием.

Пример: Если А={2,3,4,5,6,7,8}, то бинарное отношение Р={(x,y) | x,y є A, x делит y и х≤3} можно записать в виде Р = {(2,2),(2,4),(2,6),(2,8),(3,3),(3,6)}.

Если Р={(x, y) | x, y є R, x≤y}, то запись xPy означает, что x≤y. id_A = {(x,x) | x є A} – тождественное отношение, id_A принадлежит А².

U = A² – универсальное отношение. Пусть Р – некоторое бинарное отношение. Областью определения отношения Р называется множество δ_Р = {x | (x,y) є P для некоторого у}. Областью значений отношения Р называют множество ρ_Р = {y | (x,y) є P для некторого х}. Обратным отношением называется множество Р^-1 = {(y,x) | (x,y) є P}.

Образом множества Х относительно предиката Р называется множество Р(Х)={y | (x,y) є P для некоторого х є Х}

Прообразом множества относительно предиката Р называется множество Р^-1(Х) или, другими словами, образ множества Х относительно предиката Р^-1.

Произведением бинарных отношений и или композицией Р₁ и Р₂ называется множество Р₁•Р₂ = {(x,y) | x є A, y є C, и найдется элемент z є B такой, что (x,z) є Р₁ и (z,y) є P₂}.

Свойства:

1) Ассоциативность композиции: (P•Q)•R=P•(Q•R)

Доказательство: Пусть (x,y) є (P•Q)•R. Тогда для некоторых u и v имеем (x,u) є P, (u,v) є Q, (v,y) є R. Тогда (u,y) є Q•R и (x,y) є P•(Q•R). Включение P•(Q•R) є (P•Q)•R доказывается аналогично.

2) (P•Q)^-1=Q^-1•P^-1

Доказательство: Предположим, что (x,y) є (P•Q)^-1. Тогда (y,x) є P•Q, и, следовательно, (y,z) є P и (z,x) є Q для некоторого элемента z. Значит (x,z) є Q^-1, (z,y) є P^-1 и тогда (x,y) є Q^-1•P^-1. Обратное включение доказывается аналогично.

3) P•Q ≠ Q•P

4) (P^-1)^-1=P

Доказательство: Если (x,y) є P, то (y,x) є Р^-1, но тогда (x,y) є (Р^-1)^-1.

3. Функции. Инъекции, сюръекции, биекции. Понятие последовательности.

Отношение называется функцией или отображением из множества А в множество В, если и из (x,y₁) є f, (x,y₂) є f следует y₁=y₂. Если вместо выполняется , то f называется частичной функцией. Функция f из А в В обозначается через или . Если (x,y) є f, то пишем y=f(x) или . Функция называется разнозначной инъективной (инъекцией) или 1-1 функцией если из условия, что выполняется х₁≠х₂, следует y₁≠y₂. Функция называется функцией из А на В или сюръекцией, если . Функция называется взаимно однозначным соответствием между множествами А и В или биекцией, если она инъективна и сюръективна одновременно.

Биекция называется подстановкой.

Утверждения:

1) Если , , то

2) Если , то

3) Если f и g - инъекции, то f•g – инъекция.

Доказательство: Предположим противное, т.е. найдутся элементы x₁, x₂, y такие, что х₁≠х₂, (x₁,y) є f•g и (x₂,y) є f•g, т.е. g(f(x₁))=y=g(f(x₂)). В силу разнозначности f имеем f(x₁)≠f(x₂). Отсюда в силу разнозначности g получаем g(f(x₁))≠g(f(x₂)), а это противоречит предположению.

4) Если f,g – сюръекции, то f•g – сюръекция

Доказательство: Нужно доказать, что для любого с существует а такое, что f•g(a)=c. Т.к. g – сюръекция, то существует b, для которого g(b)=c, а т.к. f – сюръекция, то для любого b существует а такое, что f(a)=b. Тогда f•g(a)=g(f(a))=c

5) Если f и g – биекции, то f•g – биекция

6) Если , то

Функция называется последовательностью. Её можно представить в виде f(0)=b₀, f(1)=b₁,…, f(n)=b_n.

4. Множество натуральных чисел. Два подхода к определению множества натуральных чисел. Аксиомы Дедекинда-Пеано. Принцип математической индукции.

Два подхода к определению множества натуральных чисел:

1) Конструктивный.

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

Положим по определению . Множества 0, 1, 2,… называются натуральными числами. Объединение этих чисел N={0, 1, 2,…, n,…} называется множеством натуральных чисел.

Замечание: А^В – множество всех функций из В в А. Если В=n={0,1,2…,n-1}, A=2={0,1}, то А^В=2ⁿ.

2) Аксиоматический подход.

Рассмотрим аксиоматику Дедекинда Пеано:

Пусть имеется некоторое множество N, в котором выбран элемент 0 и функция, которая элементу n из N ставит в соответствие элемент n’ из N, называемый непосредственно следующим (элемент n’ играет роль числа n+1).

Множество N называется множеством натуральных чисел, если система <N,0,’> удовлетворяет аксиомам:

- для любого m≠0 найдется n из N такой, что n’=m.

- для любых m,n из N, если m’=n’, то m=n.

- n’≠0 для любого n из N.

- на множестве N выполняется аксиома математической индукции.

Принцип (аксиома) математической индукции:

Для любого свойства Р (унарного отношения на множестве N), если Р выполняется на элементе 0 (т.е. 0 обладает свойством Р), и для любого n из N из выполнимости Р на элементе n следует выполнимость Р на элементе n’, то свойство Р выполняется на любом элементе n из N.

или или

Иногда удается установить только выполнение Р(к) для некоторого к>0 и свойство Р(n)=>Р(n+1) для всех n≥к:

Принцип полной индукции:

Если для всякого n из N из предположения, что P(k) верно при любом натуральном k<n, следует, что P(k) верно также при k=n, то P(n) верно при любом натуральном n:

5. Понятие мощности множества. Сравнение мощностей. Теорема Кантора-Берштейна. Операции над кардинальными числами.

Множества А и В называются эквивалентными (А~В), если существует биекция f: А↔В.

Свойства отношения эквивалентности:

1) А~А (поскольку id_A: А↔А);

2) если А~В, то В~А (т.к. из f: А↔В следует f^-1: В↔А);

3) если А~В и В~С, то А~С (т.к. из f: А↔В, g: В↔С следует f•g: А↔С).

Мощностью множества А называется класс всех множеств, эквивалентных множеству А (|А|).

Эквивалентные множества А и В называются равномощными: |A|=|B|.

Если А~n для некоторого , т.е. А имеет ровно n элементов, то множество А называется конечным (|A|=n).

Множество, не являющееся конечным, называется бесконечным. Если А~ω, то множество А называется счетным: |A|=ω. Если А~2^ω, то множество А называется континуальным или континуумом: |A|=2^ω.

Мощности множеств также иногда называют кардинальными числами.

Сравнение мощностей:

Говорят, что мощность множества А не превосходит мощности множества В: |A|≤|B|, если А эквивалентно некоторому подмножеству множества В

Теорема Кантора-Бернштейна:

Если |A|≤|B| и |B|≤|A|, то |A|=|B|.

Доказательство: Пусть f: A→B, g: B→A – разнозначные отображения, А₀=А, А₁=g(B) и А_n+2=(f•g)(A_n). Индукцией по n легко показать, что , . Пусть и . Очевидно, что и при i≠j. Т.к. f•g разнозначно отображает M_i на М_i+2 для любого , то отображение h: А→А, определенное следующим образом:

является разнозначным отображением А на . Т.к. |B|=|A₁|, |B|=|A|.

Следствие: Для любых множеств А и В выполняется только одно из соотношений: |A|=|A|, |A|<|B|, |B|<|A|.

Операции над кардинальными числами:

Пусть |A|=α, |B|=β. Тогда

1) ;

2) ;

3) .

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

Правило суммы: Если |A|=m, |B|=n, то .

Правило произведения: Если |A|=m, |B|=n, то .

Правило степени: Если |A|=m, |B|=n, то |A^B|=mⁿ.

Некоторые свойства бесконечных кардиналов:

ω²~ω; ω~ ; |Q|=ω; |P(U)|=2^|U|; |U|<2^|U|; если |A|>ω и |B|≤ω, то |A\B|=|A|; 2^ω~10^ω~ω^ω;

6. Конечные, счетные, континуальные множества. Мощность булеана.

Если А~n для некоторого , т.е. А имеет ровно n элементов, то множество А называется конечным (|A|=n).

Множество, не являющееся конечным, называется бесконечным. Если А~ω, то множество А называется счетным: |A|=ω. Если А~2^ω, то множество А называется континуальным или континуумом: |A|=2^ω.

Мощности множеств также иногда называют кардинальными числами.

Мощность булеана:

|P(U)|=2^|U| для любого множества U.

Доказательство:

Установим биекцию между Р(U) и 2^А

Любому подмножеству А из U взаимно однозначно ставим в соответствие функцию , для которой

т.е. P(U)~2^U. Заметим, что 2^|U|=|2^U|.

7. Матрицы бинарных отношений и их свойства. Специальные бинарные отношения.

Рассмотрим два конечных множества А={a₁, a₂,…, a_m}, B={b₁, b₂,…, b_n} и бинарное отношение . Определим матрицу [P]=(p_ij) размера бинарного отношения Р по следующему правилу:

Полученная матрица содержит полную информацию о связях между элементами.

Основные свойства матриц бинарных отношений:

1) Если , [P]=(p_ij), [Q]=(q_ij), то и , где сложение осуществляется по правилам 0+0=0, 1+1=1+0=0+1=1, а умножение – обычным образом.

2) Если , , то , где умножение матриц [P] и [Q] производится по обычному правилу умножения матриц, но произведение и сумма элементов по определенным в п.1 правилам.

3) Матрица обратного отношения Р^-1 равна транспонированной матрице отношения P: [P^-1]=[P]^T.

4) Если , [P]=(p_ij), [Q]=(q_ij), то p_ij≤q_ij.

5) Матрица тождественного отношения id_A единична: [id_A]=E.

Специальные бинарные отношения:

Пусть Р – бинарное отношение на множестве А:

Отношение Р называется рефлексивным, если для всех выполняется , т.е . Отношение Р называется симметричным, если для любых из следует , т.е Р^-1=Р, или [P]^T=[P]. Отношение Р называется антисимметричным, если из и следует, что x=y, т.е , или на языке матриц это означает, что в матрице все элементы вне главной диагонали являются нулевыми. Отношение Р называется транзитивным, если из и следует , т.е

8. Отношения эквивалентности и разбиения. Фактор-множества. Матрица отношения эквивалентности.