Об использовании аксиомы Антиоснования

В этом разделе я просматриваю несколько приложений AFA, сделанных в [3] и [5].
Чтобы подтвердить мое утверждение о том, что большинство приложений AFA требуют только конструктивных
средств, различные разделы [3] и [5] переделываются на основе теории CZFA, а
не ZFA.

Маркированная Антиосновательная Аксиома

В приложениях часто бывает полезно иметь в своем распоряжении более общую форму АФА.

Определение 5.1. Помеченный график -это график вместе с функцией маркировки, которая
назначает набор

(a) меток к каждому узлу a.

Помеченное украшение помеченного графа является функцией

буду такой что

d (a) = {d(b): A → b} ∪ (a).

Немеченый граф

(Г,

) может быть идентифицирован с помощью специального маркированного графика, где

функция маркировки

: G → V всегда присваивает пустое множество, т. е., (x) = ∅ для всех

x ∈ G.

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

203

Теорема 5.2 ((CZFA), cf. [3]: Теорема 1.9). Каждый помеченный график имеет уникальный la-

колокольный декор.

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

G = (G,

,) быть помеченным графом. Пусть G = (G,→) - граф

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

i, a такое, что либо i = 1 и a∈G, либо i = 2

и

a ∈ TC (G) и имеющие в качестве ребер:

• 1

, a → 1, b всякий раз, когда a

б,

• 1

, a → 2, b всякий раз, когда a∈G и b∈ (a),

• 2

, a → 2, b всякий раз, когда b∈a ∈ TC(G).

By AFA,

G имеет уникальное украшение π. Так что для каждого a∈G

π (1, a) = {π(1, b): a

b} {{π(2, b): b∈ (a)}

и для каждого из них

a ∈ TC(G),

π(2, a) = {π (2, b): b∈a}.

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

(G) естественно снабжен структурой графа, позволяя его ребрам

икс

y определяется y∈x. уникальное украшение для (TC(G),

) очевидно, что

функция тождественности на TC

(Г). Поскольку x → π(2, x) также является украшением (TC(G),

)

мы можем сделать вывод, что

π (2, x) = x справедливо для всех x ∈ TC(G). Следовательно, если мы позволим

τ (a) = π(1, a) для a∈G, то для a∈G,

τ (a) = {τ (b): a

b} ∪ (a),

так что

τ-помеченное украшение помеченного графа G.

Для уникальности:

τ предположим, что τ является помеченным украшением G. тогда π является

украшение графика

Г, где

π (1, a) = τ (a) для a∈G,
π (2, a) = a для a ∈ TC(G).

Из АФА следует, что

π = π так что для A∈G

τ (a) = π (1, a) = π(1, a) = τ (a),

и отсюда:

τ = τ.

Определение 5.3. A отношение

R- бисимуляция между двумя помеченными графами G =

(Г,

,

0

) и H = (H,

,

1

) если R ⊆ G × H и выполняются следующие условия

удовлетворен (где

aRb означает a, b ∈ R):

1. Для каждого

a ∈ G существует b ∈ H такое, что aRb.

2. Для каждого

b ∈ H существует a ∈ G такое, что aRb.

204

M. Rathjen

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

АРБ. Тогда для каждого x ∈ G такое, что a

x существует y ∈ H

такие что

б

y и xRy.

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

АРБ. Тогда для каждого y ∈ H такое, что b

y существует x ∈ G

такие что

один

x и xRy.

5. Если

тогда aRb

0

(ля) =

1

b).

Два помеченных графа являются бисимулярными, если между ними существует бисимуляция.

Теорема 5.4 (CZFA). Пусть...

G = (G,

,

0

) и H = (H,

,

1

) быть помеченными графиками

с маркированными украшениями

д

0

и

д

1

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

Если

G и H бисимулярны, то d

0

[G] = d

1

[H].

Доказательство. Определение помеченного графика

K = (K,→,), позволяя K быть множеством { a, b: aRb}.

Для

a, b, a, b ∈ K пусть a, b → a, b, Если a

a или b

