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

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

Начальный отрезок натурального ряда [0; n − 1]= <1,2,…, n − 1>конечен и содержит n элементов. Сам же натуральный ряд N = <0,1,2,…>бесконечен. Поэтому не может быть инъективным никакое отображение N в [0; n − 1]. Следовательно, | N |> n , то есть мощность натурального ряда превосходит любое натуральное число. Множества, равномощные натуральному ряду, называются счетными . Для обозначения мощности счетных множеств используется символ 0 (читается «алеф ноль»). Если множество A конечно или счетно, его элементы могут быть занумерованы, то есть расположены в виде списка

a 0 , a 1 , a 2 , a 3 , … ,

так, что всякий элемент множества A рано или поздно встретится в этом списке. Если множество A конечно, то и список конечен; в противном случае список оказывается бесконечным. Ясно, что при таких обозначениях отображение i → a i – это и есть та самая биекция начального отрезка или всего натурального ряда на множество A , которая устанавливает конечность или счетность множества A .

Пример. Множество четных чисел счетно; их можно представить списком 0,2,4,6,… . Соответствие очевидно: n ↔ 2 n .

Точно так же счетно и множество нечетных чисел 1,3,5,… .

Здесь можно положить n ↔ 2 n +1.

Пример. Множество рациональных чисел счетно. Напомним, что всякое рациональное число однозначно записывается в виде несократимой дроби p / q , где p и q – взаимно простые целые числа и q >0. Составим список, содержащий все рациональные числа, в порядке возрастания величины | p |+ q :

0; − 1/1; 1/1; − 2/1; − 1/2; 1/2; 2/1; …

Ясно, что любая дробь p / q появится в этом списке через конечное число шагов и получит свой номер.

Укажем некоторые свойства счетных множеств.

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

Доказательство. Достаточно доказать справедливость утверждения для множества натуральных чисел: всякое подмножество A множества натуральных чисел конечно или счетно. Составим список элементов множества A в порядке их возрастания. Если этот список конечен – множество A конечно;

если бесконечен – счетно.

Из предыдущего предложения вытекает, что счетные множества являются наименьшими по мощности бесконечными множествами: если | A | ≤ 0 , то A конечно или счетно.

2. Образ счетного множества относительно произвольного отображения является конечным или счетным множеством .

Доказательство. Пусть множество В является образом счетного множества A относительно некоторого отображения.

Тогда, по теореме из предыдущего пункта, | B | ≤ | A | и, значит, B

конечно или счетно.

Если элементы множества A представлены списком с повторениями

a 0 , a 1 , a 2 , a 3 , … ,

то есть списком, в котором некоторые элементы могут попадаться многократно, это означает, что отображение i → a i сюръективно (но не инъективно). Таким образом, множество A является образом натурального ряда, и потому конечно или счетно.

3. Всякое бесконечное множество содержит счетное подмножество.

Доказательство. Пусть A – бесконечное множество.

Тогда | A | ≥ 0 . Но это неравенство означает, что существует инъективное отображение множества натуральных чисел в A . Образ этого отображения – счетное подмножество множества A .

4. Объединение любого конечного (непустого) или счетного семейства счетных множеств счетно .

Доказательство. Пусть счетные множества A 0 , A 1 , … представлены списками своих элементов:

Составим список объединения этих множеств A , располагая элементы объединения в порядке возрастания суммы индексов:

(если некоторые из множеств имеют общие элементы, в этом списке возможны повторения). Множество A бесконечно, и,

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

5. Декартово произведение конечного числа счетных множеств счетно.

– счетные множества. Покажем, что счетно декартово произведение A × B . Составим список его элементов подобно тому, как составлялся список рациональных чисел:

( a 0 , b 0 ), ( a 0 , b 1 ), ( a 1 , b 0 ), ( a 0 , b 2 ), ( a 1 , b 1 ), ( a 2 , b 0 ), … .

