Потоки, Коиндукция и Корекурсия

Ниже я продемонстрирую важные методы коиндукции и
корекурсии в обстановке, которая не слишком сложна, но все же демонстрирует общий
случай в двух словах. За презентацией внимательно следят [5].

Позволь

А будет какой-то набор. Под потоком над A мы подразумеваем упорядоченную пару s = a, s, где
a ∈ A и s-другой поток. Мы думаем о потоке как об элементе, за которым следует
другой поток. Две важные операции, выполняемые над потоками

s принимают на себя

первый элемент 1

ST

(s) который дает элемент А, и принимая его второй элемент 2

nd

(с),

что дает еще один поток. Если мы позволим

Один

∞

будь то потоки свыше

А, тогда мы хотели бы

иметь

Один

∞

= A × A

∞

.

(11)

В теории множеств с аксиомой основания уравнение (11) имеет только решение

Ля = ∅.

Однако с АФА можно не только показать, что (11) имеет решение, отличное от

∅ но
и то, что он имеет самое большое решение, последнее является самой большой неподвижной точкой оператора

Один

(Z) = A × Z. Это наибольшее решение для

Один

будет принято, чтобы быть набор потоков

над

A и обозначаться через A

∞

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

Один

∞

коиндуктивный набор. Более того, так оно и будет

будет показано, что

Один

∞

обладает "рекурсивным" характером, несмотря на то, что его нет

“базовый вариант”. Например, окажется, что можно определить функцию

застежка-молния

: Ля

∞

× Ля

∞

→ Ля

∞

такое что для всех

s, t ∈ A

∞

застежка-молния

(s, t) = 1(s), 1

ST

(t), zip(2

nd

s), 2

nd

t)).

(12)

Как и предполагает его название, zip действует как молния на двух потоках. Определение zip in

(12) является примером для определения с помощью корекурсии над коиндуктивным множеством.

Теорема 5.28 (CZFA). Для каждого набора

A существует наибольшее множество Z такое, что Z ⊆ A × Z.

Более того,

Z удовлетворяет Z = A × Z ,и если a населен, то и Z тоже.

Доказательство. Пусть...

F-множество функций от N:= ω до A. Для каждого такого f определим

другая функция

ф

+

: N → n by

ф

+

(n) = f (n + 1).

214

M. Rathjen

Для каждого

f ∈ F пусть x

ф

будь неопределенным. Мы хотел были бы разрешить систему

уравнения, приведенные по

икс

ф

= f (0), x

ф

+

.

Решение этих уравнений эквивалентно решению уравнений

икс

ф

= {год

ф

, Зет

ф

};

y

ф

= {f (0)}

зет

ф

= {f (0), x

ф

+

},

(13)

где

y

ф

и

зет

ф

есть еще неопределенность. Обратите внимание, что

f (0) является элементом из A. Чтобы быть

точно, пусть

икс

ф

= 0, f, y

ф

= 1, f и z

ф

= 2, f. Решение (13) сводится к следующему:

то же самое, что найти помеченное украшение для помеченного графа

С

Один

= (С,

,)

чей набор узлов является

S = {x

ф

: f ∈ F } {{y

ф

: f ∈ F } {{z

ф

: f ∈ F }

и чьи края даются путем

икс

ф

y

ф

,

икс

ф

зет

ф

,

зет

ф

икс

ф

+

. Кроме того, маркировка

функция

определяется по формуле:

(икс

ф

) = ∅, (y

ф

) = {f (0)}, (z

ф

) = {f (0)} для всех f ∈ F.

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

С

Один

имеет маркированное украшение

д

и мы таким образом получаем

d(x

ф

) = f (0), d (x

ф

+

).

(14)

Позволь

Один

∞

= {d (x

ф

): f ∈ F }. По (14), мы имеем A

∞

⊆ A × A

∞

. Таким образом

Один

∞

решает проблему

уравнение

Z ⊆ A × Z.

Чтобы проверить это

ЛЯ

∞

⊆ Ля

∞

держит также, пусть

a ∈ A и t ∈ A

∞

. По определению:

от

Один

∞

,

t = d (x

ф

) для некоторых f ∈ F. Пусть g: N → A определяется g(0) = a

и

g (n + 1) = f (n). Затем g

+

= f, и таким образом d(x

г

) = a, d (x

ф

) = a, t, so

a, t ∈ A

∞

.

Если

A содержит элемент a, затем f

один

∈ F, где f

один

: N → a определяется по формуле

ф

один

(n) = a. следовательно, d (x

ф

один

) ∈ Ля

∞

, так

Один

∞

тоже обитаема.

Наконец, остается показать, что

Один

∞

это самый большой набор

Z удовлетворяя Z ⊆ A × Z. Так

предположим, что

W-множество, так что W ⊆ A × W. Пусть v ∈ W. Определить f

в

: N → a by

ф

в

n) = 1

ST

(с

н

(в)),

где sec

0

(v) = v и sec

n+1

v) = 2

