Как построить биекцию между множествами

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>. Вновь полученное множество (обозначим его В Ì [0, 1]), также является счетным. Следовательно, множества А и В равномощны и существует биекция f, отображающая B на A. Построим теперь биекцию отрезка [0, 1] на интервал (0, 1) следующим образом:

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

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

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

Источник

Получите аналитическую биекцию между множествами

Установить биекцию между двумя множествами
Добрый день! Подскажите пожалуйста, как мне установить биекцию между двумя множествами Q и N2.

Можете объяснить разницу между массивами и множествами, а так же принцип работы с множествами
Можете объяснить разницу между массивами и множествами, а так же принцип работы с множествами, и их.

Сделайте несколько глубоких вдохов, успокойтесь и перечитайте сообщения 1 и 5.

Добавлено через 1 минуту
Также обратите внимание на правила форума и 4.7 и 5.18.

а все понял скриншот вышел не тот извиняюсь. Ну на счет 1го сообщения это все задание и никаких более условий не прилагается

Если отображение одновременно инъективно и сюръективно, то его называют биективным.

вот что говориться о биекции в курсе и все больше ничего

Я не сомневаюсь, что это все задание. Дело в том, что преподаватель имеет право дать на лекции определение: «Фуфлорепер — это пара (O, E), где E — не обязательно линейно независимая система векторов», и затем использовать слово «фуфлорепер» в домашнем задании. При этом ни один человек, который не относится к вашему курсу, не сможет помочь решить такую задачу.

Вопрос про представление (-1;3] △ (0;5] в виде объединения непересекающихся интервалов остается. Дело в том, что я лично отвечаю на вопросы, в которых вижу, чем они могут представлять сложность для спрашивающего. Если нужно просто сделать работу согласно понятным правилам, то это ваша ответственность.

Источник

ТГиК-2019-Лекция-16.09.2019

Содержание

Биекция и её полезные свойства

Биекция и мощность множеств

Теорема. Если между множествами А и В можно построить биективное отображение, то их мощности равны и наоборот.

Доказательство проведём по индукции.

1) Рассмотрим случай пустого множества.

\( \left | \varnothing \right | = 0\)

Для пустого множества можно составить биекцию только с пустым множеством. Тогда \(0=0\), теорема выполняется

Между множествами А и В можно установить биекцию \(\left \ \longleftrightarrow \left \\)

Из условия \( \left |A \right | = \left |B \right | \), и мы смогли построить биекцию.

3) Предположение \( \left |A \right | = \left |B \right | \Longleftrightarrow \exists f:A \longleftrightarrow B \)

4) Пусть \( \exists C, D: \left | C \right | = n + 1; \) \(\exists f:C \longleftrightarrow D \)

5) Из биекции следует, что \( \forall c \in C\) \(\exists f(c) = d; \)

6) Тогда \( f: C \backslash \left \ \longleftrightarrow D \backslash \left \\)

7) Так как мы исключили один элемент c, то \(\left |C \backslash \left \ \right | = n\). Из биекции следует, что для D \(\left |D \backslash \left \ \right | = n\)

8) «Вернём» элемент d и по правилу сложения получим, что \(\left |D \right | = n+1\)

Биекция и эквивалентность множеств

\(A \sim B \Longleftrightarrow \exists f:A \longleftrightarrow B \)

1) \( A \sim A \mbox <, так как >\exists f \mbox <: >A \longleftrightarrow A \mbox <: >f(a)=a; \)

3) \( A \sim B \mbox < (отображение f), >B \sim C \mbox < (отображение g), >\Longrightarrow A \sim C \mbox < (отображение fg) >\)

Фактор-множество

У данного набора подмножеств есть некоторое свойство\[A_i \cap A_j = \varnothing \Longleftrightarrow i \neq j \]

Доказательство проведём от противного

2) Так как \( b_1 \in A_i \), то \( \forall a’ \in A_i \mbox < : >a’ \rho \mbox < >b_1 \)

Так как \( b_1 \in A_j \), то \( \forall a» \in A_j \mbox < : >a» \rho \mbox < >b_1 \)

Следовательно, \( A_i = A_j \)

Разбиение

Разбиение множества — это представление его в виде объединения произвольного количества попарно непересекающихся непустых подмножеств (см. рис.1) Мы доказали выше, что классы эквивалентности либо не пересекаются, либо совпадают. Значит, отношение эквивалентности задаёт разбиение множества, на котором мы задаём отношение эквивалентности.

Бином Ньютона

Формула для двух элементов:

Формула для n элементов:

Число \(P^_ \) называется числом перестановок с повторениями.

Свойства комбинаторных величин

Следовательно, они равны

Нужно выбрать k+1 элемент из множества n+1 элементов. Вариантов выбора два:

Источник

Как постоить биекцию между квадратом и отрезком?

Здравствуйте, уважаемые преподаватели!

Знаю, что мощность отрезка [0; 1] равно мощности континуума. И знаю, что декартово произведение двух отрезков, то есть единичный квадрат, имеет такую же мощность.
Значит, между этими множествами существует биекция. А как её построить?

Вот что я нашла в книге Р.Курант, Г.Роббинс. Что такое математика? на c.112-113