Если счетны множества A , B , C , то счетно A × B , а вместе с ним и A × B × С = ( A × B ) × С как произведение двух счетных

Глава 1 Счётные и несчётные множества

Рассмотрим ряд примеров на определение счётности/несчётности множеств:

1. \(\mathbb\) = <1, 2, 3, …>;
2. \(\mathbb\) = <- … , -3, -2, -1, 0, 1, 2, 3, …>;
3. \(\mathbb\) = < \(\frac\) | \(m\in\mathbb\) , \(n\in\mathbb\) > ;
4. \(\mathbb\) – множество действительных чисел;
5. Точки на плоскости с целыми координатами;
6. [0 ; 1] ;
7. [0 ; 1] \(\times\) [0 ; 1] = < (x, y) | \(x\in\) , \(y\in\) >;
8. Множество бесконечных последовательностей из нулей и единиц.

Будет рассматривать эти примеры в ходе изложения в порядке их нумерации.

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

Определение:
Счётное множество — это либо конечное, либо равномощное натуральным числам множество (иными словами, каждому элементу можно сопоставить натуральное число взаимно однозначно, то есть так, что ни один элемент в таких множествах не будет пропущен).

Элементы множества натуральных чисел можно пронумеровать, следовательно множество \(\mathbb\) — счетно.

По определению счетного множества, множество целых чисел \(\mathbb\) — счётно, так как целые числа можно расположить в виде последовательности 0, 1, −1, 2, −2, 3, −3, … . Иными словами, можно привести взаимнооднозначное соответствие между целыми и натуральными числами, например, таким способом (см. рисунок):
\(0\leftrightarrow1\)
\(1\leftrightarrow2\)
\(-1\leftrightarrow3\)
\(2\leftrightarrow4\)
\(-2\leftrightarrow5\)
\(3\leftrightarrow6\)
…

1. Докажем счетность множества рациональных чисел:
   Расположим рациональные числа в виде таблицы, строку которой с номером n образуют дроби со знаменателем n. Нумеруем по прямоугольникам, начиная с нуля и пропуская при этом числа, которые уже получили номер ранее. Так, любое рациональное число получит некоторый номер, что доказывает счетность множества рациональных чисел.

1.2 Сравнимость мощностей

Утверждение: Если множество А равномощно подмножеству В, то либо мощность А меньше мощности В, либо А и В равномощны.

1. Из курса высшей алгебры:
   Для доказательства счетности множества предположим противное. Пусть множество \(\mathbb\) состоит из чисел a₁,a₂,…,a_n,…. Рассмотрим дробные части \(\alpha\) _n чисел a_n, 0 < \(\alpha\) _n < 1, расположим в виде таблицы:
   \(\alpha\) ₁ = 0, \(\alpha\) ₁₁, \(\alpha\) ₁₂, …, \(\alpha\) _1n, …
   \(\alpha\) ₂ = 0, \(\alpha\) ₂₁, \(\alpha\) ₂₂, …, \(\alpha\) _2n, …
   …
   Чтобы опровергнуть гипотезу о счетности множества \(\mathbb\) , приведем пример числа a, отличного от всех чисел a₁,a₂,…,a_n,… .
   Рассмотрим число \(\beta\) = 0, \(\beta\) ₁, \(\beta\) ₂, …, \(\beta\) _n, … . Пусть \(\beta_1\ne\alpha_<11>\) , \(\beta_2\ne\alpha_<22>\) , …, \(\beta_n\ne\alpha_\) , тогда \(\beta_k\ne\alpha_k\) , k = 1,2,…,n,…, т.е. это число не совпадает ни с одним из чисел a₁,a₂,…,a_n,…, что означает, что наше предположение о том, что все числа множества \(\mathbb\) удалось пронумеровать, привело к противоречию, и множество несчетно.

Кроме того, \(\mathbb\)

