Доказать равномощность множества точек окружности и множества точек контура квадрата (2 видео)

08. Примеры равномощных множеств

Приведенные выше примеры и теоремы показывают, что установить равномощность различных множеств далеко не просто. В этом параграфе мы рассмотрим примеры построения биекции между различными множествами. Будут приведены примеры доказательств равномощности ряда множеств.

Пример 1. Установить биекцию между отрезком [0, 1] и отрезком [а, в].

Решение. Легко устанавливается биективность линейного отображения x = (в – a)t + a отрезка [0, 1] на отрезок [а, в].

Пример 2. Установить биекцию между интервалом (0, 1) и интервалом (–¥, +¥).

Решение. Легко устанавливается биективность отображения x= ctg(pt) интервала (0, 1) на интервал (–¥, +¥).

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

Пример 3. Построить биекцию между отрезком [0, 1] и интервалом (0, 1).

Решение. Решение этой задачи основано на несчетности рассматриваемых множеств и теореме 4 из параграфа 6. Идея решения состоит в том, что из интервала (0, 1) выделяют некоторое счетное множество А. Затем к нему добавляют две точки и . Вновь полученное множество (обозначим его В Ì [0, 1]), также является счетным. Следовательно, множества А и В равномощны и существует биекция f, отображающая B на A. Построим теперь биекцию отрезка [0, 1] на интервал (0, 1) следующим образом:

Пример 4. Построить биекцию между окружностью единичного радиуса и отрезком [0, 1].

Схема решения. Легко устанавливается биекция между точкой окружности и углом, соответствующим этой точке. Этим получается биекция окружности и полуотрезка [0, 2p). Затем по схеме примера 3 строится биекция полуотрезка [0, 2p) на отрезок [0, 1].

Пример 5. Доказать, что множество всех окружностей на плоскости, радиусы которых рациональные числа и координаты центра которых — рациональные числа, есть счетное множество.

Решение. Нетрудно видеть, что каждый элемент рассматриваемого множества может быть отождествлен с тройкой чисел (х, у, r), где (х, у) — координаты центра окружности, а r — ее радиус. Этим между множеством указанных окружностей и множеством Q´Q´Q устанавливается биекция. Но произведение счетных множеств счетно (см. задачу в 6 параграфе) и, следовательно, наше множество также счетно.

Пример 6. Доказать, что множество точек разрыва монотонной функции, заданной на отрезке [а, в], конечно или счетно.

Содержание

О равномощности множеств
∀ x, y, z
4. Равномощность множеств / Парадоксы теории множеств
Иван Ященко
4. Равномощность множеств
💡 Видео

Видео:2.7 Декартово произведение | Константин Правдин | ИТМОСкачать

О равномощности множеств

Парадокс Галилея – пример, иллюстрирующий свойства бесконечных множеств. В двух словах: натуральных чисел столько же, сколько квадратов натуральных чисел, то есть в множестве 1, 2, 3, 4, … столько же элементов, сколько в множестве 1, 4, 9, 16 …

В своей последней работе «Две Науки», Галилей привёл два противоречащих друг другу суждения о натуральных числах:

Суждение1. Некоторые числа являются точными квадратами (т.е. квадратами других целых чисел), другие же числа таким свойством не обладают.

Вывод1. Таким образом, точных квадратов должно быть меньше, чем всех чисел.

Суждение2. Для каждого натурального числа найдётся его точный квадрат, и наоборот – для каждого точного квадрата найдётся целый квадратный корень.

Вывод2. Точных квадратов и натуральных чисел должно быть одинаковое количество.

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

В 19 веке, Георг Кантор, используя свою теорию множеств показал, что можно ввести «количество элементов» для бесконечных множеств – так называемая мощность множества. При этом мощности множества натуральных чисел и множества точных квадратов совпали (оказалось верным второе суждение Галилея).

В защиту Галилея:

Применение термина «равномощность» к бесконечным множествам некорректно, т.к. бесконечные множества не могут быть равными по мощности, по крайней мере не существует однозначного метода это установить. Можно говорить определённо только про неравномощные множества (например, множество действительных чисел мощнее натуральных). Но рассматривая бесконечные множества равномощные натуральному множеству, приходится признать что это не равномощность, а неопределённость.

