Размещено на http://www.allbest.ru/

Лекция

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

Определение. Множества 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, то B₁=A.

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

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

1) Рефлективность:

2) Транзитивность:

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

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

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

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

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

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

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

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

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

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

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

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

Примеры.

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

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

Выберем элемент a₁A.

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

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

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

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

Пусть:

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

a₁₁, a₁₂, a₂₁, a₃₁, a₂₂, a₁₃, a₁₄, a₂₃, a₃₂, a₄₁.

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

Если в множествах A₁, A₂, A₃,… есть общие элементы, то их объединение 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].

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

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

Размещено на Allbest.ru