Эквивалентность множеств функций

[Someone]

Нет, $c$ переводится не в $a$. Но Вы же один раз это сказали правильно. И потом вдруг какая-то композиция…

[Xaositect]

Хм.
Даже не знаю, ка объяснить. Такие вещи, в них часто путаются, но когда ты их понял, очень сложно вспомнить, что же было не так.

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

Так вот, композиция - это когда у нас есть два ящика $f\in B^C$ и $g\in A^B$ и мы из них делаем конвеер - кладем в ящик $f$ элемент $c\in C$, из него перекладываем элемент $f(c)\in B$ в ящик $g$, и в итоге получаем $g(f(c))$.

А теперь я в этих терминах объясню функцию $\varphi\in (A^B)^C$. Это значительно интереснее. Мы в нее кладем $c\in C$, а достаем из нее $\varphi(c)\in A^B$, которая не что-то там, а другая коробка. То есть $\varphi\in (A^B)^C$ --- это такая фабрика по производству волшебных коробок.

После этого мы в эту новую коробку можем уже положить какое-нибудь еще $b\in B$ и на выходе получить элемент множества $A$

Понимаете разницу?

[Manticore]

Так. Попытался ещё раз вдуматься.
Функция из $B$ в $A$: область отправления - в $B$, прибытия - в $A$.
Из $C$ в функции из $B$ в $A$: область отправления - в $C$, прибытия - во множестве функций из $B$ в $A$.
Т.е. $c$ соответствует функция, где $b$ соответствует $a$

И тогда:

Xaositect в сообщении #766718 писал(а):

А теперь я в этих терминах объясню функцию $\varphi\in (A^B)^C$. Это значительно интереснее. Мы в нее кладем $c\in C$, а достаем из нее $\varphi(c)\in A^B$, которая не что-то там, а другая коробка.

Получается ли, что $\varphi(c)$ - это $f(b)$?

[Xaositect]

Manticore в сообщении #766722 писал(а):

Получается ли, что $\varphi(c)$ - это $f(b)$?

Нет.

Вот у нас есть $\varphi\in (A^B)^C$. С помощью нее мы из $c\in C$ получаем $\varphi(c)$. Ее можно как-нибудь обозначить, давайте обозначим ее $f$. Итак, $f = \varphi(c)\in A^B$.
Дальше в $f$ мы можем подать еще $b\in B$ и получить $f(b) = \varphi(c)(b)\in A$.

-- Вс сен 22, 2013 21:14:01 --

Вот такая двухступенчатая конструкция получается.

[Manticore]

Так, это понял, и чем отличается от композиции - тоже. Только теперь совсем не представляю, как строить биекцию при такой конструкции.

[Xaositect]

Вот.

С $(A^B)^C$ мы разобрались. А $A^{B\times C}$ --- это значительно проще. Это функции $\psi$, которые принимают пару аргументов $(b,c)\in B\times C$ и получается результат $\psi(b, c)$. То есть обычная функция от двух переменных.

Теперь про биекцию. Я на самом деле ее уже описал в пролом посте, но Вы сами попробуйте не смотря на него сделать это еще раз. Вот есть у нас функция $\varphi\in (A^B)^C$ и из нее надо получить функцию $\psi\in A^{B\times C}$, причем так, чтобы была биекция. Но давайте пока просто, а биективность потом докажем.

Итак, у нас есть $\varphi\in (A^B)^C$. И нам надо на ее основе построить $\psi\in A^{B\times C}$. Для того, чтобы определить эту функцию $\psi$, надо сказать, какой результат будет на любой паре. Возьмем произвольную пару $(b,c)$. Можем мы построить из нее элемент $A$?

[Manticore]

Xaositect в сообщении #766730 писал(а):

Итак, у нас есть $\varphi\in (A^B)^C$. И нам надо на ее основе построить $\psi\in A^{B\times C}$. Для того, чтобы определить эту функцию $\psi$, надо сказать, какой результат будет на любой паре. Возьмем произвольную пару $(b,c)$. Можем мы построить из нее элемент $A$?

Видимо, при помощи $\varphi$ и $f$ - да. То есть применяем $f$ к $c$, а потом применяем к $b$, и получаем функцию от $c$ и $b$.

-- 22.09.2013, 20:47 --

То есть получается то же самое, что и $\psi (b,c)$

[Xaositect]

Верно.
То есть каждой функции $\varphi\in (A^B)^C$ соответствует функция $\psi\in A^{B\times C}$, переводящая произвольную пару $(b,c)$ в $\varphi(c)(b)$.

Теперь осталось доказать, что это биекция. Для этого в данном случае легче всего привести обратное преобразование. Все наоборот: пусть у нас есть $\psi\in A^{B\times C}$. Мы хотим получить из нее $\varphi\in (A^B)^C$. Для этого надо определить эту функцию на каждом $c\in C$. Итак, по каждой функции $\psi\in A^{B\times C}$ можно построить функцию $\varphi\in (A^B)^C$, которая переводит $c\in C$ в функцию из $A^B$, которая переводит каждый $b\in B$ в $\psi(b, c)$. Эту функцию часто пишут как $\psi(-, c)$ или $\psi(\cdot, c)$.

Итак.
У нас есть преобразования из функции $\varphi\in (A^B)^C$ в функцию $\psi\in A^{B\times C}$, которая работает так: $(b, c)\mapsto\varphi(c)(b)$.
У нас есть преобразование из функции $\psi\in A^{B\times C}$ в функцию $\varphi\in (A^B)^C$, которая работает так: $c\mapsto \psi(-, c)$.
Осталось доказать, что это два взаимно обратных преобразования, то есть они задают биекцию $(A^B)^C\sim A^{B\times C}$. Для этого надо доказать, что если применить сначала одну конструкцию, а потом другую, то в итоге окажется то же самое, что было в самом начале. Справитесь?

