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

В конструктивной математике коллекция является подсчетной, если существует частичная сюръекция из натуральных чисел на нее. Это можно выразить как , где обозначает, что является сюръективной функцией из a на . Сюръекция является членом и здесь подкласс должен быть множеством. Другими словами, все элементы подсчетной коллекции функционально находятся в образе индексирующего множества счетных чисел , и, таким образом, множество можно понимать как доминируемое счетным множеством .${\displaystyle X}$ $${\displaystyle \exists (I\subseteq {\mathbb {N} }).\,\exists f.\,(f\colon I\twoheadrightarrow X),}$$${\displaystyle f\двоеточие I\twoheadrightarrow X}$${\displaystyle f}$${\displaystyle Я}$${\displaystyle X}$${\displaystyle {\mathbb {N} }\rightharpoonup X}$${\displaystyle Я}$${\displaystyle {\mathbb {N}}}$${\displaystyle X}$${\displaystyle I\subseteq {\mathbb {N} }}$${\displaystyle X}$${\displaystyle {\mathbb {N}}}$

Обратите внимание, что номенклатура свойств счетности и конечности существенно различается — отчасти потому, что многие из них совпадают при допущении исключенного третьего. Повторим, обсуждение здесь касается свойства, определенного в терминах сюръекций на характеризуемое множество. Язык здесь распространен в текстах по конструктивной теории множеств , но название подсчетный также давалось свойствам в терминах инъекций из характеризуемого множества.${\displaystyle X}$

Множество в определении также можно абстрагировать и в терминах более общего понятия назвать его подчастным . ${\displaystyle {\mathbb {N}}}$${\displaystyle X}$${\displaystyle {\mathbb {N}}}$

Важными являются случаи, когда рассматриваемое множество является некоторым подклассом большего класса функций, изучаемого в теории вычислимости . Для контекста напомним, что быть тотальным — это, как известно, неразрешимое свойство функций. Действительно, теорема Райса об индексных множествах , большинство доменов индексов, на самом деле, не являются вычислимыми множествами .

Не может быть вычислимой сюръекции из на множество полных вычислимых функций , как показано с помощью функции из диагональной конструкции, которая никогда не могла бы быть в таком изображении сюръекции. Однако с помощью кодов всех возможных частично вычислимых функций , которые также допускают нетерминированные программы, такие подмножества функций, такие как полные функции, рассматриваются как подсчетные множества: Полные функции являются диапазоном некоторого строгого подмножества натуральных чисел. Будучи доминируемым невычислимым множеством натуральных чисел, название подсчетный таким образом передает, что множество не больше . В то же время, для некоторых конкретных ограничительных конструктивных семантик функциональных пространств, в случаях, когда доказано, что не вычислимо перечислимо , такое также не счетно , и то же самое справедливо для .${\displaystyle n\mapsto f_ {n}}$${\displaystyle {\mathbb {N}}}$ ${\displaystyle X}$${\displaystyle n\mapsto f_ {n}(n)+1}$${\displaystyle Я}$${\displaystyle X}$${\displaystyle {\mathbb {N}}}$${\displaystyle Я}$${\displaystyle Я}$${\displaystyle X}$

Обратите внимание, что в определении подсчетности не утверждается эффективное отображение между всеми счетными числами и неограниченным и неконечным индексирующим множеством — только отношение подмножества . Демонстрация, которая является подсчетной в то же время, подразумевает, что она является классически (неконструктивно) формально счетной, но это не отражает никакой эффективной счетности. Другими словами, тот факт, что алгоритм, перечисляющий все полные функции в последовательности, не может быть закодирован, не охватывается классическими аксиомами относительно существования множеств и функций. Мы видим, что в зависимости от аксиом теории подсчетность может быть более вероятно доказуемой, чем счетность.${\displaystyle {\mathbb {N}}}$${\displaystyle Я}$${\displaystyle I\subseteq {\mathbb {N} }}$${\displaystyle X}$

