2014 dxdy logo

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

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




На страницу 1, 2  След.
 
 Счётность множества слов конечного алфавита
Сообщение03.07.2006, 21:12 
Аватара пользователя
В одном учебнике прочитал, что множество всех слов любого, конечного алфавита-
счётно. Это доказывается тем, что существует лексикографическая сортировка.

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

Например слово:

S=abaabaaabaaaab….

- охватывается этой биекцией или нет?

 
 
 
 
Сообщение03.07.2006, 21:35 
Аватара пользователя
:evil:
Слово, по определению -- конечная цепочка символов алфавита.

 
 
 
 
Сообщение03.07.2006, 21:50 
Аватара пользователя
Виноват.
Но, если- бы среди всех слов, не нашлось бы не одного ,
содержащего бесконечное количество букв- то мощность
такого множества была бы конечна а не счётна.

 
 
 
 
Сообщение03.07.2006, 22:04 
Аватара пользователя
Пусть алфавит содержит две буквы- "0" и "1"
Тогда множество слов:
длины 1 равно 2
длины 2 равно 4
длины 3 равно 8
длины n равно $2^n$

 
 
 
 
Сообщение03.07.2006, 22:07 
Там считают не только те слова, которые уже где-то написаны, но и те, которые принципиально можно где-то написать.

Сравните: все натуральные числа конечные, а множество натуральных чисел счётное.

 
 
 
 
Сообщение03.07.2006, 22:20 
Аватара пользователя
Цитата:

Там считают не только те слова, которые уже где-то написаны, но и те, которые принципиально можно где-то написать.


То есть, длина слова может рости до бесконечности?
В чём же тогда проблема со словом которое я привёл?
Раз растёт , то вот и до росло до бесконечности.


Цитата:
Сравните: все натуральные числа конечные, а множество натуральных чисел счётное.

Это то, и есть самая заколдованная для меня фраза.
[/quote]

 
 
 
 
Сообщение03.07.2006, 22:27 
Аватара пользователя
Или может быть, длина слова растёт до бесконечности но до неё не
дорастает?

Последнюю фразу, совершенно не могу взять в толк.

 
 
 
 
Сообщение03.07.2006, 22:43 
Аватара пользователя
Ну, попытайтесь представить: есть слова длины $1,2,3,\dots,10,11,\dots,100,\dots,10^{10},\dots,10^{10^{10}},\dots$, а слов бесконечной длины нет.

 
 
 
 
Сообщение03.07.2006, 22:44 
Аватара пользователя
:evil:
Я не понимаю, что именно Вы не понимаете. Разумеется, количество слов любой конечной длины -- конечно. Но количество конечных длин -- бесконечно. Поеэтому и количество слов -- бесконечно.

Вы можете рассматривать натуральные числа как слова в алфавите "0", "1",.."9". Языку принадлежат слова, начинающиеся не с "0". Эта бикеция называется десятичной записью.

 
 
 
 
Сообщение03.07.2006, 22:53 
Woland
Вы понимаете (и принимаете) фразу:
"Множество натуральных чисел счётное"?

 
 
 
 
Сообщение03.07.2006, 23:11 
Аватара пользователя
Меня больше всего тревожит следующее:
Если у нас имеется тетрадь в клетку, и мы выделили некоторое
вподряд идущее количество клеток, скажем n, затем стали вписывать
сюда все возможные, перетасовки из двух букв то мы можем быть
уверенны в том , что получив $2^n различных перетасовок,
мы исчерпаем все возможные варианты. Т.е. можно сказать,что
массив из клеток длины n будет заполнен сплошь. И каждое слово прри этом
будет иметь свой номер.
Но это верно для любого n.
По этому при стремление n бесконечногсти мы должны будем зыполнить сплош
вообще весь,интервал от нуля до еденицы, если отождествим последовательности
0,01101010 с а,abbababa. Но интервал не счётен.

Вот гдето здесь я чегото и не допонимаю.
Чего?

 
 
 
 
Сообщение03.07.2006, 23:22 
Когда n стремиться к бесконечности, число n становиться все больше и больше, но оно остаётся конечным (вместе с Вашим интервалом).

Ответьте, пожалуйста, на мой предыдущий вопрос.

 
 
 
 
Сообщение03.07.2006, 23:46 
Аватара пользователя
nworm спрашивал:
Цитата:
Woland
Вы понимаете (и принимаете) фразу:
"Множество натуральных чисел счётное"?

Я понимаю чётко, что такое биекция. И ,что если множество биективно отражается на некоторое другое множество(называемое натуральным рядом),то оно счётное. Однако ,что такое натуральный ряд, я не вполне понимаю.

А именно:
Что значит фраза: количество чисел в натуральном ряду бесконечно.
Что , такое бесконечность вообще?

 
 
 
 
Сообщение04.07.2006, 00:09 
По определению, S есть бесконечное множество, если оно имеет ту же мощность, что и хотя бы одно из его собственных подмножеств; в противном случае S - конечное множество.

Натуральный ряд имеет ту же мощность, что и ряд чётных чисел.

Про бесконечность вообще ничего сказать не могу, просто не знаю.

 
 
 
 
Сообщение04.07.2006, 01:23 
Woland писал(а):
...
Что значит фраза: количество чисел в натуральном ряду бесконечно.
Что , такое бесконечность вообще?

1. Это значит, что для любого сколь угодно большого конечного натурального числа существует еще большее.

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

 
 
 [ Сообщений: 24 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group