Эквивалентность множеств
Если каждому элементу множества A сопоставлен единственный элемент множества B и при этом всякий элемент множества B оказывается сопоставленным одному и только одному элементу множества A, то говорят, что между множествами A и B существует взаимно однозначное соответствие. Множества A и B в этом случае называют эквивалентными или равномощными. Эквивалентность множеств обозначается следующим образом: A ~ B. Эквивалентность множеств обладает следующим свойством транзитивности. Если A ~ B и B ~ C, то A ~ C. Докажем это свойство. Так как A ~ B, то для всякого элемента a Î А существует единственный элемент b Î B. Но так как B ~ C, то для всякого элемента b Î B существует единственный элемент c Î C. Сопоставим этот элемент элементу a Î А. Значит, для всякого элемента a Î А существует единственный элемент c Î C и для всякого элемента c Î C существует единственный элемент a Î А. Следовательно, A ~ C. Очевидно, что два конечных множества эквивалентны тогда и только тогда, когда количество элементов в них одинаково. Например, множества А = {4, 5, 6} и В = {x, y, z} эквивалентны, A ~ B. Взаимно однозначное соответствие может быть установлено между элементами 4 и x, 5 и y, 6 и z. Мощностью конечного множества А (обозначается çАç) называется число элементов этого множества. Например, мощность множества А = {1, 2} равна çАç= 2. Пример. Ранее мы рассматривали множество всех подмножеств данного множества А, которое называется множеством-степенью и обозначается P(A). Множество P(A) состоит из 2n элементов. Таким образом, çP(A) ç = 2n. Рассмотрим задачу определения мощности объединения n конечных множеств. Пусть n = 2 и A и B – два пересекающихся множества. Докажем с помощью диаграммы Эйлера – Венна следующее соотношение: çАÈB ç= çА ç+ çB ç– çАÇB ç. (1) Из рис. 3 видим, что çАÈB ç= n1+n2+n3; çА ç= n1+n2; çB ç= n2+n3; çАÇB ç= n2. Рисунок 3.
Очевидно, что n1+n2+n3 = (n1+n2) +(n2+n3) – n2, что и доказывает формулу (1). Формула (1) справедлива и для случая, если множества A и B не пересекаются. В этом случае çАÈB ç= çА ç+ çB ç. Пусть n = 3 и A, B и С – три пересекающихся множества. В этом случае справедливо следующее соотношение: çАÈBÈ Сç= çА ç+ çB ç+ çC ç– çАÇB ç– çАÇC ç– çBÇC ç+ çАÇB ÇC ç. (2) Из рис. 4 видим, что çАÈBÈ Сç= n1+n2+n3+n4+n5+n6+n7; çА ç= n1+n2+n4+n5; çB ç= n2+n3+n5+n6; çСç=n4+n5+n6+n7; çАÇB ç= n2+n5; çАÇC ç= n4+n5; çBÇC ç= n5+n6; çАÇB ÇC ç= n5.
Рисунок 4.
Очевидно, что n1+n2+n3+n4+n5+n6+n7 =(n1+n2+n4+n5) + (n2+n3+n5+n6) +(n4+n5+n6+n7) – (n2+n5) – (n4+n5) – (n5+n6) + n5, что и доказывает формулу (2). Формула (2) справедлива и для случая, если множества A, B и С попарно не пересекаются. В этом случае çАÈBÈ Сç= çА ç+ çB ç+ çC ç. В общем случае мощность объединения n множеств определяется по формуле: çА1È А2 È…ÈАnç= çА1ç+çА2ç+…+ çАnç– (çА1Ç А2ç+ çА1Ç А3ç+ … +çАn–1ÇАnç)+ çАÇB ÇC ç+ (çА1Ç А2 Ç А3ç + … +çАn–2ÇАn–1ÇАnç) – … + (–1)n – 1 çА1ÇА2 …ÇАnç. (3) Понятие эквивалентности годится и для бесконечных множеств. Пусть, например, A = {1, 2, 3, …, n,…}, B = {– 1, –2, …, –n, …}. Тогда A ~ B. Взаимно однозначное соответствие устанавливается по правилу: элементу nÎ A соответствует элемент – nÎ B, т.е. n « – n. Пример. A = {1, 2, 3, …, n,…}, B = {2, 4 …, 2n, …}. Тогда A ~ B. Взаимно однозначное соответствие устанавливается по правилу: n « 2*n. A = {1, 2, 3, …, n,…} – множество натуральных чисел, B = {…, –n, …– 2, –1, 0, 1, 2, …, n, …} – множество всех целых чисел. Перепишем множество B следующим образом: B = {0, –1, 1, – 2, 2, …, –n, n, …}, так, что 0 будет на первом месте, –1 на втором, 1 на третьем, –2 на четвертом и т.д. Нетрудно заметить, что отрицательные числа будут стоять на местах с четными номерами, а 0 и положительные числа – на местах с нечетными номерами. Поэтому взаимно однозначное соответствие между множествами A и B устанавливается по правилу: для всякого n ³ 0 элементу a = 2n +1 из множества A (т.е. нечетному элементу) соответствует элемент b = n из множества B; элементу a = 2n из множества A (т.е. четному элементу) соответствует элемент b = –n из множества B. Таким образом, реализуется взаимно однозначное соответствие между множествами A и B: 1 « 0, 2 « –1, 3 « 1, 4 « –2 и т.д. Установить эквивалентность множеств, т.е. установить взаимно однозначное соответствие между их элементами можно различными способами. Множество, эквивалентное множеству натуральных чисел N = {1, 2, 3, …, n,…}, называется счетным. Можно сказать также, что множество счетно, если его элементы можно перенумеровать. Пример. Установить, являются ли следующие множества счетными: 1. A1 = {–1, –2, …, – n, …}; 2. A2 = {2, 22, …, 2n,…}; 3. A3 = {2, 4, …, 2n,…}; 4. A4 = {…, – n, …, – 1, 0, 1, …, n,…}; Решение. Чтобы установить счетность некоторого множества, достаточно указать взаимно однозначное соответствие между элементами данного множества и множества натуральных чисел. Взаимно однозначное соответствие устанавливается по следующим правилам: · для множества A1: –n « n; · для множества A2: 2n « n; · для множества A3: 2*n « n; · счетность множества A4 установлена ранее в примере. Упорядоченной парой (x, y) называется совокупность двух элементов x и y, расположенных в определенном порядке. Две упорядоченные пары (x, y) и (u, v) равны межу собой тогда и только тогда, когда x = u и y = v. Например, (a, b), (1, 2), (x, 4) – упорядоченные пары. Аналогично можно рассматривать тройки, четверки, n-ки элементов (x1, x2, … xn). Прямым (или декартовым)произведением двух множеств A и B называется множество упорядоченных пар, таких, что первый элемент каждой пары принадлежит множеству A, а второй – множеству B: A ´ B = {(a, b), / aÎ А и bÎ В}. В общем случае прямым произведением n множеств А1, А2,… Аn называется множество А1 ´ А2 ´ …´ Аn, состоящее из упорядоченных наборов элементов (a1, a2, …, an) длины n, таких, что i- ый ai принадлежит множеству Аi, ai Î Аi. Пример. Пусть А = {1, 2}, В = {2, 3}. Тогда A ´ B = {<1, 2>, <1, 3>,<2, 2>,<2, 3>}. Пусть А = {x / 0 £ x £ 1} и B = {y / 2 £ y £ 3}. Тогда A ´ B = {< x, y > / 0 £ x £ 1и2 £ y £ 3}. Таким образом, множество A ´ B состоит из точек, лежащих внутри и на границе прямоугольника, образованного прямыми x = 0 (ось ординат), x = 1, y = 2и y = 3. Французский математик и философ Декарт впервые предложил координатное представление точек плоскости. Это исторически первый пример прямого произведения.
©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.
|