Построить биекцию

Автор темы molotov 
ОбъявленияПоследний пост
ОбъявлениеИщем преподавателя для углубленного обучения статистическим методам29.05.2020 13:22
ОбъявлениеПреподаватель мехмата МГУ удостоен международной премии по математике Presburger Award28.07.2020 01:04
ОбъявлениеИсследовательские гранты фонда «БАЗИС» 202118.02.2021 17:56
04.01.2021 11:07
Построить биекцию
Приветствую!
Для конечного множества Х построить биекцию между множеством подмножеств икса с четным числом элементов и множеством подмножеств икса с нечётным числом элементов



Редактировалось 1 раз(а). Последний 04.01.2021 12:31.
04.01.2021 13:09
хм
вам надо вы и стройте
04.01.2021 14:53
Ответ
Очевидно, что биекция существует, только если X не пусто.
Пусть A - подмножество X с нечётным числом элементов.
Тогда симметрическая разность с A будет биекцией между чётными и нечётными подмножествами X.
Если в самом X нечётное число элементов, то операция дополнения тоже будет такой биекцией (это, на самом деле, частный случай примера, приведённого выше).
04.01.2021 15:04
Встречная задачка
Пока решал задачу выше, родилась такая задачка:
Доказать, что всякая монотонная биекция $F:2^X\to2^X$ индуцирована некоторой биекцией множества X на себя.



Редактировалось 2 раз(а). Последний 04.01.2021 15:07.
05.01.2021 09:00
Монотонная биекция
Как я понимаю,монотонная биекция булевой алгебры - это автоморфизм.
Следовательно, она сохраняет не только булевские операции, но и бесконечные суммы, т.е. объединения.
Далее очевидно.
05.01.2021 13:32
Далее очевидно
museum: "... Далее очевидно.".
Ну, разумеется. Осталось доказать только, что монотонная биекция - это изоморфизм.
05.01.2021 23:44
Вообще-то
Цитата
bystrikov (Bystrikov Alexey)
museum: "... Далее очевидно.".
Ну, разумеется. Осталось доказать только, что монотонная биекция - это изоморфизм.
Булевы операции, в т.ч. и бесконечные, определимы в сигнатуре упорядоченного множества, следовательно, автоморфизм упорядоченного множества булевой алгебры является автоморфизмом булевой алгебры.
Это, конечно, общий принцип, в частном случае топикстартер может поупражняться.
06.01.2021 07:58
Вообще-то
В условиях задачи не было автоморфизма упорядоченного множества. Если монотонная биекция определена на частично упорядоченном множестве, обратная биекция может два сравнимых между собой элемента отображать в несравнимые, и монотонность её, таким образом, может нарушаться.
06.01.2021 16:59
Доказательство
Прошу прощения, здесь, конечно, есть, что доказывать.
Если множество Х конечно, то всё очевидно.
Прежде всего покажем, что $f^{-1}(\{a\})\inX$, т.е. прообраз одноэлементного множества есть одноэлементное множество.
Предположим противное, пусть $f^{-1}(\{a\})=v=\{x,y, ...\}$.
Т.к. $\{x\}\subsetv$ и $\{у\}\subsetv$, и $\{f(\{x\}),f(\{y\})\}\subset f(v) = \{a\}$ и содержит не менее двух элементов. Противоречие.
Таким образом, $f$ инъективно отображает одноэлементные множества (в дальнейшем их будем отождествлять с их элементами) во множество одноэлементных множеств.
Для конечного $X$ это отображение биективно и дальнейшее не составляет труда. Но и для бесконечного $X$ всё довольно просто.
Очевидно: $f(A)\bigcupf(B)\subsetf(A\bigcupB)$. В частности, для любого $A\subsetX$ имеет место $\bigcup_{x\inA}f(x)\subsetf(A)$.
Аналогично $f(A\bigcapB)\subsetf(A)\bigcapf(B)$.

Покажем, что образом одноэлементного множества является одноэлементное множество.
Пусть $f(a)=A$ для двух различных элементов имеет место: $x,y\inA$ и $f^{-1}(x)\nea$.
Тогда для любого $B$, если $a\inB$, то $\bigcup_{x\inB}f(x)\subsetf(B)$.
Полагая $B=X\setminus\{f^{-1}(x)\}$ мы получим: $f(B)=X$ - противоречие.
Таким образом, наше отображение индуцирует биекцию множества $X$ на себя.
Покажем, что $f(\bar{A})=\bar{f(A)}$, т.е.функция $f$ сохраняет булеву операцию дополнения.
Действительно, т.к. $f(A)\bigcupf(B)\subsetf(A\bigcupB)$, то $f(A)\bigcupf(\bar{A})=X$
и $f(A)\bigcapf(\bar{A})=\emptyset$. Следовательно, $f(\bar{A})=\bar{f(A)}$.
Отсюда легко получается сохранение других булевых функций.



Редактировалось 2 раз(а). Последний 07.01.2021 01:06.
06.01.2021 17:11
хм
Цитата
bystrikov (Bystrikov Alexey)
Очевидно, что биекция существует, только если X не пусто.
Пусть A - подмножество X с нечётным числом элементов.
Тогда симметрическая разность с A будет биекцией между чётными и нечётными подмножествами X.
Если в самом X нечётное число элементов, то операция дополнения тоже будет такой биекцией (это, на самом деле, частный случай примера, приведённого выше).

ничего не понятно. а где случай, когда X имеет четное число элементов?
10.01.2021 18:42
Правильное решение
Спасибо, museum, это правильное решение. (Извиняюсь, что не сразу его заметил.)
Замечу ещё, что аналогичная формулировка для произвольных частично упорядоченных множеств уже не будет верной
(то есть множества в данном случае существенны не только для доказательства, но и для истинности).
11.01.2021 00:47
Это я извиняюсь, точнее, уже извинился.
Цитата
bystrikov (Bystrikov Alexey)
Спасибо, museum, это правильное решение. (Извиняюсь, что не сразу его заметил.)
Замечу ещё, что аналогичная формулировка для произвольных частично упорядоченных множеств уже не будет верной
(то есть множества в данном случае существенны не только для доказательства, но и для истинности).
И, разумеется, здесь существенно именно "булеан".
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти