Счетные множества

[Rusit8800]

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

[Anton_Peplov]

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

[Rusit8800]

Anton_Peplov в сообщении #1100002 писал(а):

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

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

[Mihr]

Rusit8800 в сообщении #1099999 писал(а):

множества счетны если их можно "пронумеровать".

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

[Dan B-Yallay]

Rusit8800 в сообщении #1100007 писал(а):

Счетные множества бесконечны, а алфавит конечен, поэтому не счетен.

[Mihr]

Rusit8800 в сообщении #1100007 писал(а):

Счетные множества бесконечны, а алфавит конечен, поэтому не счетен.

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

[Anton_Peplov]

Есть также полезная теорема, что подмножество счетного множества либо конечно, либо счетно. С помощью этой теоремы можно, например, сразу сказать, что множество всех натуральных чисел, делящихся на три, счетно. Впрочем, и указать правило для их нумерации тоже легко:
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 писал(а):

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

[Rusit8800]

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

[Rusit8800]

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

[Mihr]

Rusit8800 в сообщении #1100018 писал(а):

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

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

[Rusit8800]

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

[Mihr]

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

[Rusit8800]

Mihr в сообщении #1100172 писал(а):

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

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

[Mihr]

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

[Brukvalub]

Rusit8800 в сообщении #1100175 писал(а):

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

- бессмысленный набор слов.