Что такое счетное множество

Счётное множество

В теории множеств, счётное мно́жество есть бесконечное множество, элементы которого возможно пронумеровать натуральными числами. Более формально: множество является счётным, если существует биекция » width=»» height=»» /> обозначает множество всех натуральных чисел. Другими словами, счётное множество — это множество, равномощное множеству натуральных чисел.

Счётное множество является «наименьшим» бесконечным множеством, то есть в любом бесконечном множестве найдётся счётное подмножество. Мощность множества всех натуральных чисел обозначается символом (произносится: «алеф-нуль»).

Свойства

1. Любое подмножество счётного множества не более чем счётно (т.е. конечно или счётно). [1]
2. Объединение конечного или счётного числа счётных множеств счётно. [1]
3. Прямое произведение конечного числа счётных множеств счётно.
4. Множество всех конечных подмножеств счётного множества счётно.
5. Множество всех подмножеств счётного множества континуально и, в частности, не является счётным.

Связанные понятия

Несчётное множество — такое бесконечное множество, которое не является счётным. Таким образом, любое множество является либо конечным, либо счётным, либо несчётным.

Примеры

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

• Простые числа
• Натуральные числа
• Целые числа
• Рациональные числа
• Алгебраические числа
• Кольцо периодов
• Вычислимые числа
• Арифметические числа
• Множество всех конечных слов над конечным или счётным алфавитом
• Любое бесконечное семейство непересекающихся открытых интервалов на действительной оси
• Множество всех прямых на плоскости, каждая из которых содержит хотя бы 2 точки с рациональными координатами
• Любое бесконечное множество точек на плоскости, все попарные расстояния между элементами которого рациональны

Несчётные множества

• Вещественные числа
• Комплексные числа
• Числа Кэли

Примечания

1. ↑ 12В. А. Ильин , В. А. Садовничий , Бл. Х. Сендов . Глава 2. Вещественные числа // Математический анализ / Под ред. А. Н. Тихонова . — 3-е изд. , перераб. и доп. — М .: Проспект, 2006. — Т. 1. — С. 62 — 63. — 672 с. — ISBN 5-482-00445-7

См. также

• Теория множеств

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

Определение. Множество, эквивалентное множеству всех натуральных чисел, называют счетным множеством.

Можно сказать иначе: множество счетно, если все его элементы можно занумеровать всеми натуральными числами.

Всякое бесконечное подмножество счетного множества счетно.

Действительно, пусть дано счетное множество

а — его бесконечное подмножество. Располагая в порядке возрастания номеров все элементы подмножества