b, и положить (a, b) =

0

(ля) =

1

b). К имеет уникальное обозначенное украшение д. Используя бисимуляцию Р,

можно легко проверить, что

д

∗

0

(a, b): = d

0

а) и d

∗

1

(a, b): = d

1

b) имеют маркировку

украшения из

К тому же. Следовательно, d = d

∗

0

= д

∗

1

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

д

0

[G] = d[K] = d

1

[Ч ].

Следствие 5.5 (CZFA). Два графика являются бисимулярными тогда и только тогда, когда их украшения имеют
одинаковое изображение.

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

G = (G,

) и H = (H,

) с украшениями d

0

и

д

1

соответственно, такие

тот

д

0

[G] = d

1

[Ч ]. Затем определите R ⊆ G × H по aRb iff d

0

(д

1

b). Один охотно

проверяет, что

R-это бизимуляция.

Вот еще один полезный факт:

Лемма 5.6 (CZFA). Если бы...

A -транзитивное множество, А d: A → V -функция такая, что
d(A) = {d(x): x ∈ a} для всех a ∈ A, то d(a) = a для всех a ∈ A.

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

A можно считать множеством вершин графа G

Один

= (Ля,

) где а

б

МКФ

b ∈ a и a, b ∈ A. поскольку A является транзитивным, d является украшением G. Но так же и

функция

a → a. таким образом, получаем d(a) = a.

Системный

В приложениях часто бывает полезно воспользоваться графами, которые являются классами, а не
наборами. По карте

℘ с областью M мы имеем в виду определяемую функцию класса с областью M,

и мы напишем:

℘: M → V.

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

205

Определение 5.7. Маркированная система -это класс

M узлов вместе с маркировочной картой
℘: M → V и классом e ребер, состоящих из упорядоченных пар узлов. Кроме того,
система должна удовлетворять этому для каждого узла

a ∈ M, {b ∈ M: a

b} - множество,

где

один

b означает a, b ∈ E.

Маркированная система, как говорят, является

0

если связь между множествами

X и y определены

Автор: “

y = {b ∈ M: a

b для некоторых A ∈ x} " является

0

определимо.

Мы будем сокращать обозначенную систему мимо

M = (M,

, ℘).

Теорема 5.8 ((CZFA

+ IND

ω

), ср. [3]: Теорема 1.10). Для каждой обозначенной системы

M = (M,

, ℘) существует единственное отображение d: M → V такое, что для всех a ∈ M:

d (a) = {d(b): A → b} ∪ (a).

(2)

Доказательство. К каждому

a ∈ M мы можем связать помеченный граф M

один

= (М

один

,

один

, ℘

один

) с

М

один

=

n ω ω

Икс

н

, где

Икс

0

= {a} и X

n+1

= {b: a

b для некоторых A ∈ X

н

}. То

существование функции

n → X

н

отображается с помощью рекурсии на

ω, используя IND

ω

в

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

Y,

{b: a

b для некоторых a ∈ Y } также является множеством. И следовательно к тому м

один

это набор.

один

является ли ограничение на

до узлов из

М

один

. Тот

Е

один

= { x, y ∈ M

один

× М

один

: икс

y}

это набор требует сильной коллекции, тоже. Далее, пусть

℘

один

будет ограничением из

℘ to M

один

.

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

М

один

является множеством, И мы можем применить теорему 5.2, чтобы заключить, что

М

один

имеет уникально

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

д

один

.

d: M → V теперь получается путем исправления функции

д

один

с

a ∈ M, то есть d =

a∈V

д

один

. Один легко показывает, что две функции

д

один

и

д

б

согласитесь на

М

один

∩ М

б

. Для уникальности:

d, обратите внимание, что каждая другая определяемая карта d

выполнение (2) дает функцию, ограниченную на

М

один

(Сильное собрание) и таким образом

производит также маркированное украшение

М

один

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

d (x) = ℘

один

(x) = d (x) для всех x ∈ M

один

.

А следовательно, и к тому,

d (x) = d(x) для всех x ∈ M.

