4. Прямое произведение множеств. Мощность прямого произведения множеств.

ДЕКАРТОВО ПРОИЗВЕДЕНИЕ МНОЖЕСТВ.

Рассмотрим два элемента a и b. Если соблюдать порядок расположения этих элементов, то пару (a,b) называют упорядоченной парой. То есть (a,b)< >(b,a). Говорят, что упорядоченная пара определяет вектор длины 2 с координатами a и b.

Если у вектора n координат, то речь идет о n-мерном векторе или упорядоченной n-ке.

Равенство векторов определяется правилом:

(а_1, а₂, … а_n)= (b_1, b₂, … b_m)  n=m и (i=1,2…n) a_i=b_i , т.е. векторы равны, если у них равны длины и соответствующие координаты.

Прямым (декартовым) произведением двух множеств А и В называется множество всех упорядоченных пар, в которых первая координата взята из первого множества, а вторая из второго.

Если в декартовом произведении более двух множеств, то множество строится из упорядоченных n-ок длины, равной числу множеств.

Если перемножаемые множества равны, то речь идет о степени множества:

Теорема: мощность прямого произведения множеств равна произведению мощностей перемножаемых множеств.

Доказательство: результатом прямого произведения множеств будет множество векторов, первые элементы которых можно выбрать |А₁| способами, вторые координаты - |А₂| и т.д., где |А_i| - мощность i-того множества. Таким образом мы имеем |А₁|*|А₂|*…*|А_n| векторов в полученном множестве.

Следствие.|Aⁿ|=|A|ⁿ.

5. Соответствие двух множеств. Виды соответствий. Равномощные множества. Примеры.

СООТВЕТСТВИЯ.

Подмножество прямого произведения множеств называется соответствием: GA₁x…xA_n.

Элементы первых n-1множеств задают область определения соответствия (прообразы), последнего множества – область значений соответствия (образы). Говорят, что каждому вектору прообразов соответствует образ. Если область определения состоит из всех элементов образующих его множеств, то соответствие всюду определенное (инъективное), иначе частичное. Если область значений состоит из всего последнего множества соответствия, то соответствие сюръективное.

сюръективное

соответствие

взаимооднозначное

соответствие

Соответствие называется функциональным, оно всюду определено, сюръективно и любой прообраз имеет единственный образ. Если в функциональном соответствии каждому образу соответствует единственный прообраз, то это взаимнооднозначное соответствие.

Теорема: Если между конечными множествами установлено взаимнооднозначное соответствие, то множества равномощны.

Доказательство: пусть даны два конечных множества А и В, между которыми можно установить взаимооднозначное соответствие. Допустим, что |A|<>|B|, тогда

|A|<|B|, значит дано сюръективное соответствие, но не инъективное, т.е. в множестве В есть два элемента, имеющие один и тот же прообраз;

|A|>|B|, значит дано инъективное соответствие, но не сюръективное, т.е. в множестве А есть два элемента, имеющие один и тот же образ.

В любом случае мы не получаем взаимооднозначности соответствия, что приводит к неверности предположения.

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

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

Объединение конечного числа четных множеств счетно.

Множество всех действительных чисел из отрезка [0,1] несчетно (теорема Кантора). Мощность несчетного множества называется континуум. Булеан счетного множества континуален, поскольку его можно сопоставить во взаимооднозначное соответствие с отрезком [0,1].