Счётность множества слов конечного алфавита

[Woland]

Введём следующие определения:
1.Массивом M длины k , для алфавита мощности |A|=n, называется упорядочное множество, содержащее $n^k$ различных элементов, каждый из которых является упорядоченным набором из k элементов т.е. s= <a1,a2,..,ak>
Например:
Пусть A={0,1}, тогда массивом длины 1 будет множество:
M1=<<0>,<1>>
Длины 2 .множество:
M2=<<0,0>,<0,1>,<1,0>,<1,1>>
и т.д.
Замечание1: массив длины k обладает свойством полноты, проявляемой в том, что
какую бы упорядоченную цепочку <a1,a2,..,ak> мы не взяли она с необходимостью входит в Mk. И наоборот- цепочками из массива Mk исчерпываются все возможные варианты таких цепочек.

Замечание2: Если число k конечно то и число |M1|+|M2|+..+|M(k-1)| +|Mk|-конечно,оно
равно $ 2^k+2$. По этому, для того что бы множество было счётным (т..е содержало
бесконечное множество элементов), необходимо чтобы и число k было бесконечным
т.е что бы рассматривались и цепочки s= <a1,a2,…..> (бесконечной длины или содержащие столько же мест
сколько и чисел в натуральном ряду).

Теорема.
Множество точек интервала ---счётно.
Доказательство
Так как существует биекция между A2 и Aq (A- обозначает систему счисления), то
достаточно будет доказать, счётность $ (0,1)^w$.

Доказательство будет получатся из того, что с одной стороны (согласно теореме
о лексикографической сортировке) множество двоичных последовательностей
счетно , а с другой согласно замечанию2 последовательностями s= <a1,a2,…..>,
вообще, исчерпывается все возможные двоичные последовательности, т.е.
весь интервал.

1.Согласно замечанию1, массивом длины k исчерпываются все возможные цепочки длины k.
2.Тогда массивом $ M_{k+1}=M_k\cup (0,1) =(<a1,a2,..,ak,0> \cup <a1,a2,..,ak,1>) $ исчерпываются все возможные цепочки длины k+1. Но тогда (чтоб такое
не было натуральным рядом)это положение остаётся верным- решительно для всех его значений т.е все места в кортеже <a1,a2,....> получаются занятыми, так как задействованны одновременно все элементы натурального ряда.Но кроме цепочек <a1,a2,....> не каких других нет и быть не может. Значит мы за нумеровали интервал.

P.s
Это противоречит известным фактам, а значит -глупость.
Однако я не как не могу выбраться из этого тупика.
Помогите пожайлуста.

[nworm]

Woland писал(а):

Замечание2: Если число k конечно то и число |M1|+|M2|+..+|M(k-1)| +|Mk|-конечно,оно
равно $ 2^k+2$. По этому, для того что бы множество было счётным (т..е содержало
бесконечное множество элементов), необходимо чтобы и число k было бесконечным
т.е что бы рассматривались и цепочки s= <a1,a2,…..> (бесконечной длины или содержащие столько же мест
сколько и чисел в натуральном ряду).

Нет. Итоговое множество ($\cup _{k=1}^{\infty}Mk$) представляет собой бесконечное множество конечных элементов. Вдумайтесь: мощность итогового множества больше мощности любого конечного множества.

[bot]

Суть заблуждений Woland'а как мне кажется состоит в том,
что он считает бесконечные последовательности элементами этого объединения.

[незваный гость]

Woland писал(а):

Если число k конечно то и число |M1|+|M2|+..+|M(k-1)| +|Mk|-конечно,оно
равно $ 2^k+2$.

Тут одна недоговорка и одна ошибка. Недоговорка в том, что мы плавно (через пример) перешли от афавита произвольной длины $n$ в алфавит $\{0,1\}$. Ошибка в том, что количество слов длина строго меньшей $k$ равно $2^k-2$.

