Избранные главы дискретной математики

 

      Многие доказательства счетности множеств можно провести с помощью их диагональной записи, предложенной Г. Кантором. Так Кантор доказал счетность множества рациональных чисел: 
 
 
 
 
 
 
 
 
 
 
 
 

     Бесконечное множество рациональных чисел (т.е. чисел, которые можно представить  как частное двух целых чисел) могло бы показаться значительно  бóльшим, чем множество целых чисел. Например, между двумя любыми соседними целыми числами, допустим 0 и 1, имеется бесконечно много рациональных чисел. Тем не менее в 1874 г. Кантор показал, что рациональные числа можно одно за другим объединить в пары с целыми числами. Всякое рациональное число можно разместить в квадратной таблице, как показано на рисунке. Тогда каждое из них может быть связано с целым числом путём проведения цветной линии. Таким образом, множество рациональных чисел является счётным.

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

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

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

     Примеры несчетных множеств:

• Вещественные числа
• Комплексные числа

 

     Доказательство  существования несчетных  множеств.

     Множество всех действительных чисел несчетно и равномощно интервалу (0,1). Докажем несчетность последнего.

     Будем считать известным, что каждое число  интервала (0, 1) записывается в виде конечной или бесконечной десятичной дроби вида 

     0, a₁ a₂ a₃ ... 

     При этом хотя бы одна из цифр a_i отлична от нуля (т. к. число 0 = 0,000... не принадлежит интервалу). Далее, для чисел, имеющих запись в виде конечной десятичной дроби, существует и другая запись, где все цифры a_i, начиная с некоторого места, равны 9. Например, 

     0,53000... = 0,52999... 

     Остальные числа (т. е. иррациональные и те рациональные, которые разлагаются в периодическую  дробь с периодом, не равным 9) имеют  единственную запись. Из двух возможных  записей для первых чисел выберем  какую-нибудь одну, например, в виде конечной десятичной дроби. Тогда все  числа интервала (0, 1) будут единственным образом записываться в виде 

     0, a₁ a₂ a₃ ..., 

     где не все a_i равны 0 и никогда все цифры, начиная с некоторой, не могут равняться 9. Обратно, всякая десятичная дробь дает число интервалов (0, 1).

       Легко видеть, что интервал (0, 1) есть бесконечное множество, т. к. он содержит множество 
 

     равномощное множеству натуральных чисел. Покажем, что (0, 1) не является счетным множеством.

     Предположим обратное. Тогда все числа интервала  можно занумеровать так: 

     (0, 1) = {c₁, c₂, c₃, ...}. 

     Запишем каждое число десятичной дробью указанного вида: 

        (1.1) 

     Построим  число 

     c = 0, b₁ b₂ b₃ ... 

следующим образом: берем цифру b₁, отличную от a₁₁, 0 и 9; берем b₂, отличную от a₂₂, 0 и 9; b₃, отличную от a₃₃, 0 и 9; b_n, отличную от a_nn, 0 и 9, ... Наличие десяти цифр оставляет для такого выбора достаточно возможности (именно, каждый раз в нашем распоряжении остается еще семь цифр). Дробь 0, b₁ b₂ b₃... обладает нужными свойствами и даже в усиленной форме — она вовсе не имеет цифр 0 и 9. Значит, число c принадлежит интервалу (0, 1). Но запись c отлична от записей всех чисел (1.1). В самом деле, запись c отличается от c₁, т. к. b₁ ≠ a₂₂, от c₂, т. к.  и т. д. Но дробью нашего типа числа интервала записываются однозначно. Значит, 

     c ≠ c₁, c ≠ c₂, c ≠ c₃,.., c ≠ c_n,… 

     Оказалось, что число c не входит во множество чисел (1.1), тогда как мы предположили, что в (1.1)перенумерованы все числа интервала. Полученное противоречие доказывает наше утверждение. 

 

