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

На каждом шагу нам приходиться сталкиваться с тем трудно определяемым понятием, которое выражается словом совокупность. Например,Ва можно говорить о совокупности людей присутствующих в данный момент времени в данной комнате, о совокупности гусей плавающих на деревенском пруду, страусов живущих в Сахаре и тому подобное.

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

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

Изучение множеств и их свойств занимается такой раздел математике как Влтеория множествВ» Этот раздел имеет сравнительно небольшую историю. Первые серьёзные работы в этой области, принадлежащие Г. Кантору, появились в конце прошлого века. Тем немение, в настоящие время теория множеств представляет собой весьма обширную область математики.

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

Определение 1. Множество называется конечным, если количество элементов этого множества есть конечное число. Если же количество элементов множества есть число бесконечное, то множество называется бесконечным.

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

Определение 2. Пусть А и В два множества. Правило j которое каждому элементу а множества А соотносит один и только один элемент b множества В, причем каждый элемент bВ оказывается соотнесенным одному и только одному аА, называется взаимно однозначным соответствием между множеством А и множеством В.

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

А ~ В.

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

II.Определение 1.Пусть N множество всех натуральных чисел

N={1, 2, 3, . . .},

тогда всякое множество А эквивалентное множеству N будет называться исчислимым, или счётным множеством.

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

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

Вот несколько примеров счётных множеств:

А={1, 4, 9, 16, . . . ,n, . . .};

B={3, 6, 9, 12, . . . ,3n, . . . };

Ва C={,};

D={1, 8, 27, 64, . . . ,n, . . . };

ВаТеорема 1. Для того чтобы множество Х было счётным необходимо и достаточно, чтобы его можно было ВлперенумероватьВ», то есть представить в форме последовательности:

Х={x, x, x, . . . ,x, . . . } .

Доказательство необходимости: Пусть множество Х счетное, то из определения счётного множества следует существование взаимно однозначного соответствия j между множеством Х и множеством натуральных чисел N. Достаточно обозначить через х, тот из элементов множества Х, который в соответствии с j отвечает числу n,чтобы получить представление множества Х в форме (*).

Доказательство достаточности: Если множество Х представлено в форме (*), то достаточно каждому его элементу х, соотнести индекс n этого элемента, чтобы получить взаимно однозначного соответствия j между множеством Х и множеством натуральных чисел N, так что из определения счётного множества следует, что множество Х счётное.

Следующая теорема даёт интересный пример счётного множества.

Теорема 2. Рациональные числа R образуют счётное множество.

Доказательство: Рассмотрим сначала рациональные неотрицательные числа. Расположим их в бесконечную таблицу следующим образом: в первую строчку поместим в порядке возрастания в целые числа 0, 1, 2, . . . ; во вторую тАУ все положительные несократимые дроби со знаменателем 2, упорядоченные по величине числителя; вообще в n-ую строчку, n=1, 2, 3, тАж, - все положительные рациональные числа, записывающиеся несократимой со знаменателем n, упорядоченные по величине числителя. Очевидно, что каждое рациональное неотрицательное число попадёт на какое-то место в получившейся Ватаблице;

1Ва 2Ва 3Ва 4Ва . . .

Ва. . .

Ва . . .

Ва . . . . . . . . . . . .

Ва. . . . . . . . . .

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

ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа . . .

ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа .ВаВаВа . . .

ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа .ВаВаВаВа .ВаВаВа . . .

ВаВаВаВаВаВаВаВаВаВаВаВаВаВа .ВаВаВаВаВаВа .ВаВаВаВа .ВаВаВа . . .

ВаВ результате все рациональные неотрицательные числа оказываются занумерованными, то есть мы доказали, что они образуют счётное множество.

Ва Чтобы убедится, что и множество всех рациональных чисел также счётно, достаточно их записать в подобную же таблицу. Это можно сделать, например, поместив в написанную выше таблицу после каждого положительного рационального числа х в туже строчку число - х.ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа

1 -1Ва 2 -2 . . .

Ва--. . .

Ва--. . .

Ва . . . . . . . . . . .

Ва-. . . . . . . .

Ва. . . . . . . . . . . .

Перенумеровав элементы таблицы тем же способом, что и выше, мы получили, что множество всех рациональных чисел является счётным множество.

III. Сформулируем и докажем несколько теорем характеризующих счетные множества.

Теорема 3. Из всякого бесконечного множества Х можно выделить счетное множество Y.

