В математике кардинальное число , или кардинал для краткости, это то, что обычно называют числом элементов множества . В случае конечного множества его кардинальное число, или мощность, является натуральным числом . Для рассмотрения случая бесконечных множеств были введены бесконечные кардинальные числа, которые часто обозначаются еврейской буквой ( алеф ) с нижним индексом, указывающим их ранг среди бесконечных кардинальных чисел.
Мощность определяется в терминах биективных функций . Два множества имеют одинаковую мощность тогда и только тогда , когда между элементами двух множеств существует взаимно однозначное соответствие (биекция). В случае конечных множеств это согласуется с интуитивным понятием числа элементов. В случае бесконечных множеств поведение более сложное. Фундаментальная теорема Георга Кантора показывает, что бесконечные множества могут иметь разные мощности, и, в частности, мощность множества действительных чисел больше мощности множества натуральных чисел. Также возможно, что собственное подмножество бесконечного множества имеет ту же мощность, что и исходное множество, чего не может произойти с собственными подмножествами конечных множеств.
Существует трансфинитная последовательность кардинальных чисел:
Эта последовательность начинается с натуральных чисел , включая ноль (конечные кардиналы), за которыми следуют числа алеф . Числа алеф индексируются порядковыми числами . Если аксиома выбора верна, эта трансфинитная последовательность включает в себя каждое кардинальное число. Если аксиома выбора неверна (см. Аксиома выбора § Независимость ), существуют бесконечные кардиналы, которые не являются числами алеф.
Мощность изучается сама по себе как часть теории множеств . Она также является инструментом, используемым в таких областях математики, как теория моделей , комбинаторика , абстрактная алгебра и математический анализ . В теории категорий кардинальные числа образуют скелет категории множеств .
Понятие мощности, как оно понимается сейчас, было сформулировано Георгом Кантором , создателем теории множеств , в 1874–1884 годах. Мощность может использоваться для сравнения аспекта конечных множеств. Например, множества {1,2,3} и {4,5,6} не равны , но имеют одинаковую мощность , а именно три. Это устанавливается существованием биекции ( т. е. взаимно-однозначного соответствия) между двумя множествами, например, соответствия {1→4, 2→5, 3→6}.
Кантор применил свою концепцию биекции к бесконечным множествам [1] (например, к множеству натуральных чисел N = {0, 1, 2, 3, ...}). Таким образом, он назвал все множества, имеющие биекцию с N, счетными (счетно бесконечными) множествами , которые все имеют одно и то же кардинальное число. Это кардинальное число называется , алеф-нуль . Он назвал кардинальные числа бесконечных множеств трансфинитными кардинальными числами .
Кантор доказал, что любое неограниченное подмножество N имеет ту же мощность, что и N , хотя это может показаться противоречащим интуиции. Он также доказал, что множество всех упорядоченных пар натуральных чисел счетно; это означает, что множество всех рациональных чисел также счетно, поскольку каждое рациональное число может быть представлено парой целых чисел. Позже он доказал, что множество всех действительных алгебраических чисел также счетно. Каждое действительное алгебраическое число z может быть закодировано как конечная последовательность целых чисел, которые являются коэффициентами в полиномиальном уравнении, решением которого оно является, т. е. упорядоченный n-кортеж ( a 0 , a 1 , ..., an ) , a i ∈ Z вместе с парой рациональных чисел ( b 0 , b 1 ) такой, что z является единственным корнем полинома с коэффициентами ( a 0 , a 1 , ..., an ) , который лежит в интервале ( b 0 , b 1 ).
В своей статье 1874 года « О свойстве совокупности всех действительных алгебраических чисел » Кантор доказал, что существуют кардинальные числа более высокого порядка, показав, что множество действительных чисел имеет мощность, большую, чем N. Его доказательство использовало аргумент с вложенными интервалами , но в статье 1891 года он доказал тот же результат, используя свой гениальный и гораздо более простой диагональный аргумент . Новое кардинальное число множества действительных чисел называется мощностью континуума , и Кантор использовал для него символ .
Кантор также разработал большую часть общей теории кардинальных чисел; он доказал, что существует наименьшее трансфинитное кардинальное число ( , алеф-нуль), и что для каждого кардинального числа существует следующее по величине кардинальное число
Его континуум-гипотеза — это утверждение о том, что мощность множества действительных чисел равна . Эта гипотеза не зависит от стандартных аксиом математической теории множеств, то есть она не может быть ни доказана, ни опровергнута с их помощью. Это было показано в 1963 году Полом Коэном , дополнив более раннюю работу Курта Гёделя в 1940 году.
В неформальном использовании кардинальное число — это то, что обычно называют счетным числом , при условии, что включен 0: 0, 1, 2, .... Их можно отождествить с натуральными числами, начинающимися с 0. Счетные числа — это именно то, что можно формально определить как конечные кардинальные числа. Бесконечные кардинальные числа встречаются только в высшей математике и логике .
Более формально, ненулевое число может использоваться для двух целей: для описания размера множества или для описания положения элемента в последовательности. Для конечных множеств и последовательностей легко увидеть, что эти два понятия совпадают, поскольку для каждого числа, описывающего положение в последовательности, мы можем построить множество, которое имеет точно правильный размер. Например, 3 описывает положение 'c' в последовательности <'a','b','c','d',...>, и мы можем построить множество {a,b,c}, которое имеет 3 элемента.
Однако, когда речь идет о бесконечных множествах , важно различать эти два понятия, поскольку для бесконечных множеств эти два понятия фактически различны. Рассмотрение аспекта положения приводит к порядковым числам , тогда как аспект размера обобщается описанными здесь кардинальными числами.
Интуиция, стоящая за формальным определением кардинала, заключается в построении понятия относительного размера или «величины» множества без ссылки на тип его членов. Для конечных множеств это легко; просто подсчитывается количество элементов, имеющихся в множестве. Чтобы сравнить размеры более крупных множеств, необходимо обратиться к более тонким понятиям.
Множество Y по крайней мере такого же размера, как и множество X , если существует инъективное отображение элементов X на элементы Y. Инъективное отображение отождествляет каждый элемент множества X с уникальным элементом множества Y. Это легче всего понять на примере; предположим, что у нас есть множества X = {1,2,3} и Y = {a,b,c,d}, тогда, используя это понятие размера, мы бы заметили, что существует отображение:
что является инъективным, и, следовательно, заключаем, что Y имеет мощность больше или равную X . Элемент d не имеет отображения элемента на него, но это разрешено, поскольку нам требуется только инъективное отображение, а не обязательно биективное отображение. Преимущество этого понятия в том, что его можно распространить на бесконечные множества.
Затем мы можем расширить это до отношения в стиле равенства. Говорят, что два множества X и Y имеют одинаковую мощность , если существует биекция между X и Y . По теореме Шредера–Бернштейна это эквивалентно тому, что существуют как инъективное отображение из X в Y , так и инъективное отображение из Y в X . Затем мы записываем | X | = | Y |. Кардинальное число самого X часто определяется как наименьшее порядковое число a с | a | = | X |. [2] Это называется кардинальным назначением фон Неймана ; чтобы это определение имело смысл, необходимо доказать, что каждое множество имеет ту же мощность, что и некоторое порядковое число; это утверждение является принципом хорошего упорядочения . Однако можно обсуждать относительную мощность множеств без явного назначения имен объектам.
Классический пример — парадокс бесконечного отеля, также называемый парадоксом Гильберта Гранд-Отеля . Предположим, что в отеле с бесконечным количеством номеров есть хозяин. Отель заполнен, и тут приезжает новый гость. Можно разместить дополнительного гостя, попросив гостя, который был в номере 1, переехать в номер 2, гостя из номера 2 — в номер 3 и т. д., оставив номер 1 пустым. Мы можем явно записать сегмент этого отображения:
С помощью этого назначения мы можем видеть, что множество {1,2,3,...} имеет ту же мощность, что и множество {2,3,4,...}, поскольку была показана биекция между первым и вторым. Это мотивирует определение бесконечного множества как любого множества, имеющего собственное подмножество той же мощности (т. е. бесконечное по Дедекинду множество ); в этом случае {2,3,4,...} является собственным подмножеством {1,2,3,...}.
При рассмотрении этих больших объектов, возможно, также захочется посмотреть, совпадает ли понятие порядка подсчета с понятием кардинала, определенным выше для этих бесконечных множеств. Бывает, что нет; рассматривая приведенный выше пример, мы можем увидеть, что если существует некий объект «один больше бесконечности», то он должен иметь ту же мощность, что и бесконечное множество, с которого мы начали. Можно использовать другое формальное понятие для числа, называемое ординалами , основанное на идеях подсчета и рассмотрения каждого числа по очереди, и мы обнаруживаем, что понятия мощности и ординальности расходятся, как только мы выходим за пределы конечных чисел.
Можно доказать, что мощность действительных чисел больше, чем у натуральных чисел, описанных выше. Это можно наглядно представить с помощью диагонального аргумента Кантора ; классические вопросы мощности (например, гипотеза континуума ) связаны с обнаружением того, есть ли некоторый кардинал между некоторой парой других бесконечных кардиналов. В последнее время математики описывают свойства все больших и больших кардиналов.
Поскольку мощность является таким распространенным понятием в математике, используются различные названия. Одинаковость мощности иногда называют равномощностью , равнополнотностью или равночисленностью . Таким образом, говорят, что два множества с одинаковой мощностью являются, соответственно, равномощными , равнополнотными или равночисленными .
Формально, предполагая аксиому выбора , мощность множества X — это наименьшее порядковое число α, такое, что между X и α существует биекция . Это определение известно как кардинальное присваивание фон Неймана . Если аксиома выбора не предполагается, то необходим другой подход. Самое старое определение мощности множества X (неявное у Кантора и явное у Фреге и Principia Mathematica ) — это класс [ X ] всех множеств, равночисленных с X. Это не работает в ZFC или других связанных системах аксиоматической теории множеств , потому что если X непусто, эта коллекция слишком велика, чтобы быть множеством. Фактически, для X ≠ ∅ существует инъекция из вселенной в [ X ] путем отображения множества m в { m } × X , и поэтому по аксиоме ограничения размера [ X ] является собственным классом. Однако определение работает в теории типов и в Новых Основаниях и связанных системах. Однако, если мы ограничимся этим классом до тех, которые равночисленны с X и имеют наименьший ранг , то это будет работать (это трюк, придуманный Даной Скотт : [3] он работает, потому что совокупность объектов с любым заданным рангом является множеством).
Кардинальное присваивание фон Неймана подразумевает, что кардинальное число конечного множества является общим порядковым числом всех возможных хорошо упорядоченных чисел этого множества, а кардинальная и порядковая арифметика (сложение, умножение, возведение в степень, правильное вычитание) затем дают одинаковые ответы для конечных чисел. Однако они различаются для бесконечных чисел. Например, в порядковой арифметике, в то время как в кардинальной арифметике, хотя присвоение фон Неймана ставит . С другой стороны, трюк Скотта подразумевает, что кардинальное число 0 равно , что также является порядковым числом 1, и это может сбивать с толку. Возможный компромисс (чтобы воспользоваться выравниванием в конечной арифметике, избегая при этом опоры на аксиому выбора и путаницы в бесконечной арифметике) состоит в применении присваивания фон Неймана к кардинальным числам конечных множеств (тех, которые могут быть хорошо упорядочены и не являются равномощными собственным подмножествам) и использовании приема Скотта для кардинальных чисел других множеств.
Формально порядок среди кардинальных чисел определяется следующим образом: | X | ≤ | Y | означает, что существует инъективная функция из X в Y . Теорема Кантора–Бернштейна–Шредера утверждает, что если | X | ≤ | Y | и | Y | ≤ | X |, то | X | = | Y |. Аксиома выбора эквивалентна утверждению, что для двух множеств X и Y либо | X | ≤ | Y |, либо | Y | ≤ | X |. [4] [5]
Множество X является дедекиндово-бесконечным , если существует собственное подмножество Y X с | X | = | Y |, и дедекиндово-конечным , если такое подмножество не существует. Конечные кардиналы — это просто натуральные числа , в том смысле, что множество X является конечным тогда и только тогда, когда | X | = | n | = n для некоторого натурального числа n . Любое другое множество является бесконечным .
Предполагая аксиому выбора, можно доказать, что понятия Дедекинда соответствуют стандартным. Можно также доказать, что кардинал ( алеф нуль или алеф-0, где алеф — первая буква еврейского алфавита , представленная ) множества натуральных чисел является наименьшим бесконечным кардиналом (т. е. любое бесконечное множество имеет подмножество мощности ). Следующий больший кардинал обозначается , и так далее. Для каждого порядкового числа α существует кардинальное число, и этот список исчерпывает все бесконечные кардинальные числа.
Мы можем определить арифметические операции над кардинальными числами, которые обобщают обычные операции для натуральных чисел. Можно показать, что для конечных кардинальных чисел эти операции совпадают с обычными операциями для натуральных чисел. Более того, эти операции имеют много общих свойств с обычной арифметикой.
Если аксиома выбора верна, то каждый кардинал κ имеет последующее число, обозначаемое κ + , где κ + > κ и между κ и его последующим числом нет кардиналов. (Без аксиомы выбора, используя теорему Хартогса , можно показать, что для любого кардинального числа κ существует минимальный кардинал κ + такой, что ) Для конечных кардиналов последующее число — это просто κ + 1. Для бесконечных кардиналов последующее кардиналическое число отличается от последующего ординального числа .
Если X и Y не пересекаются , сложение получается путем объединения X и Y. Если два множества уже не пересекаются, то их можно заменить непересекающимися множествами той же мощности (например, заменить X на X × {0}, а Y на Y ×{1}).
Ноль — аддитивное тождество κ + 0 = 0 + κ = κ .
Сложение ассоциативно ( κ + µ ) + ν = κ + ( µ + ν ).
Сложение коммутативно κ + µ = µ + κ .
Сложение не убывает в обоих аргументах:
Предполагая аксиому выбора, сложение бесконечных кардинальных чисел легко. Если κ или μ бесконечны, то
Предполагая аксиому выбора и учитывая бесконечный кардинал σ и кардинал μ , существует кардинал κ такой, что μ + κ = σ тогда и только тогда, когда μ ≤ σ . Он будет единственным (и равным σ ) тогда и только тогда, когда μ < σ .
Произведение кардиналов происходит от декартова произведения .
κ ·0 = 0· κ = 0.
κ · µ = 0 → ( κ = 0 или µ = 0).
Одним из них является мультипликативное тождество κ ·1 = 1 · κ = κ .
Умножение ассоциативно ( κ · µ )· ν = κ ·( µ · ν ).
Умножение коммутативно κ · µ = µ · κ .
Умножение неубывает по обоим аргументам: κ ≤ µ → ( κ · ν ≤ µ · ν и ν · κ ≤ ν · µ ).
Умножение распределяется по сложению: κ ·( µ + ν ) = κ · µ + κ · ν и ( µ + ν )· κ = µ · κ + ν · κ .
Предполагая аксиому выбора, умножение бесконечных кардинальных чисел также легко. Если либо κ , либо μ бесконечны и оба не равны нулю, то
Предполагая аксиому выбора и имея бесконечный кардинал π и ненулевой кардинал μ , существует кардинал κ такой, что μ · κ = π тогда и только тогда, когда μ ≤ π . Он будет единственным (и равным π ) тогда и только тогда, когда μ < π .
Возведение в степень определяется по формуле
где X Y — множество всех функций из Y в X. [6] Легко проверить , что правая часть зависит только от и .
Возведение в степень не убывает в обоих аргументах:
2 | X | — это мощность множества мощности множества X , и диагональный аргумент Кантора показывает, что 2 | X | > | X | для любого множества X. Это доказывает, что не существует наибольшего кардинала (потому что для любого кардинала κ мы всегда можем найти больший кардинал 2 κ ). Фактически, класс кардиналов является собственным классом . (Это доказательство не работает в некоторых теориях множеств, в частности в New Foundations .)
Все остальные предложения в этом разделе предполагают аксиому выбора:
Если 2 ≤ κ и 1 ≤ μ и хотя бы одно из них бесконечно, то:
Используя теорему Кенига , можно доказать κ < κ cf ( κ ) и κ < cf(2 κ ) для любого бесконечного кардинала κ , где cf( κ ) — конфинальность κ .
Предполагая аксиому выбора и учитывая бесконечный кардинал κ и конечный кардинал μ, больший 0, удовлетворяющий кардинал ν будет .
Предполагая аксиому выбора и учитывая бесконечный кардинал κ и конечный кардинал μ больше 1, может существовать или не существовать кардинал λ, удовлетворяющий . Однако, если такой кардинал существует, он бесконечен и меньше κ , и любая конечная кардинальность ν больше 1 также будет удовлетворять .
Логарифм бесконечного кардинального числа κ определяется как наименьшее кардинальное число μ такое, что κ ≤ 2 μ . Логарифмы бесконечных кардинальных чисел полезны в некоторых областях математики, например, при изучении кардинальных инвариантов топологических пространств , хотя им не хватает некоторых свойств, которыми обладают логарифмы положительных действительных чисел. [7] [8] [9]
Гипотеза континуума (ГК) утверждает, что строго между и нет кардиналов Последнее кардинальное число также часто обозначается как ; это мощность континуума (множества действительных чисел ). В этом случае
Аналогично, обобщенная континуум-гипотеза (GCH) утверждает, что для любого бесконечного кардинала нет кардиналов строго между и . Как континуум-гипотеза, так и обобщенная континуум-гипотеза, как было доказано, не зависят от обычных аксиом теории множеств, аксиом Цермело–Френкеля вместе с аксиомой выбора ( ZFC ).
Действительно, теорема Истона показывает, что для регулярных кардиналов единственными ограничениями, накладываемыми ZFC на мощность, являются то, что , и что экспоненциальная функция не убывает.
Примечания
Библиография
