Эквивалентыне множества. Мощность множеств.

Определение 6.

Назовём множества А и В (AB) равномощными, если биекция, это отношение является эквивалентностью.

Утверждение.

Отношение «» является эквивалентностью.



Рефлексивность: , т. к.биекция.

Симметричность: , тогдабиекцияи обратная функциятоже является биекцией.

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

биекция

биекция

является биекцией .



Следствие.

Конечные множества эквивалентны они содержат одинаковое число элементов.

Определение 7.

Мощность множества А – это класс эквивалентности по этому отношению, содержащий А.

Обозначение.

, если инъекция

, если иAB

Утверждение.

.



Пусть инъекция

–биекция

Пусть , т. е.биекция.

Построим инъекцию следующим образом, для каждого.



Следствия.

Мощности конечных множеств – ноль и натуральные числа.

Замечание.

Ни одно конечное множество не является эквивалентным своему собственному подмножеству, а для бесконечных множеств это не так.

Пример.

(чётные натуральные числа)

является биекцией

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

Определение 7.

Множество А называется счётным, если АN, («алеф-ноль»).

Пример.

N2NZ

Биекция

Пример.

Множество положительных рациональных чисел счётно

Теорема 1.

1. Каждое подмножество счётного множества счётно.

2. Из любого бесконечного множества можно выделить счётное подмножество.

3. Если А и В счётны, то итоже счётны.

4. Объединение счётного семейства множеств тоже счётно.

5. Если А бесконечное множество, а В – конечно или счётно, то .



1. Пусть А – счётно,

Удалим все . Получим либо конечное множество, либо последовательность А, т. е. счётное множество.

2. Пусть А – бесконечное множество.

Рассмотрим .

тоже бесконечное множество,

тоже бесконечное множество, и т. д.

В силу бесконечности А этот процесс не закончится.

Получим последовательность – счётное подмножество.

3.

Вычёркиваем повторяющиеся элементы и получаем последовательность занумерованных элементов .

Занумеруем элементы декартового произведения

4. Рассмотрим счётное семейство счётных множеств

Элементы рассмотрим в виде бесконечной матрицы и занумеруем их.

5. Пусть , иначе можно рассмотреть вместо А(также бесконечно).

A бесконечно – счётное подмножество А,.

, тогда

, т. к. В конечно или счётно.

Существует биекция .

Установим биекцию .



Следствие.

Если множество счётно, то

Утверждение.

Пусть А – конечный или счётный алфавит, – множество всех слов в алфавите А, тогдасчётно.

Если множество А конечно, то конечно. Множество А счётно, как объединение счётного семейства конечных множеств.

Если множество А бесконечно счётно, то ... счётно как объединение счётного семейства счётных множеств.

Теорема 2.

Множество всех вещественных чисел из не является счётным.

представим двоичной дробью:

и это представление однозначно.

Предположим, что это множество счётно (его можно занумеровать)

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

Покажем, что .

Дробь y отличается от дроби вi-ом разряде в силу условия (1). Т. о. предположение не верно, т. е. множество не является счётным. 

Замечание.

счётно.