[Manticore]

Эх. Сижу 2 часа мучаюсь, хотя Вы вроде бы всё расписали и объяснили, тем не менее, сформулировать не получается.
$C \xrightarrow{f} \varphi(c)$
$C \xrightarrow{f(b)} \varphi(b)(c)$

$(b,c) \xrightarrow{\psi} \psi(b,c)$ И нужно получить $c$? Или применить $\psi$ к $\varphi$ - бред начался.


-- 22.09.2013, 22:23 --

Пусть у нас есть $\varphi(b)(c) [1]$ (после применения функции $f$ и добавления $b$). К $b$ и $c$ из $[1]$ применяем функцию $\psi$ и получаем $\psi(b,c) [2]$ Из $[2]$ берём $c$ и применяем $f$. Добавляем $b$ из $[2]$ и получаем $\varphi(b,c)$.
Может, так?

[arseniiv]

Manticore в сообщении #766762 писал(а):

$C \xrightarrow{f} \varphi(c)$

У вас тут слева множество, справа один элемент — это нормально? Лучше бы записи обозначали всё время одно и то же, типа $X \xrightarrow{f} Y$ — это $f: X \to Y$, $x \stackrel{f}{\mapsto} y$ — это $f(x) = y$.

[Manticore]

arseniiv в сообщении #766777 писал(а):

Лучше бы записи обозначали всё время одно и то же

Извините, просто устал немного и автоматически нажал на shift.

В общем за всё это время пришёл только к тому, что написал выше.

[arseniiv]

Ещё у вас там то

Manticore в сообщении #766762 писал(а):

$\varphi(b)(c) [1]$

, то

Manticore в сообщении #766762 писал(а):

$\varphi(b,c)$

Давайте обозначим первую функцию Xaositect, которая $(A^B)^C \to A^{B\times C}$, $F$, а вторую — $G$. $F(\varphi) = \psi, G(\psi)$ (т. е. так мы предполагаем пока).

Теперь вы начинаете с, скажем, $\varphi$, функции двух аргументов, и делаете $F(\varphi) = (b, c) \mapsto \varphi(c)(b)$ (см. выше). Теперь применим к этому $G$. $G(F(\varphi)) = \ldots ?$ — и тут лучше посмотреть, что будет, если применить к $F(\varphi)$ только второй аргумент, а первый оставить, т. к. это требуется выше. Это будет функция $b \mapsto F(\varphi)(b, c)$, т. е. $b \mapsto \varphi(c)(b)$, т. е. просто $\varphi(c)$. Теперь можно приняться за старое: $G(F(\varphi)) = c \mapsto \phi(c) = \varphi$. Всё: $(G\circ F)(\varphi) = \varphi$ [раз уж вы упоминали композицию ], и так как $\varphi$ была выбрана произвольно, $G\circ F$ должно быть равно $\operatorname{id}_{(A^B)^C}$. А теперь найдите $F\circ G$.

Самое главное сейчас здесь — внимательно следить, что каждая запись означает. $x \mapsto K$ — функция, отображающая $x$ в какое-то выражение $K$ от этой переменной.

(Если с композицией в обратном порядке не получится, попробуйте взять конкретные $A, B, C, \psi$. Например, целые числа и операцию сложения: $\psi(b, c) = b + c$.)
________

Xaositect, мне кажется, вместо $c \mapsto \psi(-,c)$ стоило написать $c \mapsto (x \mapsto \psi(x, c))$. Может, это выглядело бы понятнее?

[Manticore]

arseniiv в сообщении #766785 писал(а):

Теперь применим к этому $G$. $G(F(\varphi)) = \ldots ?$ — и тут лучше посмотреть, что будет, если применить к $F(\varphi)$ только второй аргумент, а первый оставить, т. к. это требуется выше. Это будет функция $b \mapsto F(\varphi)(b, c)$, т. е. $b \mapsto \varphi(c)(b)$, т. е. просто $\varphi(c)$.

Простите, а почему? Мы применяем $G$ к $F$ и переводим только $c$ ($b$ не "добавляем"). Получается, что $c \rightarrow \varphi(c)$, а почему это равно $\varphi$? Функция, переводящая $c$ в $\varphi$ - это $f$, или я что-то не так понял?

[arseniiv]

Ага, всё-таки с пониманием обозначений бяда, значит. Извините, сегодня именно я уже не отвечу.

[Manticore]

Сейчас попробовал ещё раз перечитать всё, что мне здесь пытались объяснить.
$F: (A^B)^C \to A^{B\times C}$
$G: A^{B\times C} \to (A^B)^C$

Дальше вот что: $\varphi$ - это функция, при помощи которой мы получаем $\varphi(b)(c)$. Значит, применяя к ней $F$, получаем:
$F(\varphi): \varphi(b)(c) \to (b,c)$
Применяем к этому $G$:
$G(F(\varphi)): (b,c) \to \varphi(b)(c)$

Может, это уже ближе?

Ах да, насчёт обозначений - я правда очень плохо пока в них ориентируюсь. Но понимаю так: $f: X \to Y$ - функция переводит $X$ в $Y$ и $dom(f)=X$, а $rng(f)=Y$
А $f: X \mapsto Y$ значит, что $dom(f)=X, rng(f)= \lbrace f(x) : x \in X \rbrace$
Поправьте, пожалуйста, у кого нервы выдерживают.