WikiDer > Подсчетность

Эта статья включает в себя список общих Рекомендации, но он остается в основном непроверенным, потому что ему не хватает соответствующих встроенные цитаты. Пожалуйста, помогите улучшать эта статья введение более точные цитаты. (Сентябрь 2020) (Узнайте, как и когда удалить этот шаблон сообщения)

В конструктивная математика, Коллекция ${ displaystyle X}$ является подсчетный если существует частичный сюрприз от натуральные числа на него. Это можно выразить как

${ displaystyle exists (I substeq omega). , exists f. , (f двоеточие I twoheadrightarrow X).}$

куда ${ displaystyle omega}$ - счетные числа (${ Displaystyle { mathbb {N}}}$ без учета арифметики) и где ${ displaystyle f двоеточие I twoheadrightarrow X}$ означает, что пересечение ${ displaystyle f}$ и ${ Displaystyle I раз X}$ дает полное отношение то есть сюръективно. Другими словами, все элементы подсчетной коллекции ${ displaystyle X}$ функционально представляют собой индексирующий набор счетных чисел ${ Displaystyle I substeq omega}$ и, таким образом, множество ${ displaystyle X}$ можно понимать как доминирующее счётное множество ${ displaystyle omega}$.

Обсуждение

Пример

Важный случай, когда ${ displaystyle X}$ обозначает некоторый подкласс большего класса функций, как изучено в теория вычислимости.

Рассмотрим подкласс общие функции и обратите внимание, что быть полным не является разрешимым свойством, то есть не может быть конструктивного взаимно однозначного соответствия между полными функциями и натуральными числами. Однако посредством перечисления кодов всех возможных частичных функций (которые также включают в себя функции без завершения) их подмножества, такие как общие функции, рассматриваются как подсчетные множества. Обратите внимание, что Теорема Райса на наборы индексов, большинство доменов ${ displaystyle I}$ не рекурсивны. Действительно, нет эффективной карты между всеми счетными числами ${ displaystyle omega}$ и бесконечное (не конечное) множество индексации ${ displaystyle I}$ здесь утверждается, просто отношение подмножества ${ Displaystyle I substeq omega}$. Доминирование конструктивно несчетным набором чисел ${ displaystyle I}$, название подсчетный таким образом означает, что несчетное множество ${ displaystyle X}$ не больше чем ${ displaystyle omega}$.

Демонстрация того, что ${ displaystyle X}$ субсчетный также означает, что он классически (неконструктивно) формально счетный, но это не отражает какой-либо эффективной счетности. Другими словами, тот факт, что алгоритм, перечисляющий все функции в целом, не может быть закодирован, не фиксируется классическими аксиомами о существовании множеств и функций. Мы видим, что в зависимости от аксиом субсчетность может быть более доказуемой, чем счетность.

Отношение к исключенному среднему

В конструктивная логика и установить теории, которые связывают существование функции между бесконечными (не конечными) множествами с вопросами эффективность и разрешимость, свойство подсчетности отделяется от счетности и, следовательно, не является избыточным понятием. Набор для индексации ${ displaystyle I}$ натуральных чисел может существовать, например как подмножество с помощью теоретических аксиом, таких как Аксиома разделения, так что

${ Displaystyle forall (я в я). (я в омега)}$.

Но этот набор может и не быть съемным в том смысле, что

${ Displaystyle forall (п в омега). { большой (} (п в я) лор нег (п в я) { большой)}}$

невозможно доказать, не приняв это за аксиому. ${ displaystyle X}$ если не удается сопоставить счетные числа ${ displaystyle omega}$ в набор индексации ${ displaystyle I}$, по этой причине.

В классической математике

Утверждая все законы классической логики, дизъюнктивное свойство ${ displaystyle I}$ рассмотренное выше действительно верно для всех наборов. Тогда для непустого ${ displaystyle X}$, числовые свойства (${ displaystyle X}$ вводит в ${ displaystyle omega}$), счетное (${ displaystyle omega}$ имеет ${ displaystyle X}$ как его диапазон), субсчетный (подмножество ${ displaystyle omega}$ сюрпризы в ${ displaystyle X}$) а также не ${ displaystyle omega}$-продуктивная (свойство счетности, существенно определяемое в терминах подмножеств ${ displaystyle X}$, формализованные ниже) все эквивалентны и выражают, что множество конечный или же счетно бесконечный.

