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

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

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

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

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

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

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

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

   

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

                                                  группы 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₂,_… .