Наибольшие фиксированные точки операторов

Теория наибольших неподвижных точек была начата Акцелем в работе [3].

Определение 5.16. Пусть...

быть оператором класса, т. е.

(X) является классом для каждого класса X.

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

Икс

(Икс) =

{(x): x -множество с x ⊆ X}.

(5)

Заметим, что заданный непрерывный оператор монотонен, т. е., если

X ⊆ Y тогда

(Икс) ⊆

(Год).

В нижеследующем я передам, что

x-это множество по x∈V. Если

является ли набор непрерывным

оператор пусть

Дж

=

{x∈V: x ⊆

(икс)}.

A установить непрерывный оператор

является

0

если связь есть “

год ∈

(x) " между множествами x и y является

0

определимо. Заметить это

J - это a

1

класс если

это

0

оператор.

Теорема 5.17 ((CZF

−

+ RDC), ср. [3]: Теорема 6.5). Если бы...

является ли набор непрерывным op-

erator и

J = J тогда

1.

Дж ⊆

J),

2. Если бы...

Икс ⊆

(X) тогда X ⊆ J,

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

209

3.

J -самая большая неподвижная точка из

.

Доказательство. (1): пусть

Дж. Тогда a∈x для некоторого множества x такое, что x ⊆

(икс). Из этого следует, что

ля ∈

J) как x ⊆ J и

это монотонно.

(2): Пусть

Икс ⊆

(X) и пусть a∈X. нам нравится показывать, что a∈J. Мы сначала покажем, что

для каждого набора

x ⊆ X существует множество c

икс

⊆ X такое, что x ⊆

(с

икс

). Итак, пусть x ⊆ X. Тогда

икс ⊆

X) уступчивость

∀у∈Х ∃У [У∈ (Х) ∧ в U ⊆ х].

По сильной коллекции есть набор

А такое что

∀у∈Х ∃У∈С [У∈ (Х) ∧ в U ⊆ Х] ∧ ∀У∈А ∃у∈Х [У∈ (Х) ∧ в U ⊆ х].

Сдача в аренду

с

икс

=

А, мы получаем с

икс

⊆ Х ∧ х ⊆

(с

икс

) по мере необходимости.

Далее мы используем RDC, чтобы найти бесконечную последовательность

икс

0

, икс

1

,... подмножеств X таких, что

икс

0

= {a} и x

н

⊆

(икс

n+1

). Пусть x

∗

=

н

икс

н

. Затем

икс

∗

является ли набор и если

y∈x

∗

затем

y∈x

н

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

n так что y ∈ x

н

⊆

(икс

n+1

) ⊆

(икс

∗

). Следовательно x

∗

⊆

(икс

∗

). Как A∈x

0

⊆ икс

∗

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

Дж.

(3): по (1) и монотонности

(Дж) ⊆

((Дж)).

Следовательно, по (2)

J) ⊆ J. Это и (1) означает, что J является фиксированной точкой из

. По формуле (2) это

должно быть наибольшая фиксированная точка из

.

Если он существует и является множеством, то наибольшая фиксированная точка оператора

будет называться то

множество, заданное коиндуктивно по формуле

.

Теорема 5.18 (CZF

−

+

0

-НТЦ). Если бы...

является ли набор непрерывным

0

оператор и

J = J

затем

1.

Дж ⊆

J),

2. Если бы...

X - это a

1

класс и

Икс ⊆

(X) тогда X ⊆ J,

3.

J является самым большим

1

неподвижная точка

.

Доказательство. Это то же самое доказательство, что и для теоремы 5.17, заметив, что

0

- RDC достаточно

здесь.

В приложениях установите операторы непрерывного действия

часто удовлетворяют дополнительное свойство.

будет называться fathomable, если существует функция частичного класса

q такое, что всякий раз, когда

ля ∈

(x) для некоторого множества x тогда q (a) ⊆ x и a ∈

(q (a)). Например, детерминистский

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

Если на графике из

q также является

0

определяемо мы скажем, что

