Автор Тема: Построить биекцию (установить взаимно однозначное соответствие)  (Прочитано 5940 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн light

  • Пользователь
  • Сообщений: 1
    • Просмотр профиля
Построить биекцию между полуинтервалом и интервалом: A=[-7,2) и B=(5,16).
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5234
  • Поблагодарили: 1586 раз(а)
    • Просмотр профиля
Проведём прямую через две точки \(  \large (-7,5) \) и \(  \large (2,16) \): \(  \large \frac{x+7}{2+1}=\frac{y-5}{16-5}  \). Итак, отображение \(  \large f(x)=\frac{11}{9}x+\frac{122}{9} \) есть биекция между интервалами \(  \large (-7,2) \) и \(  \large (5,16) \). Добавление одного элемента к бесконечному множеству (числа \(  \large 7 \) к интервалу \(  \large (-7,2) \)) не меняет его мощности. Итак, найдённая функция есть искомая биекция.
 

Оффлайн Екатерина94

  • Пользователь
  • Сообщений: 3
    • Просмотр профиля
Установить взаимно однозначное соответствие между множествами:

а) отрезком \(  \large [0,1]  \) и квадратом \(  \large [0,1] \times [0,1]  \);

б) точками открытого квадрата \(  \large \left( -\frac{\pi}{2} , \frac{\pi}{2} \right) \times \left( -\frac{\pi}{2} , \frac{\pi}{2} \right)  \) и точками открытого прямоугольника \(  \large (a,b) \times (c,d)  \);

в) точками открытого квадрата \(  \large \left( -\frac{\pi}{2} , \frac{\pi}{2} \right) \times \left( -\frac{\pi}{2} , \frac{\pi}{2} \right)  \) и точками плоскости.
 

Оффлайн Тичер

  • Пользователь
  • Сообщений: 36
    • Просмотр профиля
а) возьми кривую Пеано
б) перевести интервал в интервал несложно
в) точка (х,у) переходит в точку (tg x, tg y)
 

Оффлайн UsesABC

  • Пользователь
  • Сообщений: 81
  • Поблагодарили: 3 раз(а)
    • Просмотр профиля
Здравствуйте! Помогите пожалуйста с решением данной задачки. Установить взаимно-однозначное соответствие между множествами Х и Y где Х = [0;1] а Y=(0;1) (взаимно-однозначное соответствие между отрезком и интервалом).
Век живи - век учись!
 

Оффлайн phobos

  • Модератор
  • Сообщений: 95
  • Поблагодарили: 85 раз(а)
    • Просмотр профиля
Решение данного задания разобрано в книге Тишин В. В. Дискретная математика в примерах и задачах.
 
Сказали спасибо: Admin, Байт, UsesABC

Оффлайн Байт

  • Пользователь
  • Сообщений: 1002
  • Поблагодарили: 702 раз(а)
    • Просмотр профиля
Небольшое дополнение. Непрерывной биекции нет и быть не может, так как множества топологически не эквивалентны.
Поэтому отображаем внутренность Х на Y естественным образом. Остаются 2 лишние точки. Вытягиваем из Y счетное множество. Сдвигаем его элементы на 2 позиции, и в освободившиеся отображаем эти 2 неприкаянные. Уважаемый phobos очень подробно описал пример такого "вытягивания" и построения.
Важно понять, что если осталось "неприкаянным" конечное или счетное множество, то его можно "погрузить" в любое вытянутое из целевого множества счетное подмножество.
Я духов вызывать могу из бездны! - И я могу, и каждый это может. Вопрос лишь, явятся ль они на зов?
 
Сказали спасибо: Admin, UsesABC

Оффлайн UsesABC

  • Пользователь
  • Сообщений: 81
  • Поблагодарили: 3 раз(а)
    • Просмотр профиля
Век живи - век учись!
 

Оффлайн gigoh

  • Пользователь
  • Сообщений: 22
  • Поблагодарили: 3 раз(а)
    • Просмотр профиля
Приветствую!
Необходимо доказать что множества X и Y равномощны, построив взаимно однозначное соответствие.
X: (-6;11)
Y: [-3;2]

Всем заранее признателен за помощь, подобный пример решаю впервые.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5234
  • Поблагодарили: 1586 раз(а)
    • Просмотр профиля
Установить равномощность отрезков \(  \large [-6;11]  \) и \(  \large [-3;2]  \) легко. Расположим эти отрезки на осях координат - первый на оси абсцисс, второй на оси ординат. Проведём через концы этих отрезков прямую. Линейная функция, графиком которой будет эта прямая, является искомой биекцией. Имеем:

\(  \large \frac{y-y_1}{y_2-y_2}=\frac{x-x_1}{x_2-x_1} \Leftrightarrow \frac{y+3}{2+3}=\frac{x+6}{11+6} \Leftrightarrow y=\frac{5x-21}{17} \).