[0 ; 1] — это несчетные множества с одинаковой мощностью. Однако как можно показать, что \(\mathbb\) не мощнее [0 ; 1] ? Для наглядности можно использовать график арктангенса. Преобразуем его до вида \(atan(x)/pi+1/2\) . Видно, что его асимптоты будут иметь координаты 0 и 1 по оси ординат. Также видно, что каждой точке на оси X (эквивалентно множеству \(\mathbb\) ) соответствует значение на оси Y, причем каждое из соответствующих значений лежит в промежутке от нуля до единицы. Таким образом, \(\mathbb\)

1. Проведем в данном случае аналогию с точками на плоскости. Так, например, можно двигаться “по спирали”, пересчитывая тем самым все точки на этой плоскости.
   Во избежание путаницы, важно отметить, что в рамках этого способа \((-3,-1)\ne(-6,-2)\) , в то время как \(\frac<-3><-1>=\frac<-6><-2>\) .

Отрезок [0,1] равномощен множеству всех бесконечных последовательностей нулей и единиц, то есть является несчетным множеством. Подробнее см. в учебнике Н.К.Верещагина и А.Шень Начала теории множеств.

[0 ; 1] \(\times\) [0 ; 1] — декартов квадрат; он обладает большей мощностью, чем отрезок [0 ; 1], который является несчетным множеством. Заключаем, что [0 ; 1] \(\times\) [0 ; 1] — несчетное множество.

Пусть есть некоторое множество А, состоящее из последовательностей 0 и 1. Рассмотрим такие последовательности и пронумеруем их:
\(1\leftrightarrow <\underline<0>,1,0,1,0,1,0,1. >\in A\)
\(2\leftrightarrow<0,\underline<0>,0,1,0,0,0,1. >\in A\)
…
Во множестве А содержится бесконечное количество элементов — последовательностей из 0 и 1.

1.3 Доказательство от принцессы

Утверждение: А — несчетно.
Доказательство от принцессы: Тому, кто приведет взаимнооднозначное соответствие между множеством А и множеством натуральных чисел \(\mathbb\) , полагается сердце и полцарства в придачу!
Пусть пришел индийский принц. Принц развернул длинный список, и она видит, что он пронумеровал бесконечно много последовательностей из нулей и единиц. Что будет делать принцесса? Предположим, что в его списке, помимо отмеченных нами последовательностей №1 и №2, присутствуют и такие последовательности:
\(3\leftrightarrow <1,1,\underline<1>,1,1,1,1,1. >\in A\)
\(4\leftrightarrow<0,0,0,\underline<0>,0,0,0,0. >\in A\) .
Чтобы принцу ничего не досталось, принцесса меняет значение i-го элемента i-го списка на противоположное (0 на 1 и 1 на 0 соответственно). Это можно сделать в каждой последовательности, тогда
…
\(101\leftrightarrow<. \underline<1>>\in A\)
…
И такая измененная последовательность не может быть у него ни под каким номером.
Пусть пришел и арабский принц. Принцесса проводит аналогичную операцию по замене значения i-го элемента i-го списка на противоположное:
\(1\leftrightarrow <\underline<1>,1,1,1,1,1,1,1,1,1. >\in A\)
\(2\leftrightarrow<1,\underline<0>,1,0,0,1,0,0,0,1. >\in A\)
\(3\leftrightarrow<. \underline< >. >\in A\)
Аналогичный результат и со списком второго принца. Таким образом, мы можем сделать вывод, что такого взаимнооднозначного соответствия не существует, и принцесса может отказать любому принцу! Отсюда следует, что множество А не равномощно множеству \(\mathbb\) .
Пояснение: A > \(\mathbb\) :
\(1\leftrightarrow<100000. >\in A\)
\(2\leftrightarrow<010000. >\in A\)
\(3\leftrightarrow<001000. >\in A\)
\(4\leftrightarrow<000100. >\in A\)
…

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