В конструктивной логике и теории множеств существование функции между бесконечными (неконечными) множествами связывают с вопросами разрешимости и, возможно, эффективности . Там свойство подсчетности отделяется от счетности и, таким образом, не является избыточным понятием. Индексирующее множество натуральных чисел может быть постулировано как существующее, например, как подмножество с помощью аксиом теории множеств, таких как схема аксиом разделения . Тогда по определению , Но это множество может тогда все еще не быть отделяемым, в том смысле, что может быть не доказуемо без предположения его как аксиомы. Можно не эффективно подсчитать подсчетное множество , если не отобразить подсчитывающие числа в индексирующее множество , по этой причине. Быть счетным означает быть подсчетным . В соответствующем контексте с принципом Маркова обратное эквивалентно закону исключенного третьего , т. е. что для всех предложений выполняется . В частности, конструктивно это обратное направление, как правило, не выполняется.${\displaystyle Я}$${\displaystyle I\subseteq {\mathbb {N} }}$$${\displaystyle \forall (i\in I).(i\in {\mathbb {N} }).}$$$${\displaystyle \forall (n\in {\mathbb {N} }).{\big (}(n\in I)\lor \neg (n\in I){\big )}}$$${\displaystyle X}$${\displaystyle {\mathbb {N}}}$${\displaystyle Я}$${\displaystyle \фи}$${\displaystyle \phi \lor \neg \phi }$

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

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

