МИНИСТЕРСТВО  ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

 ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

 ГОУ ВПО «ЧЕРЕПОВЕЦКИЙ ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ»

 Институт  Информационных Технологий

 Кафедра Прикладной математики

 Дисциплина  Дискретная математика

 Курсовая  работа

     На  тему:  «Счетные и несчетные множества».

                                                  Выполнила студентка

                                                  группы 1 ПМ-21

 Мишичева  В.В.

                                                               Проверил преподаватель

                                                   Данилов А.Н.

  г. Череповец

 2010 г.

Оглавление 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

   Конечные  множества можно сравнивать между  собой по числу содержащихся в  них элементов, причем осуществить такое сравнение можно как с помощью непосредственного подсчета элементов множества, так и без него. Например, пусть нужно сравнить число пальто, сданные в гардероб с числом имеющихся там вешалок. Достаточно повесить каждое пальто отдельно на вешалку. Если каждое пальто удасться повесить на вешалку, и при том свободные вешалок не останется, то это будет означать, что число пальто совпадает с числом вешалок. В противном случае мы обнаружим, что либо пальто имеется больше, чем вешалок, либо число вешалок больше, чем число пальто. Непосредственный подсчет числа теряет смысл при переходе к бесконечным множествам. Однако, второму способу сравнения можно придать такую общую математическую форму, которая позволит производить сравнение в «количественном отношении» также и бесконечных множеств. Тем самым окажется, что и бесконечные множества могут быть по-разному насыщены элементами.

   Перейдем  теперь к точным формулировкам. Пусть  даны множества А и В. Говорят, что между элементами этих множеств установлено взаимно − однозначное отображение, если указано правило, которое каждому элементу а из А ставит в соответствие  один и только один элемент в из В (образ элемента а) и при этом:

1. любые два различных элемента из А имеют различные образы;
2. каждый элемент из В является образом некоторого элемента из А.

   Определение 1. Два множества А и В называются эквивалентными или имеющими одинаковую мощность (равномощными), если между их элементами может быть установлено взаимно-однозначное соответствие. 

   Обозначают  эквивалентность множеств А и В так: А ~ В.

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

   Очевидно, что если А и В − конечные множества, то А ~ В тогда и только тогда, когда |А|=|В|.

   Рассмотрим  примеры эквивалентных между собой множеств:

1. Множество N всех натуральных чисел и множество N₁ всех целых отрицательных чисел эквивалентны. Взаимно однозначное соответствие f между их элементами получится, например, если каждому натуральному числу n сопоставить число −n: f(n)=−n.
2. Множество N натуральных чисел и множество P всех четных положительных чисел эквиваленты. Если каждому n из N сопоставить число 2n из P, то получится взаимно − однозначное соответствие между элементами множеств N и P. Таким образом, N ~ P и при этом P N (P N). Этот пример показывает, что бесконечное множество может быть эквивалентно своей части в собственном смысле (т.е. части, отличной от всего множества). Такое положение не может иметь места для конечных множеств.

Отношение эквивалентности обладает следующими свойствами:

1. Каждое множество эквивалентно себе: А~А (рефлексивность);
2. Если множество А эквивалентно множеству В, то множество В эквивалентно множеству А:  А~В В~А (симметричность);
3. Если А эквивалентно В и В эквивалентно С, то А эквивалентно С: А~В & В~С    А~С ( транзитивность).

§2. Счетные множества и их свойства

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

   Будем обозначать мощность счетного множества  через a.

   Если  N − множество всех натуральных чисел, а множество А~N, то существует взаимно-однозначное соответствие между элементами a А и числами n из N, т.е. можем считать, что каждому a А сопоставлен номер n N, и элемент множества А будем записывать в виде a₁, a₂,…, a_n,…. Здесь через a_n обозначен тот элемент из А, которому сопоставлено число n из N. Таким образом, элементы множества А могут быть расположены в бесконечную последовательность. Обратно, если множество А таково, что его элементы образуют бесконечную последовательность: a₁, a₂,…, a_n,…, то самой нумерацией элементов уже установлено взаимно-однозначное соответствие между элементами множеств А и N, т.е. А~N.

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

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

   Рассмотрим  примеры счетных множеств.

