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

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

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

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

В конструктивной логике и теории множеств существование функции между бесконечными (неконечными) множествами связывают с вопросами разрешимости и, возможно, эффективности . Там свойство подсчетности отделяется от счетности и, таким образом, не является избыточным понятием. Индексирующее множество натуральных чисел может быть постулировано как существующее, например, как подмножество с помощью аксиом теории множеств, таких как схема аксиом разделения . Тогда по определению , Но это множество может тогда все еще не быть отделяемым, в том смысле, что может быть не доказуемо без предположения его как аксиомы. Можно не эффективно подсчитать подсчетное множество , если не отобразить подсчитывающие числа в индексирующее множество , по этой причине. Быть счетным означает быть подсчетным . В соответствующем контексте с принципом Маркова обратное эквивалентно закону исключенного третьего , т. е. что для всех предложений выполняется . В частности, конструктивно это обратное направление, как правило, не выполняется. ${\displaystyle I}$ ${\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 I}$ ${\displaystyle \phi }$ ${\displaystyle \phi \lor \neg \phi }$

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

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

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

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

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

Ссылки

1. Герт Смолка, Парадокс Сколемса и конструктивизм, Конспект лекций, Саарский университет, январь 2015 г.
2. Мехкери, Дэниел (2010), Простая вычислительная интерпретация теории множеств , arXiv : 1005.4380
3. Бауэр, А. "Инъекция из N^N в N", 2011
4. Гитман, Виктория (2011), Что такое теория ZFC без набора мощности , arXiv : 1110.2430
5. Белл, Джон Л. (2004), «Парадокс Рассела и диагонализация в конструктивном контексте» (PDF) , в Link, Godehard (ред.), Сто лет парадокса Рассела , De Gruyter Series in Logic and its Applications, т. 6, de Gruyter, Берлин, стр. 221–225, MR  2104745
6. Rathjen, Michael (2006), «Принципы выбора в конструктивных и классических теориях множеств» (PDF) , в Chatzidakis, Zoé; Koepke, Peter; Pohlers, Wolfram (ред.), Logic Colloquium '02: Совместные труды Ежегодной европейской летней встречи Ассоциации символической логики и Двухгодичной встречи Немецкой ассоциации математической логики и основ точных наук (Colloquium Logicum), состоявшейся в Мюнстере, 3–11 августа 2002 г. , Lecture Notes in Logic, т. 27, La Jolla, CA: Association for Symbolic Logic, стр. 299–326, MR  2258712
7. Маккарти, Чарльз (1986), «Подсчетность при реализуемости», Notre Dame Journal of Formal Logic , 27 (2): 210–220, doi : 10.1305/ndjfl/1093636613 , MR  0842149