Конструктивное доказательство также является классически допустимым. Если множество доказано несчетным конструктивно, то в классическом контексте оно доказуемо не подсчетным. Поскольку это применимо к , классическая структура с ее большим функциональным пространством несовместима с конструктивным тезисом Чёрча , аксиомой русского конструктивизма.${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$

Множество будет называться - продуктивным , если всякий раз, когда любое из его подмножеств является областью действия некоторой частичной функции на , всегда существует элемент , который остается в дополнении этой области действия. ^[1]${\displaystyle X}$${\displaystyle \омега}$${\displaystyle W\subset X}$${\displaystyle {\mathbb {N}}}$${\displaystyle d\in X\setminus W}$

Если существует какая-либо сюръекция на некоторое , то ее соответствующее дополнение, как описано, будет равно пустому множеству , и поэтому подсчетное множество никогда не является -продуктивным. Как определено выше, свойство быть -продуктивным связывает область действия любой частичной функции с определенным значением, не входящим в область действия функции, . Таким образом, множество, являющееся -продуктивным, говорит о том, насколько сложно сгенерировать все его элементы: они не могут быть сгенерированы из натуральных чисел с помощью одной функции. Свойство -продуктивности является препятствием для подсчетности. Поскольку это также подразумевает несчетность, диагональные аргументы часто включают это понятие, явно с конца семидесятых годов.${\displaystyle X}$${\displaystyle X\setminus X}$${\displaystyle \omega }$${\displaystyle \omega }$${\displaystyle W}$${\displaystyle d\in X}$${\displaystyle d\notin W}$${\displaystyle X}$${\displaystyle \omega }$${\displaystyle \omega }$

Можно установить невозможность вычислимой перечислимости, рассматривая только вычислимо перечислимые подмножества , и можно потребовать, чтобы множество всех препятствующих было образом полной рекурсивной так называемой производственной функции.${\displaystyle X}$${\displaystyle W}$${\displaystyle d}$

${\displaystyle {\mathbb {N} }\rightharpoonup X}$обозначает пространство, которое точно содержит все частичные функции на , имеющие в качестве своего диапазона только подмножества . В теории множеств функции моделируются как набор пар. Всякий раз, когда является набором, набор наборов пар может быть использован для характеристики пространства частичных функций на . Для -продуктивного набора можно найти${\displaystyle {\mathbb {N} }}$${\displaystyle W}$${\displaystyle X}$${\displaystyle {\mathcal {P}}{\mathbb {N} }}$${\displaystyle \cup _{I\subseteq {\mathbb {N} }}X^{I}}$${\displaystyle {\mathbb {N} }}$${\displaystyle \omega }$${\displaystyle X}$

${\displaystyle \forall (w\in ({\mathbb {N} }\rightharpoonup X)).\exists (d\in X).\forall (n\in {\mathbb {N} }).w(n)\neq d.}$

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

В качестве справочной теории мы рассматриваем конструктивную теорию множеств CZF, которая имеет Replacement , Bounded Separation , strong Infinity , является агностичной по отношению к существованию множеств мощности , но включает аксиому, которая утверждает, что любое функциональное пространство является множеством, если также являются множествами. В этой теории, кроме того, последовательно утверждать, что каждое множество является подсчетным. Совместимость различных дополнительных аксиом обсуждается в этом разделе посредством возможных сюръекций на бесконечном множестве счетных чисел . Здесь будет обозначать модель стандартных натуральных чисел.${\displaystyle Y^{X}}$${\displaystyle X,Y}$${\displaystyle I\subseteq {\mathbb {N} }}$${\displaystyle {\mathbb {N} }}$

Напомним, что для функций , по определению общей функциональности, существует уникальное возвращаемое значение для всех значений в домене, ${\displaystyle g\colon X\to Y}$${\displaystyle x\in X}$

${\displaystyle \exists !(y\in Y).g(x)=y,}$

и для подсчетного множества сюръекция все еще является полной на подмножестве . Конструктивно, меньше таких экзистенциальных утверждений будут доказуемы, чем классически.${\displaystyle {\mathbb {N} }}$

Ситуации, обсуждаемые ниже — на степенные классы против функциональных пространств — отличаются друг от друга: в отличие от общих подклассов, определяющих предикаты и их значения истинности (не обязательно доказуемо просто истина и ложь), функция (которая в терминах программирования является завершающей) делает доступной информацию о данных для всех своих поддоменов (подмножеств ). Когда функции являются характеристическими функциями для своих подмножеств , через свои возвращаемые значения определяют принадлежность к подмножеству. Поскольку принадлежность к общему определенному множеству не обязательно разрешима, (общие) функции не находятся автоматически во взаимной связи со всеми подмножествами . Таким образом, конструктивно, подмножества являются более сложной концепцией, чем характеристические функции. Фактически, в контексте некоторых неклассических аксиом поверх CZF даже класс мощности синглтона, например класс всех подмножеств , показан как надлежащий класс.${\displaystyle X}$${\displaystyle X\to \{0,1\}}$${\displaystyle X}$${\displaystyle {\mathcal {P}}\{0\}}$${\displaystyle \{0\}}$

Ниже используется тот факт, что частный случай закона введения отрицания подразумевает, что он противоречив.${\displaystyle (P\to \neg P)\to \neg P}$${\displaystyle P\leftrightarrow \neg P}$

Для простоты аргумента предположим, что есть множество. Затем рассмотрим подмножество и функцию . Далее, как в теореме Кантора о степенных множествах, определим ^[2] , где, Это подкласс определенного в зависимости от и его также можно записать Оно существует как подмножество посредством Разделения. Теперь предположение о существовании числа с влечет противоречие Так как множество, можно найти является -продуктивным в том смысле, что мы можем определить препятствие для любой заданной сюръекции. Также отметим, что существование сюръекции автоматически превратилось бы в множество посредством Замены в CZF, и поэтому существование этой функции безусловно невозможно. ${\displaystyle {\mathcal {P}}{\mathbb {N} }}$${\displaystyle I\subseteq {\mathbb {N} }}$${\displaystyle w\colon I\to {\mathcal {P}}{\mathbb {N} }}$$${\displaystyle d=\{k\in {\mathbb {N} }\mid k\in I\land D(k)\}}$$$${\displaystyle D(k)=\neg (k\in w(k)).}$$${\displaystyle {\mathbb {N} }}$${\displaystyle w}$$${\displaystyle d=\{k\in I\mid \neg (k\in w(k))\}.}$$${\displaystyle n\in I}$${\displaystyle w(n)=d}$$${\displaystyle n\in d\,\leftrightarrow \,\neg (n\in d).}$$${\displaystyle {\mathcal {P}}{\mathbb {N} }}$${\displaystyle \omega }$${\displaystyle d}$${\displaystyle f\colon I\twoheadrightarrow {\mathcal {P}}{\mathbb {N} }}$${\displaystyle {\mathcal {P}}{\mathbb {N} }}$

Мы приходим к выводу, что аксиома подсчетности, утверждающая, что все множества подсчетны, несовместима с тем, чтобы быть множеством, как это следует, например, из аксиомы мощности множества.${\displaystyle {\mathcal {P}}{\mathbb {N} }}$

Следуя вышеприведенному доказательству, становится ясно, что мы не можем отобразить ни на один из них. Ограниченное разделение действительно подразумевает, что ни одно множество не отображается на .${\displaystyle I}$${\displaystyle {\mathcal {P}}I}$${\displaystyle X}$${\displaystyle {\mathcal {P}}X}$

Соответственно, для любой функции , аналогичный анализ с использованием подмножества ее диапазона показывает, что не может быть инъекцией. Ситуация более сложная для функциональных пространств. ^[3]${\displaystyle h\colon {\mathcal {P}}Y\to Y}$${\displaystyle \{y\in Y\mid \exists (S\in {\mathcal {P}}Y).y=h(S)\land y\notin S\}}$${\displaystyle h}$

В классическом ZFC без Powerset или любого из его эквивалентов также последовательно, что все подклассы вещественных чисел, которые являются множествами, являются подсчетными. В этом контексте это переводится в утверждение, что все множества вещественных чисел счетны. ^[4] Конечно, эта теория не имеет функционального пространства set .${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$

По определению функциональных пространств множество содержит те подмножества множества , которые доказуемо являются тотальными и функциональными. Утверждение допустимой подсчетности всех множеств превращается, в частности, в подсчетное множество. ${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$${\displaystyle {\mathbb {N} }\times {\mathbb {N} }}$${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$

Итак, здесь мы рассматриваем сюръективную функцию и подмножество разделенного как ^[5] с диагонализирующим предикатом, определенным как который мы также можем сформулировать без отрицаний как Это множество является классически доказуемо функцией в , разработанной для принятия значения для конкретных входных данных . И его можно классически использовать для доказательства того, что существование как сюръекции на самом деле противоречиво. Однако, конструктивно, если только предложение в его определении не разрешимо, так что множество фактически определяет функциональное назначение, мы не можем доказать, что это множество является членом функционального пространства. И поэтому мы просто не можем сделать классический вывод.${\displaystyle f\colon I\twoheadrightarrow {\mathbb {N} }^{\mathbb {N} }}$${\displaystyle {\mathbb {N} }\times {\mathbb {N} }}$$${\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 D(n,y)={\big (}f(n)(n)=0\land y=1{\big )}\lor {\big (}f(n)(n)\geq 1\land y=0{\big )}.}$$${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$${\displaystyle y=0}$${\displaystyle n}$${\displaystyle f}$${\displaystyle n\in I}$

Таким образом, подсчетность допускается, и действительно существуют модели теории. Тем не менее, также в случае CZF, существование полной сюръекции , с областью , действительно противоречиво. Разрешимое членство в делает множество также не счетным, т.е. несчетным.${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$${\displaystyle {\mathbb {N} }\twoheadrightarrow {\mathbb {N} }^{\mathbb {N} }}$${\displaystyle {\mathbb {N} }}$${\displaystyle I={\mathbb {N} }}$

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

Аксиома подсчетности, утверждающая, что все множества подсчетны, несовместима с любой новой аксиомой, делающей множества счетными, включая LEM.${\displaystyle I}$

Приведенный выше анализ затрагивает формальные свойства кодировок . Были построены модели для неклассического расширения теории CZF постулатами подсчетности. ^[6] Такие неконструктивные аксиомы можно рассматривать как принципы выбора, которые, однако, не имеют тенденции значительно увеличивать доказательно-теоретическую силу теорий. ${\displaystyle \mathbb {R} }$

• Существуют модели IZF, в которых все множества с отношениями обособленности являются подсчетными. ^[7]
• CZF имеет модель, например, в теории типов Мартина-Лёфа . В этой конструктивной теории множеств с классически несчетными функциональными пространствами действительно последовательно утверждать аксиому подсчетности , утверждая, что каждое множество является подсчетным. Как обсуждалось, полученная теория противоречит аксиоме степенного множества и закону исключенного третьего .${\displaystyle {\mathsf {ML_{1}V}}}$
• Более того, некоторые модели теории множеств Крипке–Платека , теории без постулата о функциональном пространстве, даже подтверждают, что все множества счетны.

Подсчетность как суждение о малом размере не следует путать со стандартным математическим определением отношений мощности, как определено Кантором, при этом меньшая мощность определяется в терминах инъекций, а равенство мощностей определяется в терминах биекций. Конструктивно предпорядок " " на классе множеств не может быть разрешимым и антисимметричным. Функциональное пространство (а также ) в умеренно богатой теории множеств всегда оказывается ни конечным, ни биекцией с , по диагональному аргументу Кантора . Это то, что означает быть несчетным. Но аргумент о том, что мощность этого множества, таким образом, в некотором смысле превысит мощность натуральных чисел, опирается на ограничение только на классическую концепцию размера и ее индуцированное упорядочение множеств по мощности.${\displaystyle \leq }$${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$${\displaystyle \{0,1\}^{\mathbb {N} }}$${\displaystyle {\mathbb {N} }}$

Как видно из примера пространства функций, рассматриваемого в теории вычислимости , не каждое бесконечное подмножество из обязательно находится в конструктивной биекции с , тем самым оставляя место для более тонкого различия между несчетными множествами в конструктивных контекстах. Мотивированное вышеприведенными разделами, бесконечное множество можно считать «меньше», чем класс .${\displaystyle {\mathbb {N} }}$${\displaystyle {\mathbb {N} }}$${\displaystyle {\mathbb {N} }^{\mathbb {N} }}$${\displaystyle {\mathcal {P}}{\mathbb {N} }}$

Субсчетное множество альтернативно также называется субсчетно индексированным . Аналогичное понятие существует, в котором " " в определении заменяется существованием множества, являющегося подмножеством некоторого конечного множества. Это свойство по-разному называется субконечно индексированным .${\displaystyle \exists (I\subseteq {\mathbb {N} })}$

В теории категорий все эти понятия являются подчастными.

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