Реферат: Счётные множества
Курсоваяработа по математическому анализу
Выполнилстудент 104 группы Стенин В. В.
Мордовскийгосударственный университет имени Н.П.Огарёва
Cаранск-2002.
I. Введение
На каждом шагу нам приходиться сталкиваться с темтрудно определяемым понятием, которое выражается словом совокупность.Например, можно говорить о совокупности людей присутствующих в данный моментвремени в данной комнате, о совокупности гусей плавающих на деревенском пруду,страусов живущих в Сахаре и тому подобное.
В каждом из этих случаев можно было бы вместо словасовокупность употребить слово множество. Итак, под словом множествоподразумевается совокупность, коалиция, собрание каких-то элементовобъединенных определенными свойствами или свойством.
В математике постоянно приходиться иметь дело сразличными множествами: например множество точек прямой, являющихся вершинамикакого-нибудь многоугольника, множество перестановок 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 … .
/> /> /> /> /> .. .
/> /> /> /> /> … .
… .
/> .… .
Занумеруем теперь элементы получившейся таблицысогласно следующей схеме (в кружочках стоят номера соответствующих элементов,стрелка указывает направление нумерации).
/>/>/>/>/>/>/> … .
/>/>
/>/> . … .
/> /> /> /> /> /> <td/> />/> . . … .
/>
. . . …
В результате все рациональные неотрицательные числаоказываются занумерованными, то есть мы доказали, что они образуют счётноемножество.
Чтобы убедится, что и множество всех рациональныхчисел также счётно, достаточно их записать в подобную же таблицу. Это можносделать, например, поместив в написанную выше таблицу после каждого положительногорационального числа х в туже строчку число — х.
1 -1 2 -2… .
/> -/>/>-/> />… .
/> -/>/>-/> />… .
…
/> -/>.…
… .
Перенумеровав элементы таблицы тем же способом, что ивыше, мы получили, что множество всех рациональных чисел является счётныммножество.
III.Сформулируем и докажем несколько теорем характеризующих счетные множества.
Теорема 3. Из всякого бесконечного множества Х можновыделить счетное множество Y.
Доказательство: Пусть множество Х бесконечноемножество. Выделим из множества Х произвольный элемент и обозначим его х1.Так множество Х бесконечно, то оно не исчерпывается выделение этого элемента х1.<sub/>и мы можем выделить элемент х2 из оставшегося множества Х\{ х1}.По тем же соображениям множество Х\{ х1, х2} не пусто, имы можем и из него выделить элемент х3. Ввиду бесконечностимножества Х мы можем продолжать этот процесс неограниченно, в результате чегополучим последовательность выделенных элементов х1, х2, х3,..., хn,..., которая и образует искомое подмножество Yмножества Х.
Данная теорема может натолкнуть на интересный вопрос.А в свою очередь можно ли из счётного множества выделить бесконечноеподмножество, которое было так же счётным? На этот вопрос отвечает следующаятеорема.
Теорема 4. Всякое бесконечное подмножество счётногомножества так же является счётным множеством.
Доказательство: Пусть множество Х счётное множество, амножество Y его бесконечное подмножество. Следовательно,множество Х может быть представлено в виде
Х={а1, а2, а3,…., аn,… .}.
Будем перебирать один за другим элементы множество Хв порядке их номеров, при этом мы время от времени будем встречать элементымножества Y, и каждый из элементов множества Yрано или поздно встретится нам. Соотнося каждому элементу множества Yномер «встречи» с ним, мы перенумеруем множество Y, причём в силубесконечности его, нам придется на эту нумерацию израсходовать все натуральныечисла. Следовательно, множество Y является счётным множеством.
Приведем пример непосредственно относящийся к этойтеореме.
Пример: Множество Х={1, />,/>} как известно, является счётным множеством, а таккак множество Y={/>,/>} является подмножеством множества Х, то по доказаннойвыше теоремы 3, множество Y так же является счётным.
Из выше изложенной теоремы вытекает следующиеследствие.
Следствие: Если из счётного множества Х удалитьконечное подмножество Y, то оставшееся множество Х\Y будет счётныммножеством.
IV.Теорема 5. Объединение конечного множества и счётного множества без общихэлементов есть счётное множество.
Доказательство: Пусть дано
А={а1, а2,..., аn}и В={b1, b2, b3,….},
/>причемАÇВ = О./>
Если множество С=АÈВ, тоС можно представить в форме
С={а1, а2,..., аn,b1, b2, b3,….},
после чего становиться очевидной возможностьперенумеровать множество, следовательно по теореме 1 получаем, что множество Ссчетно.
— 4 —
Теорема 6. Объединение конечного числа попарно непересекающихся счётных множеств есть счётное множество.
Доказательство: Проведем доказательство для случаяобъединения трёх множеств, из контекста будет ясна полная общность рассуждения.
Пусть А, В, С три счётных множества:
А={а1,а2, а3,… .}, В={b1, b2, b3,… } и
С={с1, с2, с3,...}.
Тогда множество D = АÈВÈС можно представить вформе последовательности:
D={а1,b1, c1, а2, b2, c2, а3,… .},
и счётность множества D очевидна.
Теорема 7. Объединение счётного множества попарно непересекающихся конечных множеств есть счётное множество.
Доказательство: Пусть Аk (k=1,2, 3,… ) суть попарно не пересекающихся конечных множеств:
А1={/> ..., />};
А2={/>..., />};
А3={/> .… ,/>};
. . . . . . . . . . . . . . .
Для того чтобы расположить объединение их С в формепоследовательности, достаточно выписать подряд все элементы множества А1,а затем элементы множества А2 и так далее.
Теорема 8. Объединение счётного множества попарно непересекающихся счётных множеств есть счетное множество.
Доказательство: Пусть множества Аk(k=1, 2, 3,… .) попарно не пересекаются и счетные.Запишем эти множества следующим образом:
А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, есть счётное множество. Предположим, что доказанасчётность множества Sm всех последовательностей, состоящих из mэлементов данного счётного множества D. Докажем, что множество Sm+1 всехпоследовательностей, состоящих из m+1 элементов множества Dтакже счётно. В самом деле, пусть
D={d1, d2,…,dk,… .}.
Каждой последовательности S(m+1)=(di/>, .., di/>, dk)Î Sm+1 соответствует пара (S(m), dk),где S(m)= (di/>, .., di/>)Î Sm,причем различным парам соответствуют различные пары этого вида. Так какмножество Sm всех S(m) счётно, и может быть записано в виде S/>,..., S/>, ..., то счётно и множество всех пар (S/>, dk) (взаимно однозначно соответствующих парамнатуральных чисел индексов i, k), а значит, и множество всех S(m+1).
Так как каждое Smсчётно, то счётно и множество S, что и доказывает теорему.
В заключении докажем следующую, весьма общую теорему:
— 6 —
Теорема 11. Если элементы множества А определяются nзначками, каждый из которых независимо от других пробегает счётное множествозначений
А={a/>,/>,… ,/>} (xk=x/>, x/>,...; k=1, 2, 3,… ,n),
то множество А счётно.
Доказательство: Докажем теорему методом математическойиндукции.
Теорема очевидна, если n=1, то естьимеется только один значок. Допустим, что теорема верна для n=m, ипокажем, что она справедлива для n=m+1.
Итак пусть А={a/>,/>,… ,/>, />}.
Обозначим через Aiмножество тех элементов А, для которых /> ,где /> одно из возможных значений(m+1)-го значка, т. е. положим Ai=={a/>,/>,… ,/>, /> }.
В силу сделанного допущения множество Aiсчётно, а так как А=/>, то счётно имножество А.
Вот несколько предложений, вытекающих из этойтеоремы:
Множество точек (x, y)плоскости, у которых обе координаты рациональны, счётно.
Но более интересным является следующий факт:
Множество многочленов />сцелыми коэффициентами счётно.
В самом деле, это непосредственно следует из теоремы11, если только рассматривать многочлены фиксированной степени n, идля завершения доказательства следует применить теорему 8.
Списоклитературы
1.Александров П.С. Введение в общую теорию множеств ифункций. –Ленинград, 1948.
Никольский С.М. Курс математического анализа. –Москва, 1983.
Кудрявцев Л.Д. Математический анализ (том 1). –Москва, 1973.
Архангельский А. В. Канторовская теория множеств. –Москва, 1988.
Куратовский К. и Мастовский А. Теория множеств. –Москва, 1970.
Медведев Ф.А. Развитие теории множеств в 19 веке. –Москва, 1965.