2014 dxdy logo

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

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




На страницу 1, 2, 3, 4  След.
 
 Счетные множества
Сообщение16.02.2016, 22:26 
Аватара пользователя
В интернете говорят, что множества счетны если их можно "пронумеровать".Каким же образом?
По определению множество $F$ счетно, если $F\sim\mathbb{N}$, то есть $f : F \Rightarrow \mathbb{N}$.Каким образом можно составить "правило" $f$ и сколько их?Можете дать совет как находить такие "правила" для доказательства равномощности множеств.Объясняйте ,пожалуйста, не сложным языком, я пока только знакомлюсь с мат. анализом.

 
 
 
 Re: Счетные множества
Сообщение16.02.2016, 22:35 
Аватара пользователя
Например, множество всех слов, составленных из букв русского алфавита, счетно (словом называем любой конечный набор букв, независимо от того, есть ли у него смысл). Нумеруем их так: выписываем в алфавитном порядке сначала все однобуквенные слова, затем все двухбуквенные и т.д.
а - 1
б - 2
....
я - 33
аа - 34
аб - 35
....
ая - 66
ба - 67
....
Таким образом, каждое слово имеет единственный номер, и каждому номеру соответствует единственное слово. Это и есть нужное правило.

 
 
 
 Re: Счетные множества
Сообщение16.02.2016, 22:46 
Аватара пользователя
Anton_Peplov в сообщении #1100002 писал(а):
Например, множество всех слов, составленных из букв русского алфавита, счетно (словом называем любой конечный набор букв, независимо от того, есть ли у него смысл). Нумеруем их так: выписываем в алфавитном порядке сначала все однобуквенные слова, затем все двухбуквенные и т.д.
а - 1
б - 2
....
я - 33
аа - 34
аб - 35
....
ая - 66
ба - 67
....
Таким образом, каждое слово имеет единственный номер, и каждому номеру соответствует единственное слово. Это и есть нужное правило.

А почему не дать такую нумеровку: 1.в 2.ипп 3.ба... или что-то в этом роде?

 
 
 
 Re: Счетные множества
Сообщение16.02.2016, 22:47 
Аватара пользователя
Rusit8800 в сообщении #1099999 писал(а):
множества счетны если их можно "пронумеровать".

Видимо, Вы хотите сказать: их элементы можно "пронумеровать" (не сами множества).
Для этого, по сути, достаточно найти перечисление элементов множества, гарантированно "выдающее" все элементы (желательно без повторений, но это требование не принципиально). И если существует хоть одно такое перечисление, то можно найти и бесконечно много других.
Например, множество целых чисел можно выписать в следующем порядке:
$0,1,-1,2,-2,3,-3...$
Представьте себе, чтоб под каждым элементом этой последовательности мы записали его номер:
$1,2,3,4...$
Тем самым будет построено биективное (взаимно-однозначное) отображение множества целых чисел на множество натуральных чисел, то есть, будет доказана счётность множества целых чисел.
Но общего рецепта для построения подобных отображений нет. Например, счётность множества рациональных чисел доказывается чуть более сложно.
Да, и конечно же, если Вам удастся построить в аналитическом виде (в виде формулы) функцию, которая вычисляет каждый элемент счётного множества по его номеру, это также служит доказательством счётности множества.
Например, для последовательности целых чисел, записанных так, как я указал выше, такую функцию построить несложно.

 
 
 
 Re: Счетные множества
Сообщение16.02.2016, 22:50 
Аватара пользователя
Rusit8800 в сообщении #1100007 писал(а):
Счетные множества бесконечны, а алфавит конечен, поэтому не счетен.
:shock:

 
 
 
 Re: Счетные множества
Сообщение16.02.2016, 22:52 
Аватара пользователя
Rusit8800 в сообщении #1100007 писал(а):
Счетные множества бесконечны, а алфавит конечен, поэтому не счетен.

Rusit8800,
Вы лучше вдумывайтесь в то, что Вам говорят, раз уж просите помощи.
Алфавит конечен, но это не значит, что множество слов в алфавите конечно.
Натуральные числа - это "слова" в "алфавите" из 10 цифр. Разве отсюда следует, что множество натуральных чисел конечно?

 
 
 
 Re: Счетные множества
Сообщение16.02.2016, 22:52 
Аватара пользователя
Есть также полезная теорема, что подмножество счетного множества либо конечно, либо счетно. С помощью этой теоремы можно, например, сразу сказать, что множество всех натуральных чисел, делящихся на три, счетно. Впрочем, и указать правило для их нумерации тоже легко:
3 - первое число
6 - второе число
9 - третье число
...