Неклассические утверждения

Не утверждая закон исключенного среднего

${ Displaystyle ( фи лор нег фи)}$ для всех предложений ${ displaystyle phi}$,

тогда также может быть непротиворечивым утверждение о подсчетности множеств, которые классически (т. е. неконструктивно) превышают мощность натуральных чисел. Обратите внимание, что в конструктивном контексте утверждение о счетности примерно ${ Displaystyle { mathbb {N}} ^ { mathbb {N}}}$ из полного набора ${ displaystyle omega}$, как в ${ displaystyle omega twoheadrightarrow { mathbb {N}} ^ { mathbb {N}}}$, может быть опровергнуто. Но подсчет ${ displaystyle I twoheadrightarrow { mathbb {N}} ^ { mathbb {N}}}$ бесчисленного множества ${ Displaystyle { mathbb {N}} ^ { mathbb {N}}}$ набором ${ Displaystyle I substeq omega}$ это не эффективно отделяется от ${ displaystyle omega}$ может быть разрешено.

Установить теории

Канторовские аргументы о подмножествах натуральных чисел

В функциональные пространства

Например, теория CZF имеет Ограниченное разделение, Бесконечность, не зависит от существования комплекты питания, но он включает аксиому, которая утверждает, что любое функциональное пространство ${ displaystyle X ^ {Y}}$ установлено, учитывая ${ displaystyle X, Y}$ тоже наборы. В этой теории, кроме того, логично утверждать, что каждый набор субсчетный.

Утверждая разрешенную субсчетность всех наборов, ${ Displaystyle { mathbb {N}} ^ { mathbb {N}}}$ субсчет в частности. Для функции на бесконечном подмножестве счетных чисел ${ displaystyle f двоеточие I twoheadrightarrow { mathbb {N}} ^ { mathbb {N}}}$, множество понималось как^[1]

${ displaystyle { Big {} langle n, y rangle in { mathbb {N}} times { mathbb {N}} mid { big (} n in I land D (n , y) { big)} lor { big (} neg (n in I) land y = 1 { big)} { Big }}}$

с диагонализацией

${ Displaystyle D (N, Y) = { big (} neg (f (n) (n) geq 1) land y = 1 { big)} lor { big (} neg (f (n) (n) = 0) land y = 0 { big)}}$

классически функция в ${ Displaystyle { mathbb {N}} ^ { mathbb {N}}}$Однако конструктивно набор не приводит к нарушению потенциальной сюръективности ${ displaystyle f}$, пока не ${ displaystyle n in I}$ разрешима, например когда ${ Displaystyle I = { mathbb {N}}}$. Полная сюръекция ${ displaystyle { mathbb {N}} twoheadrightarrow { mathbb {N}} ^ { mathbb {N}}}$, с доменом ${ Displaystyle { mathbb {N}}}$, действительно противоречиво.

Для любого ненулевого числа ${ displaystyle d}$, функции ${ Displaystyle я mapsto f (я) (я) + d}$ в ${ displaystyle I to { mathbb {N}}}$ не может распространяться на все ${ Displaystyle { mathbb {N}}}$ по той же причине. Обратите внимание, что при задании ${ displaystyle n in { mathbb {N}}}$, нельзя обязательно решить, ${ displaystyle n in I}$, т.е. имеет ли значение продолжения потенциальной функции на ${ displaystyle n}$ уже определяется ${ displaystyle f}$. Другими словами, есть частичные функции, которые нельзя расширить до полных функций. ${ displaystyle { mathbb {N}} to { mathbb {N}}}$.

Аксиома субсчетности несовместима с какими-либо новыми аксиомами. ${ displaystyle I}$ счетные, в том числе ЛЕМ.

В классы мощности

Предполагая ${ Displaystyle { mathcal {P}} { mathbb {N}}}$ - множество, множество, нарушающее возможную сюръекцию ${ displaystyle f двоеточие I twoheadrightarrow { mathcal {P}} { mathbb {N}}}$, данный

${ Displaystyle {п ин { mathbb {N}} середина п ин I земля D (п) }}$

куда

${ Displaystyle D (п) = neg { big (} п in f (n) { big)}}$,