Доказательство: Пусть множество Х бесконечное множество. Выделим из множества Х произвольный элемент и обозначим егоВа х₁. Так множество Х бесконечно, то оно не исчерпывается выделение этого элемента х₁.и мы можем выделить элемент х₂ из оставшегося множества Х\{ х₁}. По тем же соображениям множество Х\{ х₁, х₂} не пусто, и мы можем и из него выделить элемент х₃. Ввиду бесконечности множества Х мы можем продолжать этот процесс неограниченно, в результате чего получим последовательность выделенных элементов х₁, х₂, х₃, . . . , х_n, . . . , которая и образует искомое подмножество Y множества Х.

Данная теорема может натолкнуть на интересный вопрос. А в свою очередь можно ли из счётного множества выделить бесконечное подмножество, которое было так же счётным? На этот вопрос отвечает следующая теорема.

Теорема 4. Всякое бесконечное подмножество счётного множества так же является счётным множеством.

Доказательство: Пусть множество Х счётное множество, а множество Y его бесконечное подмножество. Следовательно, множество Х может быть представлено в виде

Х={а₁, а₂, а₃, . . . , а_n,. . .}.

БудемВа перебирать один за другим элементы множество Х в порядке их номеров, при этом мы время от времени будем встречать элементы множества Y, и каждый из элементов множества Y рано или поздно встретится нам. Соотнося каждому элементу множества Y номер ВлвстречиВ» с ним, мы перенумеруем множество Y, причём в силу бесконечности его, нам придетсяВа на эту нумерацию израсходовать все натуральные числа. Следовательно, множество Y является счётным множеством.

Приведем пример непосредственно относящийся к этой теореме.

Пример: Множество Х={1, ,} как известно, является счётным множеством,ВаВа а так как множество Y={,} является подмножеством множества Х, то по доказанной выше теоремы 3, множество Y так же является счётным.

Из выше изложенной теоремы вытекает следующие следствие.

Следствие: Если из счётного множества Х удалить конечное подмножество Y, то оставшееся множество Х\Y будет счётным множеством.

IV. Теорема 5. Объединение конечного множества и счётного множества без общих элементов есть счётное множество.

Доказательство: Пусть дано

А={а₁, а₂, . . . , а_n} и В={b₁, b₂, b₃, . . . },

причем АÇВ = О.

Ва Если множество С=АÈВ, то С можно представить в форме

С={а₁, а₂, . . . , а_n, b₁, b₂, b₃, . . . },

после чего становиться очевидной возможность перенумеровать множество, следовательно по теореме 1 получаем, что множество С счетно.

- 4 -

Теорема 6. Объединение конечного числа попарно не пересекающихся счётных множеств есть счётное множество.

Доказательство: Проведем доказательство для случая объединения трёх множеств, из контекста будет ясна полная общность рассуждения.

Пусть А, В, С три счётных множества:

ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа А={а₁, а₂, а₃, . . .}, В={b₁, b₂, b₃, . . . } и

С={с₁, с₂, с₃, . . .}.

Тогда множество D = АÈВÈС можно представитьВа в форме последовательности:

D={а₁, b₁, c₁, а₂, b₂, c₂, а₃, . . .},

и счётность множества D очевидна.

Теорема 7. Объединение счётного множества попарно не пересекающихся конечных множеств есть счётное множество.

Доказательство: Пусть А_k (k=1, 2, 3, . . . ) суть попарно не пересекающихся конечных множеств:

А₁={Ва. . . , };

А₂={. . . , };

А₃={Ва. . . ,};

.Ва .Ва .Ва .Ва .Ва .Ва .Ва .Ва .Ва .Ва .Ва .Ва .Ва .Ва .

Для того чтобы расположить объединение их С в форме последовательности, достаточно выписать подряд все элементы множества А₁, а затем элементы множества А₂ и так далее.

Теорема 8. Объединение счётного множества попарно не пересекающихся счётных множеств есть счетное множество.

Доказательство: ПустьВа множества А_k (k=1, 2, 3, . . .) попарно не пересекаются и счетные. Запишем эти множества следующим образом:

ВаА₁={Ва. . . };

А₂={. . . };

А₃={Ва. . . };

.Ва .Ва .Ва .Ва .Ва .Ва .Ва .Ва .Ва .Ва .Ва .

ЕслиВа мы выпишем элемент , затем оба элемента Ваи Вау которых сумма верхнего и нижнего индексов равна 3, затем элементы у которых эта сумма равна 4, и так далее, то множество С=Ваокажется представленной в форме последовательности:

С = {Ва. . . },

Откуда и следует счётность множества С.

Ва Замечание: Условие отсутствия общих элементов в теоремах 5-8 могло быть опущено.

- 5 -

V. Используя доказанные выше теорем можно привести другое доказательство теоремы 2 отличное от предыдущего.

Доказательство теоремы 2: Множество дробей вида Вас данным знаменателем q, то есть множество . . . , очевидно счётное. Но знаменатель может принять также