Замечание *1. Количество слов конечной длины бесконечно при непустом алфавите.
Доказаельство Рассмотрим $w_k = \underbrace{a ... a}\limits_{k \ \text{раз}}, a \in A$. Все эти слова различны, поскольку имеют разную длину. Следовательно, их число бесконечно.

Замечание *2.Множество слов в конечном алфавите по крайней мере счетно.
Доказаельство Пусть $L$ -- множество всех слов в конечном алфавите. Тогда $ {w_k} \subset L$. Следовательно $|N| = |{w_k}| \leqslant |L|$

[Woland]

незваный гость писал(а):

:evil:
Замечание *1. Количество слов конечной длины бесконечно при непустом алфавите.
Доказаельство Рассмотрим $w_k = \underbrace{a ... a}\limits_{k \ \text{раз}}, a \in A$. Все эти слова различны, поскольку имеют разную длину. Следовательно, их число бесконечно.

Я понимаю это.
Но ,чтобы записать слово
длины 1 нужен кортеж длины 1;
длины 2 нужен кортеж длины 2;
…….
длины n нужен кортеж длины n;

Поэтому, если мы имеем кортеж максимальной длины, скажем k т.е.s=<a,a,..,a>
(а взято k раз),то мы можем записать лишь, k различных слов. Т.е. не исчерпаем
весь натуральный ряд.(что, необходимо для счётности множества). Но так как по предположению наше
множество счётно, то и количество мест в кортеже .s=<a,a,..,a> должно быть счётно,т.е должно содержать бесконечное множество мест.

[незваный гость]

Woland писал(а):

Поэтому, если мы имеем кортеж максимальной длины

Конечность каждого слова не означает ограничения на остальные слова. Поэтому непонятно, почему Вы рассматриваете максимальную длину. Для каждого слова длины $k$ мы можем рассмотреть слово длины $k+1$ -- принадлежащее нашему множеству.

Woland писал(а):

Но так как по предположению наше множество счётно

Мы не высказывали нигде такого предположения. Мы построили бесконечное множество слов $w_k$ с очевидной его биекцией в натуральный ряд.

~~~~~~~~~~

Позвольте общее наблюдение. Ваши высказывания трудно прочитать правильно, поскольку Вы употребляете неспецифичные термины (множество, слово, функция, и т.п.). Естественный вопрос, возникающий у читателя -- какое именно множество, какой именно алфавит, какое именно слово Вы имеете в виду? Если вы будете последовательно вводить и использовать обозначения (например, $M_k$ -- множество слов длины $k$ в алфавите $A$, далее писать не "рассмотрим множество", а "рассмотрим множество $M_k$") и Вам и нам будет проще разобраться в Ваших вопросах.

[Woland]

незваный гость писал(а):

~~~~~~~~~~

Позвольте общее наблюдение. Ваши высказывания трудно прочитать правильно, поскольку Вы употребляете неспецифичные термины (множество, слово, функция, и т.п.). Естественный вопрос, возникающий у читателя -- какое именно множество, какой именно алфавит, какое именно слово Вы имеете в виду? Если вы будете последовательно вводить и использовать обозначения (например, -- множество слов длины в алфавите , далее писать не "рассмотрим множество", а "рассмотрим множество ") и Вам и нам будет проще разобраться в Ваших вопросах.

Здесь и далее используется следующая терминология:
Множество,функция,счётность,биекция,декартово произведение-в их обычном смысле.

Слово- тоже,что кортеж т.е. любой элемент декартова произведения n множеств
$A\times A \times ... \times A$ (A записанно n раз),слово обычно обозначается для кратости $S_k $ ,где k означает длину слова,или просто S если понятно о какой длине идёт речь.

Массив -кортеж кортежей или матрица, он состоит из тех же элементов из которых
состоит и декартово произведение множеств $A\times A \times ... \times A$(Aзаписанно n раз), но только взятых не в любом а в строгом порядке. И обозначается $M_n$, где n- количество множеств в произведении $A\times A \times ... \times A$ , или что тоже самое количество мест в кортеже <a1,a2,..,an>.