в Теорема кантора о множествах власти существует через Разделение и действительно сразу приводит к противоречию.^[2] Это демонстрирует, что ${ Displaystyle { mathcal {P}} { mathbb {N}}}$ на самом деле не может быть набором и, следовательно, является правильным классом.

Две обсуждаемые ситуации отличаются тем, что функция делает доступными данные для всех своих поддоменов (подмножеств надмножества). Естественно, что в CZF общие функции ${ Displaystyle Х к {0,1 }}$ не находятся в биекции с подмножествами ${ displaystyle X}$, более сложная концепция. Фактически, даже набор мощности синглтона, например ${ Displaystyle { mathcal {P}} {0 }}$, показано, что это правильный класс в этом контексте (доказано, что существуют не только два значения истинности ${ displaystyle 0}$ и ${ displaystyle 1}$).

Понятие размера

Исходя из вышесказанного, бесконечное множество ${ Displaystyle { mathbb {N}} ^ { mathbb {N}}}$ можно считать «меньше», чем класс ${ Displaystyle { mathcal {P}} { mathbb {N}}}$Подсчетность не следует путать со стандартным математическим определением отношений мощности, как определено Кантором, с меньшей мощностью, определяемой в терминах инъекций. снаружи ${ displaystyle X}$ а равенство мощностей определяется в терминах взаимных отклонений. Кроме того, обратите внимание, что конструктивно упорядочивание "${ displaystyle <}$"как и мощность мощности могут быть неразрешимыми. Как видно на примере функционального пространства, рассматриваемого в теория вычислимости, не каждое бесконечное подмножество ${ displaystyle omega}$ обязательно находится в конструктивном взаимно однозначном соответствии с ${ displaystyle omega}$, тем самым оставляя место для более тонкого разграничения несчетных множеств в конструктивных контекстах. Функциональное пространство ${ Displaystyle { mathbb {N}} ^ { mathbb {N}}}$ (а также ${ Displaystyle {0,1 } ^ { mathbb {N}}}$) в умеренно богатой теории множеств всегда оказывается ни конечной, ни биективной с ${ Displaystyle { mathbb {N}}}$, к Диагональный аргумент Кантора. Вот что значит быть бесчисленным. Но аргумент, что мощность этого набора, таким образом, в некотором смысле превосходит натуральные числа, полагается только на классическую концепцию размера и ее индуцированное упорядочение множеств по мощности.

Модели

Проведенный выше анализ влияет на формальные свойства кодировок ${ Displaystyle mathbb {R}}$. Построены модели для этого неклассического расширения теории КЦФ.^[3] Такие неконструктивные аксиомы можно рассматривать как принципы выбора, которые, однако, не имеют тенденции к увеличению доказательство теоретической силы теорий много.

Еще примеры:

• Есть модели IZF в котором все наборы с отношения обособленности являются субсчетными.^[4]
• В CZF, как обсуждалось, действительно последовательно утверждать Аксиома подсчетности который все наборы (внутренне) субсчетные. Полученная теория противоречит Аксиома власти и с закон исключенного среднего.
• Более того, некоторые модели Теория множеств Крипке-Платека убедитесь, что все наборы даже счетны.

Subcountable подразумевает не ${ displaystyle omega}$-продуктивный

Любой счетный набор является субсчетным, а любой субсчетный набор - нет. ${ displaystyle omega}$-продуктивно: Набор ${ displaystyle X}$ как говорят ${ displaystyle omega}$-продуктивный если, всякий раз, когда любое из его подмножеств является диапазон некоторая частичная функция ${ displaystyle g}$, всегда остается хотя бы один элемент, выходящий за пределы этого диапазона. Это можно выразить как

${ displaystyle forall g. , { big (} (g двоеточие omega к X) подразумевает существует (x in X). , x notin { mathrm {rng}} (g) {большой )}.}$

Набор, являющийся ${ displaystyle omega}$-productive говорит о том, насколько сложно создать его элементы: они не могут быть созданы с помощью одной функции. В качестве таких, ${ displaystyle omega}$-производственные наборы не учитываются.Диагональные аргументы часто включают это понятие явно или неявно.

Смотрите также

• Диагональный аргумент Кантора
• Вычислимая функция
• Конструктивная теория множеств
• Теорема Шредера – Бернштейна.
• Общий заказ

Рекомендации