§3 Трансфинитные числа и множества

     Порядковое  число, или трансфинитное число, или ординал в теории множеств — некоторое обобщение понятия натурального числа «за пределы бесконечности».  

     История

     Впервые введены Георгом Кантором в 1897 году с целью классификации вполне упорядоченных множеств. Играют ключевую роль в доказательстве многих теорем теории множеств, в особенности в  связи со связанным с ними принципом  трансфинитной индукции.

     Между точками плоскости и точками  прямой можно установить взаимно  однозначное соответствие.

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

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

     Трансфинитные числа, введённые в конце концов Кантором, широко известны в обозначении, которое он принял для них позже: в виде буквы א (алеф) — первой буквы еврейского алфавита. Этой буквой обозначается мощность, или число элементов бесконечного множества, так что отношения эквивалентности между бесконечными множествами, которые Кантор доказал в 70-х годах, часто выражают через трансфинитные кардинальные числа, алефы. Поэтому значительный исторический интерес представляет то, что первыми трансфинитными числами были не кардинальные числа, а ординальные.

     Ординальное число определяется его порядком или положением в некотором перечне. Этот перечень порождается в соответствии с двумя принципами.

     Во-первых, каждое новое ординальное число получается из непосредственно предшествующего ординального числа добавлением одной единицы, в точности также как если бы мы «считали» за пределами трансфинитного ординального числа ω, т.е. числа, связанного с множеством целых чисел, расположенных в их естественном порядке.

     Во-вторых, если существует последовательность трансфинитных ординальных чисел, у которой нет наибольшего числа, то новое ординальное число определяется как следующее число, большее всех остальных чисел последовательности. Такие числа помещаются в перечне непосредственно после отметки пропуска. Например, 2ω представляет собой следующее трансфинитное ординальное число, большее всех чисел ω, ω+1, ω+2, ... На рисунке представлены два примера множеств, соответствующих ординальным числам ω, ω+1, ω+2, и 2ω. Однако всякое бесконечное множество, представляемое ординальным числом этого перечня, имеет одно и то же кардинальное число, а именно 0א, другими словами, каждое множество содержит одно и то же число элементов.

     Ординальное число, ассоциируемое с конечным множеством, соответствует кардинальному  числу этого множества. Например, всякое множество, состоящее из пяти элементов (т.е. всякое множество, кардинальное число которого равно пяти), можно в некотором роде мыслить как непосредственно следующее за любым множеством из четырёх элементов. Другими словами, ординальное число этого множества тоже равно пяти; оно является пятым множеством в перечне множеств. Однако ординальное число бесконечного множества следует отличать от его кардинального числа. Кантор показал, что можно построить бесконечное число бесконечных множеств, имеющих различные ординальные числа, но одно и то же кардинальное число. Фактически Кантор позднее сумел превратить это свойство бесконечных множеств в критерий отличия их от конечных множеств: множество конечно, если его кардинальное и ординальное числа совпадают.

     Кантор  показал, что ординальное число последовательности конечных множеств возрастающей величины 1, 2, 3, ... получается путём повторного прибавления единицы. Не существует наибольшего ординального числа, ассоциированного с последовательностью конечных множеств, но, так же как возможно определить иррациональное число π в виде предела последовательности рациональных чисел, можно, как считал Кантор, определить новое, трансфинитное ординальное число ω как первое число, следующее за всей последовательностью числе 1, 2, 3, ... . Как только ω определено, становится возможным путём последовательного прибавления единицы порождать другие трансфинитные ординальные числа: ω+1, ω+2, ω+3, ... . Поскольку у этой последовательности не существует наибольшего элемента, то можно представить следующее ординальное число ω+ω или 2ω в виде первого ординального числа, следующего за последовательностью ω+1, ω+2, ω+3, ... . Повторяя попеременно эти два принципа порождения, Кантор определил некую иерархию трансфинитных ординальных чисел: 

 

§4 Теория нечетких множеств

     Нечёткое (или размытое, расплывчатое, туманное, пушистое) множество — понятие, введённое Лотфи Заде в 1965 г. в статье «Fuzzy Sets» (нечёткие множества) в журнале «Information and Control». Л. Заде расширил классическое канторовское понятие множества, допустив, что характеристическая функция (функция принадлежности элемента множеству) может принимать любые значения в интервале [0,1], а не только значения 0 или 1.

     Определение

     Под нечётким множеством A понимается совокупность

     где X — универсальное множество, а — функция принадлежности (характеристическая функция), характеризующая степень принадлежности элемента x нечёткому множеству A.

     Функция принимает значения в некотором вполне упорядоченном множестве M. Множество M называют множеством принадлежностей, часто в качестве M выбирается отрезок [0,1]. Если M = {0,1}, то нечёткое множество может рассматриваться как обычное, чёткое множество.

     Для пространства рассуждения X и данной функции принадлежности нечёткое множество определяется как 
 
 

     Функция принадлежности количественно градуирует принадлежность элементов фундаментального множества пространства рассуждения нечёткому множеству . Значение 0 означает, что элемент не включен в нечёткое множество,  описывает полностью включенный элемент. Значения между 0 и 1 характеризуют нечётко включенные элементы.

     

     Основные  определения

     Пусть A нечёткое множество с элементами из универсального множества X и множеством принадлежностей M = [0,1]. Тогда

• Носителем (суппортом) нечёткого множества supp A называется множество

.

• Величина

 
 

называется  высотой нечёткого множества  A. Нечёткое множество нормально, если его высота равна 1. Если высота строго меньше 1, нечёткое множество называется субнормальным.

• Нечёткое множество пусто, если . Непустое субнормальное нечёткое множество можно нормализовать по формуле:

 

.

• Нечёткое множество унимодально, если только на одном x из X.
• Элементы , для которых , называются точками перехода нечёткого множества A.

Операции  над нечёткими  множествами

При M = [0,1]

• Пересечением нечётких множеств A и B называется наибольшее нечёткое подмножество, содержащееся одновременно в A и B: