Глава 2. Числовые множества § 2.1. Множества: определение и основные свойства Множество (по Тьюрингу) – это объединение в одно общее объектов, хорошо различимых нашей интуицией или нашей мыслью.Можно привести другое определение множества:Множество (по Кантору) – это совокупность объектов безразлично какой природы, неизвестно существующих ли, рассматриваемая как единое целое.Дополнительные определения и операции над множествами Множество, которое не имеет ни одного элемента, называется пустым и обозначается Ø. Единичное множество – множество, все элементы которого тождественны. Множество М1 называется подмножеством множества М тогда и только тогда, когда любой элемент множества М1 принадлежит множеству М. Множества называются равными, если они имеют одни и те же элементы. Подмножество М1 множества Мназывается собственным подмножеством множества М, если М1 является его подмножеством, но при этом существует хотя бы один элемент, принадлежащий М, но не принадлежащий М1. Пусть А и В – два множества. Множество М=А U В такое, что его каждый элемент принадлежит А или В (а возможно и А и В), называется суммой или объединением множеств А и В. Пусть А и В – два множества. Множество М=А ∩ В такое, что его каждый элемент принадлежит и А и В одновременно, называется пересечением множеств А и В. Пусть А и В – два множества. Множество М=А \ В такое, что оно состоит из тех элементов множества А, которых нет во множестве В, называется разностью множеств А и В, или дополнением В до А. Пусть А и В – два множества. Множество М=А × В такое, что оно образовано из всех пар (a, b) таких, что a принадлежит A и b принадлежит B, называется декартовым произведением множеств А и В. ^ Пусть А = {а,b}; В = {m,n} Тогда А×В = {(a,m),(a,n),(b,m),(b,n)} Пусть А – множество. Множество М, элементами которого являются подмножества множества А, включая само А и пустое множество, называется множеством всех подмножеств множества А или булеаном А и обозначается Р(А).^ Пусть А = {а,b,c} Тогда M= Р(А)={Ø, (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)} Отображением f множества А в множество В называется некое правило, по которому каждому элементу множества А ставят в соответствие элемент множества В. Множество всех отображений множества А в В обозначается как ВА (В в степени А).Пусть А = {а,b,c}; В = {m,n} Тогда ВА это набор функций fi приведенных в таблице 2.1 (1). Таблица 2.1 (1) A f1(A) f2(A) f3(A) f4(A) f5(A) f6(A) f7(A) f8(A) a m m m m n n n n b m m n n m m n n c m n m n m n m n Каждая такая функция задана своими значениями в каждой из трех точек области определенности.^ § 2.2. Классификация множеств Мощность множества (по Кантору) – это та общая идея, которая остается у нас, когда мы, мысля об этом множестве, отвлекаемся как от всех свойств его элементов, так и от их порядка.Можно привести другое определение мощности:^ Мощность множества – это характеристика, которая объединяет данное множество с другими множествами, применение процедуры сравнения к которым дает основание предполагать, что каждый элемент одного множества имеет парный элемент из другого множества и наоборот. Далее мощность будем называть кардинальным числом множества.Кардинальные числа некоторых множеств1. Мощность пустого множества равна 0: | Ø |=0. 2. Мощность множества из одного элемента равна 1: |{a}|=1. 3. Если множества равномощны (A~B), то их кардинальные числа равны: |A|=|B|. 4. Если А - подмножество В и C: (A~C)&(C B), то кардинальное число А не превосходит кардинального числа В, т.е. |A|≤|B|. 5. Мощность булеана множества А равна 2|А|: |P(A)|=2|А| 6. Мощность множества всех отображений А в В равна |В|А||: |ВА|=|В|А||Конечные, счетно-бесконечные и несчетные множества чиселМожно классифицировать множества, опираясь на такой признак, как конечность. ^ Конечное множество – множество, состоящее из конечного числа элементов, его кардинальное число совпадает с одним из натуральных чисел. В противном случае множество называется бесконечным. Тогда все множества делятся на два класса конечные и бесконечные, которые в свою очередь делятся на два подкласса: счетно-бесконечные и несчетные.Счетно-бесконечные - бесконечные множества, равномощные множеству натуральных чисел (их элементы можно пронумеровать натуральными числами без пропусков и повторений).Несчетные - бесконечные множества, не равномощные множеству натуральных чисел.Можно классифицировать множества и по другому признаку: счетности. Тогда все множества делятся на два класса: счетные и несчетные. Счетные множества в свою очередь делятся на два подкласса: конечные и счетно-бесконечные.Счетное множество – это множество, являющееся конечным или счетно-бесконечным.Важное свойство конечных множеств: конечные множества не равномощны никакому своему собственному подмножеству. Важное свойство бесконечных множеств: бесконечное собственное подмножество бесконечного множества может быть равномощно самому множеству (внимание, именно «может быть», а вовсе не «всегда» - пример тому несчетные множества, рассмотренные далее). Иллюстрацией данного факта могут служить два известных парадокса.Т.2.2.(1) Парадокс ГалилеяХотя большинство натуральных чисел не является квадратами, всех натуральных чисел не больше, чем квадратов (если сравнивать эти множества по мощности). Доказательство Рассмотрим множество квадратов натуральных чисел: 1, 4, 9, 16, 25, 36,… Назовем его N1. Пусть его мощность равна |N1|. По построению N1 N (N1собственное подмножество N). Пронумеруем множество N1 натуральным рядом: 1 , , , , , , Т.о. можно построить взаимнооднозначное соответствие, доказав, что |N1|=|N|, значит, квадратов натуральных чисел столько же, сколько и самих натуральных чисел, Q.E.D. Т.2.2.(2) Парадокс ГильбертаЕсли гостиница с бесконечным количеством номеров полностью заполнена, в неё можно поселить ещё посетителей, даже бесконечное число. Доказательство Первого постояльца следует поселить во второй номер, второго – в третий, далее аналогично, n-ого в (n+1)-ый. Поскольку номеров бесконечное количество, места всем хватит, т.к. для каждого натурального n найдется число n+1. Подобную процедуру можно повторять столько, сколько потребуется, Q.E.D. Это оригинальная версия парадокса, в ней под бесконечным числом постояльцев следует понимать счетно-бесконечное число. Для обозначения мощности конечных множеств используются натуральные числа. Для обозначения мощности бесконечных множеств нужны числа иного рода, их называют трансфинитными.Трансфинитное число (finis – “конец”, лат.) – кардинальное число бесконечного множества.Алеф-нуль (– первое трансфинитное число. По определению это мощность множества всех натуральных чисел. Это наименьшая бесконечная мощность. ^ § 2.3. Счетные множества Счетно-бесконечными также будут все множества, для которых удастся доказать равномощность с множеством натуральных чисел. Далее в этой главе для краткости и соответствия общепринятым формулировкам теорем, вместо термина «счетно-бесконечные» при доказательстве равномощности рассматриваемого множества и множества натуральных чисел будет использоваться термин «счетные». Это не является ошибочным утверждением, любое счетно-бесконечное множество является счетным, но не наоборот. Строго говоря, доказать факт того, что множество счетное проще, чем доказать том факт, что оно счетно-бесконечное (в последнем случае требуется показать, что множество не является конечным). Для доказательства того, что множества равномощны, обычно используется какой либо способ, позволяющий поставить в соответствие каждому элементу рассматриваемого множества какое-то натуральное число. Подобный прием использовался при доказательстве Теорем 2.2.(1) и 2.2.(2). В общем случае оказывается вовсе необязательным конкретное указание эффективного способа установления такого соответствия. Достаточно доказательства самого факта. Более того, если в процессе доказательства равномощности такой (обязательно эффективный, т.е. основанный на алгоритме) способ будет найден, то помимо собственно требуемого доказательства счетности, попутно будет доказан факт эффективной перечислимости исследуемого множества. При этом уже становится обязательным наличие процедуры, которая устанавливает взаимно - однозначное соответствие между элементами исследуемого множества и элементами множества натуральных чисел. Помимо указанного способа, зачастую используется методика оценки кардинального числа множества сверху и снизу, что зачастую позволяет точно вычислить реальное значение мощности исследуемого множества. В дальнейшем в ряде задач рассматривается «расширенное» множество натуральных чисел, включающее в себя стандартный ряд натуральных чисел (1,2,3,…) и число 0. Доказательство равномощности этих множеств не составляет труда. Будем обозначать множество натуральных чисел буквой N, а расширенное множество натуральных чисел N*. Обычное и расширенное множество натуральных чисел являются эффективно перечислимыми (первое по определению, второе по причине простейшего установления нумерации 0->1, 1->2, 2->3,….и т.д., позволяющей установить взаимно-однозначное соответствие между элементами исследуемого множества и элементами множества натуральных чисел). Стоит также отметить, что любое конечное множество также эффективно перечислимо. Важно обратить особое внимание на тот факт, что исходя из сформулированных определений, счетность конкретного множества вовсе не означает, что это множество гарантированно будет эффективно перечислимым. Более того, как будет показано в последующем, найдутся множества, являющиеся счетными и эффективно не перечислимыми одновременно.2.3.1. Множество целых чиселМножество целых чисел – множество, состоящее из натуральных чисел, числа ноль и чисел, построенных на основе натуральных только со знаком «минус» (отрицательных чисел).Т.2.3. (1) Теорема Множество целых чисел счетно и эффективно перечислимо.Доказательство Ряд целых чисел: -n, …, -3,-2,-1,0,1,2,3,…, n,…Будем обозначать множество целых чисел буквой Z. Расположим целые числа следующим образом: 0, 1, -1, 2, -2, 3, -3, …., n, -n, … Тогда каждому числу можно поставить в соответствие натуральное число 0, 1, -1, 2, -2, 3, …., n, -n, … 1, 2, 3, 4, 5, 6, …., 2n, 2n+1, … Таким образом доказано, что множество Z равномощно множеству N, а значит оно счетно. Для доказательства эффективной перечислимости множества Z необходимо установить тот факт, что все элементы множества Z могут быть перебраны по алгоритму и должны получить в результате такого перебора порядковые номера, без пропусков и повторений. Факт эффективной перечислимости множества Z напрямую следует из приведенного способа нумерации элементов натуральными числами. Итак, множество Z счетно и эффективно перечислимо, Q.E.D. Если оперировать трансфинитными числами, получим: +1+ = ^ 2.3.2. Множество упорядоченных пар натуральных чиселДва элемента a и b называют упорядоченной парой, если указано, какой их этих элементов первый, а какой второй и при этом ((a,b)=(c,d))(a=c)^(b=d). Упорядоченную пару элементов обозначают (a,b).Т.2.3. (2) Теорема Множество упорядоченных пар натуральных чисел счетно и эффективно перечислимо.Доказательство Обычно, употребляя термин «упорядоченная» пара считают, что допустим пара (1,5) и пара (5,1) имеют разный смысл и рассматриваются как различные. Чтобы установить взаимно-однозначное соответствие между упорядоченными парами натуральных чисел и натуральными числами, достаточно расположить пары (p,q) в таблицу так, что (p,q) находится в p-ой строке и в q-ом столбце. (1,1) (1,2) (1,3) ... (2,1) (2,2) (2,3) … … … … … Затем указанные пары перечисляются диагональным методом, начиная с левого верхнего угла. Последовательность обхода матрицы по сути может быть любой. Например, можно расположить пары в последовательность по возрастающей сумме p + q, а при равной сумме – по возрастанию p. Получим ряд: n 1 2 3 4 5 6 … (p,q) (1,1) (1,2) (2,1) (1,3) (2,2) (3,1) … Таким образом доказано, что множество упорядоченных пар натуральных чисел равномощно множеству N, а значит, оно счетно. Иногда под термином «упорядоченные» понимают ситуацию, при которой в паре (p,q) например, гарантированно p ≤ q, т.е. первый член пары меньше или равен второму. В этом случае пары (p,q) и (q,p) считаются тождественными, т.е. пара воспринимается как неупорядоченное множество из двух элементов, в котором на первом месте пишется меньшее число, а на втором – большее. Множество таких пар является собственным подмножеством множества рассмотренных выше пар и по логике вещей тем более будет счетно. Факт эффективной перечислимости множества упорядоченных пар натуральных чисел независимо от конкретной трактовки термина «упорядоченный» представляется вполне очевидным. В первом случае он напрямую следует из приведенного способа нумерации элементов натуральными числами. Во втором случае к предложенному алгоритму перечисления необходимо добавить процедуру проверки соотношения между элементами p и q, и если, например, p≤q, то присваивать очередной номер этой паре, а в противном случае пропускать её. Итак, множество упорядоченных пар натуральных чисел счетно и эффективно перечислимо, Q.E.D. Если оперировать трансфинитными числами, то при основной трактовке термина «упорядоченные» получим что • = . Важно, что при второй трактовке этого термина, получим тот же результат. Действительно, (•-)/2+= (на основе алгоритма построения пар формируем матрицу, из матрицы формата на выбрасываем элементы главной диагонали, остальное множество при сокращаем вдвое и добавляем обратно элементы главной диагонали).^ 2.3.3. Множество упорядоченных n-ок натуральных чиселУпорядоченная n-ка натуральных чисел – это набор из n элементов вида (m1, m2, …, mn), где mi– натуральное число.Т.2.3. (3) ТеоремаМножество упорядоченных n-ок натуральных чисел счетно и эффективно перечислимо.Доказательство Чтобы установить взаимно-однозначное соответствие между упорядоченными n-ками натуральных чисел и натуральными числами, достаточно расположить разложить n-ку вида (m1, m2, m3,…,mn) следующим образом: (m1, m2, m3,…,mn) = (m1, (m2, m3,…,mn)) = (m1, (m2, (m3,…,mn))) = =(m1, (m2, (m3, (…(mn-1,mn))))) Расположив по горизонтали таблицы пары натуральных чисел, а по вертикали – натуральные числа, диагональным методом получим нумерацию троек натуральных чисел. Далее по горизонтали таблицы располагаются тройки натуральных чисел, а по вертикали – натуральные числа, диагональным методом получаем нумерацию четверок натуральных чисел и т.д. Таким образом доказано, что множество n-ок натуральных чисел равномощно множеству N, а значит оно счетно. Факт эффективной перечислимости множества напрямую следует из приведенного способа нумерации элементов натуральными числами. Итак, множество упорядоченных n-ок натуральных чисел счетно и эффективно перечислимо, Q.E.D.Если оперировать понятием кардинального числа (мощности), то получим, что произведенное n раз (n - натуральное число) умножение первого трансфинитного числа само на себя не изменяет его значения • •… • = или n= ^ 2.3.4. Множество конечных комплексов натуральных чиселКонечные комплексы натуральных чисел - это элементы вида (p1), (p1, p2), (p1, p2, p3), …, (p1, p2, …, pk), где k и piпробегают все натуральные числа.Т.2.3. (4) ТеоремаМножество конечных комплексов натуральных чисел счетно и эффективно перечислимо.Доказательство Чтобы установить взаимно-однозначное соответствие между конечными комплексами натуральных чисел и натуральными числами, можно использовать двоичное разложение вида: n=2^(p1-1) + 2^(p1+p2-1)+ …+2^(p1+p2+ …+pk -1), где ^ - значок степени. Например, в двоичном коде 27 = 11011= 1•20 + 1•21 +0•22 +1•23 +1•24 = 20 + 21 +23 + 24, откуда получим: p1-1 = 0 p1=1 p1=1 p1+ p2 -1 = 1 p1+ p2=2 p2=1 p1+ p2 + p3 -1 = 3 p1+ p2 + p3 = 4 p3 =2 p1+ p2 + p3 + p4 -1 = 4 p1+ p2 + p3+ p4 = 5 p4 =1 Итак, натуральное число 27 является кодом комплекса (1,1,2,1). В свою очередь комплексу (2,1,1,1) соответствует следующий код: p1-1 = 2 -1 = 1 p1+ p2 -1 = 2 + 1 – 1 = 2 p1+ p2 + p3 -1 = 2 + 1 - 1 -1 = 3 p1+ p2 + p3 + p4 -1 = 2 + 1 – 1 + 1 – 1 = 4 В итоге число n = 21 + 22 + 23 + 24 = 11110 (в двоичном коде) или 2 + 4 + 8 + 16 = 30 ( в десятичном коде). Таким образом, комплексу (2,1,1,1) соответствует натуральное число 30. В результате доказано, что множество конечных комплексов натуральных чисел равномощно множеству N, а значит оно счетно. Факт эффективной перечислимости множества напрямую следует из приведенного способа нумерации элементов натуральными числами. Итак, множество конечных комплексов натуральных чисел счетно и эффективно перечислимо, Q.E.D. Если оперировать трансфинитными числами, то получим: +2+3 +…+k= k == k• = ^ 2.3.5. Множество рациональных чиселРациональное число - число вида , где n – целое число, m – натуральное число.Т.2.3. (5) ТеоремаМножество рациональных чисел счетно и эффективно перечислимо.Доказательство Обозначим множество рациональных чисел Q. Рассмотрим сначала положительные рациональные числа – множество Q+. Определим положительное рациональное число как q=n/m, где n и m – натуральные числа. Запишем их в виде бесконечной матрицы, строки и столбцы которой пронумерованы натуральными числами начиная с 1. Элемент, стоящий на пересечении i-ой строки и j-ого столбца, получит наименование qij Используя диагональный метод, перечислим их (пронумеруем натуральными числами):q11 q21 q12 q13 q22 q31 q41 q32 q23 q14 q15 q24 q33 1 2 3 4 5 6 7 8 91 2 3 4 1 q11 q12q13 q14 …2 q21q22 q23 q24 …3 q31q32 q33q34 ……………………………….……...n qn1qn2……………….…… ………………………..……..…… Все (и положительные, и отрицательные) рациональные числа в совокупности перечисляются по аналогии с целыми числами, путем чередования положительной дроби и её отрицательного аналога. При этом некоторые рациональные числа мы нумеруем по нескольку раз: например, 1 будет пронумерована как 1/1, 2/2, и т.д., а например 4/5 как 8/10, 12/15 и т.д. Т.о., показано, что множество рациональных чисел не превосходит по мощности множество натуральных чисел, |Q|≤|N|, т.к. каждое рациональное число получит соответствующий номер, а если быть точным – то даже несколько номеров. С другой стороны то, что множество натуральных чисел не превосходит по мощности множество рациональных чисел очевидно, |N|≤|Q| (хотя бы потому, что оно является его подмножеством). Т.о. доказано, что множество рациональных чисел равномощно множеству натуральных чисел |Q|=|N| = , а значит оно счетно. Факт эффективной перечислимости множества Q напрямую следует из приведенного способа нумерации элементов натуральными числами. В ходе этой нумерации каждое рациональное число получает соответствующий номер, и если к алгоритму добавить процедуру, проверяющую дробь на предмет сокращаемости (если числитель и знаменатель имеют общие делители) и исключающую из нумерации сокращаемые дроби, то мы в чистом виде получим перечисление рациональных чисел по алгоритму без пропусков и повторений, что совпадает с определением эффективной перечислимости. Итак, множество рациональных чисел счетно и эффективно перечислимо, Q.E.D. Это вероятно следующий, после парадоксов Галилея и Гильберта, не вполне очевидный и по началу воспринимаемый как парадоксальный, факт. Ведь множество рациональных чисел расположено на прямой повсюду плотно, и между любыми двумя рациональными числами существует другие рациональные числа, однако мощность множества таких чисел оказывается не больше, чем у множества целых или натуральных чисел. ^ 2.3.6. Множество действительных алгебраических чиселАлгебраическое действительное число – действительный корень алгебраического уравнения ненулевой степени с рациональными коэффициентами.Множество алгебраических действительных чисел обозначим латинской буквой А. Общий вид алгебраического уравнения: a0+a1∙x1+a2∙x2+…+an∙xn=0, где a0, a1,…- рациональные коэффициенты. Исходя из определения, можно утверждать, что рассмотренные ранее классы натуральных, целых и рациональных чисел являются подмножествами множества алгебраических чисел.Т.2.3. (6) Теорема Множество алгебраических чисел счетно и эффективно перечислимо.Доказательство Доказательство построим привычным образом, а именно предложим процедуру нумерации всех алгебраических чисел числами натурального ряда. При этом каждое число будем задавать через образующее его алгебраическое уравнение. Так, для линейных уравнений будем иметь упорядоченные пары рациональных чисел, для квадратных уравнений – тройки, в общем случае получаем упорядоченную n-ку рациональных чисел: (ai1,ai2…ain) для каждого i-ого алгебраического уравнения (n-1)-ой степени. Располагать элементы будем в двусторонне бесконечной матрице. Выпишем на первой строке будущей матрицы все упорядоченные пары рациональных чисел. Это возможно, т.к. пары рациональных чисел эффективно перечислимы (рациональные числа эффективно перечисляются, их можно записать в матрицу и перечислить пары чисел диагональным способом). Такие пары рациональных чисел соответствуют линейным уравнениям и имеют по одному корню: т.о. каждая пара однозначно определяет корень линейного уравнения. На второй строке выпишем все упорядоченные тройки рациональных чисел. Это возможно, т.к. тройки рациональных чисел эффективно перечислимы (рациональные числа эффективно перечисляются, их пары тоже эффективно перечисляются, значит можно записать в матрицу по строкам пары, по столбцам числа и перечислить тройки чисел диагональным способом). Такие тройки соответствуют квадратным уравнениям и имеют максимум по два корня: таким образом, в процессе формирования матрицы каждую тройку рациональных чисел нужно будет повторить два раза для обеспечения процесса получения соответствующего номера для двух чисел, являющихся решением соответствующего уравнения. На третьей строке – по три числа на каждое кубическое уравнение соотв. упорядоченным четверкам и т.д. Т.о. получим матрицу, которую можно обойти при помощи диагонального процесса Кантора. Если часть корней алгебраического уравнения комплексная, при нумерации их просто пропускаем. Т.о. каждое алгебраическое число получит соответствующий номер, и это подтверждает тот факт, что множество алгебраических действительных чисел счетно. Факт эффективной перечислимости множества А напрямую следует из приведенного способа нумерации элементов натуральными числами, т.к. попутно указана эффективная процедура нумерации наборов рациональных чисел, однозначно задающих алгебраические уравнения соответствующей степени. При этом важно то, что алгебраическое уравнение n-ой степени имеет эффективный алгоритм решения, т.о. процедура полностью эффективна. Итак, множество алгебраических действительных чисел счетно и эффективно перечислимо, Q.E.D. Счетными также будут множества, составленные из всех пар, троек, и т.д. алгебраических чисел. ^ 2.3.7. Счетные числовые множества: обобщениеТ.2.3. (7) Теорема (без доказательства)Множество элементов, которые можно представить с помощью конечного числа счетной системы знаков, счетно. В реальной жизни мы используем различные конечные системы знаков, например цифры, буквы, ноты. Рассмотрим систему знаков, например, числа в любой конечной системе счисления, допустим десятичной. Имея 10 знаков в нашем распоряжении: 0,1,2,3,4,5,6,7,8,9 мы можем составлять два типа множеств: фиксированной длины и произвольной длины. В первом случае речь идет о чисто комбинаторной задаче, например можно составить 105 различных последовательностей из пяти символов. Это немаленькое число, но оно натуральное и мощность рассматриваемого множества всех возможных последовательностей такого рода выражается натуральным числом. Во втором случае множество таких последовательностей будет счетно-бесконечно, по аналогии с множествами комплексов натуральных чисел, и его мощность есть число алеф-ноль. Можно обобщить, что полученное в результате применения Теоремы 2.3.(7) множество будет счетно-бесконечно, если в случае конечной системы знаков допустить сколь угодно длинные комплексы знаков (сколько угодно длинные, но при этом все равно конечные!). Счетно-бесконечными являются, например: множество «слов», которое можно составить при помощи конечного алфавита («слово» здесь - комплекс букв, не важно имеющих смысл или нет), множество всех книг, написанных на любом или даже на всех языках, множество всех симфоний и т.д.^ § 2.4. Несчетные множества 2.4.1. Несчетность множества действительных чисел (континуума)Множество действительных чисел обозначим латинской буквой R.Т.2.4. (1) ТеоремаМножество действительных чисел несчётно.ДоказательствоПредположим противное, пусть множество действительных чисел счетное. Тогда любое подмножество счетного множества тоже счетное. Возьмём на множестве действительных чисел подмножество R1 - интервал (0,1) и выкинем из этого отрезка числа, содержащие хотя бы в одном своём разряде нули или девятки (примеры таких чисел: 0.9, 0.0001 и т.д.). Множество R2, составленное из оставшихся чисел, является подмножеством множества R1 . Это означает, что R2 – счетное. Из того факта, что R2 – счетное, напрямую следует, что возможен какой-либо способ перечисления его элементов для установления взаимно-однозначного соответствия между элементами R2 и элементами множества натуральных чисел. Это следует из самого определения мощности множества, согласно которому предполагается, что в равномощных множествах каждый элемент одного множества имеет парный элемент из другого множества и наоборот. Обратите внимание, фундаментальное отличие данного определения от определения эффективной перечислимости состоит в том, что в данном случае мы даже не говорим о наличии какого-либо алгоритма перечисления, мы просто утверждаем, что можно привести список действительных чисел из множества R2 и список соответствующих им натуральных чисел из множества N. Алгоритм построения связи N ↔ R2 нас в данном случае не интересует, достаточно того, что такое соответствие возможно. Построим такой список чисел из множества R2 и пронумеруем числа в разрядах: 0.a11a12a13… 0.a21a22a23… …………… 0.an1an2an3… Теперь построим число b=0.b1b2…, причём bi=aii+1, где + обозначает операцию сложения, результатом которого не могут быть числа 0 и 9, т.е. если aii=1, то bi=2; если аii=2, то bi=3, …., если aii=8, то bi=1). Таким образом, построенное число b будет отличаться от каждого из чисел множества R2 хотя бы в одном разряде, и, следовательно, не попадёт в составленный список. Однако по своей структуре число b должно содержаться в множестве R2. Получили противоречие, значит исходное предположение неверно и множество R2 - несчётно. Так как множество R2 является по условию подмножеством множества R1, то R1 – несчетно, а т.к. R1 несчетно – то значит и множество R несчётно, Q.E.D.Примечание: можно и не выбрасывать числа, содержащие 0 и 9. Таким образом, в наш ряд некоторые числа войдут дважды. Это связано с тем, что конечные дроби могут быть превращены в бесконечные. Например ½=0,5=0,5(0)=0,4(9). В общем случае это могло стать причиной того, что не удалось сосчитать множество действительных чисел. Но множество чисел, представимых двояким образом (конечные дроби) – это множество рациональных чисел. Как было доказано ранее, их счетное количество. Можно даже показать, что это множество эффективно перечислимо. Т.о. даже двойное представление множества таких чисел образует счетное множество, следовательно, доказательство верно даже без такого упрощения. Получен принципиально новый результат – найдено несчетное множество чисел. Его мощность согласно доказанной теореме не равна алеф-нуль (, а значит необходимо новое число в трансфинитной шкале.Алеф (– второе трансфинитное число. По определению это мощность континуума (всех действительных чисел). Это вторая по величине бесконечная мощность. Доказанная только что Теорема 2.4.(1) о несчетности множества действительных чисел является убедительным доказательством того, что мощность этого множества больше, чем алеф-ноль (больше множества натуральных чисел). И это весьма важный результат после череды доказательства счетности разнообразных множеств чисел. Если оперировать понятием кардинального числа (мощности), то получим, что, так как каждое число сегмента (0,1) может быть представлено десятичной дробью вида 0.a1a2a3… не менее одного раза и не более двух, то: ≤10 ≤2 , а т.к. 2=, то получим что 10 =. Те же рассуждения справедливы в случае, если мы будем разлагать числа не в десятичные, а, например, в двоичные дроби, дроби с основанием 3, 15, 10005 или даже (если вы можете такое себе представить). Т.о. =2=3=…=10=…n=…Если задуматься, можно обнаружить очередной не вполне очевидный факт из теории множеств. 2=• есть мощность множества пар действительных чисел. Пара действительных чисел, вообще говоря, соответствует точке на плоскости. В свою очередь, 3=•• есть мощность множества троек действительных чисел, а это точки в пространстве. Рассуждения можно продолжить далее вплоть до - мерного пространства или множества всех последовательностей действительных чисел счетной длины. Т.о. все конечно-мерные или счетно-мерные пространства имеют одинаковую мощность (здесь - количество точек в пространстве). Для - мерного действительного пространства или множества всех последовательностей действительных чисел счетной длины с точки зрения операций над кардинальными числами получим =(2)=2∙=2=. В этом месте интересно будет обратиться к историческим событиям, связанным с чередой доказательств в этой сфере. С тем, что на бесконечной прямой столько же точек, сколько и на отрезке, математики, хотя и не сразу, но в итоге примирились. Но следующий результат Кантора оказался еще более неожиданным. В поисках множества, имеющего больше элементов, чем отрезок на действительной оси, он обратил внимание на множество точек квадрата. Изначально сомнений в результате не было: ведь отрезок целиком размещается на одной стороне квадрата, а множество всех отрезков, на которые можно разложить квадрат, само по себе имеет ту же мощность, что и множество точек отрезка. На протяжении почти трех лет (с 1871 по 1874) Кантор искал доказательство того, что взаимно однозначное соответствие между точками отрезка и точками квадрата невозможно. И в какой то момент совершенно неожиданно получился прямо противоположный результат: ему удалось построить соответствие, которое он искренне считал невозможным. Кантор не верил сам себе и даже написал немецкому математику Рихарду Дедекинду: «Я вижу это, но не верю этому». Когда шок от этого факта прошел, стало интуитивно понятно и вскоре доказано, что и куб имеет столько же точек, сколько отрезок. Вообще говоря, любая геометрическая фигура на плоскости (геометрическое тело в пространстве), содержащая хотя бы одну линию, имеет столько же точек, сколько отрезок. Такие множества назвали множествами мощности континуума (от латинского continuum – непрерывный). Следующий шаг почти очевиден: размерность пространства в определенных пределах несущественна. Например, 2-х мерная плоскость, 3-х мерное привычное пространство, 4-х, 5-ти и далее n-мерные пространства с точки зрения количества точек, содержащихся в соответствующем n-мерном теле, равномощны. Такая ситуация будет наблюдаться даже в случае пространства с бесконечным количеством измерений, важно только чтобы это количество было счетным. На данном этапе обнаружены два типа бесконечностей и соответственно два трансфинитных числа, обозначающих их мощности. Множества первого типа имеют мощность, эквивалентную мощности натуральных чисел (алеф-ноль). Множества второго типа имеют мощность, эквивалентную количеству точек на действительной оси (мощность континуума, алеф). Показано, что во множествах второго типа элементов больше, чем во множествах первого типа. Естественно, возникает вопрос – а нет ли в природе «промежуточного» множества, которое имело бы мощность больше чем количество натуральных чисел, но при этом меньше, чем множество точек на прямой? Этот непростой вопрос получил название «проблема континуума». Она же известна как «континуум-гипотеза» или «первая проблема Гильберта». Точная формулировка звучит следующим образом:Континуум-гипотеза: с точностью до эквивалентности, существуют только два типа бесконечных числовых множеств: счетное множество и континуум. Иначе говоря, гипотеза предполагает, что не существует множества промежуточной мощности, т. е. такого множества X, X, которое не эквивалентно ни , ни . Этой проблемой занимались очень многие математики. Сам Георг Кантор неоднократно заявлял, что доказал эту гипотезу, но всякий раз находил у себя ошибку. Название «первая проблема Гильберта» относится к публикации Давидом Гильбертом на II Международном Конгрессе математиков в Париже в 1901 году списка из 23 кардинальных проблем математики. Тогда эти проблемы не были решены, позднее окончательное решение получили 16 проблем из 23. В результате после долгих исследований по вопросу континуум-гипотезы в 1938 году немецкий математик Курт Гедёль доказал, что существование промежуточной мощности не противоречит остальным аксиомам теории множеств. И позднее, в 1963-1964 гг. почти одновременно, но независимо друг от друга, американский математик Коэн и чешский математик Вопенка показали, что наличие такой промежуточной мощности не выводимо из остальных аксиом теории множеств. Кстати, интересно заметить, что этот результат очень похож на историю с постулатом о параллельных прямых. Как известно, две тысячи лет его пытались вывести из остальных аксиом геометрии, но только после работ Лобачевского, Гильберта и других удалось получить тот же результат: этот постулат не противоречит остальным аксиомам, но и не может быть выведен из них. ^ 2.4.2. Множества комплексных, трансцендентных и иррациональных чиселПриведем в дополнение к множеству действительных чисел еще несколько несчетных множеств. Комплексное число задается парой (r1, r2), где r1, r2 принадлежат множеству действительных чисел.Множество комплексных чисел обозначим латинской буквой С.Т.2.4.(2) ТеоремаМножество комплексных чисел несчетно.Доказательство Так как множество действительных чисел R, несчётное по доказанной ранее Теореме 2.4.(1), является подмножеством множества комплексных чисел С, то множество комплексных чисел также несчётно, Q.E.D.Иррациональным называется действительное число, не являющееся рациональным. Множество иррациональных чисел обозначим латинской буквой I.Т.2.4.(3) ТеоремаМножество иррациональных чисел несчетно.ДоказательствоПоскольку действительных чисел – несчетное множество, а рациональных – счетное, то иррациональных чисел – несчетное множество, Q.E.D. Трансцендентное число - действительное число, не являющееся алгебраи