Отождествление по Черчу

[Sinoid]

Здравствуйте! В книге Клини попалось такое место:

И вот я никак не пойму, почему случаи (с) и (е) можно отождествить. Вот смотрите. Рассмотрим пример (е). Там, ИМХО, отображение можно записать так: $x_{i}\mapsto\{\varphi(x_{i},\, y_{1}),\,\varphi(x_{i},\, y_{2}),\ldots\}$, т.е. каждой 1-ке изменяющихся аргументов соответствует не число (см. пример употребления слова "число" в пункте а) ), а множество функций (я ведь правильно понимаю?), в то время как в (с) каждой двойке $(x_{i},\, y_{i})$ изменяющихся переменных будет соответствовать уже число. Так а тогда по каким соображениям можно отождествить эти случаи?

[arseniiv]

Sinoid в сообщении #1177334 писал(а):

а множество функций (я ведь правильно понимаю?)

Нет, не множество. Пусть $f\colon X\times Y\to Z$. Тогда $\lambda y.f(x,y)$, что в теоретико-множественном контексте эквивалентно часто использующейся записи $y\mapsto f(x, y)$ — а более точно с указанием области изменения переменных $\lambda y\in Y.f(x,y)\equiv (y\in Y)\mapsto f(x, y)$ (так заодно можно её ограничить; и вообще область значений получаемой функции может быть тоже неясна и её тоже может быть нужно уточнять) — это функция $Y\to Z$, зависящая от $x$, а вот $\lambda x.\lambda y.f(x,y)\colon X\to(Y\to Z)$, где $Y\to Z\equiv Z^Y$ — множество всех функций из $Y$ в $Z$.

Отождествляют функции $f\colon X\times Y\to Z$ и функции $g\colon X\to(Y\to Z)$ не потому что эти множества равны, а потому что между ними есть биекция (каррирование/карринг, currying, в честь Карри):

$$\begin{array}{rcl} \mathop{\mathsf{curry}}f & = & x\mapsto y\mapsto f(x,y), \\ \mathop{\mathsf{uncurry}}g & = & (x, y)\mapsto g(x)(y) \end{array}$$

Я могу записать их теоретико-множественно.

[Sinoid]

Sinoid в сообщении #1177334 писал(а):

т.е. каждой 1-ке изменяющихся аргументов соответствует не число (см. пример употребления слова "число" в пункте а) ), а множество функций

Я имел ввиду не множество функций, а множество чисел. Я там просто имел ввиду первое отображение, еще до второго. По ходу я имел ввиду, выражаясь вашим языком, $Y\to(X\to Z)$. Рассуждение до конца не довел. Ведь и тут

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

функции $g\colon X\to(Y\to Z)$

во внутренней скобке каждое $y_0 \in Y$ отображается не на единственное число множества $Z$, а на целое их семейство. А вот тут

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

$$\begin{array}{rcl} \mathop{\mathsf{curry}}f & = & x\mapsto y\mapsto f(x,y), \\ \mathop{\mathsf{uncurry}}g & = & (x, y)\mapsto g(x)(y) \end{array}$$

в правой части первой строки разве не нужны скобки, указывающие порядок отображений, или он оговорен заранее?

[arseniiv]

Я понял только последнее, и там порядок всегда такой же как у аргументов.

Sinoid в сообщении #1177835 писал(а):

во внутренней скобке каждое $y_0 \in Y$ отображается не на единственное число множества $Z$, а на целое их семейство

Зачем? Чтобы отображаться на семейство, нужна функция $Y\to\mathcal Z,\mathcal Z\subset2^Z$.

[Sinoid]

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

Я понял только последнее, и там порядок всегда такой же как у аргументов.

Я имел ввиду вот что.

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

$\lambda x.\lambda y.f(x,y)\colon X\to(Y\to Z)$

я воспринимал это так, что элементы множества $X$ есть во внутренней скобке

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

а вот $\lambda x.\lambda y.f(x,y)\colon X\to(Y\to Z)$,

Так это тут каждый $x \in X$ будет переходить в некоторую функцию $Z_{x}(y)$ и на этом этапе имеет место случай (b)?

[arseniiv]

Давайте я лучше возьму конкретный пример. Пусть $f\colon\mathbb N^2\to\mathbb N$, $f(x, y) = x + y$. Значит, график