1. Множество всех четных чисел является счетным. Действительно, четные числа могут быть перенумерованы в порядке их возрастания: a₁=2, a₂=4,…, a_n=2n,….
2. Множество всех целых чисел счетно. Эти числа уже не удается перенумеровать ни в порядке возрастания, ни в порядке убывания, но можно сделать это, например, так: a₁=0, a₂=1, a₃=−1, a₄=2, a₅=−2,…, a_2n=n,…, a_2n+1=−n,...

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

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

   Доказательство. Пусть А − бесконечное множество. Возьмем любой его элемент a₁. Кроме элемента a₁ в А имеется еще бесконечное множество элементов. Возьмем любой из них и назовем его a₂. Затем возьмем какой-нибудь элемент из А, отличный от a₁ и a₂ и назовем его a₃. Продолжая этот процесс до бесконечности, мы выделим из А счетное подмножество элементов a₁, a₂,…, a_n,…. Теорема 1 доказана.

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

   Доказательство. Пусть дано счетное множество. Пусть А={ a₁, a₂,…, a_n,…}. Пусть далее В − его бесконечное подмножество. Расположим в порядке возрастания номеров все элементы подмножества В: (n₁<n₂<…n_k<…). Тогда мы сможем перенумеровать их заново натуральными числами, взять по порядку, причем в роли новых номеров будут выступать числа 1,2,…,k,…. Значит множество В счетно. Теорема 2 доказана.

   Теорема 3. Сумма конечного числа счетных множеств − тоже счетное множество.

   Доказательство. Пусть А= ,где все множества А_i счетны. Выпишем элементы множеств А_i в виде следующей таблицы:

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

   Иными словами, мы сначала занумеруем все  элементы первого столбца, за ними −  все элементы второго столбца, и  так далее. Если множества А_i содержат некоторые общие элементы, то один и тот же элемент может повториться в последовательности (2) несколько раз. Однако мы нумеруем его, естественно, только один раз, например тогда, когда, этот элемент впервые встретится в последовательности (2); при последующих встречах с этим элементом мы просто пропускаем его. Таким образом, все элементы множества А могут быть перенумерованы, т.е. А − счетно. Теорема 3 доказана.

   Теорема 4. Сумма счетного множества счетных множеств тоже счетное множество.

   Доказательство. Пусть теперь А= ,где все множества А_i счетны. Выпишем элементы множеств А_i в виде таблицы, аналогичной таблице (1), но содержащей бесконечное множество строк. Элементы такой таблицы можно перенумеровать, но не по столбцам, а , например, по диагоналям, т.е. в таком порядке: a₁₁,a₁₂,a₂₁,a₁₃,a₂₂,a₃₁, ….

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

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

   Доказательство. Каждое рациональное число, не равное нулю, можно представить в виде несократимой дроби  , где n − натуральное число, m − целое число (положительное или отрицательное). При заданном n множество всех дробей вида    (m − целое) счетно. Тогда по Теореме 2 счетно множество A_n всех несократимых дробей вида . Но Q = . Значит Q счетно по Теореме 4. Теорема 5 доказана.

§3. Несчетные множества

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

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

   Теорема 6. Множество всех вещественных чисел отрезка является несчетным.

   Доказательство. Допустим противное, т.е. допустим, что множество вещественных чисел указанного отрезка счетно. Тогда все числа этого отрезка можно занумеровать в бесконечную последовательность при помощи натурального ряда чисел: x₁, x₂,_… , x_n,….

   Разобьем  отрезок  на три равные части и обозначим через ту из этих частей, которая не содержит число x₁. Далее отрезок также разобьем на три равные части и обозначим через ту из этих частей, которая не содержит число x₂ и так далее. Продолжая этот процесс, получим бесконечную последовательность отрезков , ,…, которая обладает тремя свойствами:

1. каждый последующий отрезок последовательности вложен в непосредственно предыдущий и, значит, во все предыдущие;
2. для всякого n N число x_n ;
3. при n длина отрезка стремится к нулю.

   Применим  к этой последовательности отрезков теорему из анализа о вложенных отрезках. По этой теореме существует одно и только одно число c₀, которое принадлежит всем отрезкам последовательности. Это число удовлетворяет неравенствам: и значит оно находится среди чисел : x₁, x₂,_… .

   Пусть число c₀ имеет в последовательности x₁, x₂,_… номер k, т.е. c₀= x_k. Так как c₀= x_k, то c_k по построению последовательности отрезков. С другой стороны, c₀ есть общая точка всех отрезков последовательности отрезков и значит, c₀ . Полученное противоречие показывает, что сделанное допущение неверно и что множество есть несчетное множество. Теорема 6 доказана.

   Определение 4. Будем говорить, что множество А имеет мощность континуума , если оно эквивалентно множеству вещественных чисел отрезка .

   Можно показать, что эквивалентными являются:

1. все интервалы ,
2. все отрезки (сегменты) ,
3. все полуинтервалы и .

   Все они эквивалентны множеству  и поэтому каждое из указанных множеств является множеством мощности континуума. Множество R вещественных чисел и множество I иррациональных ( вещественных чисел) также имеет мощность континуума.

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

   Теорема 7. Сумма (объединение) конечного или счетного множества множеств, имеющих мощность c.

   Теорема 8. Множество Е  всевозможных бесконечных последовательностей натуральных чисел имеет мощность c.

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

   Теорема 9. Пусть множество М состоит из элементов, различаемых n индексами x₁, x₂,_… , x_n, причем каждый из этих индексов независимо от других принимает континуум значений. Тогда множество М= также имеет мощность континуума.

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

   Теорема 10. Множество всех подмножеств множества N натуральных чисел имеет мощность c.

   Дополнением к теореме 7 является следующая теорема.

   Теорема 11. Пусть множество А есть объединение множеств A_x: А= , где x пробегает некоторое множество мощностей c, а каждое из множеств A_x также имеет мощность c. Тогда и множество А имеет мощность c. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

