Кардинальное число

Эта статья о математической концепции. Числовые слова, обозначающие количество («три» яблока, «четыре» птицы и т. д.), см. Кардинальное числительное .

Биективная функция f демонстрирует, что множества имеют одинаковую мощность, в : X → Y от множества X к множеству Y данном случае равную кардинальному числу 4.

Алеф-нуль , наименьший бесконечный кардинал

В математике кардинальное число , или сокращенно кардинал , — это то, что обычно называют числом элементов множества . Следовательно, в случае конечного множества его кардинальное число или мощность является натуральным числом . Для рассмотрения случая бесконечных множеств были введены бесконечные кардинальные числа , которые часто обозначаются еврейской буквой. $\aleph$ ( алеф ) отмечены нижним индексом, обозначающим их ранг среди бесконечных кардиналов.

Мощность определяется в терминах биективных функций . Два множества имеют одинаковую мощность тогда и только тогда , когда существует взаимно однозначное соответствие (биекция) между элементами двух множеств. В случае конечных множеств это согласуется с интуитивным представлением о количестве элементов. В случае бесконечных множеств поведение более сложное. Фундаментальная теорема Георга Кантора показывает, что бесконечные множества могут иметь разную мощность, и, в частности, мощность набора действительных чисел больше, чем мощность набора натуральных чисел. Также возможно, что собственное подмножество бесконечного множества будет иметь ту же мощность, что и исходное множество, чего не может случиться с правильными подмножествами конечных множеств.

Существует трансфинитная последовательность кардинальных чисел:

$0,1,2,3,\ldots ,n,\ldots ;\aleph _{0},\aleph _{1},\aleph _{2},\ldots ,\aleph _{\alpha },\ldots .\$

Эта последовательность начинается с натуральных чисел, включая ноль (конечные кардиналы), за которыми следуют числа алефов . Числа алефа индексируются порядковыми номерами . Если выбранная аксиома верна, эта трансфинитная последовательность включает в себя все кардинальные числа. Если выбранная аксиома неверна (см. Аксиому выбора § Независимость ), существуют бесконечные кардиналы, которые не являются числами алеф.

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

История

Понятие мощности в нынешнем понимании было сформулировано Георгом Кантором , создателем теории множеств , в 1874–1884 годах. Мощность можно использовать для сравнения аспектов конечных множеств. Например, множества {1,2,3} и {4,5,6} не равны , но имеют одинаковую мощность , а именно три. Это устанавливается существованием биекции ( т. е. взаимно однозначного соответствия) между двумя множествами, например соответствия {1→4, 2→5, 3→6}.

Кантор применил свою концепцию биекции к бесконечным множествам. (например, набор натуральных чисел N = {0, 1, 2, 3, ...}). Таким образом, он назвал все множества, имеющие биекцию с N счетными (счетно бесконечными) множествами , которые все имеют одно и то же кардинальное число. Это кардинальное число называется $\aleph _{0}$, алеф-ноль . Он назвал кардинальные числа бесконечных множеств трансфинитными кардинальными числами .

Кантор доказал, что любое неограниченное подмножество N , хотя может показаться , имеет ту же мощность, что и N что это противоречит интуиции. Он также доказал, что множество всех упорядоченных пар натуральных чисел счетно; это означает, что множество всех рациональных чисел также счетно, поскольку каждое рациональное число может быть представлено парой целых чисел. Позже он доказал, что множество всех действительных алгебраических чисел также счетно. Каждое действительное алгебраическое число z может быть закодировано как конечная последовательность целых чисел, которые являются коэффициентами в полиномиальном уравнении, решением которого оно является, т.е. упорядоченный набор из n ( a ₀ , a ₁ , ..., a _n ) , a _i ∈ Z вместе с парой рациональных чисел ( b ₀ , b ₁ ) таких, что — единственный корень многочлена с коэффициентами ( a ₀ , a ₁ , ..., an _z ), лежащего в интервале ( б ₀ , б ₁ ).

В своей статье 1874 года « О свойстве совокупности всех действительных алгебраических чисел » Кантор доказал, что существуют кардинальные числа более высокого порядка, показав, что множество действительных чисел имеет мощность большую, чем N. мощность В его доказательстве использовался аргумент с вложенными интервалами , но в статье 1891 года он доказал тот же результат, используя свой остроумный и гораздо более простой диагональный аргумент . Новое кардинальное число множества действительных чисел называется мощностью континуума , и Кантор использовал символ ${\mathfrak {c}}$ для этого.

