Сравнение множеств


Сравнение множеств

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

Утверждение. Отношение равномощности множеств является отношением эквивалентности.

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

    1) Рефлективность можно установить, отображая множество само на себя с помощью функции f(x)=x. То есть A=A. 2) Симметричность. Если:
      - взаимно однозначное соответствие, то и: - также взаимно однозначное соответствие.
    3) Транзитивность:

Рассмотрим разные случаи.

Случай 1. A и B конечны.

Утверждение. В случае, когда A и B конечны A и B равномощны тогда и только тогда, когда количество элементов A = количеству элементов B.

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

A) Если количество элементов одинаково, то перенумеруем их и установим взаимно однозначное соответствие:

Следовательно, множества равномощны.

Б) Пусть множества A и B равномощны. Тогда существует взаимно однозначное соответствие между элементами A и B. Следовательно, их количество должно быть одинаковым.

Поэтому для конечных множеств A можно принять, что мощность |A|=количеству элементов A.

Случай 2. Бесконечные множества.

Мощность целого может равняться мощности части. Рассмотрим множества

Можно установить соответствие: . Следовательно, множества равномощны.

Определение. Говорят, что мощность множества A не превосходит мощности множества B (пишут ), если множество:

В частности, если AB, то B1=A.

Определение. Говорят что A меньше B (), если:

Теорема. Отношение на совокупности множеств есть отношение частичного порядка для мощностей множеств.

    1) Рефлективность: 2) Транзитивность:

Существуют подмножества отображения такие, что:

Тогда f - соответствие между A и каким-то подмножеством C.

3) Анти симметричность:

Теорема - отношения линейного порядка (без док-ва).

Теорема Кантора. Пусть N - множество натуральных чисел, A=[0,1] - отрезок действительной оси. Тогда N<A.

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

Любое число из A можно представить в виде бесконечной десятичной дроби:

Построим число b следующим образом:

- поскольку b отличается от aN в n-ном знаке.

Приходим к противоречию. Теорема доказана.

Счетные множества

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

Примеры.

Теоремы о счетных множествах.

Теорема 1. множество содержит счетное подмножество.

Выберем элемент a1A.

A не пусто, так как оно бесконечно.

Выберем элемент {a1} не пусто, так как A бесконечно.

В результате получим множество, каждому элементу которого сопоставлено натуральное число n.

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

Пусть:

Расположим элементы A в следующем порядке

A11, a12, a21, a31, a22, a13, a14, a23, a32, a41.

Тем самым, получили взаимно однозначное отображение N на A.

Если в множествах A1, A2, A3,... есть общие элементы, то их объединение A есть подмножество рассмотренной выше последовательности.

Следствие 1. Если A и B счетные, то A x B - счетное.

Следствие 2. множество рациональных чисел - счетное:

Следующая теорема позволяет утверждать, что не существует "самого большого" по мощности множества.

Теорема. Мощность булеана множества всегда больше мощности самого множества, т. е.:

Возможны ситуации, когда f(x).

Выделим множество:

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

Пусть yP. Тогда по определению P yP. Противоречие.

Пусть yP. Поскольку в P входят все эл-ты xf(x), то yP. Опять противоречие.

Теорема доказана.

Теорема. Мощность булеана (множества-степени) счетного множества = мощности континуума:

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

Пусть 0,010...1... - запись любого числа из A=[0,1] в 2Ой системе счисления.

Сопоставим этому числу подмножество N, состоящее из чисел, равных номерам разрядов, в которых записана единица. Этим устанавливается взаимно однозначное соответствие между B(N) и [0,1].

Примеры. математический теорема число

Установить равномощность или не равномощность множеств:

Похожие статьи




Сравнение множеств

Предыдущая | Следующая