>> |
No.105363
Два множества называются равномощными, если между ними есть хотя бы одна биекция. Если множество равномощно некоторому конечному ординалу (то есть натуральному числу n), то мы говорим, что это множество конечно и содержит n элементов. Мы говорим, что множество бесконечно, если оно не является конечным. То есть множество бесконечно, если оно не равномощно никакому натуральному числу n.
Мы говорим, что множество счётно, если оно равномощно множеству натуральных чисел. Счётные множества - это как бы такие множества, которые можно "расположить в виде строки". Например, множество натуральных чисел 0, 1, 2, 3, ... счётно, множество являющихся целыми квадратами натуральных чисел 1, 4, 9, 16, ... счётно, множество целых отрицательных чисел -1, -2, -3, ... счётно, множество всех целых чисел 0, 1, -1, 2, -2, 3, -3, ... счётно.
Бесконечный ординал и его последователь равномощны. В самом деле, пусть X - бесконечный ординал, и Y = X∪{X} - его последователь. Так как X бесконечно, ординал ω является подмножеством X. Рассмотрим функцию f: X→Y, определённую так. Ординалу 0 сопоставим X, любому другому конечному ординалу x сопоставим ординал x+1, а все остальные ординалы оставим неподвижными. Легко видеть, что f - биекция.
Мы говорим, что мощность множества M меньше или равна мощности множества N, если есть хотя бы одна инъекция M в N. Мы говорим, что мощность множества M строго меньше мощности множества N, если есть хотя бы одна инъекция M в N, но нет ни одной биекции между M и N.
Лемма Кантора. Между множеством и его булеаном нет биекции.
Два множества называются равномощными, если между ними есть хотя бы одна биекция. Если множество равномощно некоторому конечному ординалу (то есть натуральному числу n), то мы говорим, что это множество конечно и содержит n элементов. Мы говорим, что множество бесконечно, если оно не является конечным. То есть множество бесконечно, если оно не равномощно никакому натуральному числу n.
Мы говорим, что множество счётно, если оно равномощно множеству натуральных чисел. Счётные множества - это как бы такие множества, которые можно "расположить в виде строки". Например, множество натуральных чисел 0, 1, 2, 3, ... счётно, множество являющихся целыми квадратами натуральных чисел 1, 4, 9, 16, ... счётно, множество целых отрицательных чисел -1, -2, -3, ... счётно, множество всех целых чисел 0, 1, -1, 2, -2, 3, -3, ... счётно.
Бесконечный ординал и его последователь равномощны. В самом деле, пусть X - бесконечный ординал, и Y = X∪{X} - его последователь. Так как X бесконечно, ординал ω является подмножеством X. Рассмотрим функцию f: X→Y, определённую так. Ординалу 0 сопоставим X, любому другому конечному ординалу x сопоставим ординал x+1, а все остальные ординалы оставим неподвижными. Легко видеть, что f - биекция.
Мы говорим, что мощность множества M меньше или равна мощности множества N, если есть хотя бы одна инъекция M в N. Мы говорим, что мощность множества M строго меньше мощности множества N, если есть хотя бы одна инъекция M в N, но нет ни одной биекции между M и N.
Лемма Кантора. Между множеством и его булеаном нет биекции. Доказательство. Пусть M - множество. Предположим, что между ним и его булеаном есть биекция. Эта биекция сопоставляет произвольному элементу множества M некоторое подмножество M. То есть образами элементов M являются подмножества M. Мы назовём элемент множества M обычным, если он является элементом своего образа, и необычным в противном случае; всякий элемент M является либо обычным, либо необычным. Рассмотрим множество всех необычных элементов M. Оно является элементом булеана M и потому является образом некоторого элемента x из M. Каким является элемент x, обычным или необычным? Если x является обычным, то он должен быть элементом множества всех необычных элементов, то есть быть необычным; это невозможно. Если же x является необычным, то он должен быть элементом множества всех обычных элементов, а потому должен быть обычным; это тоже невозможно. Значит, рассматриваемой биекции нет.
Теорема Кантора. Мощность множества строго меньше мощности булеана этого множества. Доказательство. Чтобы инъективно отобразить множество X в ℘(X), достаточно каждому x из X сопоставить множество {x}. А биекции между X и ℘(X) нет по лемме.
Из теоремы Кантора следует, что бывают разные бесконечности. Например, мощность ω строго меньше мощности ℘(ω).
В общем случае довольно сложно понять, есть ли между двумя множествами хотя бы одна биекция. Имеется, однако, инструмент, который несколько упрощает дело.
Теорема Кантора-Бернштейна. Пусть есть два множества. Если мощность первого меньше или равна мощности второго, а мощность второго меньше или равна мощности первого, то эти два множества равномощны.
Доказательство. Пусть f: A→B и g:B→A две инъекции. Требуется доказать, что есть биекция h: A→B. Для всякого a из A его предшественником назовём такой b из B, что g(b) = a. Поскольку g инъективно, у каждого a не больше одного предшественника. Аналогично, для всякого b из B его предшественником назовём такой a из A, что f(a) = b. У элемента либо вообще нет предшественника, либо есть ровно один предшественник. Для каждого a из A построим максимально возможную цепочку предшественников: a, g(b), f(a'), g(b''), ... здесь g(b) = a, f(a') = b, g(b'') = a' и т.д. Весом элемента a назовём длину максимальной цепочки минус 1 (минус стоит для удобства). Если цепочка предшественников конечна, то её вес равен натуральному числу n. Если цепочка бесконечна, то её вес есть ω. Пусть A0 - множество элементов A веса 0, ... An - множество элементов веса n, ... , Aω - множество элементов, имеющих бесконечные цепочки предшественников. Аналогично определяются веса элементов B и множества B0, B1, ... , Bω.
Заметим, что между A0 и B1 есть биекция: элементу a из A0 соответствует элемент f(a). Это биекция, потому что у неё есть обратное отображение: элементу b' из B1 соответствует его прообраз. Этот прообраз лежит в A0, потому что вес b' равен 1. Аналогично, между A1 и B0 есть биекция: элементу a' из A1 соответствует элемент b из B0 такой, что g(b) = a'.
Так же устроены биекции между A2 и B3, A3 и B2, и т.д. Таким образом, получаем биекцию между множеством элементов конечного веса в A и множеством элементов конечного веса в B. Осталось получить биекцию между Aω и Bω. Для этого заметим, что каждому элементу a из Aω соответствует один-единственный элемент b=f(a) из Bω. И у этого соответствия есть обратное отображение: каждый элемент b из Bω имеет предшественника a в Aω такого, что f(a) = b.
Итак, теорема доказана. Пикрелейтед.
Кардинал - это ординал, который не равномощен никакому меньшему ординалу. Все конечные ординалы - кардиналы. Это можно доказать с помощью математической индукции. Они называются конечными кардиналами. Бесконечные кардиналы - это кардиналы, не являющиеся конечными. Бесконечные кардиналы называются алефами. ω - наименьший бесконечный кардинал. Все бесконечные кардиналы - это предельные ординалы (но не все предельные ординалы - бесконечные кардиналы). В самом деле, если некий кардинал не является предельным, то он имеет предшественника; но ведь он равномощен своему предшественнику, следовательно, не является кардиналом.
Пусть множество M вполне упорядочено. Тогда, по теореме о вполне упорядоченных множествах, оно изоморфно одному-единственному ординалу и потому биективно отображается на, по крайней мере, один ординал. То есть существует множество равномощных ему ординалов. Среди этих ординалов существует наименьший ординал. Он является кардиналом, так как не равномощен никакому из предшественников. Этот кардинал мы назовём мощностью множества M. Ясно, что если два множества равномощны, то их кардиналы равны. Вот мы и определили, что же такое мощность множества сама по себе; до этого у нас было лишь понятие двух равномощных множеств, но мощность не была объектом.
На основании аксиомы выбора мы можем утверждать, что у любого множества есть мощность, которая является кардиналом. Ведь любое множество может быть вполне упорядочено.
Для любого ординала a существует кардинал, больший a. Он обозначается символом a⁺ (a с плюсиком) и называется кардинал-последователь ординала a. Следовательно, для каждого кардинала есть больший кардинал. Доказательство. Рассмотрим функцию Хартогса H(x), заданную на классе всех множеств. Если x - множество, то числом Хартогса H(x) для x называется наименьший ординал a, для которого нет инъекции из a в x. Если M - множество, то класс всех полных порядков на частях M является множеством. Следовательно, класс ординалов, инъективно отображающихся в M, тоже является множеством. Но поскольку класс всех ординалов не является множеством, существуют ординалы, не отображающиеся инъективно в M. Следовательно, существует наименьший такой ординал. То есть число Хартогса существует для каждого множества M. Нетрудно видеть, что число Хартогса - кардинал. Определим a⁺ для ординала a как H(a).
Если у нас есть какое-то множество кардиналов, то супремум этого множества - кардинал.
Бесконечные кардиналы обозначаются с помощью символа ℵ. Каждому ординалу с помощью нижеследующего определения по трансфинитной рекурсии соответствует кардинал. Символом ℵ₀ (алеф-нуль) обозначается ω. Символом ℵ(a+1) обозначается кардинал-последователь кардинала ℵa, где a+1 - ординал-последователь ординала a. Пусть a - предельный ординал, и для каждого ординала b, меньшего a, определён кардинал ℵb. Тогда символом ℵa обозначается супремум множества всех кардиналов ℵb, где b<a.
Кардинал ℵ(a+1) называется преемником (successor) кардинала ℵa, или, иначе, последователем. Кардинал ℵλ, где λ - предельный ординал, называется предельным кардиналом.
Вдобавок к алефам можно ввести символы ωa. Мы положим ωa = ℵa; например, ω₀ = ℵ₀ = ω. Нужно заметить, что ординалы ωa - это очень большие ординалы. Ординал ω₁ уже несчётен, он больше даже эпсилон-нулевого.
Пусть a - ненулевой предельный ординал. Пусть b - другой предельный ординал, и пусть {an, n<b} - возрастающая трансфинитная последовательность длины b. Мы будем говорить, что последовательность {an} кофинальна в a, если предел этой последовательности при n->b равен a. Пусть a - ненулевой предельный ординал. Пусть A - подмножество a. Мы будем говорить, что A кофинально в a, если супремум A равен a. Пусть a - бесконечный предельный ординал. Кофинальность a - наименьший предельный ординал b такой, что существует последовательность длины b, кофинальная a. То есть кофинальность a - это наименьшая из мощностей всех тех множеств, которые кофинальны a. По-русски почему-то принято говорить "конфинальная последовательность", "конфинальное множество", "конфинальность".
Кофинальность a - предельный ординал. Он обозначается cf(a). В случаях, когда это не ведёт к неточностям, скобки можно опускать и писать cf a. Ясно, что cf a меньше или равна a. Можно доказать, что cf (cf a) = cf a. Если a - ненулевой предельный ординал и A - подмножество a, кофинальное a, то порядковый тип A больше или равен cf A. Если предел некоторой неубывающей c-последовательности элементов a равен a, то cf a = cf a. Бесконечный кардинал ℵa называется регулярным, если он равен своей кофинальности. Он называется сингулярным, если больше своей кофинальности. Кофинальность каждого предельного ординала - регулярный кардинал.
Прежде чем строить теорию кардиналов дальше, вернёмся ненадолго к классу всех ординалов. Класс Ord×Ord всех упорядоченных пар ординалов вполне упорядочен с помощью следующего порядка: (a,b) < (p,q) тогда и только тогда, когда или max{a,b} < max{p,q}, или max{a,b} = max{p,q} и a<p, или max{a,b} = max{p,q} и a=p и b<q. Можно доказать, что это отношение (обобщение алфавитного порядка) действительно является полным порядком на Ord×Ord, достаточно погуглить по словам the canonical well-ordering on pairs of ordinals. Если мы обозначим как Г(x,y) порядковый тип множества всех пар (a,b), меньших чем (x,y) в смысле этого порядка, то установим биекцию из Ord×Ord в Ord. Более того, (a,b)<(p,q) тогда и только тогда, когда Г(a,b)<Г(p,q). Отсюда можно вывести, что Г(ω,ω) = ω и, более того, что для любого ординала a Г(ωa, ωa) = ωa.
|