Кантор также разработал большую часть общей теории кардинальных чисел; он доказал, что существует наименьшее трансфинитное кардинальное число ( $\aleph _{0}$, aleph-null), и что для каждого кардинального числа есть следующее по величине кардинальное число.

$(\aleph _{1},\aleph _{2},\aleph _{3},\ldots ).$

Его континуальная гипотеза состоит в том, что мощность ${\mathfrak {c}}$ набора действительных чисел то же самое, что $\aleph _{1}$. Эта гипотеза не зависит от стандартных аксиом математической теории множеств, то есть на их основе ее нельзя ни доказать, ни опровергнуть. Это было показано в 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}, тогда, используя это понятие размера, мы бы заметили, что существует отображение:

1 → а

2 → б

3 → с

который является инъективным, и, следовательно, заключаем, что мощность Y больше или равна X . Элемент d не имеет никакого отображения на него, но это разрешено, поскольку нам требуется только инъективное отображение, а не обязательно биективное отображение. Преимущество этого понятия в том, что его можно распространить на бесконечные множества.

Затем мы можем расширить это до отношения в стиле равенства. два множества X и Y Говорят, что имеют одинаковую мощность существует биекция , если между X и Y . По теореме Шредера-Бернштейна это эквивалентно существованию как инъективного отображения в Y , так и инъективного отображения Y в X. X Затем мы пишем | Х | = | Ю |. Кардинальное число самого X часто определяется как наименьший порядковый номер a с | а | = | Х |. Это называется кардинальным присвоением фон Неймана ; чтобы это определение имело смысл, необходимо доказать, что каждое множество имеет ту же мощность, что и некоторый порядковый номер; это утверждение является принципом хорошего порядка . Однако можно обсуждать относительную мощность множеств без явного присвоения имен объектам.

Классический пример — парадокс бесконечного отеля, также называемый парадоксом Гильберта Гранд-отеля . Предположим, в отеле с бесконечным числом номеров есть трактирщик. Отель полон, и тут приезжает новый гость. Можно разместить дополнительного гостя, попросив гостя, который был в комнате 1, переехать в комнату 2, гостя из комнаты 2 — в комнату 3 и так далее, оставив комнату 1 свободной. Мы можем явно написать сегмент этого отображения:

1 → 2

2 → 3

3 → 4

...

п → п + 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 и имеет наименьший ранг , то это сработает (это трюк из-за Дана Скотт : это работает, потому что коллекция объектов любого заданного ранга представляет собой набор).

Кардинальное присвоение фон Неймана подразумевает, что кардинальное число конечного набора является общим порядковым числом всех возможных правильных порядков этого набора, а кардинальная и порядковая арифметика (сложение, умножение, степень, правильное вычитание) тогда дают одни и те же ответы для конечных чисел. цифры. Однако они различаются для бесконечных чисел. Например, $2^{\omega }=\omega <\omega ^{2}$ в порядковой арифметике, пока $2^{\aleph _{0}}>\aleph _{0}=\aleph _{0}^{2}$ в кардинальной арифметике, хотя задание фон Неймана ставит $\aleph _{0}=\omega$. С другой стороны, трюк Скотта подразумевает, что кардинальное число 0 $\{\emptyset \}$, который также является порядковым номером 1, и это может сбивать с толку. Возможный компромисс (чтобы воспользоваться преимуществом выравнивания в конечной арифметике, избегая при этом зависимости от аксиомы выбора и путаницы в бесконечной арифметике) состоит в том, чтобы применить присвоение фон Неймана к кардинальным числам конечных множеств (тех, которые могут быть хорошо упорядочены и не являются равносильны собственным подмножествам) и использовать трюк Скотта для количественных чисел других множеств.

Формально порядок кардинальных чисел определяется следующим образом: | Х | ≤ | Ю | означает, что существует инъективная функция из X в Y . Теорема Кантора –Бернштейна–Шредера утверждает, что если | Х | ≤ | Ю | и | Ю | ≤ | Х | тогда | Х | = | Ю |. Аксиома выбора эквивалентна утверждению, что для данных двух множеств X и Y либо | Х | ≤ | Ю | или | Ю | ≤ | Х |.

Множество X является дедекиндово бесконечным , если существует собственное подмножество Y множества X такое, что | Х | = | Y |, и дедекинд-конечное, если такого подмножества не существует. Конечные кардиналы — это просто натуральные числа в том смысле, что множество X конечно тогда и только тогда, когда | Х | = | п | = n для некоторого натурального числа n . Любое другое множество бесконечно .

