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

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

${\ Displaystyle \ существует (I \ substeq \ omega). \, \ exists f. \, (f \ двоеточие I \ twoheadrightarrow X).}$

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

Обсуждение

Пример

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

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

Как несчетно и классический , в своей очереди доказуемо не subcountable, классическая структура с большой функцией пространства несовместима с тезисом Конструктивной Церкви , аксиомой русского конструктивизма. ${\ Displaystyle {\ mathbb {N}} ^ {\ mathbb {N}}}$

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

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

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

Совместимость различных аксиом обсуждается в этом разделе посредством возможных сюрпризов на бесконечный набор счетных чисел . ${\ Displaystyle I \ подмножество {\ mathbb {N}}}$

В функциональных пространствах по сравнению в классах мощности - - Рассмотренные ниже ситуации различны , поскольку для функций , по определению существует единственное значение , возвращаемое для каждого значения в домене . В отличие от общих предикатов и их значений истинности (не обязательно только истинных и ложных), функция (которая в терминах программирования завершается) делает доступной информацию о данных для всех своих поддоменов (подмножеств ). Рассматриваемые как характерные функции, они определяют членство. Таким образом, в (общие) функции не находятся автоматически в взаимно однозначном соответствии со всеми подмножествами . Конструктивно подмножества представляют собой более сложное понятие, чем характеристические функции. ${\ displaystyle f \ двоеточие от X \ до Y}$${\ displaystyle x \ in X}$${\ Displaystyle \ существует! (у \ в Y). f (х) = у}$${\ displaystyle X}$${\ displaystyle {\ mathsf {CZF}}}$${\ Displaystyle Х \ к \ {0,1 \}}$${\ displaystyle X}$

Фактически, в контексте некоторых неклассических аксиом, даже класс мощности одиночного элемента, например, класс всех подмножеств , показан как правильный класс. ${\ Displaystyle {\ mathcal {P}} \ {0 \}}$${\ displaystyle \ {0 \}}$

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

Утверждение разрешенной субсчетности всех наборов превращается, в частности, в субсчетную совокупность. ${\ Displaystyle {\ mathbb {N}} ^ {\ mathbb {N}}}$

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

Этот набор классически является функцией в и может быть использован для доказательства того, что существование на самом деле противоречиво. Однако конструктивно, если предложения в его определении не разрешимы, так что набор действительно определил функциональное назначение, мы просто не можем сделать этот вывод. ${\ Displaystyle {\ mathbb {N}} ^ {\ mathbb {N}}}$${\ displaystyle f}$${\ displaystyle n \ in I}$

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

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

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

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

Далее мы изучаем возможные постулаты существования сюръекции . Это, замена в то подразумевает это набор. Нарушение подмножество IS ${\ displaystyle f \ двоеточие I \ twoheadrightarrow {\ mathcal {P}} {\ mathbb {N}}}$${\ displaystyle {\ mathsf {CZF}}}$${\ Displaystyle {\ mathcal {P}} {\ mathbb {N}}}$${\ displaystyle I}$

${\ Displaystyle \ {п \ in {\ mathbb {N}} \ mid n \ in I \ land D (n) \}}$

который, согласно определению , в этом случае упрощается до ${\ Displaystyle I \ подмножество {\ mathbb {N}}}$

${\ Displaystyle \ {п \ в I \ середине D (п) \}}$

куда

${\ Displaystyle D (п) = \ neg (п \ в е (п)),}$

адаптировано из теоремы Кантора о множествах мощности. Это подмножество существует через разделение. Существование сюръекции сразу подразумевает существование числа с ${\ displaystyle c \ in I}$

${\ Displaystyle с \ в е (с) \ если и только если \ neg (с \ в е (с))}$,

делая членство неизбежно неразрешимым и несовместимым с какой-либо реализацией. Предложения такой формы должны быть отклонены в соответствии с последствиями закона о введении отрицания . Так что такой сюрприз не существует и не может быть подсчитан. ${\ Displaystyle P \ iff \ neg P}$${\ Displaystyle {\ mathcal {P}} {\ mathbb {N}}}$

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

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

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

Модели

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

Еще примеры:

• Существуют модели, в которых все множества с отношениями обособленности субсчетны.${\ displaystyle {\ mathsf {IZF}}}$
• В конструктивной теории множеств , как обсуждалось, действительно согласовано утверждение аксиомы подсчетности о том, что все множества (внутренне) подсчитываемы. Полученная в результате теория противоречит Аксиоме множества сил и закону исключенного третьего .${\ displaystyle {\ mathsf {CZF}}}$
• Более того, некоторые модели теории множеств Крипке-Платека подтверждают, что все множества даже счетны.

Subcountable подразумевает не -productive${\ 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}$${\ displaystyle \ omega}$

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

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

использованная литература