$$\Gamma f = \{(x, y, x+y) : x,y\in\mathbb N\} = \{(0,0,0), (1,0,1), (0,1,1), (2,0,2), (1,1,2), \ldots\}.$$

Теперь возьмём функцию $g=\mathop{\mathsf{curry}}f\colon\mathbb N\to\mathbb N\to\mathbb N$. Её графиком будет

$$\Gamma g = \{(x, h) : x\in\mathbb N, h=y\mapsto x+y\} = \{(0, (\mathbb N,\mathbb N,\Gamma_0)),(1, (\mathbb N,\mathbb N,\Gamma_1)),(2, (\mathbb N,\mathbb N,\Gamma_2)),\ldots\},$$

где $\Gamma_a = \{(0,a),(1,a+1),(2,a+2),(3,a+3),\ldots\}$.

Я не понимаю, как можно говорить о том, что

Sinoid в сообщении #1178058 писал(а):

элементы множества $X$ есть во внутренней скобке

$Y\to Z$ — это множество функций из $Y$ в $Z$, в каком смысле там могут содержаться элементы $X$?

Sinoid в сообщении #1178058 писал(а):

Так это тут каждый $x \in X$ будет переходить в некоторую функцию $Z_{x}(y)$ и на этом этапе имеет место случай (b)?

Да, только не (b), потому что $Z_x = y\mapsto f(x,y)$, а в случае (b) фигурирует функция $x\mapsto f(x,y)$.

[Sinoid]

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

$$\Gamma g = \{(x, h) : x\in\mathbb N, h=y\mapsto x+y\} = \{(0, (\mathbb N,\mathbb N,\Gamma_0)),(1, (\mathbb N,\mathbb N,\Gamma_1)),(2, (\mathbb N,\mathbb N,\Gamma_2)),\ldots\},$$

Конечно, пока трудно представимый график. Но... Вот смотрите.

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

$\lambda x.\lambda y.f(x,y)\colon X\to(Y\to Z)$, где $Y\to Z\equiv Z^Y$ — множество всех функций из $Y$ в $Z$.

Давайте я все поэтапно распишу. Вы же тут употребили слово всех потому что $f$ - функция общая, безликая? А для конкретной функции $f$ и отображение функция, стоящая вот здесь

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

вот ... $X\to(Y\to Z)$

в скобках будет единственным? Если это так, то пусть в примере с) при изменяющихся $i$ и $j$ будет $\phi(x_{i},\, y_{j})=z_{ij}$. Функцию я ведь могу задать и просто записью соответствия, таблично. Тогда, если $x_i$- произвольный элемент множества $X$, то определяю функцию $z_i (y)$ ( $Y \to Z$ ) как функцию, которая при $y=y_i$ принимает значение $z_{ij}$. Теперь, я точно так же, перечислением могу задать функцию, соответствие, в котором $x_i$- произвольному элементу множества $X$, будет соответствовать функция $z_i (y)$ и тогда аналогия с примером (с) проявится, так сказать, на втором этапе, когда я, после выбора $x_i$ вдруг вздумаю найти $z_i (y_j)$. Верно?

[arseniiv]

Sinoid в сообщении #1178160 писал(а):

А для конкретной функции $f$ и отображение функция, стоящая вот здесь <…> в скобках будет единственным?

Нет, конечно, не обязательно. Одна и та же $y\mapsto f(x,y)$ будет тогда и только тогда, когда она не зависит от $x$, т. е. когда $f$ не зависит от первого аргумента. В частности, в моём примере все функции $h_a = (\mathbb N,\mathbb N,\Gamma_a)$ для разных $a$ различны, а их множество $\{h_a : a\in\mathbb N\}\subset(\mathbb N\to\mathbb N)$ счётно.

[Sinoid]

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

Одна и та же $y\mapsto f(x,y)$

я имел ввиду при постоянном $x$. Для конкретной функции

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

Пусть $f\colon X\times Y\to Z$

при конкретном $x$ функция

Sinoid в сообщении #1178160 писал(а):

то определяю функцию $z_i (y)$ ( $Y \to Z$ ) как функцию, которая при $y=y_i$ принимает значение $z_{ij}$.

(вот тут у меня косяк, надо было "определяю функцию $z_i (y)$ ( $Y \to Z$ ) как функцию, которая при $y=y_j$ принимает значение $z_{ij}$") единственна. При изменении же $x$ меняется и сам вид, таблица зависимости $z$ от $y$. Теперь аналогия между

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