является ли бездонный набор

непрерывный

0

оператор.

Для fathomable операторов одно может обойтись без RDC и

0

- RDC в Тео-

rems 5.17 и 5.18 в пользу IND

ω

и

- IND

ω

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

210

M. Rathjen

Следствие 5.19 (CZF

−

+ IND

ω

). Если бы...

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

J = J тогда

1.

Дж ⊆

J),

2. Если бы...

Икс ⊆

(X) тогда X ⊆ J,

3.

J -самая большая неподвижная точка из

.

Доказательство. В доказательстве теоремы 5.17 RDC был использован для (2), чтобы показать, что для каждого
класса

X с X ⊆

(X) он содержит X ⊆ J. Теперь, если a ∈ X, то a ∈

u) для

некоторый набор

u ⊆ X, as

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

ля ∈

(q (a)) и q(a) ⊆ X.

Использование IND

ω

а сильная коллекция one определяет последовательность

икс

0

, икс

1

,... по x

0

= {ля}

и

икс

n+1

=

{q (v): v∈x

н

}. Мы используем индукцию на ω, чтобы показать x

н

⊆ X. Очевидно, Что

икс

0

⊆ X. предположим x

н

⊆ X. Тогда x

н

⊆

(Икс). Таким образом, для каждого v∈x

н

,

q (v) ⊆ X, и

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

икс

n+1

⊆ X. Пусть x

∗

=

н

икс

н

. Затем

икс

∗

⊆ X. предположим, что u ∈ x

∗

. Затем

u ∈ x

н

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

n, а следовательно, как u ∈

(X), u ∈

(q (u)). Таким образом, q (u) ⊆ x

n+1

⊆ икс

∗

, и

у ∈

(икс

∗

). В результате, a ∈ x

∗

⊆

(икс

∗

), и следовательно a ∈ J.

Следствие 5.20 (CZF

−

+

- IND

ω

). Если бы...

является ли множество непрерывных измеримых

0

оператор

и

J = J тогда

1.

Дж ⊆

J),

2. Если бы...

X -это

1

и

Икс ⊆

(X) тогда X ⊆ J,

3.

J является самым большим

1

неподвижная точка

.

Доказательство. Если на графике из

q-это

0

поддается определению,

- IND

ω

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

икс

0

, икс

1

,....

Для специальных операторов также возможно отказаться

- IND

ω

в пользу транс.

Следствие 5.21 (CZF

−

+ ТРАНСПОРТ). Пусть...

быть множеством непрерывных измеримых

0

оператор-

АТОР такой что

q -общее отображение и q (a) ⊆ TC ({a}) для всех множеств a. Пусть J = J.

Затем

1.

Дж ⊆

J),

2. Если бы...

X -это

0

и

Икс ⊆

(X) тогда X ⊆ J,

3.

J является самым большим

0

неподвижная точка

.

Доказательство. (1) доказано, как и в Теореме 5.17. Для (2) Предположим, что

X-это класс с

Икс ⊆

(Икс). Пусть a ∈ X. определите последовательность множеств x

0

, икс

1

,... по x

0

= {a} и

икс

n+1

=

{q (v): v∈x

н

} как и в следствии 5.19. Но без этого...

- IND

ω

- как мы можем...

убедитесь, что функция

n → x

н

- существует? Это можно увидеть следующим образом. Определять

Д

н

= {Ф ∈

n+1

ТС

({a}): f (0) = a ∧ ∀ i ∈ n [f (i + 1)∈ Q (f (i))]},

Е

н

= {f (n): f ∈ D

н

}.

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

211

Функция

n → E

н

существует за счет сильной коллекции. Более того,

Е

0

= {a} и E

n+1

=

{q (v): v ∈ E

н

} как можно легко показать индукцией на n; при этом x

н

= Ми

н

. То

оставшаяся часть доказательства соответствует следствию 5.19.

В отношении (3) следует отметить, что

J = {a: a ∈

(q (a))} и таким образом J является

0

.

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