Множества. Операции над множествами. Мощность множеств

Теория множеств N – множество всех натуральных чисел. N = {0,1,2,3,…} N1 - множество всех натуральных чисел не превосходящих 100 R - множество всех действительных чисел Y - множество всех решений уравнения sin x = 1 A1 - множество студентов группы ПИ-12 А - множество групп на ФИТе Георг Кантор 1845-1918   A1  A 2 N xM R Y 2 2 Ø – пустое множество   N xM U – универсальное множество 2 студент Василий Иванов не принадлежит множеству A1 Подмножества: BC x  B x  C BC N1  N , N  R, Y  R, C  B  BC М = {1,2,3} BC 1)B  B, 2) B  C, C  D  B  D М Ø  М , M  U BC BC N1  N , N  R, Y  R Собственные подмножества: {1}, {2}, {3}, {1,2}, {1,3}, {2,3} Несобственные подмножества: {1,2,3}, Ø М  Ø 2 несобственных подмножества М и Ø Булеан множества М: B(M)=2M= {{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}, Ø} Способы задания множеств 1) Перечисление элементов M  1,2,3,4,5,6,7,8,9 3) Порождающая процедура M n for (i  1, i  10, i  ) M [i]  i; 1, если a  M , 2) Характеристический предикат M  x | PМ ( x) PМ (a)   0, если a  M . PM ( x) " x  N & 0  x  10" M  x | x  N & 0  x  10 2 1. Берем последовательно все натуральные числа и раскладываем на простые множители; 2. Если число не содержит множителей отличных от 2, то включаем его в M n 2 Парадокс Рассела: Y – множество всех множеств, не содержащих себя в качестве элемента Y Y ?  Y Y Y Y Y Y  Y Y Подмножества в программном коде: U  u1, u2 ,...,un  U={0,1,2,3,4,5,6,7,8,9} CU= (1111111111) CA= (1101101110) A={0,1,3,4,6,7,8} 1, ui  A, CB= (0111010010) C A [i ]   B={1,2,3,5,8} 0, ui  A. Булеан в программном коде: Бертран Рассел M={1,2,3} 1872-1970 0 – 000, 1 – 001, 2 – 010, 3 – 011, 4 – 100, 5 – 101, 6 – 110, 7 – 111. Ø, {3}, {2}, {2,3}, {1}, {1,3}, {1,2}, {1,2,3} Алгебра множеств 1. Включение множеств U U={0,1,2,3,4,5,6,7,8,9} A={0,1,3,4,6,7,8} B={1,2,3,5,8} A  x | PA ( x) B  x | PB ( x) A B Круги Эйлера, диаграммы Венна B A CA= (1101101110) CB= (0111010010) A  {2,5,9} A  B ={1,3,8} A  B ={0,1,2,3,4,5,6,7,8} С A  (0010010001 ) Джон Венн 1834-1923 С A B  C A  CB  0101000010 Леонард Эйлер 1707-1783 2. Дополнение множества A  с | с  A O  U U A A U 3. Пересечение множеств A  B  с | с  A и с  B AO  A B A PA B ( x)  PA ( x)  PB ( x) A A  O  4. Объединение множеств A  B  с | с  A или с  B U B U  O PA ( x)  1  PA ( x) С A B  C A  CB  C A  CB  (1111111110 ) U A  A PA B ( x)  PA ( x)  PB ( x)  PA ( x)  PB ( x) A U  U AO  O  A U  A Разность A \ B  x | x  A и x  B U B Кольцевая сумма (симметрическая разность) A  B   A \ B   B \ A U A B A A\ B  A B Свойства операций над множествами. 1. Идемпотентность A  A  A, A  A  A 2. Коммутативность A  B  B  A, A  B  B  A A  B  C    A  B   C , A  B  C    A  B   C 4. Дистрибутивность A  B  C    A  B    A  C , A  B  C    A  B    A  C   A  B   A  A,  A  B   A  A 5. Поглощение 3. Ассоциативность 6. Инволютивность AA 7. Законы де Моргана A  B  A  B, A  B  A  B Метод взаимного включения B  C, C  B  B  C 1) A  A  A 2) A  A  A A A  A x  A  A  x  A или x  A  x  A  x A A x  A Огастес де Морган (1806-1871) A B  A B a A  x | PA ( x), B  x | PB ( x) PA B (a)  PA B (a) PA B (a)  1  PA B (a)  1  PA (a)  PB (a)  PA (a)  PB (a)  1  PA (a)  PB (a)  PA (a)  PB (a)   1  PA (a)  PB (a)(1  PA (a))  PA (a)  PB (a) PA (a)  PA (a)(1  PB (a))  PA (a)  PB (a)  PA B (a) На диаграммах. U n A1  A2  ...  An   Ai , U B A B A B A Ai | i  I  U U A A A1  A2  ...  An   Ai , A B U B i 1 n B A B B М={1,2,3} М1={1} М2={1,2} М3={2,3} A A B i 1  Ai iI  Ai iI - покрытие множества А Ai  A, Ai  O , A   Ai iI Ai  A j  O , i j - разбиение множества А {М2,M3} - покрытие, но не разбиение, {М1,M3} - покрытие, являющееся разбиением, {М1,M2} - не покрытие Мощность множеств. (Кардинальное число) Конечные множества: A={0,1,3,4,6,7,8} A  card  A  7 A~7 B={1,2,3,5,9} C={a,c,d,e,f} B 5 С 5 B~C~5 Равномощные, эквивалентные B 1 2 3 5 9 ↔ ↔ ↔ ↔ ↔ C a c d e f BC A n B~C A~ n Взаимно-однозначное соответствие Метод математической индукции a  b, a, b  N 2) a  n  a  n  1) a  0  a 2) a  n  a  n  a a b 1) a  0  0 внутр.   (n  2) 1) n  3, 3   2) n   (n  2)  n1   n  1  2 P (( P(0), n( P(n)  P(n))  nP(n)) 1) базис 2) индукционный шаг n 1  n  3    (n  2)      n  1  2 … n  1 - угольник Теорема. Для конечного множества M 1) Базис B( M )  2  )  1  20  2  )  O    B(O M O  , B(O M O  ~ k 1 M  a1,...,ak ,  2 Индукционный шаг 2) M  k  1 ~ ~  M  X  M | ak  X   M1  X  M | ak  X 2  ~ M1  M 2  O  M1  B( M )  2k 1 M1  M 2  B( M ) X1  M1 → X1  ak   X 2  M 2 k 1  M 2  M  2 1 X 2  M 2 → X 2 \ ak   X1  M1 B( M )  2 M ~ M k k 1  2k 1  2k  2 M B( M )  M 1  M 2  2 Бесконечные множества N – натуральный ряд чисел N  {0,1,2,3, … } N ,0, Дедекинда-Пеано 0, n N n  N 3) n N n  0 1) m  N , m  0 n N n  m m  n  m  n 4) P (( P(0), n( P(n)  P(n))  nP(n)) 2) m, n  N Счетные множества A ~  M 2n ~ n  m  2 M n N m  2n  M 2n  n N Z ~ 2n 6 4 2 0 1 3 5  -3-2-1 0 1 2 3 Z z>0  2 z  1 N -z<0  2 z  N Теорема. Разность счетного и конечного множества есть счетное множество. А – конечное множество m+1 ↔ 0 N \ A  {m  1, m  2,...} A ~ m, m  N m+2 ↔ 1 A  {0,1,2,...,m} m+3 ↔ … 2  \ A~ m+n ↔ n-1 … Теорема. Всякое бесконечное множество включает в себя счетное множество. А – бесконечное множество. a1  A A \ {a1; a2 ;...;an} an1  A \ {a1; a2 ;...;an} ... A \ {a1} a2  A \ {a1} ... {a1; a2 ;...;an ; an1...} ~  n шагов Теорема. Множество всех действительных чисел отрезка 0;1 несчетно. Диагональный метод Кантора. 0 b1  a11, b2  a22 , b3  a33 ,... 0, b1b2b3...  0;1 0, a11a12a13...  1 0, a21a22a23...  2 0;1 континуальное card 0;1  2 континуум 0, a31a32a33...  3 … Теорема. Множество бесконечных последовательностей из нулей и единиц несчетно a11a12a13...  0 bi  aii , a21a22a23...  1 b1b2b3... a31a32a33...  2 … Теорема. Булеан множества натуральных чисел континуальное множество 1, i  A, [ i ]  C A N  A 0, i  A. Теорема Кантора. Доказательство. M  B(M ) Предположим, что K  x  M | x  f  M M 2 M  M  B(M ) f : x  M  {x} B(M ) M  B(M )   : A  B(M )  x  M ( A  M ) a;b ~ 0;1 R ~ (0;1) O R 1    ( x)  tg    x      a R ~ 0;1 b 0;1 ~ 0,1 x  0;1 x0 1 2 1  3 1 n x  0, x  1, x   x 1 x x  0,1 1  1 n 1 n2 x 1 2 1 2 