nd

(с

н

(в)). Затем f

в

∈ F, и поэтому d(x

ф

в

) ∈ Ля

∞

.

Мы утверждаем, что для всех

v ∈ W, d(x

ф

в

) = v. заметим сначала, что для w = 2

nd

(v), мы имеем

с

н

w) = сек.

n+1

(v) для всех n ∈ N, и таким образом f

в

= (Ф

в

)

+

. Из этого следует, что

d(x

ф

в

) = 1

ST

v), d (x

(Ф

в

)

+

)

= 1

ST

v), d (x

ф

в

)

= 1

ST

v), d (x

ф

2-й

(в)

).

(15)

Предикативность, цикличность и Антиосновность

215

W порождает помеченный подграф T из S, множество узлов которого является

T: = {x

ф

в

: v ∈ W } {{y

ф

в

: v ∈ W } {{z

ф

в

: v ∈ W },

и где края и обозначая функция получены от

S путем ограничения до

узлы из

Т. Функция d С d (x

ф

в

) = v, d (y

ф

в

) = {1

ST

(v)}, и d (z

ф

в

) =

{1

ST

v), 2

nd

(v)}, очевидно, является помеченным украшением T. по (15), d ограничено до T является

обозначенное украшение

И еще T. Итак, по теореме 5.2, v = d (x

ф

в

) = d (x

ф

в

) для всех

v ∈ W, и таким образом W ⊆ A

∞

.

Замечание 5.29. Вместо применения обозначенной Антиосновной аксиомы можно
использовать лемму о решении для общих систем уравнений (Теорема 5.26) в приведенном
выше доказательстве теоремы 5.28. С этой целью пусть

B = TC (A), x

ф

= 1, 0, f

для

f ∈ F

и

икс

б

= 1, 1, b

для

b ∈ B. множество X:= {x

ф

: f ∈ F } {{x

б

: b ∈ B}. Затем

X ⊆ U и {x

ф

: f ∈ F } {{x

б

: b ∈ B} = ∅.

Далее определяем неупорядоченность

∗- пара по {c, d}

∗

= 2, {c, d} и упорядоченная ∗ - пара по

c, d

∗

= {{с}

∗

, {c, d}

∗

}

∗

. Обратите внимание, что с

c, d ∈ V [X] также имеет {c, d}

∗

, c, d

∗

∈

V [X].

Позволь

E = (X, e) - общая система уравнений с e(x

ф

) = икс

f (0)

, икс

ф

+

∗

для

f ∈ F и e(x

б

) = 2, {x

u

u ∈ b} для b ∈ B. тогда e: X → V [X]. Автор:

Теорема 5.26 существует уникальная функция

s: X → V такое, что

s(x

б

) = суб

с

(e (x

б

)) = {s (x

u

): u ∈ b} для b ∈ B,

(16)

s(x

ф

) = суб

с

(e (x

ф

)) = s (x

f (0)

), s(x

ф

+

)

для

f ∈ F.

(17)

Из (16) и леммы 5.6 следует:

s(x

б

) = b для всех b ∈ B, и таким образом из (17) следует, что

получается, что

s(x

ф

) = f (0), s (x

ф

+

) для f ∈ F. Отсюда можно продолжить путь и дальше

так же, как и в доказательстве теоремы 5.26.

В качестве следствия из теоремы 5.28 получаем следующий принцип коиндукции для

Один

∞

.

Следствие 5.30 (ЧФА). Если набор

Z удовлетворяет Z × A × Z, то Z ⊆ A

∞

.

Доказательство. Это следует из того, что

Один

∞

это самый большой такой набор.

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

Теорема 5.31 ((CZFA), Corecursion принцип для потоков). Пусть...

C быть произвольным

набор. Заданная функция

g: C → A и h: C → C существует уникальная функция

f: C → A

∞

удовлетворительный

f (c) = g (c), f (h(c))

(18)

для всех

c ∈ C.

216

M. Rathjen

Доказательство. Для каждого из них

c ∈ C пусть x

с

, год

с

, Зет

с

будьте разными неопределенностями. Если быть точным, то пусть

икс

с

= 0, c, y

с

= 1, c и z

с

= 2, c для c ∈ C. На этот раз мы хотели бы решить

система уравнений, задаваемая по формуле:

икс

с

= g (c), x

h(c)

.

Решение этих уравнений эквивалентно решению уравнений

икс

с

= {год

с

, Зет

с

};

y

с

= {g(c)};

зет

с

= {g (c), x

h(c)

}.

(19)

Решение (19) равносильно нахождению помеченного украшения для помеченного
графа

С

С

= (С

С

,

,

С

)

чей набор узлов является

С

С

= {икс

с

: c ∈ C} {{y

с

: c ∈ C} {{z

с

: c ∈ C}

и чьи края даются путем

икс

с

y

с

,

икс

с

зет

с

,

зет

с

икс

h(c)

. Кроме того, маркировка

функция

С

определяется по формуле:

С

(икс

б

) = ∅,

С

(год

б

) = {g (b)},

С

(Зет

б

) = {g (b)} для всех

b ∈ C. По обозначенной Антиосновной аксиоме Теорема 5.2, S

С

имеет маркировку

украшение

 и мы таким образом получаем

 (икс

с

) = g (c),  (x

h(c)

).

(20)

Позволять функции

f с доменом C определяется по формуле f (c): =  (x

с

), мы получаем от (20)

тот

f (c) = g (c), f (h(c))

(21)

держит для всех

c ∈ C. как ran (f) × A × ran (f), следствие 5.30 выходы ran (f) ⊆ A

∞

,

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

f: C → A

∞

.

Остается показать, что

f однозначно определяется выражением (21). Итак, предположим f: C →

Один

∞

является ли другая функция удовлетворительной

f (c) = g (c), f (h (c)) для всех C ∈ C. Тогда

функция

 с  (x

с

) = f (c),  (y

с

) = {g (c)}, и  (z

с

) = {g (c), f (h(c))}

дал бы еще одно маркированное украшение

С

С

, следовательно

f (c) =  (x

с

) =  (x

с

) = f (x

с

),

приносящий

f = f.

Пример 1. Пусть...

k: a → a быть произвольным. Тогда k порождает уникальную функцию

Карта

к

: Ля

∞

→ Ля

∞

удовлетворительный

Карта

к

s) = k(1

ST

(s)), карта

к

(2

nd

(с)).

(22)

Например, если

A = N, k (n) = 2n и s = 3, 6, 9,...

, затем сопоставить

к

(с) =

6

, 12, 18,...

. Чтобы увидеть эту карту

к

существует, пусть

C = A

∞

в Теореме 5.31,

г: а

∞

→

A определяется через g (s) = k(1

ST

s)) и h: A

∞

→ Ля

∞

будьте функцией

h (s) = 2

nd

(с).

Затем сопоставить

к

это уникальная функция

f, предусмотренный теоремой 5.31.

Предикативность, цикличность и Антиосновность

217

Пример 2. Пусть...

ν: A → A. Мы хотим определить функцию

МТЭР

ν

: A → A

∞

который “повторяется”

ν такое, что iter

ν

(a) = a, iter

ν

(ν (a)) для всех A ∈ A. Если, например

A = N и ν (n) = 2n, то iter

ν

(7) = 7, 14, 28,...

. Чтобы прибыть в iter

ν

мы

применить теорему 5.31 с

C = A

∞

,

g: C → A и h: C → C, где g (s) =

ν(1

ST

(s)) и h = карта

ν

, соответственно.

Прогноз. Было бы желательно развить теорию корекурсии [5] (в частности
теорему 17.5) и окончательную теорему коалгебры [3] в полной общности в пределах CZFA
и расширений. По-видимому, первая задача здесь заключается в том, чтобы формализовать части теории категорий
в конструктивной теории множеств. Из-за ограничений по страницам это не может быть сделано в
настоящем документе.

Подтверждение. Я благодарен институту Миттаг-Леффлер (г. Юрсхольм, Швеция)

за предоставленную мне в 2001 году возможность работать над докладом, на котором основан этот документ
. Исследование, представленное в этой статье, было также частично поддержано
грантом GR/R 15856/01 исследовательского совета по инженерным и физическим наукам Соединенного Королевства.

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

[1]

Акцель, Питер: 1978 Год. Теоретико-типологическая интерпретация теории конструктивных множеств. In: A.

MacIntyre et al. (ред.), Логический Коллоквиум ' 77, Амстердам: Северная Голландия, 55-66.

[2]

Акцель, Питер: 1982 Год. Теоретико-типологическая интерпретация конструктивной теории множеств: выбор

принципы. In: A. S. Troelstra et al. (ред.), The L. E. J. Brouwer Centenary Symposium,

Амстердам: Северная Голландия, 1-40.

[3]

Аксель, Питер: 1988. Недостаточно Обоснованные Наборы. CSLI лекционные заметки 14. Stanford: CSLI

Публикации.

[4]

Barwise, Jon: 1975. Допустимые множества и структуры. Подход к теории Определимости.
Берлин: Спрингер.

[5]

Barwise, Jon and Lawrence Moss: 1996. Порочные Круги. CSLI лекционные заметки 60.
Stanford: Csli Publications.

[6]

Beeson, Michael: 1985. Основы конструктивной математики. Берлин: Спрингер.

[7]

Cantini, Andrea: 1986. О соотношении между принципами выбора и понимания в
арифметике второго порядка. Journal of Symbolic Logic vol. 51: 360–373.

[8]

Crosilla, Laura: 1998. Интерпретации реализуемости для подсистем CZF и
теоретической прочности доказательства. технический отчет. Школа математики, университет Лидса.

[9]

Crosilla, Laura: 2000. Модели реализуемости для конструктивных теорий множеств с ограниченной
индукцией. кандидатская диссертация. Школа математики, университет Лидса.

[10] Кросилла, Лаура и Майкл Ратьен: 2002. Недоступные набор аксиом может иметь мало

прочность последовательности. Летопись чистой и прикладной логики 115: 33-70.

218

M. Rathjen

[11] Feferman, Solomon: 1964. Системы предикативного анализа I. журнал символьной логики

29: 1–30.

[12] Feferman, Solomon: 1968. Системы предикативного анализа II. представления орди-

Наль. Журнал символической логики 33: 193-220.

[13] Feferman, Solomon: 1975. Язык и аксиомы для явной математики. In: J. N.

Crossley (ed.), Алгебра и логика, конспекты лекций по математике. 450, Berlin: Springer: 87-139.

[14] Feferman, Solomon: 1977. Теории конечного типа, связанные с математической практикой. In: J.

Barwise (ed.): Справочник по математической логике, Амстердам: Северная Голландия, 913-971.

[15] Hallnäs, Lars: 1986. Не обоснованные множества: пределы обоснованных приближений.

Университет Уппсалы, кафедра математики, отчет № 12, 16 стр.

[16] Forti, Mauro and Furio Honsell: 1983. Теория множеств с принципами свободного построения.

Annali Scuola Normale Superiore di Pisa, Classe di Scienze 10, 493–522.

[17] Jäger, Gerhard: 1993. Фиксированные точки в арифметике Пеано с ординалами. Анналы чистых и

Прикладная Логика 60: 119-132.

[18] Kreisel, Georg: 1960. Порядковая логика и характеристика неформальных понятий

доказательство. В: труды международного математического конгресса 1958 года, Эдинбург:
289-299.

[19] Kripke, Saul: 1975. Набросок теории истины. Философский журнал 72: 53-81.

[20] Lewis, David: 1996. Съезд, Философское Исследование. Cmabridge, MA: Harvard Uni-

версити пресс.

[21] Lindström, Ingrid: 1989. Конструкция не вполне обоснованных наборов в рамках типа Мартина-Лефа

теория. Журнал символической логики 54: 57-64.

[22] Martin-Löf, Per: 1984. Теория Интуитивистского Типа. Неаполь: Библиополис.

[23] Myhill, John: 1975. Конструктивная теория множеств. Журнал символьной логики 40: 347-382.

[24] Rathjen, Michael: 1992. Теоретико-доказательная характеристика примитивного рекурсивного множества

функции. Журнал символической логики 57: 954-969.

[25] Rathjen, Michael: 2000. Сила теории типа Мартина-Лефа со сверхвселенной.

Часть I. архив математической логики 39: 1-39.

[26] Rathjen, Michael: 2001. Теория множеств Крипке-Платека и аксиома антиоснования. Математика-

эматическая логика квартальная 47: 435-440.

[27] Rathjen, Michael: 2003. Антиосновательная аксиома в конструктивных теориях множеств. In: G.

Мяты и R. Muskens (ред.), Игры, логика и конструктивные наборы, Стэнфорд:
публикации CSLI, 87-108.

[28] Russell, Bertrand: 1903. Принципы математики. Кембридж: Кембриджский Университет

Пресс-центр.

[29] Russell, Bertrand: 1908. Математическая логика как основанная на теории типов. Американец

Журнал математики 30: 222-262.

[30] Schütte, Kurt: 1964. Eine Grenze für die Beweisbarkeit der transfiniten Induktion in der

verzweigten Typenlogik. Archiv für Mathematische Logik und Grundlagenforschung 67:
45–60.

Предикативность, цикличность и Антиосновность

219

[31] Schütte, Kurt: 1965. Предикативная упорядоченность. In: J. Crossley and M. Dummett (eds.),

Формальные системы и рекурсивные функции, Амстердам: Северная Голландия, 176-184.

[32] Schütte, Kurt: 1977. Теория Доказательств. Берлин: Спрингер.

[33] Simpson, Stephen: 1999. Подсистемы арифметики второго порядка. Берлин: Спрингер.

[34] Weyl, Hermann: 1949. Философия математики и естественных наук. Принстон:

Издательство Принстонского Университета.

Школа математики
университет Лидса
Leeds LS2 9JT
UK

E-mail: [email protected]

Парадокс Рассела и Диагонализация в
конструктивном контексте

Джон Л. Белл

Абстрактный. Одно из наиболее известных применений парадокса Рассела, или, по крайней мере, лежащей в его основе идеи

это, в доказательстве теоремы Кантора, что мощность любого множества строго меньше, чем мощность
его множества. Другой метод доказательства теоремы Кантора-используемый самим Кантором, чтобы показать
, что множество действительных чисел неисчислимо,—это диагонализация. Обычно
аргументы диагонализации используются для того, чтобы показать, что функциональные пространства являются “большими” в подходящем смысле. Классически эти
два метода эквивалентны. Но конструктивно они таковыми не являются: в то время как аргумент для
парадокса Рассела совершенно конструктивен (т. е. использует интуитивно приемлемые принципы логики)
метод диагонализации не может быть таким. Я описываю способы, которыми эти два метода
расходятся в конструктивной обстановке.

Одно из наиболее известных применений парадокса Рассела или, по крайней мере, идеи, лежащей
в его основе, заключается в доказательстве теоремы Кантора о том, что для любого множества

E, кардинальность E строго

меньше, чем у его силового набора

P E. Это, как мы все знаем, сводится к тому, чтобы показать, что

здесь не может быть никаких сомнений

Е

P E. Чтобы установить это, достаточно показать, что, например:

любая карта

f: E → P E, утверждение

(1)

∀X ∈ P E ∃x E. E. X = f (x)

это приводит к противоречию. Теперь с конструктивной точки зрения аргумент
парадокса Рассела устанавливает больше, чем просто отрицание (1), поскольку он производит явное множество
R, для которого можно доказать, что

∃x E. E. R = f (x)

а именно знакомый " Рассел сет”

R = {x ∈ E: x /

∈ f (x)}.

Это, конечно, потому, что предполагая

R = f (e) для некоторых e ∈ E приводит мгновенно к

противоречие

e ∈ f (e) ⇔ e /

∈ f (e). Для U ⊆ E аналогичный аргумент, заменяющий R

выше по тексту:

R ∩ U, показывает, что не может быть никакого предположения U

P E. Если мы согласимся сказать

вот такой набор

B сюръективно с множеством A при условии, что существует сюръективация A

Б, тогда

это может быть поставлено: для No set

E является P E сюръективным с подмножеством E.

Эти аргументы конструктивно верны в том, что они используют только конструктивно,

или интуитивно приемлемые принципы логики.

222

J. L. Bell

Равным образом, (классически эквивалентно, но не автоматически конструктивно эквива-

лент) форма теоремы Кантора о том, что для любого множества

E там нет инъекции P E

E
также может быть дано конструктивное доказательство, используя идею парадокса Рассела. На самом деле мы
можем доказать больше, а именно, что для любого множества

E не может быть никакой инъекции P E в набор

сюръективный с

E. для предположим, что задана сюръективация f: E

А и инъекция м:

P E

A. Определите

B = {x ∈ E: ∃X E. P E. m (X) = f (x) ∧ x /

∈ Икс}.

С

f сюръективно существует b ∈ E, для которого f (b) = m(B). Тогда у нас есть

b ∈ B ⇒ ⇒ X. X. m (X) = f (b) ∧ b /

∈ Икс

⇐ ⇒ X. X. m (X) = m (B) ∧ b /

∈ Икс

⇐ ⇒ X. X. X = B ∧ b /

∈ Икс

⇐⇒ b /

∈ Б,

и у нас есть свое противоречие.

Как указывает Джордж Булос в [2], можно классически произвести явное

контрпримеры к инъективности данной карты

m: P E → E, то есть подмножества X и
Y из E, для которых X = Y и m(X) = m(Y). Для этого достаточно определить частичный
правый Инверс

r из m таких, что для M = dom (r), m (M) ∈ M и ∀x M. M. x /

∈ r (x).

Ибо тогда, написание

m (M) = a, и X = r (a), мы имеем a /

∈ X, откуда X = M,

и

m (X) = m(r(a)) = a = m(M). Используя идею, которая восходит к Zermelo,

Boolos получает

M как поле наибольшего частичного упорядочения < из E такого, что
m ({y: y < x}) = x для всех x ∈ M, и определяет r по r (x) = {y: y
Наличие хороших порядков в этом аргументе делает его в высшей степени неконструктивным; я не
знаю, существует ли такая возможность.

r и M можно установить конструктивно.

Классически, силовой набор

P E естественно биективен с 2

Е

, множество всех отображений
E → 2 = {0, 1}. Конструктивно это уже не так: здесь, в общем, P E ∼

=

Е

, где

является ли объект истинностных значений или предложений, который является только ∼

= 2, когда

принимается закон исключенной середины. По сути, конструктивно, 2

Е

изоморфна не
P E, а его булевой подрешетке CE, состоящей из всех дополненных (или отделяемых)
подмножеств

E (подмножество U из E считается дополненным, если ∀x E. E. x ∈ U ∨ x /

∈ У).

Что происходит, когда мы заменяем

P E by CE в приведенных выше аргументах? Классически,
конечно, это не имеет никакого значения, но выживают ли аргументы “парадокса Рассела
” при переходе к конструктивности?

Ну а если взять первый аргумент, показав, что никаких предположений быть не может

ф:

Е

P E, можно найти, что, когда P E заменяется CE, множество R /

range диапазон (f) сам
дополняется, и аргумент проходит, конструктивно доказывая, что не может
быть никаких предположений

Е

Совет Европы. Но второй аргумент, с заменой P E на CE (и
E заменяется подмножеством U из E), конструктивно проходит только тогда, когда U сам
дополняется. А что касается третьего аргумента, чтобы пройти конструктивно один раз

P E

заменяется на

CE, необходимо показать, что множество B, определенное там, дополняется,
и, как мы увидим, это вообще не может быть сделано. Неудача этих двух последних

Диагонализация в конструктивном контексте

223

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

М

гладкого бесконечно малого анализа, см., например, [1]. В

М

вещественная ось

У R есть только два

съемные подмножества

∅, R, то есть CR имеет только два элемента. A fortiori CR является инжектируемым

в

R, показывая, что третий аргумент конструктивно не работает. Дело в том, что его нет

сюръекция

R → CR соответствует просто тому факту, что, поскольку R связан, существуют

отсутствие непрерывных неконстантных отображений

R → 2 (все карты в

М

быть ровным, и конечно же

непрерывный). Но

CR тривиально сюръективен с подмножеством {0, 1} из R, опровергающим

второй аргумент—конечно же, в

М

,

{0, 1} не является дополняемым подмножеством R! В

в конце статьи мы приводим совершенно другой конструктивный пример набора

E для чего:

CE сюръективен с подмножеством E.

Давайте еще раз вернемся к аргументу, что здесь нет никаких сомнений

Е

P E.

Классически, мы можем заменить

P E по изоморфному объекту 2

Е

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

φ: E → 2

Е

является ли карта канонически связанной с

данная карта

f: E → P E через характеристические функции (т. е. E., определяемые φ (x) (y) =

1

⇔ y ∈ f (x)) тогда множеству "Рассел" R ∈ P E вне диапазона f соответствует

именно к карте

r: E → 2 вне диапазона φ и определяется “диагонализацией”:

r (x) =

0

если

φ (x) (x) = 1

1

если

φ (x) (x) = 0.

Этот аргумент является совершенно конструктивным и параллелями, которые приведены выше для
несуществования сюръекции

Е

Совет Европы.

Диагонализация появляется в одном из его самых знакомых обличий в известном доказательстве

что не может быть никакого сюррекции множества

N натуральных чисел на множестве N

Н

от

все карты

N → N, что, одним словом, N

Н

это неисчислимо. Здесь же дана одна карта

φ:

N → N

Н

; затем карта

f: N → N определяется предписанием

f (n) =

0

если

φ(n) (n) = 0

1

если

φ (n) (n) = 0.

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

ϕ. Это пример диагонализации, хотя и не совсем так

идентично с предыдущим, также кажется очень похожим на парадокс Рассела.

Рассматриваемый конструктивно, это доказательство критически зависит от разрешимости

Н,

т. е., истинность утверждения

∀m ∈ N ∀N N. N. m = n ∨ m = n.

С

N является разрешимым с конструктивной точки зрения, аргумент конструктивен

действительно, так что

Н

Н

конструктивно неисчислим. (В более общем случае, тот же аргумент

показывает, что если

X-любое разрешимое множество С по крайней мере двумя различными элементами, X

Икс

не может быть

сюръективный с

Икс.)

Будем называть множество подсчитываемым, если оно сюръективно с подмножеством из

Н. классически, это

тривиально следует из того, что

Н

Н

неисчислимо, что он также не может быть подсчетом-

224

J. L. Bell

способный, то есть,

Н

Н

не является сюръективным с подмножеством

N. Для данного φ: U → N

Н

; карта

f: N → N определяется новым предписанием (все еще напоминающим парадокс Рассела)

f (n) =











0

если

n ∈ U & φ(n) (n) = 0

1

если

n ∈ U & φ(n) (n) = 0

1

если

н /

∈ У

это опять же явно за пределами диапазона

φ. Теперь этот аргумент проходит только через конструкцию-

тивно когда

U является отделяемым подмножеством N, так что наиболее "диагонализация" показывает,

конструктивно, разве что

Н

Н

не является” отделяемо " субсчетным. Но на первый взгляд ничего

предотвращает

Н

Н

от того, чтобы быть” недетерминируемым " субсчетным; ибо если, учитывая

φ: U → N

Н

мы

повторите оригинальный рецепт, карту

f, полученная таким образом, определяется только на U, а не на

весь из

N, и аргумент рушится. Итак, пока это все еще следует из Рассела

парадокс в том, что

P N не может быть конструктивно подсчитан, диагонализация (а также

Парадокс Рассела) не удается установить соответствующий факт для

Н

Н

.

Фактически были созданы модели конструктивной математики, в которых

Н

Н

на самом
деле подсчитывается. Так обстоит дело, в частности,в эффективном topos Eff, см., например,
гл. 23 из [3]. В Eff,

П р и М е ч А Н И Е

Н

эффективно(!) часть компании, что делает
парадокс Рассела и диагонализацию более легко различимыми. Парадокс Рассела
по-прежнему приводит к несубсчитываемости

P N, которая соответственно остается “большой". Но

диагонализация, пока продолжающ произвести несчетность

Н

Н

, не может предотвратить его
от того, чтобы быть подсчитываемым в Eff, и поэтому быть в некотором смысле “маленьким” там.
Причина этого заключается в том, что в Eff,

Н

Н

состоит, но не из произвольных карт

N → N, но только из

те, что рекурсивны. Подмножество

U establishing N установление субсчетности N

Н

является
множеством кодов полных рекурсивных функций; поскольку в Eff дополняемые подмножества
N являются просто рекурсивными подмножествами, то факт, что U не может быть дополнено, соответствует
тому факту, что множество кодов полных рекурсивных функций само по себе не рекурсивно.
Субсчетность данных

Н

Н

сразу же подразумевает, что из его подмножества 2

Н

, а следовательно и о

последний изоморфен

CN, вновь демонстрируя несостоятельность, в конструктивном контексте

аргумент, что не может быть никакого набора

E, для которого CE сюръективен с подмножеством E.

"Расхождение” в Eff между диагонализацией и парадоксом Рассела может быть

далее указано вверх, наблюдая, что Eff содержит несинглтонные объекты

C для которых:

объект

С

С

само-отображений фактически изоморфен к

С. Такие объекты не могут быть классическими
множествами, поскольку ясно, что единственными такими множествами, удовлетворяющими этому условию, являются синглеты. Для
классического набора

C, условие существования синглтона эквивалентно условию, что

нет никакой инъекции 2-объекта истинностных значений в классической теории множеств-в

С.

Итак, в классической теории множеств условие, что

С

С

∼

= C означает, что нет инъекции

от

в

С. Фактически парадокс Рассела показывает, что этот вывод продолжает оставаться в силе

конструктивная установка. Ибо предположим, что

i - это изоморфизм (даже просто инъекция)

от

С

С

с

C и что m-это инъекция

в

С. Затем карта

X → i ({ x, m (x ∈ X): x ∈ C})

Диагонализация в конструктивном контексте

225

легко видна инъекция препарата

P C в C, который по аргументу парадокса Рассела

выше, это невозможно.

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

C: такая карта дала бы результат

инъекция внутрь

C его силового объекта P C, который по парадоксу Рассела слишком велик

быть таким непригодным для инъекций.

Заключить. Мы видели, что в некоторых конструктивных контекстах диагонализация
может не обеспечить того, чтобы функциональные пространства были “относительно большими”. Напротив,
парадокс Рассела—по крайней мере, в правильном применении к наборам власти-сохраняет свою потенцию даже в
конструктивных средах, гарантируя, что наборы власти или объекты сохраняют свой “размер”. Поэтому
представляется уместным утверждать для парадокса Рассела универсальную применимость, которая
в то же время должна быть отвергнута диагонализацией.

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

[1] Bell, John L.: 1998. Праймер бесконечно малого анализа. Кембридж: Кембриджский Университет

Пресс-центр.

[2] Boolos, George: 1997. Построение канторианских контрпримеров. Журнал философский

Логика 26: 237-239.

[3] McLarty, Colin: 1992. Элементарные Категории, Элементарные Топосы. Нью-Йорк: Оксфорд

университетское издательство.

Факультет философии
Talbot College
University of Western Ontario
London, Ontario
Canada N6A 3K7

E-mail: [email protected]