$f\colon X\times Y\to Z$.

и

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

$\lambda x.\lambda y.f(x,y)$

допустима в такой форме?

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

функции $h_a = (\mathbb N,\mathbb N,\Gamma_a)$

честно говоря, не понимаю, что это такое

[arseniiv]

Sinoid в сообщении #1178313 писал(а):

я имел ввиду при постоянном $x$

При постоянном $x$ функция $y\mapsto f(x, y)$, конечно, одна-единственная, да.

Sinoid в сообщении #1178313 писал(а):

честно говоря, не понимаю, что это такое

Функция в обычном определении — это тройка (область определения, область значений, график). В контексте этого определения $f\colon A\to B$ значит $\exists\Gamma(\Gamma\subset A\times B\wedge\mathop{\text{функционально}}(\Gamma)\wedge\operatorname{dom}\Gamma = A\wedge f = (A, B, \Gamma))$, а если добавить к этому определение $f(x) = e$ или $f=x\mapsto e$, то значит уже целое $f = (A, B, \{(x, e) : x\in A\})$.

$\mathop{\text{функционально}}(\Gamma)$ означает, что $\Gamma$ — функциональное отношение, т. е. $\forall x\forall y'\forall y''((x,y')\in\Gamma\wedge(x,y'')\in\Gamma\to y'=y'')$;
$\operatorname{dom}\Gamma = \{x : \exists y((x,y)\in\Gamma)\}$.

-- Пн дек 19, 2016 21:34:39 --

Ещё, если вам нетрудно, перезадайте вопрос заново, а то я лично уже не понимаю, в чём он состоит.

-- Пн дек 19, 2016 21:41:01 --

UPD: Внёс критические дополнения.

-- Пн дек 19, 2016 21:43:27 --

UPD2: Ну теперь-то уже всё.

[Sinoid]

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

Ещё, если вам нетрудно, перезадайте вопрос заново, а то я лично уже не понимаю, в чём он состоит.

Я пытался установить хотя бы одно аналогию между конкретной функцией

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

$f\colon X\times Y\to Z$.

и опять-таки конкретной функцией

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

$\lambda x.\lambda y.f(x,y)\colon X\to(Y\to Z)$,

для этого если при произвольных $x_i \in X$, $y_j \in Y$ конкретная функция

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

$f\colon X\times Y\to Z$.

принимает значение $f(x_i,\,y_j)=z_{ij}$, то для каждого $x_i \in X$ я вводил функцию с областью определения $Y$ и областью значений $Z$:

Sinoid в сообщении #1178313 писал(а):

"определяю функцию $z_i (y)$ ( $Y \to Z$ ) как функцию, которая при $y=y_j$ принимает значение $z_{ij}$")

Да, для разных $x_i$ функция $z_i (y)$ своя, но она

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

При постоянном $x$ функция $y\mapsto f(x, y)$, конечно, одна-единственная, да.

и, значит, соответствие $x_i \to z_i (y)$ (при переменном $x_i \in X$) будет функцией. И тогда значение функции $z_i (y)$, соответствующей $x_i$, при $y=y_j$ будет в точности равно $z_{ij}$- значению функции

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

Пусть $f\colon X\times Y\to Z$

при $x=x_i$, $y=y_j$. И нам удалось построить хотя бы один пример искомой аналогии.

[arseniiv]

Спасибо, кажется, понял. Функции $\mathsf{curry}, \mathsf{uncurry}$ как раз одну такую функцию переводят в таком смысле аналогичную ей: если $f(x,y) = z$, то $\operatorname{\mathsf{curry}}(f)(x)(y) = z$, и наоборот, если $g(x)(y) = z$, то $\operatorname{\mathsf{uncurry}}(g)(x,y) = z$.

[Sinoid]

Sinoid в сообщении #1178429 писал(а):

$f(x_i,\,y_j)=z_{ij}$,

$z_{ij}$ - это те же $z$, что и

Sinoid в сообщении #1178160 писал(а):

$\phi(x_{i},\, y_{j})=z_{ij}$.

просто, раз уж функцию стали обозначать через букву $f$, я их и переопределил.

-- 19.12.2016, 23:01 --

Немного опоздал, но для полноты картины пусть будет.

[Sinoid]

Спасибо.