Слова в конечном алфавите

[oleg.k]

Успенский В.А. "Вводный курс математической логики писал(а):

Пример 3.Пусть дан некоторый алфавит, т.е. набор элементарных знаков, называемых буквами. Конечный ряд букв, написанных друг за другом, называется словом в данном алфавите. Иногда бывает удобно рассматривать также пустое слово, совсем не содержащее букв и обычно обозначаемое $\Lambda$. Если алфавит $A$ конечен, то множество $A^\ast$ всех слов в алфавите $A$ счетно.
Действительно, пусть $A = \{S_1, ... , S_{p-1}\}$ $(p \geqslant 2)$. Определим последовательность $f: \mathbb{N} \to A^\ast$ следующим образом: $f(0) = \Lambda$; если же $x > 0$, то рассмотрим запись числа $x$ в $p$-ичной системе счисления, выпишем в порядке вхождения в нее все "ненулевые" цифры $k_1, ... , k_m (1 \leqslant k_i \leqslant p-1)$ и положим $f(x) = S_{k_i}...S_{k_m}$. Очевидно, что $\rho_f = A^\ast$. А именно, произвольное слово $S_{i_0}...S_{i_n}$ является значением функции $f$ при значении аргумента $i_0p^n + i_1p^{n-1}+...+i_n$.

Зачем так сложно? Пусть есть конечный алфавит $S_1, S_2, ... , S_n$. Возьмем да и начнем выписывать сначала все слова длины 1 (их будет $n^1 = n$ штук), затем все слова длины 2 (их будет $n^2$ штук) и т.д. Слова упорядочены в лексикографическом порядке, взаимно однозначное соответствие между $A^\ast$ и $\mathbb{N}$ очевидно. Где подвох?

-- 03.01.2020, 15:16 --

Upd. Название темы криво написал. Надо - "слова в конечном алфавите".

[Lia]

oleg.k
Ну так исправьте.

[oleg.k]

Да, действительно получилось исправить Я почему-то думал, что название темы нельзя исправить Вобщем, спасибо.

[Connector]

По-моему, подвоха нет, просто Вы описали процедуру построения последовательности, и исходя из построения непросто определить $n$-ный её член для известного $n$ . А В. А. Успенский даёт такое правило.
Так, например, если проанализировать Вашу последовательность, то окажется, что $f((p-1)^{m-1}+...+1)$ есть первое слово длины $m$, то есть $\underbrace{aa...a}_{m \,\ \text{раз}}$, $a=S_1$.

[arseniiv]

Можно придраться к «расписанному» доказательству ещё и тем, что там предполагается, что в алфавите больше одного символа, тогда как и $1^*$ счётно. А вот если использовать не обычные позиционные системы счисления, а т. н. «биективные», то во-первых случай одноэлементного алфавита покрывается, а во-вторых нумерация собственно становится биективной (исходно числа 123, 1203, 100230 и т. д. все дадут одну и ту же строку 123). Пример биективной нумерации натуральных чисел с основанием 2: 1, 2, 11, 12, 21, 22, 111, 112, 121, …; ноль может обозначаться пустой записью. (Кстати говоря унарная система счисления — одна из именно таких; «эксельная система счисления», использующаяся в названиях столбцов — биективная с основанием 26.)

-- Сб янв 04, 2020 00:33:26 --

Ах да, между биективной и обычной системой (в случае основания не меньше 2, когда вторая определена) есть несложное соответствие, при котором в частности записи $a\ldots a$ (одной и той же длины и из одинаковых цифр, присутствующих в обеих системах) обозначают одно и то же число. Ноль позиционной системы достаточно ясно соответствует цифре-основанию биективной через перенос единиц в старшие разряды.

[Connector]

arseniiv, спасибо! В Вашем же сообщении в другой теме нашёл ссылку на статью, посвящённую биективным системам.
Поясните только

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

что там предполагается, что в алфавите больше одного символа

где именно это предполагается? Там ведь $p \geqslant 2$, а длина алфавита равна $p-1$... UPD. Понял. Важнее следующее:

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

(исходно числа 123, 1203, 100230 и т. д. все дадут одну и ту же строку 123).

действительно; я тоже подумал, что таким образом мы докажем только, что множество слов в алфавите не более чем счётно (понятно, что оно и не менее чем счётно, но это придётся доказывать отдельно — хоть и совсем несложно).

[arseniiv]

Connector в сообщении #1433333 писал(а):

Там ведь $p \geqslant 2$, а длина алфавита равна $p-1$...

А, ну это я балда конечно.