Приняв аксиому выбора, можно доказать, что понятия Дедекинда соответствуют стандартным. Можно также доказать, что кардинал $\aleph _{0}$ ( алеф ноль или алеф-0, где алеф — первая буква еврейского алфавита , представленная $\aleph$) множества натуральных чисел является наименьшим бесконечным кардиналом (т. е. любое бесконечное множество имеет подмножество мощности $\aleph _{0}$). Следующий больший кардинал обозначается $\aleph _{1}$, и так далее. Для каждого порядкового числа α существует кардинальное число $\aleph _{\alpha },$ и этот список исчерпывает все бесконечные кардинальные числа.

Кардинальная арифметика

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

Кардинал-преемник

Дополнительная информация: Кардинал-преемник.

Если аксиома выбора верна, то каждый кардинал κ имеет преемника, обозначаемого κ ⁺ , где κ ⁺ > κ и между κ и его преемником нет кардиналов. (Без аксиомы выбора, используя теорему Хартогса , можно показать, что для любого кардинального числа κ существует минимальный кардинал κ ⁺ такой, что $\kappa ^{+}\nleq \kappa .$) Для конечных кардиналов преемником является просто κ + 1. Для бесконечных кардиналов преемник кардинал отличается от порядкового номера преемника .

Кардинальное дополнение

Если X и Y пересекаются не определяется объединением X и сложение Y. , Если два множества еще не являются непересекающимися, то их можно заменить непересекающимися множествами той же мощности (например, заменить X на X ×{0} и Y на Y ×{1}).

$|X|+|Y|=|X\cup Y|.$

Ноль — аддитивное тождество κ + 0 = 0 + κ = κ .

Сложение ассоциативно ( κ + µ ) + ν = κ + ( µ + ν ).

Сложение коммутативно κ + µ = µ + κ .

Сложение неубывает по обоим аргументам:

$(\kappa \leq \mu )\rightarrow ((\kappa +\nu \leq \mu +\nu ){\mbox{ and }}(\nu +\kappa \leq \nu +\mu )).$

Если принять аксиому выбора, сложить бесконечные кардинальные числа несложно. Если либо κ , либо µ бесконечны, то

$\kappa +\mu =\max\{\kappa ,\mu \}\,.$

Вычитание

Предполагая выбранную аксиому и учитывая бесконечный кардинал σ и кардинал µ , существует кардинал κ такой, что µ + κ = σ тогда и только тогда, когда µ ≤ σ . Оно будет единственным (и равным σ ) тогда и только тогда, когда µ < σ .

Кардинальное умножение

Произведение кардиналов происходит от декартова произведения .

$|X|\cdot |Y|=|X\times Y|$

κ 0 = 0 κ = 0.

κ · µ = 0 → ( κ = 0 или µ = 0).

Одним из них является мультипликативное тождество κ ·1 = 1 · κ = κ .

Умножение ассоциативно ( · ν ν ; = κ · ( µ · κ )

Умножение коммутативно κ · µ = µ · κ .

Умножение не убывает по обоим аргументам: κ ≤ µ → ( κ · ν ≤ µ · ν и ν · κ ≤ ν · µ ).

Умножение распределяет над сложением: κ ·( µ + ν ) = κ · µ + κ · ν и( μ + ν ); κ знак равно μ · κ + ν · κ ;

Если принять аксиому выбора, умножение бесконечных кардинальных чисел также легко. Если либо κ , либо µ бесконечны и оба отличны от нуля, то

$\kappa \cdot \mu =\max\{\kappa ,\mu \}.$

Разделение

Предполагая аксиому выбора и учитывая бесконечный кардинал π и ненулевой кардинал µ , существует кардинал κ такой, что µ · κ = π тогда и только тогда, когда µ ≤ π . Оно будет единственным (и равным π ) тогда и только тогда, когда µ < π .

Кардинальное возведение в степень

Возведение в степень определяется выражением

$|X|^{|Y|}=\left|X^{Y}\right|,$

где Х ^И это набор всех функций от Y до X. — Легко проверить, что правая часть зависит только от ${|X|}$ и ${|Y|}$.

Мистер ⁰ = 1 (в частности 0 ⁰ = 1), см. пустую функцию .

Если 1 ≤ µ , то 0 ^м = 0.

1 ^м = 1.

Мистер ¹ = к .

Мистер ^{м + н} = Мистер ^м · Мистер ^н .

Мистер ^{м · н} = ( Господин ^м ) ^н .

( к · м ) ^н = Мистер ^н · м ^н .

Возведение в степень не убывает по обоим аргументам:

(1 ≤ ν и κ ≤ µ ) → ( ν ^Мистер ≤ n ^м ) и

( κ ≤ μ ) → ( κ ^н ≤ м ^н ).

2 ^{| Х |} - мощность набора степеней множества X , а диагональный аргумент Кантора показывает, что 2 ^{| Х |} > | Х | для любого X. множества Это доказывает, что никакого наибольшего кардинала не существует (поскольку для любого кардинала κ мы всегда можем найти больший кардинал 2 ^Мистер ). На самом деле класс кардиналов — это настоящий класс . (Это доказательство терпит неудачу в некоторых теориях множеств, особенно в «Новых основаниях ».)

Все остальные предложения в этом разделе предполагают аксиому выбора:

Если κ и µ конечны и больше 1, а ν бесконечно, то κ ^н = м ^н .

Если κ бесконечно, а µ конечно и ненулевое, то κ ^м = к .

Если 2 ≤ κ и 1 ≤ µ и хотя бы один из них бесконечен, то:

Макс ( к , 2 ^м ) ≤ к ^м ≤ Макс (2 ^Мистер , 2 ^м ).

Используя теорему Кенига , можно доказать, что κ < κ ^{ср( к )} и κ < cf(2 ^Мистер ) для любого бесконечного кардинала , где cf( κ ) — конфинальность κ κ .

Корни

Предполагая выбранную аксиому и учитывая бесконечный кардинал κ и конечный кардинал µ, больший 0, кардинал ν, удовлетворяющий $\nu ^{\mu }=\kappa$ будет $\kappa$.

Логарифмы

Предполагая аксиому выбора и учитывая бесконечный кардинал κ и конечный кардинал µ, больший 1, может существовать или не быть кардинал λ, удовлетворяющий $\mu ^{\lambda }=\kappa$. Однако, если такой кардинал существует, он бесконечен и меньше κ , и любая конечная мощность ν больше 1 также будет удовлетворять $\nu ^{\lambda }=\kappa$.

Логарифм бесконечного кардинального числа κ определяется как наименьшее кардинальное число µ такое, что κ ≤ 2 ^м . Логарифмы бесконечных кардиналов полезны в некоторых областях математики, например, при изучении кардинальных инвариантов топологических пространств , хотя им не хватает некоторых свойств, которыми обладают логарифмы положительных действительных чисел.

Гипотеза континуума

Гипотеза континуума (CH) утверждает, что строго между кардиналами нет $\aleph _{0}$ и $2^{\aleph _{0}}.$ Последнее кардинальное число также часто обозначается ${\mathfrak {c}}$; это мощность континуума (набора действительных чисел ). В этом случае $2^{\aleph _{0}}=\aleph _{1}.$

Аналогичным образом, обобщенная гипотеза континуума (GCH) утверждает, что для каждого бесконечного кардинала $\kappa$, нет кардиналов строго между $\kappa$ и $2^{\kappa }$. Было доказано, что как гипотеза континуума, так и обобщенная гипотеза континуума независимы от обычных аксиом теории множеств, аксиом Цермело – Френкеля вместе с аксиомой выбора ( ZFC ).

Действительно, теорема Истона показывает, что для правильных кардиналов $\kappa$, единственные ограничения, которые ZFC накладывает на мощность $2^{\kappa }$ это что $\kappa <\operatorname {cf} (2^{\kappa })$, и что показательная функция не убывает.

См. также

• Число Алеф
• Число Бет
• Парадокс величайшего кардинала
• Кардинальное число (лингвистика)
• Подсчет
• Принцип включения-исключения
• Большой кардинал
• Названия чисел на английском языке
• Номинальный номер
• Порядковый номер
• Обычный кардинал

Ссылки

Примечания

Библиография

• Даубен, Джозеф Уоррен (1990), Георг Кантор: его математика и философия бесконечного , Принстон: Princeton University Press, ISBN  0691-02447-2
• Хан, Ганс , Бесконечность , Часть IX, Глава 2, Том 3 « Мира математики» . Нью-Йорк: Саймон и Шустер, 1956.
• Халмос, Пауль , Наивная теория множеств . Принстон, Нью-Джерси: Компания Д. Ван Ностранда, 1960. Перепечатано Springer-Verlag, Нью-Йорк, 1974. ISBN   0-387-90092-6 (издание Springer-Verlag).
• Шиндлер, Ральф-Дитер (2014). Теория множеств: исследование независимости и истины . Университеттекст. Чам: Спрингер-Верлаг . дои : 10.1007/978-3-319-06725-4 . ISBN  978-3-319-06725-4 .

Внешние ссылки

• «Кардинальное число» , Математическая энциклопедия , EMS Press , 2001 [1994]