Однако нам нужно построить биекцию между интервалом \(  \large (-6;11)  \) и отрезком \(  \large [-3;2]  \). Тут нужно как-то вычленить рациональные точки этих множеств и установить биекцию между ними.
 

Оффлайн gigoh

  • Пользователь
  • Сообщений: 22
  • Поблагодарили: 3 раз(а)
    • Просмотр профиля
 То есть для моих множеств док-во через функцию не подойдёт?

Однако нам нужно построить биекцию между интервалом \(  \large (-6;11)  \) и отрезком \(  \large [-3;2]  \). Тут нужно как-то вычленить рациональные точки этих множеств и установить биекцию между ними.

Между данными множествами ведь не может существовать биективного непрерывного отображения, разве нет?
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5234
  • Поблагодарили: 1586 раз(а)
    • Просмотр профиля
То есть для моих множеств док-во через функцию не подойдёт?

Равномощность всегда устанавливается через функцию. Но в данном случае она не может быть непрерывной.

Легко установить, что множества \(  \large  X=[0;1]  \) и \(  \large Y=(0;1)  \) имеют одинаковую мощность. Пусть \(  \large Z= \{0,1,\frac{1}{2},\frac{1}{3}, \ldots, \frac{1}{n}, \ldots\} \), \(  \large W= \{\frac{1}{2},\frac{1}{3}, \ldots, \frac{1}{n}, \ldots\} \). Ясно, что \(  \large (X \setminus Z) \cup Z=X  \), \(  \large (Y \setminus W) \cup W =Y  \). Биекцией между множествами \(  \large X \setminus Z  \) и \(  \large Y \setminus W  \) является тождественное отображение: \(  \large f(x)=x  \). Биекцию между множествами \(  \large Z  \) и \(  \large W  \) установим следующим образом: \(  \large f(0)=\frac{1}{2}, f(1)=\frac{1}{3}, f(2)=\frac{1}{4}, \ldots , f \left( \frac{1}{n}\right)=\frac{1}{n+2}  \).

В Вашем случае нужно проделать что-то подобное или искать иной способ.

Можно поступить следующим образом:

\(  \large f(x) =\begin{cases} \frac{5x-21}{17}, если \ x \not = -3, x \not = 2 \\ x, если  \ x=-3,x=2  \end{cases}  \).

Если не ошибаюсь, эта функция взаимно однозначна. Функции \(  \large g(x)=\frac{5x-21}{17}  \) и \(  \large h(x)=x  \) взаимно однозначны, как и любые другие линейные функции. Их множества определения и множества значений не пересекаются. Первое очевидно (множество определения второй функции прямо исключено из множества определения первой). Второе можно показать так: \(  \large \frac{5x-21}{17}=-3 \Leftrightarrow x=-6 \not \in D(g)  \), \(  \large \frac{5x-21}{17}=2 \Leftrightarrow x=11 \not \in D(g)  \) (первая функция никогда не принимает значения, равные \(  \large -3  \) и \(  \large 2  \)).
 

Оффлайн programmizd

  • Пользователь
  • Сообщений: 9
    • Просмотр профиля
Построить биекцию между множествами \(  \large [0;1]  \) и \(  \large (2;5)  \).
 

Оффлайн Байт

  • Пользователь
  • Сообщений: 1002
  • Поблагодарили: 702 раз(а)
    • Просмотр профиля
Строим естественную биекцию F: (0;1) -> (2;5) Остаются 2 неприкаянные точки 0 и 1
Берем любую бесконечную последовательность в (0; 1) a1, a2, a3, ... an ...
0->F(a1)
1->F(a2)
a1->F(a3)
...
an->F(an=2)
...
Я духов вызывать могу из бездны! - И я могу, и каждый это может. Вопрос лишь, явятся ль они на зов?
 
Сказали спасибо: Admin, programmizd

Оффлайн Admin

  • Администратор
  • Сообщений: 5234
  • Поблагодарили: 1586 раз(а)
    • Просмотр профиля
Байт, а вот так нельзя: \(  \large \begin{cases} \frac{3x}{2}+2, \ если \ x \not = 0, x \not =1 \\ x , \ если \ x=0, \ x=1 \end{cases}  \)?
 
Сказали спасибо: programmizd

Оффлайн Байт

  • Пользователь
  • Сообщений: 1002
  • Поблагодарили: 702 раз(а)
    • Просмотр профиля
а вот так нельзя:
Не-а... Точки 0 и 1 лежат вне интервала (2;5)
И здесь (3x/2 + 2) видимо, описка. Следует писать 3x + 2
Я духов вызывать могу из бездны! - И я могу, и каждый это может. Вопрос лишь, явятся ль они на зов?
 
Сказали спасибо: Admin, programmizd

