Субсчетность

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

\exists (I\subseteq {\mathbb {N} }).\,\exists f.\,(f\colon I\twoheadrightarrow X),

где

f\colon I\twoheadrightarrow X

означает, что

f

является сюръективной функцией от

I

на

X

. Сюръекция является членом

{\mathbb {N} }\rightharpoonup X

и здесь подкласс

I

из

{\mathbb {N} }

должен быть набором.Другими словами, все элементы подсчетной совокупности

X

функционально являются образом индексного набора счетных чисел

I\subseteq {\mathbb {N} }

и, таким образом, набор

X

можно понимать как доминируемое счетное множество

{\mathbb {N} }

.

Обсуждение [ править ]

Номенклатура [ править ]

Обратите внимание, что номенклатура свойств счетности и конечности существенно различается - отчасти потому, что многие из них совпадают, если предположить исключенное третье. Еще раз повторим, что здесь речь идет о свойстве, определяемом в терминах сюръекций на множество $X$ будучи охарактеризованным. Этот язык распространен в текстах по конструктивной теории множеств , но в других случаях название «подсчетный» также присваивалось свойствам в терминах инъекций из характеризуемого множества.

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

Пример [ править ]

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

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

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

Связь с исключенным средним [ править ]

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

\forall (i\in I).(i\in {\mathbb {N} }).

Но тогда это множество все равно может оказаться неразъемным в том смысле, что

\forall (n\in {\mathbb {N} }).{\big (}(n\in I)\lor \neg (n\in I){\big )}

не может быть доказуемо, если не считать это аксиомой.Можно не эффективно посчитать подсчетное множество.

X

если не удается сопоставить счетные числа

{\mathbb {N} }

в набор индексации

I

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

\phi

держит

\phi \lor \neg \phi

. В частности, конструктивно это обратное направление вообще не имеет места.

В классической математике [ править ]

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

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

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

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

-производительное взаимоисключающие понятия Субсчетное и ω

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

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

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

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

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

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

Теории множеств [ править ]

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

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

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

\exists !(y\in Y).g(x)=y,

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

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

О классах мощности [ править ]

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

Для простоты рассуждения предположим, что ${\mathcal {P}}{\mathbb {N} }$ это набор. Затем рассмотрим подмножество $I\subseteq {\mathbb {N} }$ и функция $w\colon I\to {\mathcal {P}}{\mathbb {N} }$ . Далее, как в теореме Кантора о степенных множествах, определим ^[2]

d=\{k\in {\mathbb {N} }\mid k\in I\land D(k)\}

где,

D(k)=\neg (k\in w(k)).

Это подкласс

{\mathbb {N} }

определяется в зависимости от

w

и это также можно написать

d=\{k\in I\mid \neg (k\in w(k))\}.

Он существует как подмножество через разделение. Теперь предположим, что существует число

n\in I

с

w(n)=d

подразумевает противоречие

n\in d\,\leftrightarrow \,\neg (n\in d).

Таким образом, в качестве набора можно найти

{\mathcal {P}}{\mathbb {N} }

является

\omega

-продуктивно в том смысле, что мы можем определить препятствующее

d

для любой данной сюръекции. Также отметим, что существование сюръекции

f\colon I\twoheadrightarrow {\mathcal {P}}{\mathbb {N} }

автоматически сделал бы

{\mathcal {P}}{\mathbb {N} }

в набор, посредством замены в CZF, поэтому существование этой функции безусловно невозможно.

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

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

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

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

О функциональных пространствах [ править ]

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

Итак, здесь мы рассматриваем сюръективную функцию $f\colon I\twoheadrightarrow {\mathbb {N} }^{\mathbb {N} }$ и подмножество ${\mathbb {N} }\times {\mathbb {N} }$ разделен как ^[5]

{\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 \}}

с диагонализующим предикатом, определяемым как

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 )}

которое мы также можем сформулировать без отрицаний как

D(n,y)={\big (}f(n)(n)=0\land y=1{\big )}\lor {\big (}f(n)(n)\geq 1\land y=0{\big )}.