можно перенумеровать их заново всеми натуральными числами, взятыми по порядку (в роли нового номера будет выступать индекс . Следовательно, счетно.

Объединение конечной или счетной совокупности счетных множеств есть счетное множество.

Объединением множеств называется множество, состоящее из всех элементов, принадлежащих хотя бы одному из этих множеств, и обозначается через .

Рассмотрим сначала случай конечного числа множеств. Пусть даны счетные множества

Выпишем элементы множеств в виде следующей таблицы:

Теперь перенумеруем заново все элементы этой таблицы, располагая их по столбцам:

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

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

При этом повторяющиеся элементы так же, как и в предыдущем случае, нумеруем по одному разу. Таким образом, все элементы множества могут быть перенумерованы, т.е. множество счетно.

Множество всех рациональных чисел счетно.

Действительно, множество всех рациональных чисел есть объединение следующих счетных множеств:

т.е. . Множества , составляют счетную совокупность счетных множеств. Из 11.3 следует, что их объединение счетно.

Что такое счетное множество

Что такое творческие кладовые по дискретной математике
портала «Русский след»?

Поэзия всей сути чисел
Сравнима с россыпью светил,
Прекрасна как алмазный бисер
Родоначальница мерил. (Ю.Н. Пиллигримов)

7 . Счётные множества, их свойства

Определение. Под множеством А понимается любое собрание определенных и различимых между собой
объектов, представляемых как единое целое. Эти объекты называются элементами множества А.

Существенной деталью является то, что для любого объекта можно установить, принадлежит он
множеству или нет.

Множество задают (специфицируют) двумя способами:

— характеристикой свойств, общих для элементов множества:

А = < X | P ( X )>(А — это множество тех и только тех элементов X для которых P от X истинное предложение).

А- есть множество всех Х, таких, что Х-целое и Х>0 и Х

Если элемент Х принадлежит множеству А, то значит X î A , если не принадлежит, то X ï A . Например, 7 î А, 6 ï А.

Определение. Множества А и В считаются равными, если они состоят из одинаковых элементов. Обозначение: А=В.

То есть элемент не считается равным множеству, если даже множество состоит только из этого элемента.

Таким образом, Под множеством А понимается любое собрание определенных и различимых между собой
объектов, представляемых как единое целое. Эти объекты называются элементами множества А.

Множество задают (специфицируют) двумя способами:

-перечислением: A =;

— характеристикой свойств, общих для элементов множества

2. Мощность множества.

Множества называются равномощными, эквивалентными, если между ними есть взаимно — однозначное или одно-однозначное соответствие , то есть такое попарное соответствие. когда каждому элементу одного множества сопоставляется один-единственный элемент другого множества и наоборот, при этом различным элементам одного множества сопоставляются различные элементы другого.

Например, возьмём группу студентов из тридцати человек и выдадим экзаменационные билеты по одному билету каждому студенту из стопки, содержащей тридцать билетов, такое попарное соответствие из 30 студентов и 30 билетов будет одно-однозначным.

Два множества, равномощные с одним и тем же третьим множеством, равномощны. Если множества M и N равномощны, то и множества всех подмножеств каждого из этих множеств M и N , также равномощны.

Под подмножеством данного множества понимается такое множество, каждый элемент которого является элементом данного множества. Так множество легковых автомобилей и множество грузовых автомобилей будут подмножествами множества автомобилей.

Мощность множества действительных чисел, называют мощностью континуума и обозначают буквой «алеф» א . Наименьшей бесконечной областью является мощность множества натуральных чисел. Мощность множества всех натуральных чисел принято обозначать (алеф-нуль) .

Часто мощности называют кардинальными числами. Это понятие введено немецким математиком Г. Кантором. Если множества обозначают символическими буквами M , N , то кардинальные числа обозначают через m , n . Г.Кантор доказал, что множество всех подмножеств данного множества М имеет мощность большую, чем само множество М.

Множество, равномощное множеству всех натуральных чисел, называется счетным множеством

Счётные множества, их свойства

Множество — равномощное множеству всех натуральных чисел (1, 2,3. n-1) , например множество целых чисел, множество чётных чисел, множество рациональных чисел; все другие бесконечные множества являются несчётными бесконечными множествами. Это означает, что все элементы счётного множества можно перенумеровать, то есть обозначить натуральными числами. Говорят, также, что счётное множество имеет мощность , а всякое множество, равномощное с множеством всех подмножеств какого-нибудь счётного множества, имеет мощность или мощность континуума. Бесконечное множество считается счётным, если можно установить одно-однозначное соответствие между его элементами и натуральными числами. Мощность счётного множества, например, множества простых чисел, меньше мощности любого бесконечного несчётного множества. Отношение между счётным множеством и бесконечным несчётным множеством выражается следующими теоремами:

1) мощность бесконечного множества не изменяется от прибавления к нему счётного множества;

2)мощность несчётного множества не изменяется от удаления из него счётного множества;

3) любое подмножество счётного множества счётно;

4)сумма двух счётных множеств счётна;

5) сумма конечного и счётного множества счётна;

6) если множество А счётно, то множество всех конечных последовательностей его элементов также счётно;

7) множество алгебраических чисел счётно.

Мощность множества

Мощность счетных множеств минимальна по сравнению с другими бесконечными множествами.

Мощность Q

Если А — бесконечное множество, то в нем содержится по меньшей мере одно счетное подмножество.

[math] B \subset A [/math]

[math] a_1 \in A \Rightarrow A \backslash \ < a_1 \>= A_1 [/math] — бесконечное множество.

