В математике кардинальное число , или сокращенно кардинал , — это то, что обычно называют числом элементов множества . Следовательно, в случае конечного множества его кардинальное число или мощность является натуральным числом . Для рассмотрения случая бесконечных множеств были введены бесконечные кардинальные числа, которые часто обозначаются еврейской буквой ( алеф ) с нижним индексом, указывающим их ранг среди бесконечных кардиналов.
Мощность определяется в терминах биективных функций . Два множества имеют одинаковую мощность тогда и только тогда , когда существует взаимно однозначное соответствие (биекция) между элементами двух множеств. В случае конечных множеств это согласуется с интуитивным представлением о количестве элементов. В случае бесконечных множеств поведение более сложное. Фундаментальная теорема Георга Кантора показывает, что бесконечные множества могут иметь разную мощность, и, в частности, мощность набора действительных чисел больше, чем мощность набора натуральных чисел. Также возможно, что собственное подмножество бесконечного множества будет иметь ту же мощность, что и исходное множество, чего не может случиться с правильными подмножествами конечных множеств.
Существует трансфинитная последовательность кардинальных чисел:
Эта последовательность начинается с натуральных чисел , включая ноль (конечные кардиналы), за которыми следуют числа алефов . Числа алефа индексируются порядковыми номерами . Если выбранная аксиома верна, эта трансфинитная последовательность включает в себя все кардинальные числа. Если выбранная аксиома неверна (см. Аксиому выбора § Независимость ), существуют бесконечные кардиналы, которые не являются числами алеф.
Кардинальность изучается сама по себе как часть теории множеств . Это также инструмент, используемый в разделах математики, включая теорию моделей , комбинаторику , абстрактную алгебру и математический анализ . В теории категорий кардинальные числа образуют скелет категории множеств .
Понятие мощности в нынешнем понимании было сформулировано Георгом Кантором , создателем теории множеств , в 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 , ..., a n ) , a i ∈ Z вместе с парой рациональных чисел ( b 0 , b 1 ) таких, что z — единственный корень многочлена с коэффициентами ( a 0 , a 1 , ..., an ) , лежащего в интервале ( б 0 , б 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 часто определяется как наименьший порядковый номер a с | а | = | Х |. [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 либо | Х | ≤ | Ю | или | Ю | ≤ | Х |. [4] [5]
Множество X является дедекиндово бесконечным, если существует собственное подмножество Y множества X такое, что | Х | = | Y |, и дедекинд-конечное, если такого подмножества не существует. Конечные кардиналы — это просто натуральные числа в том смысле, что множество X конечно тогда и только тогда, когда | Х | = | п | = 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 , а диагональный аргумент Кантора показывает, что 2 | Х | > | Х | для любого множества X. Это доказывает, что наибольшего кардинала не существует (поскольку для любого кардинала κ всегда можно найти больший кардинал 2 κ ). На самом деле класс кардиналов — это настоящий класс . (Это доказательство терпит неудачу в некоторых теориях множеств, особенно в «Новых основаниях» .)
Все остальные предложения в этом разделе предполагают аксиому выбора:
Если 2 ≤ κ и 1 ≤ µ и хотя бы один из них бесконечен, то:
Используя теорему Кенига , можно доказать κ < κ cf( κ ) и κ < cf(2 κ ) для любого бесконечного кардинала κ , где cf( κ ) — конфинальность κ .
Предполагая выбранную аксиому и учитывая бесконечный кардинал κ и конечный кардинал µ, больший 0, кардинал ν, удовлетворяющий условиям, будет равен .
Предполагая аксиому выбора и учитывая бесконечный кардинал κ и конечный кардинал µ больше 1, может существовать или не быть кардинал λ, удовлетворяющий . Однако, если такой кардинал существует, он бесконечен и меньше κ , и любая конечная мощность ν больше 1 также будет удовлетворять .
Логарифм бесконечного кардинального числа κ определяется как наименьшее кардинальное число µ такое, что κ ≤ 2 µ . Логарифмы бесконечных кардиналов полезны в некоторых областях математики, например, при изучении кардинальных инвариантов топологических пространств , хотя им не хватает некоторых свойств, которыми обладают логарифмы положительных действительных чисел. [7] [8] [9]
Гипотеза континуума (CH) утверждает, что между и нет кардиналов . Последнее кардинальное число также часто обозначается ; это мощность континуума (набора действительных чисел ). В этом случае
Точно так же обобщенная гипотеза континуума (GCH) утверждает, что для каждого бесконечного кардинала нет кардиналов строго между и . Было доказано, что как гипотеза континуума, так и обобщенная гипотеза континуума независимы от обычных аксиом теории множеств, аксиом Цермело – Френкеля вместе с аксиомой выбора ( ZFC ).
Действительно, теорема Истона показывает, что для регулярных кардиналов единственные ограничения, которые ZFC накладывает на мощность, - это то , что , и что экспоненциальная функция не убывает.
Примечания
Библиография