Поскольку биекция — НЕОБХОДИМОЕ условие равномощности множеств, но совершенно НЕДОСТАТОЧНОЕ условие равномощности. Для того, чтобы понять почему это так рассмотрим пример с конечными множествами (метод биекции в своё время был применён к бесконечным множествам на основе аналогии с конечными множествами, но как мы увидим был некорректно применён, т.к. нельзя автоматически переносить правила, справедливые для конечных множеств на бесконечные).
Итак, рассмотрим два конечных множества:
в корзине №1 10 бильярдных шаров с разными номерами (скажем от 1 до 10),
в корзине №2 10 бильярдных шаров с разными номерами (скажем от 21 до 30).
По условию задачи, Вы не знаете сколько шаров в корзинах. Чтобы сравнить их количество Вы одновременно достаёте по одному шару из корзин (таким образом применяете метод биекции, т.е. пытаетесь установить биекцию: если количество шаров будет одинаковым, то мощности равномощны; если разное, то мощность одного множества будет больше мощности другого). При этом не важно какие номера стоят на этих двух шарах (например: 4-26, 7-22 и т.п.), в любом случае получится, что мощности этих множеств равномощны.

Таким образом, для конечных множеств существование хотя бы одного способа биекции однозначно говорит об их равномощности. Но это не выполняется для бесконечных множеств, так как в зависимости от порядка сопоставления элементов, мы получаем противоречащие друг другу результаты: либо мощности множеств равны, либо неравны. Таким образом если существует хотя бы 1 способ, когда биекции не существует, то мы не имеем право однозначно судить о равномощности. Подобно тому, как мы не можем судить о сумме бесконечного ряда чисел, если ряд расходящийся, т.к. сумма зависит от порядка слагаемых.
Вообще, количество способов биекции между двумя равными множествами определяется факториалом числа элементов. Например, если в двух множествах по 2 элемента, то способов биекции 2!=1*2=2, если по 3 элемента, то 3!=1*2*3=6 и т.д. И если в случае 3-х элементов — 5 способов давали бы биекцию, а шестой — нет, то говорить о равенстве количества элементов мы бы не могли.

Существующее правило: «Два множества называются равномощными, если между ними существует биекция» неполное. Полное должно звучать так: «Равномощные множества — это множества между которыми существуют биекции при любом порядке сопоставления их элементов».

Отсюда следует важный вывод, что равномощные множества на самом деле множества относящиеся к одному классу (в отличие от более мощных множеств, например, множества действительных чисел R). И говорить о том, что чётных чисел столько же сколько натуральных — неправомерно. Так как мы не можем даже утверждать, что натуральных чисел столько же сколько и натуральных. Так как для сравнения мощностей множеств существует только один метод — метод установления биекции, а этот метод несовершенен.

1. Существующее правило: Множество натуральных чисел (N) равномощно множеству целых чисел (Z). Т.к. мы можем установить биекцию, т.е. занумеровать числа множества Z числами множества N так, что ни одно число не повторится и все окажутся пронумерованными. Делается это так:
Целые числа: 0, 1, -1, 2, -2,…,+/-
Натуральные: 1, 2, 3, 4, 5,…,+
Видно что нечётные числа нумеруют ноль и отрицательные, а чётные – положительные. На этом основании делается вывод, что множества равны по мощности.

2. Множество натуральных чисел неравномощно множеству целых чисел.
Запишем целые числа: -, …, -5, -4, -3, -2, -1, 0 , 1, 2, 3, 4, 5,…,+
Запишем натуральные числа: 1, 2, 3, 4, 5,…,+.
Начнем пересчитывать точки одного множества в другое: Начнем с 1.
Целые числа: 1, 2, 3, 4, 5,…,+
Натуральные: 1, 2, 3, 4, 5,…,+
Как видно натуральные числа нумеруют только положительные целые числа, таким образом, отрицательные числа и 0 не могут быть пронумерованы. Ибо какое бы натуральное число мы ни взяли оно уже занято, т.е. оно нумерует число из ряда положительных целых чисел. Таким образом, для чисел -, …, -5, -4, -3, -2, -1, 0 не существует свободных натуральных чисел, которыми можно пронумеровать этот ряд.

Т.е. в зависимости от порядка сопоставления элементов из разных множеств друг с другом, мы получаем разные результаты. Современная теория множеств считает, что это свидетельствует о том, что часть равна целому (часть множества Z также равномощна и N, и Z). На самом же деле мы не можем однозначно утверждать равномощны ли эти множества, это неопределённость.

Видео:Такие разные бесконечности. Счётные и несчётные множества | матан #005 | Борис Трушин !Скачать

∀ x, y, z