Следствие 5.9 (CZFA

+

- IND

ω

). Для каждой обозначенной системы

M = (M,

, ℘) что

является

0

существует уникальная карта

d: M → V такое, что для всех a ∈ M:

d (a) = {d(b): A → b} ∪ (a).

(3)

Доказательство. Это следует из тщательного изучения доказательства теоремы 5.8 и понимания того, что для a

0

система одна только нужна

- IND

ω

.

Следствие 5.10 (ЧФА). Пусть...

M = (M,

,℘) быть помеченным

0

система такая, что для

каждый

a ∈ M существует функция n → X

н

с доменами

ω такое, что X

0

= {a} и

Икс

n+1

= {b: a

b для некоторых A ∈ X

н

}. Тогда существует единственное отображение d: M → V

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

a ∈ M:

d (a) = {d(b): A → b} ∪ (a).

(4)

Доказательство. В доказательстве теоремы 5.8 мы использовали IND

ω

только один раз, чтобы убедиться, что

М

один

=

n ω ω

Икс

н

это набор. Это мы сейчас получаем совершенно бесплатно из предположений.

206

M. Rathjen

Теорема 5.11 ((CZFA

+ IND

ω

), ср. [3]: Теорема 1.11). Пусть...

M = (M,

,℘) быть a

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

Y.

1. Если бы...

π -отображение с доменом Y, то есть существует уникальная функция ˆ

π с доменом M

такие что для каждого

a∈M

ˆ