счётное множество натуральных значений 1, 2, 3, . . .Ва . Значит в силу теоремы 8, множество дробей вида Ваявляется счётным множеством; удаляя из него все сократимые дроби и применяя теорему 4, убеждаемся в счётностиВа множества всех положительных рациональных чисел R₊. Так как множество R_- отрицательных рациональных чисел очевидно эквивалентно множеству R₊, то счетным являетсяВа и оно, а тогда счётно и множество R, ибо R= R₊R_-{0}.

Из теоремы 2 вытекает следующие очевидное следствие.

Следствие. Множество рациональных чисел любого сегмента [a, b] является счётным множеством.

Сформулируем в виде теоремы еще один пример счётного множества.

Теорема 9. Множество Р всех пар натуральных чисел является счетным множеством.

Отступление: Под парой натуральных чисел понимают два натуральных числа данных в определённом порядке.

Доказательство: Назовём высотою пары (n, m) натуральное число n+m. Очевидно, имеется ровно k-1 пар данной высоты k, где k>1, именно

(1, k-1), (2, k-2), . . . , (k-1, 1).

По этому обозначая через Р_k множество всех пар высоты k, видим что множество Р есть объединение счётного множества конечных множеств Р_k, а отсюда по теореме 7 получаем что множество Р является счётным множеством.

Теорема 10 также даёт любопытный пример счетного множества.

Теорема 10. Множество S всех конечных последовательностей, составленных из элементов данного счётного множества D, есть счётное множество.

Доказательство: (посредствам полной математической индукции) Из предыдущей теоремы вытекает, что множество пар, составленных из элементов счётного множества D, есть счётное множество. Предположим, что доказана счётность множества S_m всех последовательностей, состоящих из m элементов данного счётного множества D. Докажем, что множество S_m+1 всех последовательностей, состоящих из m+1 элементов множества D также счётно. В самом деле, пусть

D={d₁, d₂, . . . , d_k, . . .}.

Каждой последовательности S^{(m +1)}=(d_i,Ва . . , d_i, d_k)Î S_m+1 соответствует пара (S^(m), d_k), где S^(m)= (d_i,Ва . . , d_i)Î S_m, причем различным парам соответствуют различные пары этого вида. Так как множество S_m всех S^(m)Ва счётно, и может быть записано в виде S, . . . , S,Ва . . . , то счётно и множество всех пар (S, d_k) (взаимно однозначно соответствующих парам натуральных чисел индексов i, k), а значит, и множество всех S^{(m +1)}.

Так как каждое S_m счётно, то счётно и множество S, что и доказывает теорему.

В заключении докажем следующую, весьма общую теорему:

- 6 -

Теорема 11. Если элементы множества А определяются n значками, каждый из которых независимо от других пробегает счётное множество значений

А={a,, . . . ,}ВаВаВа (x_k=x, x, . . . ; k=1, 2, 3, . . . ,n),

то множество А счётно.

Доказательство: Докажем теорему методом математической индукции.

Теорема очевидна, если n=1, то есть имеется только один значок. Допустим, что теорема верна для n=m, и покажем, что она справедлива для n=m+1.

Итак пусть А={a,, . . . ,, }.

Обозначим через A_i множество тех элементов А, для которых Ва, где ВаВаодно из возможных значений (m+1)-го значка, т. е. положим A_i =={a,, . . . ,, Ва}.

В силу сделанного допущения множество A_i счётно, а так как А=, то счётно и множество А.

ВаВот несколько предложений, вытекающих из этой теоремы:

Множество точек (x, y) плоскости, у которых обе координаты рациональны, счётно.

Но более интересным является следующий факт:

Множество многочленов с целыми коэффициентами счётно.

В самом деле, это непосредственно следует из теоремы 11, если только рассматривать многочлены фиксированной степени n, и для завершения доказательства следует применить теорему 8.

Список литературыВаВаВа

1.Александров П.С. Введение в общую теорию множеств и функций. тАУ Ленинград,ВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВаВа 1948.

Никольский С.М. Курс математического анализа. тАУ Москва, 1983.

Кудрявцев Л.Д. Математический анализ (том 1). тАУ Москва, 1973.

Архангельский А. В.Ва Канторовская теория множеств. тАУ Москва, 1988.

Куратовский К. и Мастовский А. Теория множеств. тАУ Москва, 1970.

Медведев Ф.А. Развитие теории множеств в 19 веке. тАУ Москва, 1965.

Вместе с этим смотрят:

"Инкарнация" кватернионов

* Алгебры и их применение

*-Алгебры и их применение

10 способов решения квадратных уравнений

Bilet