Доказательство теоремы

[popique]

Для $x, y \in N$

$J(x,y)=\binom{x+y+1}{2}+x$.

Теорема: функция $J$ взаимно однозначно отображает множество $N \times N$ на $N$.

Доказательство. Пусть $J(x,y) = J(a,b)$. Покажем сначала, что $x=a$. Если бы было $x>a$, т.е. $x=a+r, r>0$, то мы имели бы

$\binom{a+r+y+1}{2}+a+r = \binom{a+b+1}{2}$.

Вот здесь я совершенно не понял как из левой части получилась правая. Куда, в том числе, делся хвост левой части $a+r$? Правильно ли я понимаю, что число два условно является слагаемым или множителем или делителем и т.д., то есть конкретная его функция не обозначена намеренно? Прошу тех, кто знает объяснить.

Еще я не уловил в чем суть отображения $N \times N$ на $N$, помимо того, что это как я понял является замкнутой операцией.

[Xaositect]

popique в сообщении #1461586 писал(а):

Доказательство. Пусть $J(x,y) = J(a,b)$. Покажем сначала, что $x=a$. Если бы было $x>a$, т.е. $x=a+r, r>0$, то мы имели бы

$\binom{a+r+y+1}{2}+a+r = \binom{a+b+1}{2}$.

Тут опечатка: должно быть $\binom{a+r+y+1}{2}+a+r = \binom{a+b+1}{2} + a$. Это расписанное равенство $J(a + r, y) = J(a,b)$.

popique в сообщении #1461586 писал(а):

Правильно ли я понимаю, что число два условно является слагаемым или множителем или делителем и т.д., то есть конкретная его функция не обозначена намеренно?

Обозначение $\binom{n}{k}$ - это биномиальный коэффициент, $\binom{n}{k} = \frac{n!}{k! (n-k)!}$. В частности, $\binom{n}{2} = \frac{n(n-1)}{2}$.

[arseniiv]

popique в сообщении #1461586 писал(а):

Еще я не уловил в чем суть отображения $N \times N$ на $N$, помимо того, что это как я понял является замкнутой операцией.

Не знаю, что для вас означает «суть», но польза от такой функции в том, что она биективна и позволяет в конечном итоге кодировать произвольные последовательности натуральных чисел одним натуральным числом. Обычно пример такой функции и проходят в курсе, где это понадобится, и неужели ничего про её будущее использование там не написали?

[Someone]

popique в сообщении #1461586 писал(а):

Для $x, y \in N$

$J(x,y)=\binom{x+y+1}{2}+x$.

Теорема: функция $J$ взаимно однозначно отображает множество $N \times N$ на $N$.

Что-то здесь не так. У Вас натуральный ряд начинается с нуля или с единицы?
Если с нуля, то, наверное, должно быть $J(0,0)=0$. А если с единицы — то $J(1,1)=1$. Или соответствующие значения должны получаться для каких-то других натуральных $x$ и $y$. У Вас же этого не получается.

[Утундрий]

Someone в сообщении #1461655 писал(а):

Что-то здесь не так

Построил первую сотню в Ехеле, всё работает. Получается обход по диагоналям.

arseniiv
Кстати, для произвольной размерности просто запускаем "склейку ласт" по произвольно выбраным парам индексов до победы или есть более изящные решения?

[arseniiv]

Да, это обычная канторовская пара (но я тоже на всякий случай проверил в М. ).

-- Вс май 10, 2020 21:26:01 --

(Может показаться, что $\binom{0+0+1}2$ должно быть равно 1 (под влиянием $C_2^1$), но на самом-то деле это 0.)

[denisart]

Утундрий в сообщении #1461657 писал(а):

Кстати, для произвольной размерности просто запускаем "склейку ласт" по произвольно выбраным парам индексов до победы или есть более изящные решения?

Есть обзор этой задачи, например, в лекции М. Всемирного http://www.mathnet.ru/php/presentation.phtml?option_lang=rus&presentid=22941

[arseniiv]

Утундрий в сообщении #1461657 писал(а):

arseniiv
Кстати, для произвольной размерности просто запускаем "склейку ласт" по произвольно выбраным парам индексов до победы или есть более изящные решения?

Не увидел добавления вовремя.

Как раз недавно я наткнулся на довольно приятное решение для всевозможных кортежей разом, сейчас найду пост.

-- Пн май 11, 2020 00:15:51 --

https://dxdy.ru/post1459696.html#p1459696

-- Пн май 11, 2020 00:28:52 --

(Тут конечно надо добавить, что это соответствие уж больно неэкономичное, если подумать хоть о каком-то намёке на применимость в вычислениях: оно предпочитает громаднейшие кортежи небольшим кортежам с большой суммой значений. Увидев это, и то, что творится в двоичной системе, можно вместо унарного кодирования аргументов количеством нулей между единицами начать кодировать аргументы какой-то из кодировок поэкономичнее. При этом соединять и разъединять кортежи будет не сильно уж сложнее, особенно если выражать всё через двоичное (или $b$-ичное) представление чисел какими-то «более строковыми» операциями.)

[Someone]

(Оффтоп)

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

Может показаться, что $\binom{0+0+1}2$ должно быть равно 1 (под влиянием $C_2^1$), но на самом-то деле это 0.

Нет, об этом я помнил. Но всё равно какая-то аберрация возникла.

[popique]

Очень рад, что тема вызвала дискуссию, хоть и небольшую, но мне осталось непонятным алгебраическое преобразование

$\binom{a+r+y+1}{2}+a+r = \binom{a+b+1}{2}$.

Здесь я понимаю, что $x=a+r$ и тогда видимо $b=r+y$? Тогда куда девается хвост $+a+r$? По поводу опечатки не могу сказать, но это выражение присутствует в доказательстве (оно длинное) и дальше.

Также хотелось бы понять интуитивный смысл отображения $N \times N$ на $N$. Прошу прощения за тупость, но я новичок в этом деле.

[Connector]

Мы предполагаем, что $J(x, y)=\binom{x+y+1}{2}+x = J(a, b) = \binom{a+b+1}{2} + a$, и $x \neq a$, а значит $x=a+r, r \neq 0$. Отсюда простой заменой $x$ на $a+r$ получаем
$\binom{a+r+y+1}{2}+a+r = \binom{a+b+1}{2} + a$

[Утундрий]

Да запишите уже по-человечески $J=x+(x+y+1)(x+y)/2$