Но я не понимаю, как можно видоизменить указанное построение=(

Павел Борисович, спасибо Вам большое! Я все поняла!

А приведенное выше доказательство из книги (которое я привела) придумал Кантор, как я поняла. Я очень много вчера литературы по этому поводу прочитала.

Да, а я думала над другим способом обойти проблему с «плохими точками». Хотела просто то же самое преобразование — склеивание двух координат точки квадрата, производить в двоичной системе счисления. Там же нет 9-ок=). Но потом поняла, что проблема и в этом случае никуда не исчезает: ведь ( 0.(1) )_2 = ( 1 )_2 = ( 1.(0) )_2

Это просто чтобы Вы не думали, что я только задаю вопросы — а сама ничего не делаю.

Да, согласна. Но мы можем отбросить все последовательности с 1 в периоде в принципе, кроме одной ( 0.(1) )_2, которая как раз и получается при склеивании координат правой верхней вершины квадрата, то есть двух таких же последовательностей.
Тогда у нас все точки отрезка будут образами каких-то точек квадрата.

Да? То есть нет смысла переходить в двоичную систему счисления?

Источник

Отображения множеств. Функция. Биекция.

Определение: Множество A называется эквивалентным множеству B, если существует биекция f:А→B. В этом случае говорят также, что множество A имеет одинаковую мощность с множеством B. Обозначение:A

B или .

1. Множество всех натуральных чисел эквивалентно множеству всех чётных чисел, так как отображение , определяемое формулой f(n)=2n есть биекция.

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

3. Функция f=(b-a)x+a взаимно однозначно отображает интервал (0,1) на интервал (a,b), а сегмент [0,1] на сегмент [a,b], поэтому (0,1)

1. Всегда A

B, то B

B и B

C, то A

Доказательство строится на определении эквивалентного множества и свойств биекции:

1. Тождественное отображение id:A→A есть биекция.

Теорема 2: Если A₁

B₂,то .

Пусть f₁:A₁→B₁ и f₂:A₂→B₂— биекции. Определим отображение формулой f(a₁,a₂)=(f₁(a₁), f₂(a₂)). Тогда f есть биекция, так как для любого элемента (b₁, b₂) декартова произведения в декартовом произведении имеется единственный прообраз относительно отображения f, именно точка .

Tеорема 3: Пусть и — два семейcтва попарно непересекающихся множеств, и пусть существует такая биекция: f:X→Y, что A_x

B_f(x) для любого элемента . Тогда множества и эквивалентны.

Обозначим через g_x биекцию множества А_x на множество B_f(x). Пусть — произвольный элемент из А. Тогда, так как множества первого семейства попарно не пересекаются, существует единственный элемент , такой, что . Поставим в соответствие элементу a элемент g_x(a) из B_f(x), принадлежащий вместе с тем и множеству B. Получим биекцию множества А на B. Действительно, если b произвольный элемент из B, то в силу попарной непересекаемости множеств второго семейства, существует единственный элемент , такой, что . Ясно, что элемент является единственным прообразом элемента b при нашем соответствии.

Tеорема 4: Если и A₃

Так как A₁

A₃, то существует биекция f:A₁→A₃. Положим и далее по индукции, если множества A₁, A₂. A_n уже определены, то полагаем . Таким образом, получается последовательность множеств . Покажем, что эта последовательность удовлетворяет следующим трем условиям:

1. (1)

2. для всех m≠n (2)

3. для всех (3)

Докажем условие (1) по индукции. Отношения выполнены по условию теоремы. Допустим, что верны отношения . Тогда из следует , то есть . Тем самым условие (1) доказано.
Условие (2) вытекает из (1), так как при m≠n полагая, например, m>n, будем иметь . Следовательно, любая точка из A_m\A_m+1 не принадлежитA_n\A_n+1.
Для доказательства (3) заметим, что из отношений и биективности f следует , что и означает справедливость отношений (3).

Докажем еще, что слагаемые в правой части равенства (4) попарно не пересекаются. Первое слагаемое С не пересекается с любым слагаемым в силу очевидного включения , а остальные слагаемые попарно не пересекаются в силу (2).

Если положить , то равенства (4) и (5) можно переписать следующим образом:
. В этих двух объединениях слагаемые, стоящие на одинаковых местах, начиная со второго, эквивалентны в силу (3), а первые слагаемые одинаковы и потому тоже эквивалентны. По теореме 3: множества A₁ и A₂ эквивалентны.

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

Теорема 5 (Теорема Кантора):. Множество X и его булеан (множество всех его подмножеств) не эквивалентны.

Допустим противное, что . Тогда существует биекция: . Для любого элемента f(x) есть элемент булеана , то есть подмножество множества X. Возможны две ситуации: либо , либо . Обозначим через Y множество всех таких элементов , что . Множество Yодновременнно является элементом булеана . Поэтому существует такой единственный элемент , что f(y₀)=Y. Ясно, что либо , либо . Покажем, что оба эти отношения невозможны, что и докажет теорему.

Пусть . Но Y=f(y₀), значит . Но в таком случае по определению Y . Получили противоречие.
Пусть теперь . Но такой элемент должен по определению множества Y принадлежать Y: . Опять получилось противоречие.

Источник