π (a) = { ˆ

π (b): a

b} {{π (x): x ∈ ℘ (a)}.

2. Учитывая отображение h: Y → M, существует единственное отображение π с доменом Y такое, что для

ВСЕ

y∈Y,

π (y) = ˆ

π (h (y)).

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

М

π

= (М,

, ℘

π

) получаются из M и π: Y → V путем

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

один

℘

π

(a) = {π(x): x ∈ ℘ (a)}.

Тогда требуется уникальная карта

ˆ

π уникально обозначенное украшение M

π

предоставлено:

Теорема 5.8

Ибо (2) пусть

М

∗

= (М,

) быть графом, имеющим те же узлы, что и M, и все ребра

от

M вместе с ребрами a

h (y) всякий раз, когда a∈M и y ∈ ℘ (a). согласно теореме

5.8,

М

∗

имеет уникальную карту оформления

ρ. Так что для каждого a∈M

ρ (a) = {ρ (b): a

b} {{ρ(h (y)): y ∈ ℘ (a)}.

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

π (y): = ρ (h (y)) для y∈Y, ρ также является Меченым украшением для меченых

система

М

π

так что

ρ = ˆ

π по (1), и следовательно π (x) = ˆ

π (h (x)) для x∈Y. Для

уникальность проекта

π пусть µ: M → V удовлетворяет µ (x) = ˆ

µ (h (x)) для x∈Y. Тогда ˆµ-это a

украшение из

М

∗

так же, как и то, что

ˆ

µ = ρ. В результате µ (x) = ˆ

µ (h (x)) = ρ(h(x)) =
π(x) для x∈Y. Таким образом, µ(x) = π(x) для всех x ∈ Y.

Следствие 5.12 (CZFA

+

- IND

ω

). Пусть...

M = (M,

,℘) быть маркированной системой, которая

является

0

и чьи наборы меток являются подмножествами класса

Y.

1. Если бы...

π -отображение с доменом Y, то есть существует уникальная функция ˆ

π с доменом M

такие что для каждого

a∈M

ˆ

π (a) = { ˆ

π (b): a

b} {{π (x): x ∈ ℘ (a)}.

2. При заданном отображении h: Y → M существует единственное отображение π с областью Y такое, что для

ВСЕ

x∈Y,

π (x) = ˆ

π (h (x)).

Доказательство. Доказательство такое же, как и для теоремы 5.11, за исключением того, что вместо теоремы 5.8 используется следствие 5.9
.

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

207

Следствие 5.13 (ЧФА). Пусть...

M = (M,

,℘) быть помеченной системой, которая является

0

и

чьи наборы меток являются подмножествами класса

Y. Кроме того, предположим, что для каждого a ∈ M

есть такая функция

n → X

н

с доменами

ω такое, что X

0

= {a} и X

n+1

= {b: a

b для некоторых A ∈ X

н

}.

1. Если бы...

π -отображение с доменом Y, то есть существует уникальная функция ˆ

π с доменом M

такие что для каждого

a∈M

ˆ

π (a) = { ˆ

π (b): a

b} {{π (x): x ∈ ℘ (a)}.

2. При заданном отображении h: Y → M существует единственное отображение π с областью Y такое, что для

ВСЕ

x∈Y,

π (x) = ˆ

π (h (x)).

Доказательство. Доказательство такое же, как и для теоремы 5.11, за исключением того
, что вместо теоремы 5.8 используется следствие 5.10.

Решение Лемма версия AFA

АФА может быть сформулирована в более традиционных математических терминах. Меченая
Антифундаментная аксиома предоставляет хороший инструмент для демонстрации того, что системы уравнений
определенного типа всегда имеют уникальные решения. В терминологии [5] это называется
решением леммы. В [5] аксиома Антиоснования даже выражается в терминах
однозначных решений так называемых плоских систем уравнений.

Определение 5.14. Для набора:

Y пусть P (Y) - класс подмножеств Y. Тройка E =
(X, A, e) называется общей плоской системой уравнений, если X и A-любые два
множества, и

e: X → P (X ∪ A), где последнее означает, что e является функцией с

домен

X, который отображается в класс всех подмножеств X ∪ A. X будет называться

набор неопределенных значений из

E, А a называется множеством атомов E. Пусть e

в

= e (v).

Для каждого

v ∈ X, множество b

в

:= ми

в

∩ X называется множеством неопределенностей, на которых v

сразу зависит. Точно так же и набор

с

в

:= ми

в

∩ A называется совокупностью атомов на

который

v сразу зависит.

Решение проблемы:

E-функция s, удовлетворяющая области X

с

икс

= {с

y

: y∈b

икс

} ∪ с

икс

,

для каждого

x∈X, где s

икс

: = s (x).

Теорема 5.15 (CZFA). Каждая обобщенная плоская система

E = (X, A, e) имеет единственное
решение.

Доказательство. Определение помеченного графика

H, позволив X быть его множеством узлов, а его ребра -

форма

икс

y, где y∈b

икс

для

x, y∈X. Кроме того, пусть (x) = c

икс

будьте уместны

208

M. Rathjen

функция маркировки. По Теореме 5.2,

H имеет уникально обозначенное украшение d. После этого

d (x) = {d (y): y∈b

икс

} ∪ (x) = {d (y): y∈b

икс

} ∪ с

икс

,

и так далее

d-это решение проблемы Е. Легко проверить, что каждое решение от s до E дает начало

к украшению из

H. таким образом, существует ровно одно решение для е.

Из-за условия плоскостности, т. е.,

e: X → P (X ∪ A), приведенная выше форма
леммы о решении часто неудобна для использования. Гораздо более общая его форма доказана
в работе [5]. Структура в [5], однако, включает в себя другие объекты, чем наборы, а именно
правильный класс urelements, смысл которого состоит в том, чтобы служить бесконечным запасом
неопределенностей, на которых можно выполнять операцию подстановки. Дано
множество

X из urelements one определяет класс X-множеств, которые являются теми множествами, которые используют

только urelements от

X в их наращивании. Для функции f: X → V на этих

неопределяет затем можно определить операцию подстановки sub

ф

на

Х-наборы. Для

один

X-set a, sub

ф

(a) получается из a путем подстановки f (x) для x всюду в поле

нарастание из

есть

За неимением urelements, подход [5] не является непосредственно применимым в наших
теориях множеств, хотя можно моделировать расширенную вселенную множеств с собственным
классом urelements в CZFA. Для этого потребуется класс, определяемый как наибольшая
фиксированная точка оператора, тема, которую я сейчас перемежаю.