Оффлайн programmizd

  • Пользователь
  • Сообщений: 9
    • Просмотр профиля
А как тогда правильно?
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5234
  • Поблагодарили: 1586 раз(а)
    • Просмотр профиля
Точки 0 и 1 лежат вне интервала (2;5)

Точно. Ерунду написал.
 

Оффлайн dota2

  • Пользователь
  • Сообщений: 22
    • Просмотр профиля
Доказать, что множество всех булевых функций счётно (установить биекцию между множеством всех булевых функций и множеством натуральных чисел).
Помогите пожалуйста. Очень нужно.
 

Оффлайн mnffy

  • Пользователь
  • Сообщений: 10
  • Поблагодарили: 2 раз(а)
    • Просмотр профиля
Уважаемые форумчане, требуется ваша помощь! Нужно установить биекцию между множествами рациональных чисел Q и декартовым квадратом множества натуральных чисел N2 Спасибо! :) :) :)
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5234
  • Поблагодарили: 1586 раз(а)
    • Просмотр профиля
Докажем, что множество булевых функций счётно (установим биекцию между множеством булевых функций и множеством натуральных чисел). Будем считать, что существуют функции алгебры логики от нуля переменных - тождественный нуль и тождественная единица (но можно и без этого обойтись). Известно, что всего существует \(  \Large 2^{2^n}  \) функций алгебры логики от \(  \large n  \) переменных. Значит, есть четыре функции от одной переменной: тождественные единица и нуль, отрицание и тождественная функция, шестнадцать функций от двух переменных. И так далее. Пусть образом тождественного нуля от нуля переменных при отображении \(  \large \varphi  \) будет 1, образом тождественной единицы от нуля переменных - 2, образом тождественного нуля от одной переменной - 3, образом тождественной функции от одной переменной - 4, образом отрицания от одной переменной - 5, образом тождественной единицы от одной переменной - 6. Так можно пронумеровать все булевы функции. Следовательно, \(  \large \varphi : \mathcal{F} \to \mathbb{N}  \) - биекция, где \(  \large \mathcal{F}  \) - множество всех булевых функций. Существование такой биекции доказывает счётность множества всех булевых функций.
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5234
  • Поблагодарили: 1586 раз(а)
    • Просмотр профиля
Займёмся построением биекции между множеством рациональных чисел и декартовым квадратом множества натуральных чисел.

Сначала покажем, как построить биекцию между \(  \large \mathbb{N}  \) и \(  \large \mathbb{N}^2  \).

Запишем элементы множества \(  \large \mathbb{N}^2  \) следующим образом:

\(  (1,1) \ (2,1) \ (3,1) \ (4,1) \ \ldots  \\ (1,2) \ (2,2) \ (3,2) \ (4,2) \ \ldots \\ (1,3) \ (2,3) \ (3,3) \ (4,3) \ \ldots \\ (1,4) \ (2,4) \ (3,4) \ (4,4) \ \ldots \\ (1,5) \ (2,5) \ (3,5) \ (4,5) \ \ldots \\ \ldots    \)

Начнём нумеровать их так, как показано на рисунке. Так можно пронумеровать все элементы множества.
 

Оффлайн mnffy

  • Пользователь
  • Сообщений: 10
  • Поблагодарили: 2 раз(а)
    • Просмотр профиля
Спасибо, но что дальше то? Я вообще не могу понять ничего(((
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5234
  • Поблагодарили: 1586 раз(а)
    • Просмотр профиля
Аналогичным образом можно занумеровать все рациональные числа (но придётся исключить дроби, которые можно сократить). Итак, мы имеем биекции \(  \large f \colon \mathbb{Q} \to \mathbb{N}  \) и \(  \large g \colon \mathbb{N} \to \mathbb{N}^2  \). Значит, имеем и биекцию \(  \large h \colon \mathbb{Q} \to \mathbb{N}^2  \). Думаю, так...
 
Сказали спасибо: mnffy

Оффлайн mnffy

  • Пользователь
  • Сообщений: 10
  • Поблагодарили: 2 раз(а)
    • Просмотр профиля
Аналогичным образом можно занумеровать все рациональные числа (но придётся исключить дроби, которые можно сократить). Итак, мы имеем биекции \(  \large f \colon \mathbb{Q} \to \mathbb{N}  \) и \(  \large g \colon \mathbb{N} \to \mathbb{N}^2  \). Значит, имеем и биекцию \(  \large h \colon \mathbb{Q} \to \mathbb{N}^2  \). Думаю, так...
Хорошо, спасибо за подсказки))
 

Оффлайн Admin

  • Администратор
  • Сообщений: 5234
  • Поблагодарили: 1586 раз(а)
    • Просмотр профиля
Не уверен, что такое решение примут, но, на мой взгляд, этого вполне достаточно.
Наверное, можно придумать и что-нибудь поинтереснее.