Лекция дискрет 05
.pdf§ 1.4. Мощность множества
Мощность (кардинальное число) множества - некоторое инвариантное свойство, которым характеризуется множество, если отвлечься (абстрагироваться) от природы элементов множества, то есть признаков, по которым они включены в множество, а также от порядка расположения элементов в множестве.
1) Понятие мощности множества
Множество М1 называется равномощным множеству М2 (обозначается М1 ≈ М2), если можно установить некоторое взаимно однозначное отношение между М1 и М2
Th.1.4.1 Отношение |
Система классов эквивалентности |
равномощности множеств – |
{C1,…,Ck,…} для множества Х – |
отношение эквивалентности на разбиение множества Х по |
|
множестве множеств |
отношению эквивалентности R; |
|
любой элемент множества Х входит |
ровно в один класс и классы не пересекаются (§ 1.3)
Мощностью (или кардинальным числом) множества М называется класс множеств, равномощных М
Обозначение мощности множества М: card M или │М│
2) Конечные множества
Множество М называется конечным, если оно равномощно множеству Nk = {1, 2, …, k} натуральных чисел, не превосходящих некоторого натурального числа k. Множество, не являющееся конечным – бесконечное.
Пустое множество - конечное (по определению)
Th.1.4.2 Конечное множество М не может быть равномощно никакому своему собственному подмножеству М1 (собственное подмножество: M1 M, M1 ≠ M)
Th.1.4.3 Конечное множество М1 не может быть равномощно никакому множеству М2 такому, что М1 М2
Th.1.4.4 Непустое конечное множество М равномощно единственному множеству Nk = {1, 2, …, k}
Числом элементов конечного непустого множества М называется натуральное число k такое, что М ≈ Nk. Число элементов пустого множества - нуль – по определению.
По определению – для всякого |
По Th.1.4.4 – для всякого конечного |
конечного множества |
множества |
k определено |
k единственное |
Понятие числа элементов конечного множества - корректное
Все равномощные между собой |
Мощность |
конечные множества равномощны |
(или кардинальное число) |
одному и тому же Nk, т.е. входят |
множества М - класс множеств, |
в один класс эквивалентности |
равномощных М |
Мощность конечного множества характеризуется числом элементов в нём: │{ m1, m2, … , mn }│= n, │ │= 0
Из § 1.1:
Декартово (прямое) произведение непустых множеств M1, M2,…,Mn – множество, состоящее из всех (если хотя
бы одно Mi – бесконечное, то любых) n-элементных
кортежей (упорядоченных наборов), первый элемент которых принадлежит множеству М1, второй – множеству М2, …, n-ый – множеству Mn.,
M1 M2 … Mn = {(m1,m2,…,mn): m1 M1, m2 M2 ,…, mn Mn}
Если хотя бы одно Mi = Ø, то по определению
M1 M2 … Mn = Ø
Th.1.4.5 Пусть M1, M2,…,Mn – конечные множества и │Mi│ = ri (i=1…n). Тогда мощность декартова произведения множеств M1 M2 … Mn равна произведению мощностей множеств Мi (i=1…n), т.е.
│M1 M2 … Mn│= r1 r2 … rn
Доказательство Th.1.4.5
Математическая индукция по числу множеств - n
n=1 │M1│ = r1
Пусть верно для n=k, т.е.
│M1 M2 … Mk│= r1 r2 … rk
M1 M2 … Mk – множество всех k-элементных кортежей
(mi1,mi2,…,mik), где mijMj (j=1…k)
Возьмём произвольный k-элементный кортеж, получим из него (k+1)-элементные кортежи путём приписывания
справа поочерёдно всех элементов из множества Mk+1:
|
|
|
|
|
|
|
|
|
m1k+1 |
(mi1,mi2,…,mik,m1k+1) |
|||
(m |
i |
|
,m |
i |
|
,…,m |
i |
) |
m2k+1 |
(mi1,mi2,…,mik,m2k+1) |
|||
|
1 |
|
2 |
|
k |
...... |
|
|
...... |
||||
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
mj |
(mi |
,mi |
,…,mi ,mj |
) |
|
|
|
|
|
|
|
|
|
k+1 |
1 |
2 |
k |
k+1 |
|
|
|
|
|
|
|
|
|
...... |
|
|
...... |
rk+1
раз
В произведении M1 M2 … Mk содержится r1 r2 … rk k-элементных кортежей, каждый из которых породит rk+1
кортежей из (k+1) элемента, общее количество которых тем самым и составит
(r1 r2 … rk) rk+1 = r1 r2 … rk rk+1
Доказано Th.1.4.5
Пример: Вечеринка в колледже с танцами
Участники:
Студенты: B = { b1, b2, b3, b4, b5 } Студентки: G = { g1, g2, g3, g4, g5, g6 }
Мелодии (всего-то!): D = { d1, d2, d3 }
Но сочетаний (Студент, Студентка, Танец):
│Programme│= │B G D│ =
= 5 6 3 = 90
Пример: Антропометрическая идентификация по лицу (фоторобот)
Признаки:
1 - высота лба
2 - ширина лба
3 - линия положения брови
4-линия положения глазной щели
5- зрачковая линия
6- протяженность глазной щели
7- ширина спинки носа
8 - высота носа (носовой части лица) |
Совокупность портретов – |
|
9 - ширина носа |
|
декартово произведение наборов |
10 - высота верхней губы |
|
|
|
вариантов признаков |
|
11 - протяженность ротовой щели |
|
|
|
|
|
12 - высота подбородка |
Если по 8-10 вариантов на признак |
|
13 - оттопыренность ушной |
(немного!) – мощность множества |
|
раковины |
|
портретов – не менее 1012 - 1013 |
14 - высота ушной раковины |
|
|
…………………….