Главная ≫ Инфотека ≫ Математика ≫ Книги ≫ 4. Равномощность множеств / Парадоксы теории множеств // Иван Ященко

Видео:Хорошо ли вы понимаете равномощность множеств?Скачать

4. Равномощность множеств / Парадоксы теории множеств

Видео:Отображения множествСкачать

Иван Ященко

Комментарии: 0

Видео:9 класс, 2 урок, Множества и операции над нимиСкачать

4. Равномощность множеств

Рассмотрим два множества и .

Отображение из в (обозначается ) — это правило, которое каждому элементу множества ставит в соответствие элемент множества , причем ровно один. (При этом не запрещается двум элементам множества ставить в соответствие один и тот же элемент множества , рис. 1,а.)

Доказать равномощность множества точек окружности и множества точек контура квадрата

Отображение называется взаимно однозначным, если каждый элемент множества поставлен в соответствие ровно одному элементу множества (рис. 1,б).

Множества и называются равномощными , если существует взаимно однозначное отображение . Понимать это можно так: множества равномощны, если в них одинаковое количество элементов.

Например, множества и лошадь, корова, телевизор равномощны, а множества и лошадь, корова неравномощны *7 . А равномощны ли множества и ? Неравномощны: в множестве нет ни одного элемента, а в множестве есть один элемент — пустое множество (множество — это коробка, в которой лежит пустое множество, а пустое множество — это коробка, в которой ничего не лежит).

*7 Телевизор был по делу…

1	2	3	4	5	6	7	8
1	+	+	+	–	–	–	+	–
2	+	+	–	+	–	+	–	–
3	+	–	+	+	+	–	–	–

Множества (множество всех натуральных чисел) и (множество всех натуральных чисел без единицы) равномощны: легко видеть, что отображение , , является взаимно однозначным. Множества и (множество всех целых чисел) также равномощны (достаточно рассмотреть отображение, которое переводит четные натуральные числа в целые неотрицательные, а нечетные — в отрицательные).

Обозначим через множество всех подмножеств множества . Примеры для некоторых множеств приведены в табл. 1. (Eстественно, подмножествами множества являются и пустое множество, и само множество .)

Подмножества множества не будем выписывать в строчку (так недолго запутаться), а перечислим при помощи таблицы: если элемент входит в подмножество с номером , то на пересечении -й строки и -го столбца ставится плюс, если не входит — минус (табл. 2). Например, первый столбец, в котором стоит три плюса, соответствует подмножеству .

Если составить такую же таблицу для множества из элементов, каждое подмножество будет определяться столбцом из символов (по числу элементов), и каждый символ можно выбрать двумя способами — либо » + » , либо » – » . Поэтому всего получится различных столбцов. Итак, если в множестве содержится элементов, то в множестве содержится элементов — существенно больше, чем в множестве .

Но если подмножества конечного множества мы можем просто сосчитать, то как же быть с бесконечными? Например, подмножеств множества натуральных чисел бесконечно много, и самих натуральных чисел бесконечно много. Оказывается, что в множестве «бесконечно больше» элементов, чем в множестве .

Теорема. Каково бы ни было множество , множество его подмножеств неравномощно самому множеству .

Это один из важнейших фактов теории множеств.

Доказательство. Доказывать будем методом от противного *8 . Предположим, что равномощно , т. е. существует взаимно однозначное отображение

которое каждому элементу множества ставит в соответствие — подмножество множества .

*8 Вообще, все, что можно доказать, можно доказать от противного. Поэтому на всякий случай будем доказывать от противного.

Вспоминая рефлексивные прилагательные, которые сами обладают тем свойством, которое определяют, мы назовем элемент хорошим, если (рис. 2,а), и плохим, если (рис. 2,б). Пусть — множество всех плохих элементов (возможно, пустое). Поскольку отображение взаимно однозначно, существует элемент , такой что . Вопрос: элемент — хороший или плохой? Предположим, элемент — хороший. Но тогда , а — множество плохих элементов, и значит, элемент — плохой. Противоречие. Если же элемент — плохой, то , а раз не принадлежит множеству плохих элементов, то — хороший. Снова противоречие. Получается, что элемент , с одной стороны, должен принадлежать , а с другой стороны, не должен.

Но сейчас, в отличие от парадокса с прилагательным «нерефлексивный», у нас есть лазейка. Мы получили противоречие, предположив, что равномощно . Значит, наше предположение неверно, т. е. и неравномощны. Теорема доказана.