В теории множеств, счётное мно́жество есть бесконечное множество, элементы которого возможно пронумеровать натуральными числами. Более формально: множество является счётным, если существует биекция

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

Содержание

Свойства

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

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

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

Примеры

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

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

Примечания

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

См. также

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

Wikimedia Foundation . 2010 .

Полезное

Смотреть что такое «Счётное множество» в других словарях:

Несчётное множество — В теории множеств счётное множество есть бесконечное множество, элементы которого возможно пронумеровать натуральными числами. Более формально: множество X является счётным, если существует биекция , где обозначает множество всех натуральных… … Википедия

несчётное множество — понятие теории множеств; бесконечное множество, мощность которого больше, чем мощность счётного множества. Например, множество всех действительных чисел несчётное множество. * * * НЕСЧЕТНОЕ МНОЖЕСТВО НЕСЧЕТНОЕ МНОЖЕСТВО, понятие теории множеств; … Энциклопедический словарь

счётное множество — понятие теории множеств, бесконечное множество, элементы которого возможно занумеровать натуральными числами. Множество всех рациональных чисел и даже множество всех алгебраических чисел счётны, однако множество всех действительных чисел несчётно … Энциклопедический словарь

Счётное множество — бесконечное множество, элементы которого можно занумеровать натуральными числами, то есть установить Взаимно однозначное соответствие между этим множеством и множеством всех натуральных чисел. Как доказал Г. Кантор, множество всех… … Большая советская энциклопедия

СЧЁТНОЕ МНОЖЕСТВО — понятие теории множеств, бесконечное множество, элементы к рого возможно занумеровать натуральными числами. Множество всех рациональных чисел и далее множество всех алгебр. чисел счётны, однако множество всех действит. чисел несчётно … Естествознание. Энциклопедический словарь

Множество Витали — Множество Витали  первый пример множества вещественных чисел, не имеющего меры Лебега. Этот пример, ставший классическим, опубликовал в 1905 году итальянский математик Дж. Витали в своей статье «Sul problema della misura dei gruppi di punti… … Википедия

МНОЖЕСТВО — набор, совокупность, собрание к. л. объектов, называемых его элементами, обладающих общим для всех них характеристич. свойством. Понятие M. принадлежит к числу первоначальных матем. понятий и может быть пояснено только при помощи примеров. Так,… … Физическая энциклопедия

Множество второй категории — Курсив обозначает ссылку на этот словарь # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш … Википедия

Множество первой категории — Курсив обозначает ссылку на этот словарь # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш … Википедия

множество — а; ср. 1. Очень большое количество, число кого , чего л. М. народа. М. фактов. Вырастить м. цветов. Доказательства представлены во множестве. Великое м. примеров (очень много). 2. Матем. Совокупность элементов, объединённых по какому л. признаку … Энциклопедический словарь

06. Теоремы о счетных множествах. Множества мощности континуум

Если рассмотреть любое конечное множество и любое его собственное (непустое и не совпадающее с ним самим) подмножество, то элементов в подмножестве меньше, чем в сам множестве, т. е. часть меньше целого.

Обладают ли бесконечные множества таким свойством? И может ли иметь смысл утверждение, что в одном бесконечном множестве «меньше» элементов, чем в другом, тоже бесконечном? Ведь про два бесконечных множества мы можем пока только сказать, эквивалентны они или нет. А существуют ли вообще неэквивалентные бесконечные множества?

Приведём забавную фантастическую историю из книги Н. Я. Виленкина «Рассказы о множествах». Действие происходит в далёком будущем, когда жители разных галактик могут встречаться друг с другом. Поэтому для всех путешествующих по космосу построена огромная гостиница, протянувшаяся через несколько галактик.

В этой гостинице бесконечно много номеров (комнат), но, как и положено, все комнаты пронумерованы, и для любого Натурального числа n есть комната с этим номером.

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

«После некоторых размышлений директор обратился к администратору и сказал:

