2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 
Сообщение04.07.2006, 12:38 
Аватара пользователя


28/06/06
138
Введём следующие определения:
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
Это противоречит известным фактам, а значит -глупость.
Однако я не как не могу выбраться из этого тупика.
Помогите пожайлуста.

 Профиль  
                  
 
 
Сообщение04.07.2006, 13:10 


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

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

 Профиль  
                  
 
 
Сообщение04.07.2006, 15:33 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение04.07.2006, 20:31 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
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|$

 Профиль  
                  
 
 
Сообщение04.07.2006, 22:17 
Аватара пользователя


28/06/06
138
незваный гость писал(а):
: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> должно быть счётно,т.е должно содержать бесконечное множество мест.

 Профиль  
                  
 
 
Сообщение04.07.2006, 22:44 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Woland писал(а):
Поэтому, если мы имеем кортеж максимальной длины

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

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

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

~~~~~~~~~~

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

 Профиль  
                  
 
 
Сообщение05.07.2006, 12:18 
Аватара пользователя


28/06/06
138
незваный гость писал(а):
~~~~~~~~~~

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


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

Слово- тоже,что кортеж т.е. любой элемент декартова произведения 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,..> содержится бесконечное количество мест.

 Профиль  
                  
 
 
Сообщение05.07.2006, 13:36 


06/11/05
87
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 имеет длину один децилион :wink: , тогда рассмотрим слово s+1 (+ это конкатенация), оно имеет конечную длину равную один децилион прибавить 1, то есть в силу его конечной длины оно лежит в А*, и его длина больше слова s, но по предположению s это слово наибольшей длины, получили противоречие, откуда получаем множество слов конечной длины само бесконечно, хотя ни одного слова бесконечной длины там нет.[/math]

 Профиль  
                  
 
 
Сообщение05.07.2006, 13:38 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
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$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 24 ]  На страницу Пред.  1, 2

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group