Алфавит- это двух элементное множество. Его буквами являются символы "0" и "1".
Алфавит обозначается буквой А. На образование слов не каких ограничений не накладывается.

Цепочка -тоже, что кортеж, но только без уточнения того -Сколько в этом кортеже
мест, конечно или бесконечно.

Символом $(0,1)^w$ обозначается множество всех возможных цепочек.

незваный гость писал(а):

Конечность каждого слова не означает ограничения на остальные слова. Поэтому непонятно, почему Вы рассматриваете максимальную длину. Для каждого слова длины k мы можем рассмотреть слово длины k+1 принадлежащее нашему множеству.

C ростом k количество мест в кортеже <a1,a2,..,ak> -растёт, но поскольку не каким
конечным k натуральный ряд исчерпан быть не может и конечность k автоматически
влечёт и конечность |M1|+|M2|+..+|M(k-1)| +|Mk|(конечность мощности всех слов
алфавита А) , то для того что бы множество |M1|+|M2|+..+|M(k-1)| +|Mk|-было счётным т.е содержало бы столько же элементов сколько чисел в натуральном ряду (а их бесконечно) необходимо ,чтобы и k было бесконечным ,но тогда в цепочке <a1,a2,..> содержится бесконечное количество мест.

[Trueman]

Woland писал(а):

...
C ростом k количество мест в кортеже <a1,a2,..,ak> -растёт, но поскольку не каким
конечным k натуральный ряд исчерпан быть не может и конечность k автоматически
влечёт и конечность |M1|+|M2|+..+|M(k-1)| +|Mk|(конечность мощности всех слов
алфавита А) , то для того что бы множество |M1|+|M2|+..+|M(k-1)| +|Mk|-было счётным т.е содержало бы столько же элементов сколько чисел в натуральном ряду (а их бесконечно) необходимо ,чтобы и k было бесконечным ,но тогда в цепочке <a1,a2,..> содержится бесконечное количество мест.

Может вам поможет такое утверждение.
Рассмотрим множество А* - множество всех слов конечной длины, алфавита А={0,1}. Предположим, что оно конечно, если А* - конечное множество, то найдётся хотябы одно слово наибольшей длины, пусть это слово s имеет длину один децилион , тогда рассмотрим слово s+1 (+ это конкатенация), оно имеет конечную длину равную один децилион прибавить 1, то есть в силу его конечной длины оно лежит в А*, и его длина больше слова s, но по предположению s это слово наибольшей длины, получили противоречие, откуда получаем множество слов конечной длины само бесконечно, хотя ни одного слова бесконечной длины там нет.[/math]

[Someone]

Woland писал(а):

C ростом k количество мест в кортеже <a1,a2,..,ak> -растёт, но поскольку не каким
конечным k натуральный ряд исчерпан быть не может и конечность k автоматически
влечёт и конечность |M1|+|M2|+..+|M(k-1)| +|Mk|(конечность мощности всех слов
алфавита А) , то для того что бы множество |M1|+|M2|+..+|M(k-1)| +|Mk|-было счётным т.е содержало бы столько же элементов сколько чисел в натуральном ряду (а их бесконечно) необходимо ,чтобы и k было бесконечным ,но тогда в цепочке <a1,a2,..> содержится бесконечное количество мест.

Явно путаете конечность и ограниченность. Здесь длина слова $k$ конечна, но ничем не ограничена. Когда Вы подсчитываете число слов длины, не превосходящей некоторого $k$, Вы ограничиваете длину слова этим самым $k$ и суммируете $n^1+n^2+n^3+\dots+n^k=\frac{n(n^k-1)}{n-1}$ ($n$ - число букв в алфавите; иногда бывает полезно использовать пустое слово, не содержащее ни одного символа, тогда к указанному числу нужно прибавить ещё $1$), получая тем самым конечную величину. Однако Вы же не учитываете при этом слова, длина которых больше $k$.