– Поселите его в № 1.

– Куда же я дену жильца этого номера? – удивлённо спросил администратор.

– А его переселите в № 2. Жильца же из № 2 отправьте в № 3, из № 3 – в № 4 и т. д.»

Вообще, пусть постоялец, живущий в номере K, переедет в номер K+1, как это показано на следующем рисунке:

Тогда у каждого снова будет свой номер, а № 1 освободится.

Таким образом, нового гостя удалось поселить – именно потому, что номеров в гостинице бесконечно много.

Первоначально участники съезда занимали все номера гостиницы, следовательно, между множеством космозоологов и множеством N Было установлено взаимно однозначное соответствие: каждому космозоологу дали по номеру, на двери которого написано соответствующее ему натуральное число. Естественно считать, что делегатов было «столько же», сколько имеется натуральных чисел. Но приехал ещё один человек, его тоже поселили, и количество проживающих увеличилось на 1. Но их снова осталось «столько же», сколько и натуральных чисел: ведь все поместились в гостиницу!

Мы пришли к удивительному выводу: если к множеству, которое равномощно N, добавить ещё один элемент, получится множество, которое снова равномощно N. Но ведь совершенно ясно, что делегаты-космозоологи представляют собой часть того множества людей, которые разместились в гостинице после приезда нового гостя. Значит, в этом случае часть не «меньше» целого, а «равна» целому!

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

Новый постоялец не удивился, когда на другое утро ему предложили переселиться в № 1000000. Просто в гостиницу прибыли запоздавшие космозоологи из галактики ВСК-3472, и надо было разместить ещё 999999 жильцов.

Но потом произошла какая-то накладка, и в эту же самую гостиницу приехали на съезд филателисты . Их тоже было бесконечное множество – по одному представителю от каждой галактики. Как же их всех разместить?

Эта задача оказалась весьма сложной. Но и в этом случае нашёлся выход.

«В первую очередь администратор приказал переселить жильца из № 1 в № 2.

– А жильца из № 2 переселите в № 4, из № 3 – в № 6, вообще, из номера N – в номер 2n.

Определение. Множество А, равномощное множеству натуральных чисел N, называется Счетным множеством (имеет мощность счетного множества). Если множество В является бесконечным и не равномощно множеству N, то его называют несчетным.

Множество, которое является конечным или счетным, еще называют не более чем счетным .

Пусть множество А является счетным. По определению, тогда существует биекция А на N, т. е. каждому аÎА соответствует единственный номер nÎN и множество А обращается в некоторую последовательность <аn>.

Теорема 1. Любое подмножество счетного множества не более чем счетно.

Доказательство. Пусть А = — счетное множество и В Í А. Если В конечное множество, то утверждение доказано. Предположим, что В бесконечное множество. Те элементы А, которые попали в В будут иметь некоторые номера в порядке возрастания: . Тогда необходимая нам биекция, показывающая, что В является счетным множеством, задается в виде: ® k.

Теорема 2. Объединение конечного или счетного числа счетных множеств является счетным множеством.

Доказательство. Рассмотрим счетное объединение счетных множеств (случай конечного является частным). Итак, пусть Аn — счетные множества для любого nÎN и А = Èn Аn. Для доказательства нам необходимо указать биекцию множества А на множество N, т. е. указать каждому аÎА его номер. Запишем все множества А в виде последовательностей с двумя индексами, где первый указывает номер множества. Зададим закон, который каждому элементу А ставит в соответствие некоторый порядковый номер. Если элементы множества Аn обозначить через аnk, то высотой элемента аnk назовем число n + k. Перепишем элементы множества А, располагая все его элементы по следующему правилу — сперва перепишем все элементы высоты 2, затем высоты 3, 4 и т. д: а11, а12, а21, а13, а22, а31, а14, а23, а32, а41, . Тогда любой элемент множества А будет иметь определенный номер.