§4. Теорема Кантора-Бернштейна

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

   Доказательство. Пусть имеем множества А и В, и пусть одновременно А~В₁ и В~А₁, где А и . Докажем, что А~В. При этом мы можем считать, что А₁ и В₁ правильные части А и В, так как в противном случае нечего было бы доказывать.

   В силу условия В~А₁, можно установить взаимно-однозначное соответствие между элементами В и А₁, при этом В₁, как правильная часть В, окажется во взаимно-однозначном соответствии с некоторой правильной частью А₂ множества А₁. Тогда будем иметь А~В₁ по условию, В₁~А₂ по построению А₂, поэтому А~А₂, причем . Если бы теперь удалось доказать, что А~А₁, то, учитывая условие В~А₁, мы и получили бы требуемое А~В.

   Таким образом, доказательство теоремы сводится к доказательству утверждения:

   Если  и А~А₂, т.е. множество, содержащееся в одном из двух эквивалентных множеств и содержащее другое из них, само эквивалентно этим множествам.

   Установим взаимно-однозначное соответствие между эквивалентными множествами  А и А₂. Тогда А₁, как правильная часть А, окажется во взаимно-однозначном соответствии с некоторой правильной частью А₃ множества А₂. Следовательно, А₁~А₃ и . Устанавливая теперь взаимно-однозначное между А₁ и А₃ и замечая, что , мы будем иметь взаимно-однозначное соответствие между А₂ и частью А₄ множества А₃. Следовательно, и . Совершенно таким же образом можно построить множество , которое окажется во взаимно-однозначном соответствии с , когда установим взаимно-однозначное соответствие между эквивалентными А₂ и А₄. Продолжая этот процесс, мы получим последовательность множеств:

   причем, в силу построения множеств этой последовательности, будут иметь место соотношения:

   А~А₂, А₁~А₃, А₂~А₄, А₃~А₅, … , А_n~А_n+2, …                                              (1)

   Кроме того, можно заметить, что справедливы  и следующие соотношения: 
 

   Действительно, чтобы убедиться в справедливости этих соотношений, например соотношения ~ , вспомним, как было построено А₃. Установив взаимно-однозначное соответствие между А и А₂, через А₃ мы обозначили ту часть А₂ , которая оказалась во взаимно-однозначном соответствии с , а, следовательно, остальная часть А, т.е. , будет находиться во взаимно-однозначном соответствии с той частью А₂, которая останется при удалении А₃ из А₂, т.е. . Итак, между и существует взаимно-однозначное соответствие, т.е. ~ .

   Таким же образом из построения А₄ следует, что ~ и так далее. Вообще из построения А_n следует, что ~ .

   Теперь  заметим, что для множеств А и А₁, эквивалентность которых мы хотим доказать, имеют место следующие соотношения:                                                           (3)                                                          (4)

   Где

   Докажем хотя бы равенство (3). Пусть x − элемент левой части равенства (3), т.е. . Тогда либо x содержится во всех множествах А, А₁, А₂, … , А_n, … , а значит и в D, поэтому x входит в правую часть равенства (3), либо среди этих множеств есть последнее множество, например, А_n, содержащее x, но в этом случае , так как и , и поэтому опять x будет содержаться в правой части равенства (3). Пусть теперь x есть элемент правой части равенства (3). Тогда либо x содержится в D, а значит и в А, т.е. в левой части равенства (3), либо x содержится в одном из слагаемых вида ; но если , то , а так как , то опять . Итак, любой элемент левой части равенства (3) содержится в правой части, и обратно, что и доказывает справедливость равенства (3). Точно так же можно доказать справедливость равенства (4).

   Докажем наконец, что между элементами правых частей равенств (3) и (4) можно установить взаимно-однозначное соответствие. Действительно, так как в каждый из рассматриваемых сумм слагаемые не имеют попарно общих элементов, то достаточно каждое слагаемое одной суммы поставить во взаимно-однозначное соответствие с определенным слагаемым другой суммы. Но это можно сделать так: второе, четвертое, шестое, и т.д. слагаемые из (3) поставим во взаимно-однозначное соответствие с третьим, пятым, седьмым и так далее слагаемыми из (4), учитывая, что они попарно эквивалентны в силу соотношений (2), а остальные слагаемые в (3) и (4) одинаковые, поэтому достаточно каждое из этих слагаемых суммы (3) поставить во взаимно-однозначное соответствие с таким же слагаемым из суммы (4). Отсюда следует, что правые части равенств (3) и (4) эквиваленты, а значит эквиваленты и левые части, т.е. А~А₁.

    Теорема 12 доказана. 
 
 
 
 
 
 
 

Литература

1. Вулих Б.З.  Краткий курс теории функций  вещественной переменной.− М.:Наука, 1965.

2. Фролов Н.А.  Теория функций действительного  переменного. − М.:Учпедгиз, 1953.

3. Данилов А.Н. Счетные и несчетные множества (конспект лекций).