Это множество классически доказуемо является функцией от

{\mathbb {N} }^{\mathbb {N} }

, предназначенный для принятия значения

y=0

для конкретных входов

n

. И его можно классически использовать для доказательства того, что существование

f

поскольку сюръекция на самом деле противоречива. Однако конструктивно, если только предложение

n\in I

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

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

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

Аксиома субсчетности, утверждающая, что все множества субсчетны, несовместима с любой новой аксиомой, делающей $I$ счетные, в том числе ЛЕМ.

Модели [ править ]

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

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

Понятие размера [ править ]

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

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

Связанные объекты [ изменить ]

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

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

См. также [ править ]

Ссылки [ править ]

^ Герт Смолка, Парадокс Сколемса и конструктивизм , Конспект лекций, Саарский университет, январь 2015 г.
^ Мекери, Дэниел (2010), Простая вычислительная интерпретация теории множеств , arXiv : 1005.4380
^ Бауэр, А. « Инъекция от N^N к N », 2011 г.
^ Гитман, Виктория (2011), Какова теория ZFC без набора мощности , arXiv : 1110.2430
^ Белл, Джон Л. (2004), «Парадокс Рассела и диагонализация в конструктивном контексте» (PDF) , в Link, Godehard (ред.), Сто лет парадокса Рассела , Серия Де Грюйтера по логике и ее приложениям, том. 6, де Грюйтер, Берлин, стр. 221–225, MR 2104745.
^ Ратьен, Майкл (2006), «Принципы выбора в конструктивных и классических теориях множеств» (PDF) , в Чатзидакис, Зоэ; Кепке, Питер; Полерс, Вольфрам (ред.), Коллоквиум по логике '02: Совместные материалы ежегодного европейского летнего собрания Ассоциации символической логики и проводимого раз в два года собрания Немецкой ассоциации математической логики и фондов точных наук (Коллоквиум логикум). в Мюнстере, 3–11 августа 2002 г. , Конспекты лекций по логике, том. 27, Ла-Хойя, Калифорния: Ассоциация символической логики, стр. 299–326, MR 2258712.
^ Маккарти, Чарльз (1986), «Счетность при реализуемости», Notre Dame Journal of Formal Logic , 27 (2): 210–220, doi : 10.1305/ndjfl/1093636613 , MR 0842149

[1] Герт Смолка, Парадокс Сколемса и конструктивизм , Конспект лекций, Саарский университет, январь 2015 г.

[2] Мекери, Дэниел (2010), Простая вычислительная интерпретация теории множеств , arXiv : 1005.4380

[3] Бауэр, А. « Инъекция от N^N к N », 2011 г.

[4] Гитман, Виктория (2011), Какова теория ZFC без набора мощности , arXiv : 1110.2430

[5] Белл, Джон Л. (2004), «Парадокс Рассела и диагонализация в конструктивном контексте» (PDF) , в Link, Godehard (ред.), Сто лет парадокса Рассела , Серия Де Грюйтера по логике и ее приложениям, том. 6, де Грюйтер, Берлин, стр. 221–225, MR 2104745.

[6] Ратьен, Майкл (2006), «Принципы выбора в конструктивных и классических теориях множеств» (PDF) , в Чатзидакис, Зоэ; Кепке, Питер; Полерс, Вольфрам (ред.), Коллоквиум по логике '02: Совместные материалы ежегодного европейского летнего собрания Ассоциации символической логики и проводимого раз в два года собрания Немецкой ассоциации математической логики и фондов точных наук (Коллоквиум логикум). в Мюнстере, 3–11 августа 2002 г. , Конспекты лекций по логике, том. 27, Ла-Хойя, Калифорния: Ассоциация символической логики, стр. 299–326, MR 2258712.

[7] Маккарти, Чарльз (1986), «Счетность при реализуемости», Notre Dame Journal of Formal Logic , 27 (2): 210–220, doi : 10.1305/ndjfl/1093636613 , MR 0842149

[1]

[2]

[3]

[4]

[5]

[6]

[7]