Теорема 3. Любое бесконечное множество содержит счетное подмножество.

Доказательство. Выберем в заданном множестве А какой-либо элемент, придав ему единичный индекс: а1. Среди всех оставшихся элементов множества А найдется не равный а1 элемент (в силу бесконечности А). Его мы обозначим через а2. Продолжая этот процесс до бесконечности мы получим необходимое нам счетное множество .

Теорема 4. Пусть множество М — несчетно, множество А не более чем счетно и А Í М. Тогда множество М – А равномощно множеству М.

Доказательство. Пусть множество М – А не более чем счетно. Тогда множество М = АÈ(М – А) по теореме 2 не более чем счетно. Это противоречит тому, что множество М несчетно и, следовательно, наше исходное предположение не верно. Таким образом, множество М – А несчетно. Последнее еще не означает равномощности множеств М и М – А. Докажем ее. Выделим из М – А счетное множество В. Обозначим через С множество С = (М – А) – В. Справедливы равенства М = АÈВÈС и М – А = ВÈС. Множество АÈВ счетно (теорема 2). Следовательно, существует биекция f из АÈВ на А. Теперь можно построить биекцию g из М на М – А по правилу:

Теорема 5. Если множество С бесконечно, а В не более чем счетно, то множество ВÈС равномощно множеству С.

Доказательство. Если множество С счетно, то множество ВÈС также счетно и следовательно они равномощны. Если же множество С не счетно, то мы можем воспользоваться теоремой 4, положив в ней А = СÇВ, а М = С.

Теорема 6. Если множество С является бесконечным, то существует его подмножество В такое, что В¹С и В равномощно с С.

Доказательство. По теореме 3 мы можем выделить из множества С его счетное подмножество А. Если множество С счетно, то в качестве В из утверждения теоремы можно взять В=А. Если же С не счетно, то можно положить В=С-А и утверждаемое вытекает из теоремы 4.

Теорема 7. Множество рациональных чисел Q является счетным.

Доказательство. Обозначим через Р множество всех пар натуральных чисел (p, q), таких что p и q не имеют общих целых делителей, кроме единицы. Для пары натуральных чисел (p, q) введем ее высоту m = p + q. Обозначим Рn множество пар натуральных чисел высоты n. Нетрудно проверить, что каждое множество Рn является конечным и содержит не более, чем n-1 член. Так как Р = Èn Рn, то множество Р счетно в силу теоремы 2.

Рассмотрим теперь множество Q+ положительных рациональных чисел. Каждое положительное рациональное число представим в виде не сократимой дроби p/q. Тогда между этим числом и парами из Р существует биекция p/q « (p, q), которая показывает равномощность множеств Q +и Р, т. е. счетность множества Q+. Ясно, что множества Q+ и Q — равномощны. Тогда Q = Q +ÈQ — является счетным множеством как объединение двух счетных множеств.

Теорема 8. Множество точек интервала (0,1) является несчетным.

Доказательство (Диагональный метод Кантора). Доказательство проведем от противного, предположив, что множество точек интервала (0,1) является счетным. Тогда все точки можно записать в виде последовательности:

Покажем, что на самом деле здесь записаны не все числа из интервала (0,1). Построим число 0,а1а2а3а4 . по правилу аk ¹ аkk. Это всегда можно сделать. Но тогда построенное нами число входит в интервал (0,1) и не совпадает ни с одним из записанных чисел. Мы получили противоречие с тем, что нами были выписаны все числа из интервала (0,1) и этим доказали теорему.

Множества, равномощные множеству точек интервала (0, 1), называются множествами мощности Континуум .

Задачи.

1. Показать, что если множества А и В являются счетными, то и их произведение А´В является счетным.

2. Установить биекцию между множеством N всех натуральных чисел и множеством Q всех четных положительных чисел.

3. Установить биекцию между множеством N всех натуральных чисел и множеством Р всех четных чисел.