1.13.1 Счётные и несчётные множества
Простейшими среди бесконечных множеств является множество натуральных чисел.
Определение: Множество называется счётным, если элементы множества биективно сопоставлены со множеством натуральных чисел.
Приведём примеры счётных множеств.
Пример 1. Имеем множество всех целых чисел. Установим соответствие между всеми натуральными числами по схеме:
0, -1, 1, -2, 2, -3, 3…,
1, 2, 3, 4, 5, 6, 7…,
Вообще ,для n 0 сопоставим нечётное число 2n+1 , а отрицательному n < 0 – чётное число 2|n| , и тогда получим:
n 2n+1 при n 0;
n 2|n| при n < 0.
Пример 2. Множество всех чётных положительных чисел счетно.
Соответствие вполне очевидно: n 2n.
Пример 3. Множество 2, 4, 8, 16… … счетно.
Действительно, в данном случае имеем множество степеней числа 2. Здесь каждому числу соответствует число n.
И Пример 4. Множест-во всех рациональных чисел – счетно. Известно, что рациональное число можно представить в виде дроби r=q/p, где q и p – любые целые числа. Для того чтобы убедиться в том, что множество рациональ-ных чисел счетно, представим все
………….
………….
………….
…………
. . . . . …………
множество рациональных чисел в виде таблицы, в которую занесем несократимые дроби. Обходя таблицу по направлению стрелок, приходим к последовательности
1, 2, , , , 3, 4, , , , , , , ,…..,
позволяющей занумеровать все эти числа
- 1. Элементы теории множеств
- 1.1 Понятие множества. Основные определения
- Способы задания множества
- Равенство множеств
- Подмножество
- Операции над множествами
- Предварительные замечания
- Объединение множеств
- 1.5.3 Пересечение множеств
- 1.5.4 Разность множеств
- 1.5.5 Симметрическая разность
- 1.5.6 Универсальное множество
- 1.5.7 Дополнение множества
- Принцип двойственности в алгебре множеств
- Тождества алгебры множеств
- Разбиение множества
- Упорядочение элементов и прямое произведение множеств
- Упорядоченное множество
- Прямое произведение множеств
- 1.9.3 Проекция множества
- 1.10 Соответствия
- 1.10.1 Обратное соответствие
- 1.10.2 Композиция соответствий
- 1.10.3 Отображения и функции
- 1.10.4 Основные свойства отображений
- 1.11 Функция
- 1.11.1 Способы задания функции
- 1.11.2 Сужение функции
- 1.11.3 Обратная функция
- 1.11.4 Функция времени
- 1.11.5 Понятие функционала
- 1.11.6 Понятие оператора
- 1.12 Отношения
- 1.12.1 Задание бинарных отношений
- Свойства отношений
- 1.12.3 Отношение эквивалентности
- 1.12.4 Отношение порядка
- 1.13 Конечные и бесконечные множества
- 1.13.1 Счётные и несчётные множества
- 1.13.2 Свойства счетных множеств
- 1. Всякое подмножество счетного множества конечно или счетно.
- 2. Объединение любого конечного или счетного множества счетных множеств есть снова счетное множество.
- 3. Всякое бесконечное множество содержит счетное подмножество.
- 1.13.3 Эквивалентность множеств
- 1.13.4 Теорема г. Кантора
- 1.13.5 Теорема Кантора – Бернштейна
- 1.13.6 Верхняя и нижняя границы множества
- 1.13.7 Теорема о верхних и нижних границах подмножества
- 1.13.8 Понятие мощности множества
- 2. Основные положения теории графов
- 2.1 Определение графа
- 2.2 Матричные представления графа
- 2.3. Достижимость
- 2.4. Неориентированные графы
- 2.5. Изоморфизм графов
- 2.6. Отношение порядка и отношение эквивалентности на графе
- 2.7. Характеристики графов
- 2.8 Операции над графами
- 2.9. Определение путей экстремальной длины
- 2.9.1. Задача о кратчайшем пути между двумя вершинами (ориентированного графа
- 2.9.2 Задача о нахождении пути максимальной длины между двумя фиксированными вершинами ориентированного графа
- Номера работ обозначены числами в кружке.
- Литература