Есть не менее полезная теорема: если взять конечную или счетную систему множеств $A$, $B$, ... и все эти множества объединить, то результат объединения будет снова счетным множеством. С помощью этой теоремы можно, сразу сказать, что множество всех целых чисел счетно. Впрочем, и указать правило для их нумерации, опять же, легко:
0 - первое число
1 - второе число
-1 - третье число
2 - четвертое число
-2 - пятое число...
Можно придумать и другое правило нумерации. Главное, чтобы каждое число за конечное число шагов получило номер. Пытаться перенумеровать сначала все положительные числа, а потом все отрицательные, бессмысленно: ведь положительные никогда не закончатся. Как и в первом примере - с алфавитом - не получится перенумеровать сначала все слова, начинающиеся на "а", потом все слова, начинающиеся на "б" и т.д.

-- 16.02.2016, 22:53 --

gris в сообщении #1100012 писал(а):
Интересно, а сколько различных способов пронумеровать счётное множество? То есть этих самых "правил".
Континуум.

-- 16.02.2016, 22:55 --

Rusit8800 в сообщении #1100007 писал(а):
А почему не дать такую нумеровку: 1.в 2.ипп 3.ба... или что-то в этом роде?
На это я только что отвечал.
Anton_Peplov в сообщении #1100014 писал(а):
Можно придумать и другое правило нумерации. Главное, чтобы каждое число за конечное число шагов получило номер. Пытаться перенумеровать сначала все положительные числа, а потом все отрицательные, бессмысленно: ведь положительные никогда не закончатся. Как и в первом примере - с алфавитом - не получится перенумеровать сначала все слова, начинающиеся на "а", потом все слова, начинающиеся на "б" и т.д.

 
 
 
 Re: Счетные множества
Сообщение16.02.2016, 23:00 
Аватара пользователя
То есть нумерацию нужно составлять так, чтобы получился бесконечный цикл, содержащий все "типы" чисел, например: 0; 1;-1;2;-2 и так далее с увеличением на 1.

 
 
 
 Re: Счетные множества
Сообщение16.02.2016, 23:04 
Аватара пользователя
Допустим нужно доказать счетность множества всех нечетных чисел, составим "бесконечный цикл нумерации": 1;-1;3;-3;5;-5 и т.д.Так доказывать?

 
 
 
 Re: Счетные множества
Сообщение16.02.2016, 23:08 
Аватара пользователя
Rusit8800 в сообщении #1100018 писал(а):
Допустим нужно доказать счетность множества всех нечетных чисел, составим "бесконечный цикл нумерации": 1;-1;3;-3;5;-5 и т.д.Так доказывать?

Вполне можно и так.

 
 
 
 Re: Счетные множества
Сообщение17.02.2016, 16:26 
Аватара пользователя
Ок, следующий вопрос.На mathprofi доказывают счетность рациональности так, что в дроби $\frac{m}{n}$, где $m \in \mathbb{Z}$ и $n \in \mathbb{N}$ $m$ и $n$ принадлежат счетным множествам.
$m$ и $n$ - это только элементы счетных множеств, как можно говорить о счетности элементов?

 
 
 
 Re: Счетные множества
Сообщение17.02.2016, 16:42 
Аватара пользователя
Rusit8800,
очевидно, там подразумевается использование вспомогательного утверждения: если элементы множества определяются двумя значками ("индексами"), каждый из которых пробегает счётное множество значений, то данное множество счётно. Конечно, это утверждение должно быть доказано отдельно.
Но если Вы действительно интересуетесь данным вопросом, попробуйте вначале заглянуть в какой-нибудь подробный учебник матанализа. Например, Л.Д. Кудрявцев, том 1, пункт 4.11. Обнаружите очень понятное доказательство счётности множества рациональных чисел.

 
 
 
 Re: Счетные множества
Сообщение17.02.2016, 16:49 
Аватара пользователя
Mihr в сообщении #1100172 писал(а):
Rusit8800,
очевидно, там подразумевается использование вспомогательного утверждения: если элементы множества определяются двумя значками ("индексами"), каждый из которых пробегает счётное множество значений, то данное множество счётно. Конечно, это утверждение должно быть доказано отдельно.
Но если Вы действительно интересуетесь данным вопросом, попробуйте вначале заглянуть в какой-нибудь подробный учебник матанализа. Например, Л.Д. Кудрявцев, том 1, пункт 4.11. Обнаружите очень понятное доказательство счётности множества рациональных чисел.

Я так понял вы хотите сказать, что если какую-то переменную, которая "подразумевает" из себя счетное множество поделить на аналогичную переменную, то полученное множество будет счетным, не так ли?

 
 
 
 Мощность множества функций и континуум-гипотеза
Сообщение17.02.2016, 17:20 
Аватара пользователя
Rusit8800,
Ваша формулировка мне малопонятна. Ещё раз предлагаю: загляните сначала в учебник. Указанный материал вполне доступен и школьнику.

 
 
 
 Re: Счетные множества
Сообщение17.02.2016, 17:21 
Аватара пользователя
Rusit8800 в сообщении #1100175 писал(а):
если какую-то переменную, которая "подразумевает" из себя счетное множество поделить на аналогичную переменную
- бессмысленный набор слов.

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


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