Конечная декартова степень счетного множества счетное множ

[khasanov.sm]

Вечер добрый!

В чулане нашел неразрешенный вопрос «Мощность множества» построения биективного отображения $f : X^k \to \mathbb{N}$ конечной декартовой степени счетного множества в множество натуральных чисел.

Предлагаю свой вариант биекции и прошу дать оценку правильности:

По условию дано счетное множество $X$, для которого определена конечная декартова степень $X \times X \times ... \times X = X^k = \left\lbrace (x_1,x_2,...,x_k) | x_i \in X \right\rbrace$. Ввиду того, что $X$ счетно, можем поставить в соответствие элементам $x\in X$ натуральные числа $1,2,...,n,...$ . Определим $f : X^k \to \mathbb{N}$ так, что на первом шаге поставим в соответствие всем элементам $x\in X$ с $x_1 = 1$ натуральные номера по возрастанию . При этом элементу $ (1, 1,1,...,1) $ в соответствие поставим 1, элементу $ (1, 2,1,...,1) \to 2$, $ (1, n,1,...,1) \to n + 1$ и так далее. По завершении первого цикла, приступим к аналогичному процессу для $x\in X$ с $x_1 = 2$. Продолжая описанные итерации, мы тем самым перенумеруем все элементы множества $X^k$, определяя биекцию $f : X^k \to \mathbb{N}$ .

[svv]

khasanov.sm в сообщении #1436504 писал(а):

По завершении первого цикла

А по достижении какого $n$ цикл завершится?

[khasanov.sm]

svv в сообщении #1436508 писал(а):

А по достижении какого $n$ цикл завершится?

А разве нам нужно определять конечно число? Мы просто можем быть уверены, что построенное таким образом отображение $ f: X \to Y $ биективно

[Xaositect]

Поставим вопрос по другому - какой номер будет у элемента $(2, 1, \dots, 1)$?

[Gagarin1968]

khasanov.sm в сообщении #1436519 писал(а):

Мы просто можем быть уверены, что когда-то выполнение алгоритма остановится, так как $ X $ - счетно.

У меня нет такой уверенности, потому что $ X $ бесконечно.

[khasanov.sm]

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

Поставим вопрос по другому - какой номер будет у элемента $(2, 1, \dots, 1)$?

Это будет какое-то натуральное число на единицу большее номера последнего занумерованного элемента из X^k с $ x_1 = 1$

Gagarin1968 в сообщении #1436521 писал(а):

У меня нет такой уверенности, потому что $ X $ бесконечно.

Оно бесконечно, но занумеровать мы его можем в виду его счетности

[Gagarin1968]

khasanov.sm в сообщении #1436522 писал(а):

Оно бесконечно, но занумеровать мы его можем в виду его счетности

Занумеровать-то мы его можем в силу его счётности, а вот выполнение алгоритма не остановится в силу его бесконечности.

[ИСН]

khasanov.sm в сообщении #1436522 писал(а):

Оно бесконечно, но занумеровать мы его можем в виду его счетности

Да, но на этом мы израсходуем все натуральные числа. Какой же номер мы сможем дать элементу (2,1,...,1)?

[khasanov.sm]

Gagarin1968 в сообщении #1436525 писал(а):

Занумеровать-то мы его можем в силу его счётности, а вот выполнение алгоритма не остановится в силу его бесконечности.

А разве есть условие на ограничение по времени выполнения данного процесса?

ИСН в сообщении #1436526 писал(а):

Да, но на этом мы израсходуем все натуральные числа. Какой же номер мы сможем дать элементу (2,1,...,1)?

Вот тут согласен, тем самым биекция "ни о чем"

[mihaild]

khasanov.sm в сообщении #1436530 писал(а):

А разве есть условие на ограничение по времени выполнения данного процесса?

Да, для каждого элемента алгоритм нумерации (если уж нумеруем с помощью алгоритма) должен выдавать его номер за конечное время.

[khasanov.sm]

Рассмотрим другой вариант

Все элементы $x \in X^k$ имеют вид натуральных чисел $x = (x_1, x_2, ..., x_k)$. Построим отображение $f : X^k \to \mathbb{N} $ так, что номер будем присваивать со сдвигом на $\Delta = \underbrace{1...1}_{k-1}0$. Например, $ x = \underbrace{1...1}_{k}0$ перейдет в 1....Тогда мы по представлению $x = (x_1, x_2, ..., x_k)$ можем определить соответствующее ему натуральное число. В обратную сторону тоже верно.

[mihaild]

khasanov.sm в сообщении #1436535 писал(а):

Построим отображение со сдвигом на $\Delta = \underbrace{1...1}_{k-1}0$.

Отображение чего куда? Что значит "отображение со сдвигом"?

[khasanov.sm]

mihaild в сообщении #1436537 писал(а):

Отображение чего куда? Что значит "отображение со сдвигом"?

Дополнил.

[mihaild]

Всё еще ничего не понятно. Опишите, пожалуйста, полностью предлагаемый метод получения числа по кортежу.

[svv]

И, может, для простоты начать с $f: \mathbb N^2\to\mathbb N$ ?

Тем более, если задана биекция $f_2: \mathbb N^2\to\mathbb N$, то дальнейшее можно определить рекурсивно. Например, $f_3: \mathbb N^3\to\mathbb N$ можно задать формулой $f_3(a,b,c):=f_2(f_2(a,b),c)$.