Счетность множества всех убывающих функций.

[webaib]

Нужно доказать счетность такого множества. Теоретически достаточно указать характеристическую функцию для ТМ, но как она будет работать, когда функции определены на бесконечности. С инъективностью (биективностью) к N тоже не понятно как должно выглядеть?

[venco]

По моему вы пропустили два важных условия - область определения и область значений функций.
Если оба множества - натуральные числа, то счётность можно доказать.
Если же действителные числа, то множество такий функций - несчётно.

[Maslov]

venco в сообщении #271733 писал(а):

Если оба множества - натуральные числа, то счётность можно доказать.

Мне почему-то кажется, что если оба множества -- $\mathbb{N}$, то таких функций вообще нет. Речь же идёт о строгом убывании.

[webaib]

Нет, не строгое, иначе я бы указал. А область определения\значения N или задача теряет смысл, потому как мы знаем что множество R несчетно. Можно ли составить таблицу, аки Канторовская для рациональных, в которой строка - это одна функция с различными аргументами - т.б. счетное множество. Столбцы - это множество всех таких функций - т.б. тоже счетное и их объединение тоже счетно.

[Профессор Снэйп]

Множество $\{ f : \mathbb{N} \to \mathbb{N} \,|\, f(0) \geqslant f(1) \geqslant f(2) \geqslant \ldots \}$ действительно счётно. Для каждой функции $f$ из этого множества существует число $t_f \in \mathbb{N}$, такое что $f(t) = f(t_f)$ для всех $t \geqslant t_f$. В связи с этим функция полностью задаётся набором натуральных чисел $\langle f(0), f(1), \ldots, f(t_f) \rangle$. А множество, состоящее из конечных наборов натуральных чисел, счётно.

[webaib]

Профессор Снэйп в сообщении #271746 писал(а):

Множество $\{ f : \mathbb{N} \to \mathbb{N} \,|\, f(0) \geqslant f(1) \geqslant f(2) \geqslant \ldots \}$ действительно счётно. Для каждой функции $f$ из этого множества существует число $t_f \in \mathbb{N}$, такое что $f(t) = f(t_f)$ для всех $t \geqslant t_f$. В связи с этим функция полностью задаётся набором натуральных чисел $\langle f(0), f(1), \ldots, f(t_f) \rangle$. А множество, состоящее из конечных наборов натуральных чисел, счётно.

$t \geqslant t_f$ не $t_f \geqslant t$? Т.б. как я понимаю похоже на то, что я предложил. Каждую такую функцию можно однознанчно задать счетным множеством $n \in \mathbb{N}$ чисел, а их объединение тоже счетно. Спасибо.

[Профессор Снэйп]

webaib в сообщении #271762 писал(а):

$t \geqslant t_f$ не $t_f \geqslant t$?

Не понял. У меня всё правильно написано.

[webaib]

Я тогда не понимаю смысла этой записи. Есть функция определенная на множестве натуральных чисел. Эту функцию можно однозначно определить множеством пар натуральных чисел - (аргумент, значение). В каком случае $f(t) = f(t_f)$ для всех $t \geqslant t_f$ и что это вообще значит?

[Maslov]

webaib в сообщении #271820 писал(а):

В каком случае $f(t) = f(t_f)$ для всех $t \geqslant t_f$ и что это вообще значит?

Это означает, что для каждой убывающей функции $\mathbb{N} \to \mathbb{N}$ существует значение аргумента, начиная с которого значение функции -- константа.

[webaib]

Аааааааа. Теперь понятно, в смысле по записи я тоже понимал что это значит, но вот без пары этих слов как то в голове до конца не втыкалось, что функция определена на N и следовательно когда то должна стать нулем, но не меньше.

[Профессор Снэйп]

webaib в сообщении #271853 писал(а):

следовательно когда то должна стать нулем, но не меньше.

Не обязательно нулём. Константой.

[webaib]

Профессор Снэйп в сообщении #271746 писал(а):

А множество, состоящее из конечных наборов натуральных чисел, счётно.

Объединение конечных множеств счетно разве не только в том случае, когда множество этих множеств тоже счетно? В смысле - действительно ли множество таких функций счетно?

[Профессор Снэйп]

Каждый набор длины $k$ --- это элемент $\mathbb{N}^k$. Всего наборов длины $k$ счётное число. А множество всех наборов конечной длины получается равным $\bigcup_{k \in \mathbb{N}} \mathbb{N}^k$. Объединение счётного числа счётных множеств счётно.

Далее, каждой нестрого убывающей функции из $\mathbb{N}$ в $\mathbb{N}$ сопоставляется конечный набор натуральных чисел указанным выше способом. Разных функциям сопоставляются разные наборы, так что количество нестрого убывающих функций не превосходит количества наборов, то есть счётно или конечно. Ясно, что оно бесконечно.

Что здесь непонятного??? Второй день какую-то ерунду пишете, хотя Вам уже абсолютно всё разжевали!

[ewert]

Боюсь, что тут проблема в обозначениях.

Каждая допустимая последовательность кодируется как некоторый конечный набор натуральных чисел: $\{n_1,n_2,\ldots,n_r\}$.

При этом $r$ -- тоже параметр этого набора.

Т.е., строго говоря, следует рассматривать наборы типа $\{r,\;n_1,n_2,\ldots,n_r\}$

Может, так лучше выйдет?...

---------------------------------------
Нет, я понимаю, что объём набора автоматически определяется по нему самому. Но проблема-то в том, что потом надо будет установить биекцию между множеством наборов и натуральным рядом. Так может, логически проще -- предварительно расклассифицировать все наборы по их объёмам?..