[math] a_2 \in A_1 \Rightarrow A_1 \backslash \ < a_2 \>= A_2 [/math] — также бесконечное множество.

Если [math] \ < a_1, a_2, . , a_n, . \>[/math] — совокупность попарно различных элементов, то это — счетное множество.

Для счетных множеств часто применяется следующий важный факт:

Не более чем счетное объединение не более, чем счетных множеств, не более, чем счетно, то есть, другими словами: Если все [math] A_n [/math] — счетное/конечное множество, то [math]\ \ | \bigcup\limits_n A_n | = |\mathbb N| [/math]

Выпишем все элементы этих множеств в таблицу:

[math]\ ||a^i_j||[/math] , где [math]\ a^i_j \in A_i,\ i, j \in \mathbb N [/math]

[math] \begin a^1_1 & a^1_2 & a^1_3 & \cdots \\ \\ a^2_1 & a^2_2 & a^2_3 & \cdots \\ \\ a^3_1 & a^3_2 & a^3_3 & \cdots \\ \\ \vdots &\vdots &\vdots &\ddots \end [/math]

Будем нумеровать их по диагоналям: [math] \begin 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ a^1_1 & a^2_1 & a^1_2 & a^3_1 & a^2_2 & a^1_3 & \cdots \end [/math]

В частности, множество рациональных чисел [math] \mathbb Q [/math] — счетно.

Континуум

Определение:

Множество [math] I = [0, 1][/math] называется континуумом.

[math] I [/math] — несчетное множество.

Будем доказывать от противного. Применим принцип вложенных отрезков:

Разделим I на 3 части и назовем [math] \Delta_1 : x_1 \notin \Delta_1 [/math] . Такой отрезок всегда существует.

Далее разобьем [math] \Delta_1 [/math] на 3 части. Назовем [math] \Delta_2 [/math] тот отрезок, который не содержит [math] x_2 [/math] , и так далее..

В результате выстраивается система вложенных отрезков:

[math] \ < \Delta_n : \Delta_\subset \Delta_n, x_n \notin \Delta_n \> [/math]

По свойству системы вложенных отрезков:

[math] \exists d = \bigcap\limits_^ <\infty>\Delta_n [/math]

[math] d \in I [/math] . Пусть теперь [math] d \in \ < x_i \>\Rightarrow d = x_ [/math] .

Если [math] |A| = |I| [/math] , то обычно говорят, что А обладает мощностью континиума:

Мощность R

[math] |\mathbb R| = |I| [/math]

Рассмотрим функцию [math] y = tg \, x, x \in ( -\frac<\pi>, \frac<\pi> ) [/math]

С ее помощью можно установить биекцию между множествами [math] \mathbb R [/math] и [math] ( -\frac<\pi>, \frac<\pi> ) [/math] .

Биекцию между множествами [math] (0, 1) [/math] и [math] ( -\frac<\pi>, \frac<\pi> ) [/math] можно установить параллельным переносом и сжатием:

[math] x \leftrightarrow (x \cdot \pi) — \frac <\pi> [/math]

Получили, что [math] |\mathbb R| = | ( -\frac<\pi>, \frac<\pi> ) | = | (0, 1) | [/math] .

Осталось доказать, что [math] |(0, 1)| = |[0, 1]| [/math] .

Применим следующий прием:

Пусть [math] a_1, a_2, . , a_n, . \in (0, 1) [/math] — попарно различны.

Множество [math] A = \ < a_1, a_2, . , a_n, . \>[/math] — счетное.

Определим множество [math] B = A \cup \ < 0, 1 \>[/math] . Множество [math] B [/math] также счетное.

Между счетными множествами можно установить биекцию: [math] B \leftrightarrow A \Rightarrow (0, 1) \backslash A \leftrightarrow [0, 1] \backslash B \Rightarrow (0, 1) \leftrightarrow [0, 1] \Rightarrow |(0, 1)| = |[0, 1]| [/math]

Так как [math] \mathbb Q [/math] — счетно. [math] |\mathbb R \backslash \mathbb Q| = |I| \Rightarrow [/math] иррациональных чисел по мощности континииум.