Реализация математики в теории множеств

редактировать

В этой статье исследуется реализация математических концепций в теории множеств. Реализация ряда основных математических концепций выполняется параллельно в ZFC (теория доминирующих множеств) и в NFU, версии New Foundations Куайна. R. Б. Дженсен в 1969 году (здесь подразумевается как минимум аксиомы Infinity и Choice ).

Сказанное здесь применимо также к двум семействам теорий множеств: с одной стороны, ряд теорий, включая теорию множеств Цермело около нижнего края шкалы и восходящий к ZFC. расширены гипотезами большого кардинала, такими как "существует измеримый кардинал "; и, с другой стороны, иерархия расширений NFU, которая рассматривается в статье New Foundations. Они соответствуют различным общим взглядам на то, на что похожа теоретико-множественная вселенная, и сравниваются и противопоставляются подходы к реализации математических концепций в рамках этих двух общих взглядов.

Основная цель этой статьи не состоит в том, чтобы сказать что-либо об относительных достоинствах этих теорий как основ математики. Причина использования двух различных теорий множеств состоит в том, чтобы проиллюстрировать возможность применения нескольких подходов к реализации математики. Именно благодаря такому подходу данная статья не является источником «официальных» определений для каких-либо математических понятий.

Содержание

1 Предварительные сведения
2 Пустой набор, одноэлементные, неупорядоченные пары и кортежи
3 Упорядоченная пара
4 Отношения
- 4.1 Связанные определения
- 4.2 Свойства и виды отношений
5 Функции
- 5.1 Операции с функциями
- 5.2 Специальные виды функций
6 Размер наборов
7 Конечные наборы и натуральные числа
8 Отношения эквивалентности и разбиения
9 Порядковые числа
- 9.1 Отступление: порядковые числа фон Неймана в NFU
10 Кардинальные числа
11 Аксиома подсчета и подрыв стратификации
- 11.1 Свойства строго канторианских множеств
12 Знакомые системы счисления: положительные рациональные числа, величины и reals
13 Операции с индексированными семействами наборов
14 Совокупная иерархия
15 См. также
16 Ссылки
17 Внешние ссылки

Предварительные сведения

В следующих разделах выполняются определенные конструкции в двух теориях ZFC и NFU и сравнить полученные реализации определенных математических структур (su ch как натуральные числа ).

Математические теории доказывают теоремы (и ничего больше). Таким образом, утверждение, что теория допускает конструирование определенного объекта, означает, что согласно теореме этой теории этот объект существует. Это утверждение об определении формы «x такой, что существует $ϕ {\ displaystyle \ phi}$ $\ phi$ », где $ϕ {\ displaystyle \ phi}$ $\ phi$ - это формула нашего языка : теория доказывает существование «x такого, что $ϕ {\ displaystyle \ phi}$ $\ phi$ » только в В этом случае это теорема, что «существует один и только один x такой, что $ϕ {\ displaystyle \ phi}$ $\ phi$ ». (См. теорию описаний Бертрана Рассела.) В общем, теория «определяет» или «конструирует» этот объект в данном случае. Если утверждение не является теоремой, теория не может показать, что объект существует; если утверждение доказуемо ложно в теории, оно доказывает, что объект не может существовать; в общих чертах объект не может быть построен.

ZFC и NFU используют язык теории множеств, поэтому в двух теориях можно рассматривать одни и те же формальные определения «x такой, что $ϕ {\ displaystyle \ phi}$ $\ phi$ ». Конкретной формой определения на языке теории множеств является нотация конструктора множеств : ${x ∣ ϕ} {\ displaystyle \ {x \ mid \ phi \}}$ $\ {x \ mid \ phi \}$ означает «набор A такой, что для всех x, $x ∈ A ↔ ϕ {\ displaystyle x \ in A \ leftrightarrow \ phi}$ $x \ in A \ leftrightarrow \ phi$ » (A не может быть свободным в $ϕ {\ displaystyle \ phi}$ $\ phi$ ). Это обозначение допускает некоторые традиционные расширения: ${x ∈ B ∣ ϕ} {\ displaystyle \ {x \ in B \ mid \ phi \}}$ $\ {x \ in B \ mid \ phi \}$ является синонимом ${x ∣ x ∈ В ∧ ϕ} {\ displaystyle \ {x \ mid x \ in B \ wedge \ phi \}}$ $\ {x \ mid x \ в B \ wedge \ phi \}$ ; ${f (x 1,…, xn) ∣ ϕ} {\ displaystyle \ {f (x_ {1}), \ ldots, x_ {n}) \ mid \ phi \}}$ $\ {f (x_ {1}, \ ldots, x_ {n}) \ mid \ phi \}$ определяется как ${z ∣ ∃ x 1,…, xn (z = f (x 1,…, xn) ∧ ϕ)} {\ Displaystyle \ {z \ mid \ exists x_ {1}, \ ldots, x_ {n} \, (z = f (x_ {1}, \ dots, x_ {n}) \ клин \ phi) \}}$ $\ {z \ mid \ exists x_ {1}, \ ldots, x_ {n} \, (z = f (x_ {1}, \ dots, x_ {n}) \ wedge \ phi) \}$ , где $f (x 1,…, xn) {\ displaystyle f (x_ {1}, \ ldots, x_ {n})}$ $f (x_ {1}, \ ldots, x_ {n})$ - выражение уже определено.

Выражения, определяемые в нотации построителя множеств, имеют смысл как в ZFC, так и в NFU: может оказаться, что обе теории доказывают, что данное определение является успешным, или ни одна из них (выражение ${x ∣ x ∉ x } {\ displaystyle \ {x \ mid x \ not \ in x \}}$ $\ {x \ mid x \ not \ in x \}$ не ссылается ни на что в какой-либо теории множеств с классической логикой; в теории класса вроде NBG (это обозначение действительно относится к классу, но определяется по-другому), или то, что один относится, а другой нет. Кроме того, объект, определенный таким же образом в ZFC и NFU, может иметь разные свойства в двух теориях (или может быть разница в том, что может быть доказано, если нет доказуемой разницы между их свойствами).

Кроме того, теория множеств импортирует концепции из других разделов математики (в смысле, всех разделов математики). В некоторых случаях есть разные способы импортировать концепции в ZFC и NFU. Например, обычное определение первого бесконечного ординала $ω {\ displaystyle \ omega}$ $\ omega$ в ZFC не подходит для NFU, потому что объект (определенный на чисто теоретическом языке поскольку набор всех конечных ординалов фон Неймана ) не может быть показан существующим в NFU. Обычное определение $ω {\ displaystyle \ omega}$ $\ omega$ в NFU - это (на чисто теоретическом языке множеств) набор всех бесконечных хорошо упорядоченных, все из которых надлежащие начальные сегменты конечны, объект, который, как можно показать, не существует в ZFC. В случае таких импортированных объектов могут быть разные определения: одно для использования в ZFC и связанных теориях, а другое для использования в NFU и связанных теориях. Чтобы такие «реализации» импортированных математических концепций имели смысл, необходимо показать, что две параллельные интерпретации имеют ожидаемые свойства: например, реализации натуральных чисел в ZFC и NFU различны, но обе они реализации одной и той же математической структуры, потому что оба включают определения для всех примитивов арифметики Пеано и удовлетворяют (переводам) аксиом Пеано. Затем можно сравнить то, что происходит в двух теориях, когда используется только теоретический язык множеств, при условии, что определения, соответствующие ZFC, используются в контексте ZFC, а определения, соответствующие Подразумевается, что NFU используется в контексте NFU.

Все, что доказано в теории, явно доказуемо существует в любом расширении этой теории; кроме того, анализ доказательства того, что объект существует в данной теории, может показать, что он существует в более слабых версиях этой теории (можно рассмотреть теорию множеств Цермело вместо ZFC для большей части того, что делается в этой статье, например).

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

Эти конструкции появляются первыми, потому что они являются простейшими конструкциями в теории множеств, а не потому, что они первые конструкции, которые приходят на ум в математике (хотя понятие конечного множества, безусловно, фундаментально). Несмотря на то, что NFU также позволяет создавать набор ur-elements, которые еще не стали членами набора, пустой набор является уникальным набором без элементов:

∅ = d e f. {x: x ≠ x} {\ displaystyle \ left. \ varnothing \ right. \, {\ overset {\ mathrm {def.}} {=}} \ left \ {x: x \ neq x \ right \}}

{\ displaystyle \ left. \ Varnothing \ right. \, {\ Overset {\ mathrm {def.}} {=}} \ Left \ {x: x \ neq x \ right \}}

Для каждого объекта $x {\ displaystyle x}$ $x$ существует набор ${x} {\ displaystyle \ {x \}}$ $\ {x \}$ с $x {\ displaystyle x}$ $x$ как его единственный элемент:

{x} = def. {y: y = x} {\ displaystyle \ left \ {x \ right \} {\ overset {\ mathrm {def.}} {=}} \ left \ {y: y = x \ right \}}

\ left \ {x \ right \} {\ overset {{\ mathrm {def.}}} {=}} \ Left \ {y: y = x \ right \}

Для объектов $x {\ displaystyle x}$ $x$ и $y {\ displaystyle y}$ $y$ существует набор ${x, y} {\ displaystyle \ {x, y \}}$ $\ {x, y \}$ содержащий $x {\ displaystyle x}$ $x$ и $y {\ displaystyle y}$ $y$ в качестве единственных элементов :

{x, y} = по умолчанию. {Z: Z = Икс ∨ Z = Y} {\ Displaystyle \ left \ {x, y \ right \} {\ overset {\ mathrm {def.}} {=}} \ left \ {z: z = x \ vee z = y \ right \}}

\ left \ {x, y \ right \} {\ overset {{\ mathrm {def.}}} {=}} \ left \ {z: z = x \ vee z = y \ right \}

объединение двух наборов определяется обычным способом:

x ∪ y = def. {z: z ∈ x ∨ z ∈ y} {\ displaystyle \ left.x \ чашка y \ right. \, {\ overset {\ mathrm {def.}} {=}} \ left \ {z: z \ in x \ vee z \ in y \ right \}}

{\ displaystyle \ left.x \ cup y \ right. \, {\ Overset {\ mathrm {def.}} {=}} \ Left \ {z: z \ in x \ vee z \ in y \ right \}}

Это рекурсивное определение неупорядоченных $n {\ displaystyle n}$ $n$ -кортежей для любого конкретного $n {\ displaystyle n }$ $n$ (конечные множества, заданные как списки их элементов :)

{x 1,…, xn, xn + 1} = def. {x 1,…, xn} ∪ {xn + 1} {\ displaystyle \ left \ {x_ {1}, \ ldots, x_ {n}, x_ {n + 1} \ right \} {\ overset {\ mathrm {def.}} {=}} \ left \ {x_ {1}, \ ldots, x_ {n} \ right \} \ cup \ left \ {x_ {n + 1} \ right \}}

\ left \ {x_ {1}, \ ldots, x_ {n}, x _ {{n + 1}} \ right \} {\ overset {{\ mathrm {def.}}} {=}} \ left \ {x_ {1}, \ ldots, x_ {n} \ right \} \ cup \ left \ {x _ {{n + 1}} \ right \}

В NFU, все заданные определения работают путем послойного понимания; в ZFC существование неупорядоченной пары задается аксиомой спаривания, существование пустого набора следует из разделения из существования любого набора и двоичного объединения два набора существуют по аксиомам Pairing и Union ( $x ∪ y = ⋃ {x, y} {\ displaystyle x \ cup y = \ bigcup \ {x, y \}}$ $x \ чашка y = \ bigcup \ {x, y \}$ ).

Упорядоченная пара

Сначала рассмотрим упорядоченную пару . Причина, по которой это происходит в первую очередь, носит технический характер: упорядоченные пары необходимы для реализации отношений и функций, которые необходимы для реализации других концепций, которые могут показаться предшествующими. Первым определением упорядоченной пары было определение $(x, y) = def {{{x}, ∅}, {{y}}} {\ displaystyle (x, y) {\ overset {\ mathrm { def}} {=}} \ {\ {\ {x \}, \ emptyset \}, \ {\ {y \} \} \}}$ $(x, y) {\ overset {{\ mathrm {def}}} {=}} \ {\ {\ {x \}, \ emptyset \}, \ {\ {y \} \} \}$ предложено Норбертом Винером в 1914 г. в контексте теории типов Principia Mathematica. Винер заметил, что это позволило исключить типы n-мерных отношений для n>1 из системы этой работы. Сейчас более обычным явлением является использование определения $(x, y) = d e f. {{x}, {x, y}} {\ displaystyle (x, y) {\ overset {\ mathrm {def.}} {=}} \ {\ {x \}, \ {x, y \} \ }}$ $(x, y) {\ overset {{\ mathrm {def.}}} {=}} \ {\ {x \}, \ {x, y \} \}$ , из-за Куратовски. Любое из этих определений работает как в ZFC, так и в NFU. В NFU эти два определения имеют технический недостаток: упорядоченная пара Куратовского на два типа выше, чем ее проекции, а упорядоченная пара Винера на три типа выше. Обычно постулируется существование упорядоченной пары на уровне типа (пара $(x, y) {\ displaystyle (x, y)}$ $(x, y)$ , которая является тем же типом, что и ее проекции ) в НФУ. Пару Куратовского удобно использовать в обеих системах до тех пор, пока использование пар типа-уровень не будет формально оправдано. Внутренние детали этих определений не имеют ничего общего с их реальной математической функцией. Для любого понятия $(x, y) {\ displaystyle (x, y)}$ $(x, y)$ упорядоченной пары важно то, что оно удовлетворяет определяющему условию

(x, y) = (z, w) ≡ Икс знак равно Z ∧ Y = вес {\ Displaystyle (x, y) = (z, w) \ \ Equiv \ x = z \ wedge y = w}

{\ displaystyle (x, y) = (z, w) \ \ Equiv \ x = z \ wedge y = w}

… и чтобы это было достаточно просто собирать упорядоченные пары в наборы.

Отношения

Отношения - это наборы, все элементы которых являются упорядоченными парами. Где возможно, отношение $R {\ displaystyle R}$ $R$ (понимаемое как двоичный предикат ) реализуется как ${(x, y) ∣ x R y} {\ displaystyle \ {(x, y) \ mid xRy \}}$ $\ {(x, y) \ mid xRy \}$ (который можно записать как ${z ∣ π 1 (z) R π 2 (z)} {\ displaystyle \ {z \ mid \ pi _ {1} (z) R \ pi _ {2} (z) \}}$ $\ {z \ mid \ pi _ {1} (z) R \ pi _ {2} (z) \}$ ). Когда $R {\ displaystyle R}$ $R$ является отношением, запись $x R y {\ displaystyle xRy}$ $xRy$ означает $(x, y) ∈ R {\ displaystyle \ left (x, y \ right) \ in R}$ $\ left (x, y \ right) \ in R$ .

В ZFC некоторые отношения (например, общее отношение равенства или отношение подмножества в наборах) слишком велики, чтобы быть наборами (но могут быть безвредными реифицируется как собственные классы ). В NFU некоторые отношения (например, отношение принадлежности) не являются наборами, поскольку их определения не стратифицированы: in ${(x, y) ∣ x ∈ y} {\ displaystyle \ {(x, y) \ mid x \ in y \}}$ $\ {(x, y) \ mid x \ in y \}$ $x {\ displaystyle x}$ $x$ и $y {\ displaystyle y}$ $y$ должны иметь один и тот же тип (поскольку они отображаются как проекции из той же пары), но также и последовательных типов (поскольку $x {\ displaystyle x}$ $x$ рассматривается как элемент $y {\ displaystyle y}$ $y$ ).

Связанные определения

Пусть даны $R {\ displaystyle R}$ $R$ и $S {\ displaystyle S}$ $S$ бинарные отношения. Тогда полезны следующие понятия:

конверс из $R {\ displaystyle R}$ $R$ - это отношение ${ (y, x): x R y} {\ displaystyle \ left \ {\ left (y, x \ right): xRy \ right \}}$ $\ left \ {\ left (y, x \ right): xRy \ right \}$ .

домен из $R { \ Displaystyle R}$ $R$ - это набор ${x: ∃ y (x R y)} {\ displaystyle \ left \ {x: \ exists y \ left (xRy \ right) \ right \} }$ $\ left \ {x: \ exists y \ left (xRy \ right) \ right \}$ .

диапазон из $R {\ displaystyle R}$ $R$ - это область, обратная $R {\ displaystyle R}$ $R$ . То есть набор ${y: ∃ x (x R y)} {\ displaystyle \ left \ {y: \ exists x \ left (xRy \ right) \ right \}}$ ${\ displaystyle \ left \ {y: \ exists x \ left (xRy \ right) \ right \}}$ .

The поле из $R {\ displaystyle R}$ $R$ - это объединение домена и диапазона $R {\ displaystyle R}$ $R$ .

прообраз элемента $x {\ displaystyle x}$ $x$ поля $R {\ displaystyle R}$ $R$ является set ${y: y R x} {\ displaystyle \ left \ {y: yRx \ right \}}$ $\ left \ {y: yRx \ right \}$ (используется в определении «хорошо обоснованный» ниже.)

закрытие вниз элемента $x {\ displaystyle x}$ $x$ поля $R {\ displaystyle R}$ $R$ - это наименьший набор $D {\ displaystyle D}$ $D$ , содержащий $x {\ displaystyle x}$ $x$ , и каждый из которых $z R y {\ displaystyle zRy}$ $zRy$ для каждого $y ∈ D {\ displaystyle y \ in D}$ $y \ in D$ (т. Е. Включая прообраз каждого из его элементов относительно $R {\ displaystyle R}$ $R$ как подмножество.)

r элитный продукт $R | S {\ displaystyle R | S}$ $R | S$ из $R {\ displaystyle R}$ $R$ и $S {\ displaystyle S}$ $S$ является отношением ${(Икс, Z): ∃ Y (Икс R Y ∧ Y S Z)} {\ Displaystyle \ left \ {\ left (x, z \ right): \ существует y \, \ left (xRy \ клин ySz \ right) \ right \}}$ $\ left \ {\ left (x, z \ right): \ существует y \, \ left (xRy \ wedge ySz \ right) \ right \}$ .

Обратите внимание, что в нашем формальном определении бинарного отношения диапазон и домен отношения не различаются. Это можно сделать, представив отношение $R {\ displaystyle R}$ $R$ с codomain $B {\ displaystyle B}$ $B$ как $(R, B) { \ displaystyle \ left (R, B \ right)}$ $\left(R,B\right)$ , но наша разработка этого не потребует.

В ZFC - любое отношение, домен которого является подмножеством набора $A {\ displaystyle A}$ $A$ , а диапазон которого является подмножеством набора $B {\ displaystyle. B}$ $B$ будет набором, поскольку декартово произведение $A × B = {(a, b): a ∈ A ∧ b ∈ B} {\ displaystyle A \ раз B = \ left \ {\ left (a, b \ right): a \ in A \ wedge b \ in B \ right \}}$ $A \ times B = \ left \ {\ left (a, b \ right): a \ in A \ wedge b \ in B \ righ t \}$ - это набор (являющийся подклассом $P (A ∪ B) {\ displaystyle {\ mathcal {P}} \! \ Left (A \ cup B \ right)}$ ${\ mathcal {P }} \! \ left (A \ cup B \ right)$ ), а разделение предусматривает существование ${(x, y) ∈ A × B: x R y} {\ displaystyle \ left \ {\ left (x, y \ right) \ in A \ times B: xRy \ right \}}$ $\ left \ {\ left (x, y \ right) \ in A \ times B: xRy \ right \}$ . В NFU некоторые отношения с глобальной областью видимости (например, равенство и подмножество) могут быть реализованы как наборы. В NFU имейте в виду, что $x {\ displaystyle x}$ $x$ и $y {\ displaystyle y}$ $y$ на три типа ниже, чем $R {\ displaystyle R}$ $R$ в $x R y {\ displaystyle xRy}$ $xRy$ (на один тип ниже, если используется упорядоченная пара на уровне типа).

Свойства и виды отношений

Бинарное отношение $R {\ displaystyle R}$ $R$ :

Reflexive if $x R x {\ displaystyle xRx}$ $xRx$ для каждого $x {\ displaystyle x}$ $x$ в поле $R {\ displaystyle R}$ $R$ .
Symmetric если $∀ x, y (x R y → y R x) {\ displaystyle \ forall x, y \, (xRy \ to yRx)}$ $\ forall x, y \, (xRy \ to yRx)$ .
транзитивный если $∀ Икс, Y, Z (Икс R Y ∧ Y R Z → Икс R Z) {\ Displaystyle \ forall x, y, z \, (xRy \ wedge yRz \ rightarrow xRz)}$ $\ forall x, y, z \, (xRy \ клин yRz \ rightarrow xRz)$ .
Антисимметричный если $∀ x, y (x R y ∧ y R x → x = y) {\ displaystyle \ forall x, y \, (xRy \ wedge yRx \ rightarrow x = y)}$ $\ forall x, y \, (xRy \ wedge yRx \ rightarrow x = y)$ .
Хорошо обосновано, если для каждого набора $S {\ displaystyle S}$ $S$ , который соответствует полю $R {\ displaystyle R}$ $R$ , $∃ x ∈ S { \ displaystyle \ \ exists x \ in S}$ $\ существует x \ in S$ , чей прообраз в $R {\ displaystyle R}$ $R$ не соответствует $S {\ displaystyle S}$ $S$ .
Extensional если для каждого $x, y {\ displaystyle x, y}$ $x, y$ в поле $R {\ displaystyle R}$ $R$ , $x = y {\ displaystyle x = y}$ $x = y$ тогда и только тогда, когда $x {\ displaystyle x}$ $x$ и $y {\ displaystyle y}$ $y$ имеют одинаковый прообраз в разделе $R {\ displaystyle R}$ $R$ .

Отношения, имеющие определенные комбинации вышеуказанных свойств, имеют стандартные имена. Бинарное отношение $R {\ displaystyle R}$ $R$ :

отношение эквивалентности, если $R {\ displaystyle R}$ $R$ является рефлексивным, симметричным и транзитивным.
A частичный порядок, если $R {\ displaystyle R}$ $R$ является рефлексивным, антисимметричным и транзитивным.
A линейный порядок, если $R {\ displaystyle R}$ $R$ является частичным порядком и для каждого $x, y {\ displaystyle x, y}$ $x, y$ в поле $R {\ displaystyle R}$ $R$ , либо $x R y {\ displaystyle xRy}$ $xRy$ , либо $y R x {\ displaystyle yRx}$ $yRx$ .
A well-ordering, если $R {\ displaystyle R}$ $R$ является линейным порядком и хорошо обоснованным.
A установить изображение, если $R {\ displaystyle R}$ $R$ является хорошо обоснованным и экстенсиональным, а поле $R {\ displaystyle R}$ $R$ либо равно закрытию вниз одного из его членов (так называемого верхний элемент) или пуст.

Функции

A функциональное отношение - это двоичный предикат $F {\ displayst yle F}$ $F$ такой, что $∀ x, y, z (x F y ∧ x F z → y = z). {\ displaystyle \ forall x, y, z \, \ left (xFy \ wedge xFz \ to y = z \ right).}$ ${\ Displaystyle \ forall x, y, z \, \ left (xFy \ wedge xFz \ to y = z \ right).}$ Такое отношение (предикат ) реализуется как отношение (набор) точно так, как описано в предыдущем разделе. Таким образом, предикат $F {\ displaystyle F}$ $F$ реализуется набором ${(x, y): x F y} {\ displaystyle \ left \ {\ left (x, y) \ right): xFy \ right \}}$ $\ left \ {\ left (x, y \ right): xFy \ right \}$ . Отношение $F {\ displaystyle F}$ $F$ является функцией тогда и только тогда, когда $∀ x, y, z ((x, y) ∈ F ∧ (x, z) ∈ F → y = z). {\ displaystyle \ forall x, y, z \, \ left (\ left (x, y \ right) \ in F \ wedge \ left (x, z \ right) \ in F \ to y = z \ right). }$ ${\ displaystyle \ forall x, y, z \, \ влево (\ влево (х, у \ вправо) \ в F \ клин \ влево (х, г \ вправо) \ в F \ к у = г \ вправо).}$ Следовательно, можно определить функцию значения $F (x) {\ displaystyle F \! \ Left (x \ right)}$ $F \! \ Left (x \ right)$ как уникальный объект $y {\ displaystyle y}$ $y$ такой, что $x F y {\ displaystyle xFy}$ $xFy$ - то есть: $x {\ displaystyle x}$ $x$ $F {\ displaystyle F}$ $F$ - связано с $y {\ displaystyle y}$ $y$ таким образом, что отношение $f {\ displaystyle f}$ $f$ удерживается между $x {\ displaystyle x}$ $x$ и $y {\ displaystyle y}$ $y$ - или как уникальный объект $y {\ displaystyle y}$ $y$ такой, что $(x, y) ∈ F {\ displaystyle \ left (x, y \ right) \ in F}$ $\ left (x, y \ right) \ in F$ . Присутствие в обеих теориях функциональных предикатов, которые не являются наборами, делает полезным разрешить обозначение $F (x) {\ displaystyle F \! \ Left (x \ right)}$ $F \! \ Left (x \ right)$ как для множеств $F {\ displaystyle F}$ $F$ и для важных функциональных предикатов. Пока не проводится количественная оценка функций в последнем смысле, все такие виды использования в принципе устранимы.

Помимо формальной теории множеств, мы обычно определяем функцию в терминах ее домена и домена, как во фразе «Пусть $f: A → B {\ displaystyle f: A \ to B}$ $f: A \ to B$ быть функцией ". Область определения функции - это просто область ее определения как отношения, но мы еще не определили область определения функции. Для этого мы вводим терминологию, согласно которой функция - это от $A {\ displaystyle A}$ $A$ до $B {\ displaystyle B}$ $B$ , если ее домен равен $A {\ displaystyle A}$ $A$ , а его диапазон содержится в $B {\ displaystyle B}$ $B$ . Таким образом, каждая функция является функцией от своего домена до своего диапазона, а функция $f {\ displaystyle f}$ $f$ из $A {\ displaystyle A}$ $A$ по $B {\ displaystyle B}$ $B$ также является функцией от $A {\ displaystyle A}$ $A$ до $C {\ displaystyle C}$ $C$ для любого набора $C {\ displaystyle C}$ $C$ , содержащего $B {\ displaystyle B}$ $B$ .

Действительно, независимо от того, какой набор мы считаем кодоменом функции, функция не изменяется как набор, поскольку по определению это просто набор упорядоченных пар. То есть функция не определяет свой кодомен по нашему определению. Если кто-то находит это непривлекательным, то вместо этого можно определить функцию как упорядоченную пару $(f, B) {\ displaystyle (f, B)}$ ${\ displaystyle (f, B)}$ , где $f {\ displaystyle f}$ $f$ - функциональное отношение, а $B {\ displaystyle B}$ $B$ - его кодомен, но мы не применяем этот подход в этой статье (более элегантно, если сначала определить упорядоченные тройки - например, как $(x, y, z) = (x, (y, z)) {\ displaystyle (x, y, z) = (x, (y, z))}$ ${\ displaystyle (x, y, z) = (x, (y, z)) }$ - тогда можно определить функцию как упорядоченную тройку $(f, A, B) {\ displaystyle (f, A, B)}$ ${\ displaystyle (f, A, B)}$ , чтобы также включить домен). Обратите внимание, что та же проблема существует для отношений: вне формальной теории множеств мы обычно говорим: «Пусть $R ⊆ A × B {\ displaystyle R \ substeq A \ times B}$ ${\ displaystyle R \ substeq A \ times B}$ будет бинарным отношением», но формально $R {\ displaystyle R}$ $R$ представляет собой набор упорядоченных пар таких, что $dom R ⊆ A {\ displaystyle {\ text {dom}} \, R \ substeq A}$ ${\ displaystyle {\ text {dom}} \, R \ substeq A}$ и $выполнялись R ⊆ B {\ displaystyle {\ text {ran}} \, R \ substeq B}$ ${\ displaystyle {\ text {побежал }} \, R \ substeq B}$ .

В NFU, $x {\ displaystyle x}$ $x$ имеет тот же тип, что и $F (x) {\ displaystyle F \! \ left (x \ right)}$ $F \! \ Left (x \ right)$ и $F {\ displaystyle F}$ $F$ на три типа выше, чем $F (x) {\ displaystyle F \! \ left (x \ right)}$ $F \! \ Left (x \ right)$ (на один тип выше, если используется упорядоченная пара на уровне типов). Чтобы решить эту проблему, можно определить $F [A] {\ displaystyle F \ left [A \ right]}$ $F\left[A\right ]$ как ${y: ∃ x (x ∈ A ∧ y = F (х))} {\ Displaystyle \ влево \ {у: \ существует х \, \ влево (х \ в А \ клин у = F \! \ влево (х \ вправо) \ вправо) \ вправо \}}$ $\ left \ {y: \ exists x \, \ left (x \ в A \ wedge y = F \! \ left (x \ right) \ right) \ right \}$ для любого набора $A {\ displaystyle A}$ $A$ , но это более удобно записать как ${F (x): x ∈ A} {\ displaystyle \ left \ { F \! \ Left (x \ right): x \ in A \ right \}}$ $\ left \ {F \! \ left (x \ right): x \ in A \ right \}$ . Тогда, если $A {\ displaystyle A}$ $A$ - это множество, а $F {\ displaystyle F}$ $F$ - любое функциональное отношение, Аксиома замещения гарантирует, что $F [A] {\ displaystyle F \ left [A \ right]}$ $F\left[A\right ]$ является набором в ZFC. В NFU $F [A] {\ displaystyle F \ left [A \ right]}$ $F\left[A\right ]$ и $A {\ displaystyle A}$ $A$ теперь имеют один и тот же тип, и $F {\ displaystyle F}$ $F$ на два типа выше, чем $F [A] {\ displaystyle F \ left [A \ right]}$ $F\left[A\right ]$ (тот же тип, если используется упорядоченная пара на уровне типов).

Функция $I (x) = x {\ displaystyle I \! \ Left (x \ right) = x}$ $I \! \ left ( x \ right) = x$ не является набором в ZFC, потому что "тоже большой ". $I (x) {\ displaystyle I \! \ Left (x \ right)}$ $I\!\left(x\right)$ , однако, является набором в NFU. Функция (предикат) $S (x) = {x} {\ displaystyle S \! \ Left (x \ right) = \ left \ {x \ right \}}$ $S \! \ left (x \ right) = \ left \ {x \ right \}$ не является функцией ни набор ни в одной теории; в ZFC это верно, потому что такой набор был бы слишком большим, а в NFU это верно, потому что его определение не было бы стратифицированным. Более того, можно доказать, что $S (x) {\ displaystyle S \! \ Left (x \ right)}$ $S \! \ Left (x \ right)$ не существует в NFU (см. Разрешение парадокса Кантора в New Foundations.)

Операции над функциями

Пусть $f {\ displaystyle f}$ $f$ и $g {\ displaystyle g}$ $g$ - произвольные функции. состав из $f {\ displaystyle f}$ $f$ и $g {\ displaystyle g}$ $g$ , $g ∘ f {\ displaystyle g \ circ f}$ $g \ circ f$ , определяется как относительное произведение $f | g {\ displaystyle f \, | \, g}$ ${\ displaystyle f \, | \, g}$ , но только если это приводит к такой функции, что $g ∘ f {\ displaystyle g \ circ f}$ $g \ circ f$ равно также функция, с $(g ∘ f) (x) = g (f (x)) {\ displaystyle \ left (g \ circ f \ right) \! \ left (x \ right) = g \! \ left (f \! \ left (x \ right) \ right)}$ $\ left (g \ circ f \ right) \! \ left (x \ right) = g \! \ left (f \! \ left (x \ right) \ right)$ , если диапазон $f {\ displaystyle f}$ $f$ является подмножеством домена $г {\ displaystyle g}$ $g$ . инверсия $f {\ displaystyle f}$ $f$ , $f (- 1) {\ displaystyle f ^ {\ left (-1 \ right)}}$ $f ^ {\ left (-1 \ right)}$ , определяется как обратное из $f {\ displaystyle f}$ $f$ , если это функция. Для любого набора $A {\ displaystyle A}$ $A$ функция идентичности $i A {\ displaystyle i_ {A}}$ $i_ {A}$ является набором ${(x, x) ∣ x ∈ A} {\ displaystyle \ left \ {\ left (x, x \ right) \ mid x \ in A \ right \}}$ $\ left \ {\ left (x, x \ right) \ mid x \ in A \ right \}$ , и это набор в обоих ZFC и НФУ по разным причинам.

Специальные виды функций

Функция - это инъективная (также называемая однозначная ), если он имеет обратную функцию.

функция $f {\ displaystyle f}$ $f$ от $A {\ displaystyle A}$ $A$ до $B {\ displaystyle B}$ $B$ - это:

инъекция от $A {\ displaystyle A}$ $A$ до $B {\ displaystyle B}$ $B$ если изображения в $f {\ displaystyle f}$ $f$ отдельных элементов $A {\ displaystyle A}$ $A$ являются отдельными элементами $B {\ displaystyle B}$ $B$ .
Surjection от $A {\ displaystyle A}$ $A$ до $B {\ displaystyle B}$ $B$ если диапазон $f {\ displaystyle f}$ $f$ равен $B {\ displaystyle B}$ $B$ .
Bijection from $A {\ displaystyle A} <577 От>$ $A$ до $B {\ displaystyle B}$ $B$ , если $f {\ displaystyle f}$ $f$ является одновременно инъекцией и сюръекцией.

Определение функций как упорядоченные пары $(f, B) {\ displaystyle (f, B)}$ ${\ displaystyle (f, B)}$ или упорядоченные тройки $(f, A, B) {\ displaystyle (f, A, B)}$ ${\ displaystyle (f, A, B)}$ имеет то преимущество, что нам не нужно вводить терминологию быть функцией "от $A {\ displaystyle A}$ $A$ до $B {\ displaystyle B}$ $B$ ", и что мы можем прямо говорить о "сюръективности" в отличие от возможности говорить только о «сюръективности на $B {\ displaystyle B}$ $B$ ».

Размер наборов

В обоих ZFC и NFU два набора A и B имеют одинаковый размер (или равнодоступный ) тогда и только тогда, когда существует биекция f от A к B. Это можно записать как $| А | = | B | {\ displaystyle | A | = | B |}$ $| A | = | B |$ , но обратите внимание, что (на данный момент) это выражает связь между A и B, а не связь между еще не определенными объектами $| А | {\ displaystyle | A |}$ $| A |$ и $| B | {\ displaystyle | B |}$ $| B |$ . Обозначьте это отношение как $A ∼ B {\ displaystyle A \ sim B}$ $A \ sim B$ в таких контекстах, как фактическое определение кардиналов, где должно быть даже появление предполагаемых абстрактных кардиналов. избегали.

Аналогичным образом определите $| А | ≤ | B | {\ displaystyle | A | \ leq | B |}$ $| A | \ leq | B |$ как удерживающий тогда и только тогда, когда есть инъекция из A в B.

Это просто показать что отношение равнодоступности является отношением эквивалентности : равнодоступность A и A подтверждается $i A {\ displaystyle i_ {A}}$ $i_ {A}$ ; если свидетели $| А | = | B | {\ displaystyle | A | = | B |}$ $| A | = | B |$ , затем $f - 1 {\ displaystyle f ^ {- 1}}$ $f ^ {- 1}$ свидетели $| B | = | А | {\ displaystyle | B | = | A |}$ $| B | = | A |$ ; и если найдены свидетели $| А | = | B | {\ displaystyle | A | = | B |}$ $| A | = | B |$ и g свидетели $| B | = | C | {\ displaystyle | B | = | C |}$ $| B | = | C |$ , затем $g ∘ f {\ displaystyle g \ circ f}$ $g \ circ f$ свидетели $| А | = | C | {\ displaystyle | A | = | C |}$ $| A | = | C |$ .

Можно показать, что $| А | ≤ | B | {\ displaystyle | A | \ leq | B |}$ $| A | \ leq | B |$ - это линейный порядок на абстрактных кардиналах, но не на множествах. Рефлексивность очевидна, а транзитивность доказана так же, как и равноденствие. Теорема Шредера – Бернштейна, доказываемая в ZFC и NFU полностью стандартным способом, устанавливает, что

$| А | ≤ | B | ∧ | B | ≤ | А | → | А | = | B | {\ displaystyle | A | \ leq | B | \ wedge | B | \ leq | A | \ rightarrow | A | = | B |}$ $| A | \ leq | B | \ wedge | B | \ leq | A | \ rightarrow | A | = | B |$

(это устанавливает антисимметрию по кардиналам) и

$| А | ≤ | B | ∨ | B | ≤ | А | {\ displaystyle | A | \ leq | B | \ vee | B | \ leq | A |}$ $| A | \ leq | B | \ vee | B | \ leq | A |$

стандартным образом в любой теории следует из аксиомы выбора .

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

Натуральные числа можно рассматривать как конечные порядковые или конечные кардиналы. Здесь их рассматривают как конечные кардинальные числа. Это первое место, где становится очевидным основное различие между реализациями в ZFC и NFU.

Аксиома бесконечности ZFC говорит нам, что существует множество A, которое содержит $∅ {\ displaystyle \ emptyset}$ $\ emptyset$ и содержит $y ∪ {y} {\ displaystyle y \ cup \ {y \}}$ $y \ чашка \ {y \}$ для каждого $y ∈ A {\ displaystyle y \ in A}$ $y \ in A$ . Это множество A не определено однозначно (его можно увеличить, сохранив свойство замкнутости): множество натуральных чисел N равно

${x ∈ A ∣ ∀ B (∅ ∈ B ∧ ∀ y (y ∈ B → y ∪ {Y} ∈ B) → x ∈ B)} {\ displaystyle \ {x \ in A \ mid \ forall B \, (\ emptyset \ in B \ wedge \ forall y \, (y \ in B \ rightarrow y \ cup \ {y \} \ in B) \ rightarrow x \ in B) \}}$ $\ {x \ in A \ mid \ forall B \, (\ emptyset \ in B \ wedge \ forall y \, (y \ in B \ rightarrow y \ cup \ {y \} \ in B) \ rightarrow x \ in B) \}$

который является пересечением всех наборов, содержащих пустой набор и закрытых при операции «преемника» $y ↦ y ∪ {y} {\ displaystyle y \ mapsto y \ cup \ {y \}}$ $y \ mapsto y \ cup \ {y \}$ .

В ZFC набор $A {\ displaystyle A}$ $A$ конечно тогда и только тогда, когда есть $n ∈ N {\ displaystyle n \ in N}$ $n \ in N$ такое, что $| п | = | А | {\ displaystyle | n | = | A |}$ $| n | = | A |$ : далее определите $| А | {\ displaystyle | A |}$ $| A |$ как это n для конечного A. (Можно доказать, что нет двух различных натуральных чисел одинакового размера).

Обычные арифметические операции могут быть определены рекурсивно и в стиле, очень похожем на тот, в котором определяется сам набор натуральных чисел. Например, + (операция сложения натуральных чисел) может быть определена как наименьшее множество, которое содержит $((x, ∅), x) {\ displaystyle ((x, \ emptyset), x)}$ $((x, \ emptyset), x)$ для каждого натурального числа $x {\ displaystyle x}$ $x$ и содержит $((x, y ∪ {y}), z ∪ {z}) {\ displaystyle ((x, y \ cup \ {y \}), z \ cup \ {z \})}$ $((x, y \ cup \ {y \}), z \ cup \ {z \})$ , если он содержит $((x, y), z) {\ displaystyle ((x, y), z)}$ $((x, y), z)$ .

В NFU не очевидно, что этот подход может быть использован, поскольку операция преемника $y ∪ {y} {\ displaystyle y \ cup \ {y \}}$ $y \ чашка \ {y \}$ является нестратифицированным, и поэтому невозможно показать, что множество N, как определено выше, существует в NFU (это совместимо для набора конечных ординалов фон Неймана в NFU, но это усиливает теорию, поскольку существование этого набора подразумевает Аксиома счета (см. Ниже или статью New Foundations )).

Стандартное определение натуральных чисел, которое на самом деле является самым старым теоретико-множественным определением натуральных чисел, - это классы эквивалентности конечных множеств при равнодоступности. По сути, то же определение подходит для NFU (это не обычное определение, но результаты те же): определите Fin, набор конечных множеств, как

{A ∣ ∀ F (∅ ∈ F ∧ ∀ Икс, Y (Икс ∈ F → Икс ∪ {Y} ∈ F) → A ∈ F)} {\ Displaystyle \ {A \ mid \ forall F \, (\ emptyset \ в F \ клин \ forall x, y \, (x \ in F \ rightarrow x \ cup \ {y \} \ in F) \ rightarrow A \ in F) \}}

\ {A \ mid \ forall F \, (\ emptyset \ in F \ wedge \ forall x, y \, (x \ in F \ rightarrow x \ cup \ {y \} \ in F) \ rightarrow A \ in F) \}

для любого набора $A ∈ F в {\ displaystyle A \ in Fin}$ $A \ in Fin$ , определить $| А | {\ displaystyle | A |}$ $| A |$ как ${B ∣ A ∼ B} {\ displaystyle \ {B \ mid A \ sim B \}}$ $\ {B \ mid A \ sim B \}$ . Определите N как набор ${| А | ∣ A ∈ F in} {\ displaystyle \ {| A | \ mid A \ in Fin \}}$ $\ {| A | \ mid A \ in Fin \}$ .

Аксиома бесконечности NFU может быть выражена как $V ∉ F in {\ displaystyle V \ not \ in Fin}$ $V \ not \ in Fin$ : этого достаточно, чтобы установить, что каждое натуральное число имеет непустого преемника (преемник $| A | {\ displaystyle | A |}$ $| A |$ является $| A ∪ {x} | {\ displaystyle | A \ cup \ {x \} |}$ $| A \ чашка \ {x \} |$ для любого $x ∉ A {\ displaystyle x \ not \ in A}$ $x \ not \ in A$ ), что является трудной частью доказательства выполнения аксиом арифметики Пеано.

Арифметические операции могут быть определены в стиле, аналогичном приведенному выше (с использованием только что данного определения преемника). They can also be defined in a natural set theoretical way: if A and B are disjoint finiteмножества, определим | A | + | B | как $| A ∪ B | {\ displaystyle | A \ cup B |}$ $| A \ cup B |$ . Более формально, определим m + n для m и n в N как

{A ∣ ∃ B, C (B ∈ m ∧ C ∈ n ∧ B ∩ C = ∅ ∧ A = B ∪ C)} {\ displaystyle \ {A \ mid \ exists B, C \, (B \ in m \ wedge C \ in n \ wedge B \ cap C = \ emptyset \ wedge A = B \ cup C) \}}

\ {A \ mid \ exists B, C \, (B \ in m \ wedge C \ in n \ wedge B \ cap C = \ emptyset \ wedge A = B \ cup C) \}

(Но обратите внимание, что этот стиль определения возможен и для чисел ZFC, но более схематичен: форма определения NFU облегчает манипуляции с множествами, а форма определения ZFC облегчает рекурсивные определения, но любая теория поддерживает любой стиль определение).

Эти две реализации совершенно разные. В ZFC представителем каждой конечной мощности (сами классы эквивалентности слишком велики, чтобы быть наборами); в NFU классы эквивалентности сами по себе множеством и таким образом, являются очевидным выбором для объектов, которые должны заменять мощность. Однако арифметика двух теорий идентичности: одна и та же абстракция реализуется этими двумя внешне разными подходами.

Отношения эквивалентности и разбиения

Общий метод реализации абстракций в теории множеств - это использование классов эквивалентности. Если отношение эквивалентности R говорит нам, что элементы его поля A схожи в каком-то конкретном отношении, то для любого набора x рассмотрим набор $[x] R = {y ∈ A ∣ x R y} {\ displaystyle [ x] _ {R} = \ {y \ in A \ mid xRy \}}$ $[x] _ {R} = \ {y \ in A \ mid xRy \}$ как представление абстракции из набора x, учитывающего только эти функции (идентифицируйте элементы от A до Р).

Для любого набора A набор $P {\ displaystyle P}$ $P$ является разделом из A, если все элементы P непусты, любые два различных элементы P непересекаются и $A = ⋃ P {\ displaystyle A = \ bigcup P}$ $A = \ bigcup P$ .

для каждого отношения эквивалентности R с полем A ${[x] R ∣ x ∈ A} {\ displaystyle \ {[x] _ {R} \ mid x \ in A \}}$ $\ {[x] _ {R} \ mid x \ in A \}$ является разбиением A. Более того, каждое разбиение P множества A определяет отношение эквивалентности ${(x, y) ∣ ∃ A ∈ п (Икс ∈ А ∧ Y ∈ А)} {\ Displaystyle \ {(х, у) \ середина \ существует А \ в Р \, (х \ в А \ клин у \ в А) \}}$ $\ {(x, y) \ mid \ существует A \ in P \, (x \ in A \ wedge y \ in A) \}$ .

Этот метод ограничения имеет как в ZFC, так и в NFU. В ZFC, поскольку вселенная не является набором, кажется возможным абстрагировать функции только от элементов области. Это можно обойти с помощью уловки из-за Даны Скотт : если R является отношением эквивалентности во вселенной, определите $[x] R {\ displaystyle [x] _ {R}}$ $[x] _ {R}$ как набор всех y таких, что $y R x {\ displaystyle yRx}$ $yRx$ и ранг y меньше или равен рангу любого $z р Икс {\ Displaystyle zRx}$ $zRx$ . Это работает, потому что ранги установлены. Конечно, все еще может существовать подходящий класс $[x] R {\ displaystyle [x] _ {R}}$ $[x] _ {R}$ . В NFU основная трудность заключается в том, что $[x] R {\ displaystyle [x] _ {R}}$ $[x] _ {R}$ на одном типе выше x, поэтому, например, «map» $x ↦ [x] R {\ displaystyle x \ mapsto [x] _ {R}}$ $x \ mapsto [x] _ {R}$ , как правило, не является (набором) функцией (хотя ${x} ↦ [x] R {\ displaystyle \ {x \} \ mapsto [x] _ {R}}$ $\ {x \} \ mapsto [x] _ {R}$ - это набор). Этого можно избежать, используя Аксиому выбора для выбора представителя каждого класса эквивалентности для $[x] R {\ displaystyle [x] _ {R}}$ $[x] _ {R}$ , который будет с тем же типом, что и x, или путем выбора канонического представителя, если есть способ сделать это без вызова Choice (использование также представителей неизвестно в ZFC). В NFU более распространено использование конструкций классов эквивалентных абстрактных свойств общих наборов, например, в определениях кардинальных и порядковых чисел ниже.

Порядковые числа

Два порядка расположения лунок $W 1 {\ displaystyle W_ {1}}$ $W_1$ и $W 2 {\ displaystyle W_ {2} }$ $W_2$ являются аналогичными и пишут $W 1 ∼ W 2 {\ displaystyle W_ {1} \ sim W_ {2}}$ $W_ {1} \ sim W_ {2}$ на случай, если есть биекция f из поля $W 1 {\ displaystyle W_ {1}}$ $W_1$ в поле $W 2 {\ displaystyle W_ {2}}$ $W_2$ такое что $x W 1 Y ↔ е (Икс) W 2 е (y) {\ displaystyle xW_ {1} y \ leftrightarrow f (x) W_ {2} f (y)}$ $xW_ {1} y \ leftrightarrow f (x) W_ {2} f (y)$ для всех х и у.

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

В New Foundations (NFU) типового заказа хорошо упорядоченного W - это набор всех хорошо упорядоченных, которые подобны W. из порядковых номеров - набор всех порядковых типов заказов скважин.

Это не работает в ZFC, потому что классы эквивалентности слишком велики. Формально можно было бы использовать трюк Скотта для определения порядковых чисел по существу таким же образом, но чаще используется устройство фон Неймана.

Для частичного порядка $≤ {\ displaystyle \ leq}$ $\ leq$ соответствующий строгий частичный порядок < is defined as ${(x, y) ∣ x ≤ y ∧ Икс ≠ Y} {\ Displaystyle \ {(x, y) \ mid x \ leq y \ wedge x \ neq y \}}$ $\ {(x, y) \ mid x \ leq y \ wedge x \ neq y \}$ . Аналогично строгий линейный порядок и строгий хороший порядок.

Набор A называется транзитивным, если $⋃ A ⊆ A {\ displaystyle \ bigcup A \ substeq A}$ $\ bigcup A \ substeq A$ : каждый элемент элемента из A также является элементом A. Порядковый номер (фон Неймана) - это транзитивное множество, на котором членство является строго упорядоченным.

В ZFC тип хорошо упорядоченного W затем определен как уникальный порядковый номер фон Неймана, равный список полей W, и член в котором изоморфно строгому порядку, связанному с W. (условие равнодоступности различает хорошие порядки с полями размера 0 и 1, чьи связанные строгие порядки неразличимы).

В ZFC не может быть набора всех порядковых номеров. Фактически, ординалы фон Неймана представляют собой несовместимую совокупность в любой теории множеств: с помощью скромных теоретических допущений можно показать, что каждый элемент ординалы фон Неймана является ординалом фон Неймана, а ординалы фон Неймана строго упорядочены по атрибутам.. Это строгое упорядочение ординалов фон Неймана следует, что класс ординалов фон Неймана был бы ординалом фон Неймана.

Существование типов множеств Цермело : оно требует Аксиомы замены. Даже уловка Скотта не может быть множеств множеств Цермело без дополнительных предположений (как предположение, что множество принадлежит ранг, которое является некоторым множеством Цермело, но не является теоремой этой теории).

В NFU набор всех порядковых номеров задается путем расслоенного понимания. Неожиданным способом избежать парадокса Бурали-Форти. Существует естественный порядок порядковых номеров, определенный как $α ≤ β {\ displaystyle \ alpha \ leq \ beta}$ $\ alpha \ leq \ beta$ тогда и только тогда, когда некоторые (и так любые) $W 1 ∈ α { \ Displaystyle W_ {1} \ in \ alpha}$ $W_ {1} \ in \ alpha$ аналогичен начальному сегменту некоторого (и любого другого) $W 2 ∈ β {\ displaystyle W_ {2} \ in \ beta}$ $W_ {2} \ in \ beta$ . Кроме того, можно показать, что этот естественный порядок является правильным порядком порядковых номеров и поэтому должен иметь тип порядка $Ω {\ displaystyle \ Omega}$ $\ Omega$ . Казалось бы, тип порядковых номеров меньше $Ω {\ displaystyle \ Omega}$ $\ Omega$ с естественным порядком будет $Ω {\ displaystyle \ Omega}$ $\ Omega$ , что противоречит тому факту, что $Ω {\ displaystyle \ Omega}$ $\ Omega$ является типом порядка естественного порядка на ординалах (и, следовательно, не на любом из его собственных начальных сегментов). Но это зависит от интуиции (верной в ZFC), что тип естественного порядка для порядковых чисел меньше $α {\ displaystyle \ alpha}$ $\ alpha$ равен $α {\ displaystyle \ alpha}$ $\ alpha$ для любого порядкового номера $α {\ displaystyle \ alpha}$ $\ alpha$ . Это утверждение не выполнено, потому что второй тип $α {\ displaystyle \ alpha} <5 четыре77>$ $\ alpha$ на выше, чем тип первого (на два выше, если используется пара уровней типов). Утверждение является истинным и доказанным в NFU, в том, что тип порядка естественного порядка для порядковых чисел меньше $α {\ displaystyle \ alpha}$ $\ alpha$ равен $T 4 (α) {\ displaystyle T ^ {4} (\ alpha)}$ $T ^ {4} (\ alpha)$ для любого порядкового номера $α {\ displaystyle \ alpha}$ $\ alpha$ , где $T (α) {\ displaystyle T (\ alpha)}$ $T (\ alpha)$ - тип заказа $W ι = {({x}, {y}) ∣ x W y} {\ displaystyle W ^ {\ iota} = \ {(\ { x \}, \ {y \}) \ mid xWy \}}$ $W ^ {{\ iota}} = \ {(\ {x \}, \ {y \}) \ mid xWy \}$ для любого $W ∈ α {\ displaystyle W \ in \ alpha}$ $W \ in \ альфа$ (это просто чтобы показать, что это не зависит от выбора W; обратите внимание, что T увеличивает тип на единицу). Таким образом, тип порядка порядковых чисел меньше $Ω {\ displaystyle \ Omega}$ $\ Omega$ с естественным порядком: $T 4 (Ω) {\ displaystyle T ^ {4} (\ Omega)}$ $T ^ {4} (\ Omega)$ и $Т 4 (Ом) < Ω {\displaystyle T^{4}(\Omega)<\Omega }$ $T ^ {4} (\ Omega) <\ Omega$ . Все случаи использования $T 4 {\ displaystyle T ^ {4}}$ $T ^ {4}$ здесь можно заменить на $T 2 {\ displaystyle T ^ {2}}$ $T ^ {2}$ , если используется пара тип-уровень.

Это показывает, что операция T нетривиальна, что имеет ряд последствий. Отсюда сразу следует, что одноэлементная карта $x ↦ {x} {\ displaystyle x \ mapsto \ {x \}}$ $x \ mapsto \ {x \}$ не является набором, иначе ограничения этой карты установили бы подобие W и $W ι {\ displaystyle W ^ {\ iota}}$ $W ^ {{\ iota}}$ для любого хорошо упорядоченного W. T (внешне) биективен и сохранение порядка. Поэтому факт $T 4 (Ω) < Ω {\displaystyle T^{4}(\Omega)<\Omega }$ $T ^ {4} (\ Omega) <\ Omega$ устанавливает, что $Ω>T (Ω)>T 2 (Ω)… {\ displaystyle \ Omega>T (\ Omega)>T ^ { 2} (\ Omega) \ ldots}$ $\Omega>T (\ Omega)>T ^ {2} (\ Omega) \ ldots$ - это« убывающая последовательность »в порядковых числах, которая не может быть набором.

Порядковые числа, установленные T называются канторианскими ординалами, а ординалы, которые преобладают над набором канторианских ординалов (которые, как легко показывают, являются канторианскими), называются строго канторианскими .

Отступление: ординалы фон Неймана в NFU

Можно рассуждать об ординалах фон Неймана в NFU. ограничение принадлежностей к A является строго упорядоченным. Это довольно сильное условие в контекст NFU, поскольку отношение членов включает различные типы. Ординал фон Неймана A не является порядковым в смысле NFU, но $∈ ⌈ A {\ displaystyle \ in \ lceil A}$ $\ in \ lceil A$ принадлежит порядковому номеру $α {\ displaystyle \ alpha}$ $\ alpha$ , который можно назвать порядковым типом (членом в) A. Легко показать, что порядковый тип ординала фон Неймана Канторианский: для любого хорошо упорядоченного W порядкового типа $α {\ displaystyle \ alpha}$ $\ alpha$ , индуцированное упорядочение начальных сегментов путем включения порядка порядка $T (α) {\ displaystyle T (\ alpha)}$ $T (\ alpha)$ (он на один тип выше, следовательно, применение T): но порядковые типы хорошей упорядочения По условиям и хорошей упорядоченности начальных сегментов по включению явно одинаковы, потому что два порядка на самом деле являются одним и тем же отношением, поэтому тип порядка фиксируется относительно T. порядковому номеру (будет который типом порядка н ачального сегмента A, а также порядковым номером фон Неймана) более того, любой ординал фон Неймана является строго канторианским.

Единственными предположениями, которые могут выступить в качестве альтернативы фон Неймана, является существование которых можно показать в NFU без дополнительных предположений. Однако применение метода перестановки может преобразовать любую модель NFU в модель, в которой каждый канторианский ординал является порядковым типом ординала фон Неймана. Это предполагает, что концепция «строго канторианский порядковый номер NFU» может быть лучшим аналогом «порядкового номера ZFC», чем очевидный аналог «порядкового номера NFU».

Кардинальные числа

Кардинальные числа в NFU способ, который позволяет обобщить определение натурального числа: для любого набора A $| А | = def {B ∣ B ∼ A} {\ displaystyle | А | = _ {\ mathrm {def}} \ {B \ mid B \ sim A \}}$ $| A | = _ {{{\ mathrm { def}}}} \ {B \ mid B \ sim A \}$ .

В ZFC эта эквивалентность классы как всегда слишком большие. Можно использовать трюк Скотта (и он действительно используется в ZF ), $| А | {\ displaystyle | A |}$ $| A |$ обычно определяется как тип наименьшего порядка (здесь порядковый номер фон Неймана) хорошей упорядочения A (то, что каждый набор может быть хорошо упорядочен, следует из Аксиомы выбора обычным способом в обеих теориях).

Естественный порядок кардинальных чисел выглядит хорошо упорядоченным: он рефлексивный, антисимметричный (на абстрактных кардиналах, которые теперь доступны) и транзитивный, как было показано выше. То, что это линейный порядок, следует из Аксиомы выбора: два набора с хорошим порядком будут изоморфны другому, поэтому один набор будет иметь мощность меньше, чем у другого. То, что это хороший порядок, аналогичным образом следует из Аксиомы выбора.

С каждым множеством различных типов порядков по обычным причинам.

Теорема Кантора показывает (в обоих теориях), что существуют нетривиальные различия между бесконечными кардинальными числами. В ZFC доказывается $| А | < | P ( A) |. {\displaystyle |A|<|P(A)|.}$ $| A | <| P (A) |.$ В NFU обычная форма теоремы Кантора неверна (рассмотрим случай A = V), но теорема Кантора является некорректно типизированным утверждением. Правильная форма теоремы в НФУ - $| P 1 (A) | < | P ( A) | {\displaystyle |P_{1}(A)|<|P(A)|}$ $|P_{1}(A)|<|P(A)|$ , где $P 1 (A) {\ displaystyle P_ {1} (A)}$ $P_ {1} (A)$ - это набор одноэлементных подмножеств A. $| P 1 (V) | < | P ( V) | {\displaystyle |P_{1}(V)|<|P(V)|}$ $| P_ {1} (V) | <| P (V) |$ показывает, что синглтонов «меньше», чем наборов (очевидное взаимное соответствие $x ↦ {x} {\ displaystyle x \ mapsto \ {x \}}$ $x \ mapsto \ {x \}$ из $P 1 (V) {\ displaystyle P_ {1} (V)}$ $P_{1}(V)$ до V уже было замечено не как набор). В NFU + Choice фактически доказывается, что $| P 1 (V) | < | P ( V) | ≪ | V | {\displaystyle |P_{1}(V)|<|P(V)|\ll |V|}$ $| P_ {1} (V) | <| P (V) | \ ll | V |$ (где $≪ {\ displaystyle \ ll}$ $\ ll$ сигнализирует о существовании множественных вмешивающихся кардиналов; существует много-много элементов!). Определите T-операцию типа воздействия для кардиналов, аналогичную операцию T для порядковых чисел: $T (| A |) = | P 1 (A) | {\ Displaystyle T (| A |) = | P_ {1} (A) |}$ $T (| A |) = | P_ {1} (A) |$ ; это внешний эндоморфизм кардиналов, так же как операция над ординалами является внешним эндоморфизмом ординалов.

Множество A называется канторианским на всякий случай $| А | = | P 1 (A) | Знак равно Т (| А |) {\ Displaystyle | А | = | Р_ {1} (А) | = Т (| А |)}$ $| A | = | P_ {1} (A) | = T (| A |)$ ; кардинал $| А | {\ displaystyle | A |}$ $| A |$ также считается канторианским кардиналом. Множество A называется строго канторианским (и его кардинал также является строго канторианским) на тот случай, если ограничение одноэлементного отображения на A ( $(x ↦ {x}) ⌈ A {\ displaystyle (x \ mapsto \ {x \}) \ lceil A}$ $(x \ mapsto \ {x \}) \ lceil A$ ) - это набор. Хороший порядок строго канторианских множеств всегда строго канторианский ординалы; это не всегда верно для правильного упорядочивания канторианских множеств (хотя самый короткий порядок канторианского набора будет канторианским набором). Канторианское множество - это множество, удовлетворяющая обычная форма теоремы Кантора.

Операции кардинальной арифметики модико-множественным образом в обеих теориях. $| А | + | B | Знак равно {C ∪ D ∣ C ∼ A ∧ D ∼ B ∧ C ∩ D = ∅} {\ displaystyle | А | + | B | = \ {C \ cup D \ mid C \ sim A \ wedge D \ sim B \ клин C \ cap D = \ emptyset \}}$ $| A | + | B | = \ {C \ cup D \ mid C \ sim A \ клин D \ sim B \ клин C \ cap D = \ emptyset \}$ . Хотелось бы определить $| А | ⋅ | B | {\ displaystyle | А | \ cdot | B |}$ $| A | \ cdot | B |$ как $| A × B | {\ displaystyle | A \ times B |}$ $| A \ times B |$ , и один делает это в ZFC, но есть препятствие в NFU при использовании пары Куратовского: один определяет $| А | ⋅ | B | {\ displaystyle | А | \ cdot | B |}$ $| A | \ cdot | B |$ как $T - 2 (| A × B |) {\ displaystyle T ^ {- 2} (| A \ times B |)}$ $T ^ {{- 2}} (| A \ times B |)$ из-за смещение типа 2 между парой и ее проекциями, что подразумевает смещение типа 2 между декартовым произведением и его множителями. Несложно доказать, что продукт существует всегда (но требует внимания, поскольку обратное к T не является полным).

Определение экспоненциальной операции над кардиналами требует демонстрации: если $BA {\ displaystyle B ^ {A}}$ $B ^ A$ был определен как набор функций от A до B, это на три типа выше, чем A или B, поэтому разумно определить $| B | | А | {\ displaystyle | B | ^ {| A |}}$ $| B | ^ {{| A |}}$ как $T - 3 (| BA |) {\ displaystyle T ^ {- 3} (| B ^ {A} |)}$ $T ^ {{- 3}} (| B ^ {A} |)$ так, чтобы он был того же типа, что и A или B ( $T - 1 {\ displaystyle T ^ {- 1}}$ $T ^ {- 1}$ заменяет $T - 3 {\ displaystyle T ^ {- 3} }$ $T ^ {{- 3}}$ с парами уровня типа). В результате экспоненциальная операция является частичной: например, $2 | V | {\ displaystyle 2 ^ {| V |}}$ $2 ^ {{| V |}}$ не определено. В ZFC определяет $| B | | А | {\ displaystyle | B | ^ {| A |}}$ $| B | ^ {{| A |}}$ как $| B A | {\ displaystyle | B ^ {A} |}$ $| B ^ {A} |$ без проблем.

Экспоненциальная операция является полной и ведет себя так, как ожидалось, для канторианских кардиналов, поскольку T фиксирует такие кардиналы, и легко показать, что функциональное пространство между канторианскими наборами является канторианским (как и степенные наборы, декартовы точно произведения и) другие конструкторы обычных типов). Это также мнение о том, что "стандартные" мощности в NFU являются канторианскими (действительно, строго канторианскими) мощностями, так же как "стандартные" ординалы кажутся строго канторианскими ординалами.

Теперь можно доказать обычные теоремы кардинальной арифметики с выбранной аксиомой, включая $κ ⋅ κ = κ {\ displaystyle \ kappa \ cdot \ kappa = \ kappa}$ $\ kappa \ cdot \ kappa = \ kappa$ . Из дела $| V | ⋅ | V | = | V | {\ displaystyle | V | \ cdot | V | = | V |}$ $| V | \ cdot | V | = | V |$ наличие упорядоченной пары на уровне типа может быть выведено: $| V | ⋅ | V | Знак равно Т - 2 (| V × V |) {\ Displaystyle | V | \ cdot | V | = T ^ {- 2} (| V \ times V |)}$ $| V | \ cdot | V | = T ^ {{- 2}} (| V \ times V |)$ равно $| V | {\ displaystyle | V |}$ $| V |$ на всякий случай $| V × V | = T 2 (| V |) = | P 1 2 (V) | {\ displaystyle | V \ раз V | = T ^ {2} (| V |) = | P_ {1} ^ {2} (V) |}$ $| V \ times V | = T ^ {2} (| V |) = | P_ {1} ^ {2 } (V) |$ , что засвидетельствовало бы одно- однозначное соответствие между парами Куратовского $(a, b) {\ displaystyle (a, b)}$ $(a, b)$ и двойными синглетонами ${{c}} {\ displaystyle \ {\ {c \} \}}$ $\{\{c\}\}$ : переопределить $(a, b) {\ displaystyle (a, b)}$ $(a, b)$ как c так, чтобы ${{c}} {\ displaystyle \ {\ {c \} \}}$ $\{\{c\}\}$ связан с Kuratowski $(a, b) {\ displaystyle (a, b)}$ $(a, b)$ : это тип -уровневое понятие упорядоченной пары.

Аксиома подсчета и подрыв стратификации

Итак, есть две разные реализации натуральных чисел в NFU (хотя они одинаковы в ZFC ): конечные ординалы и конечные кардиналы. Каждый из них поддерживает операцию T в NFU (в основном та же операция). Легко доказать, что $T (n) {\ displaystyle T (n)}$ $T(n)$ - натуральное число, if n - натуральное число в NFU + Infinity + Choice (и поэтому $| N | {\ displaystyle | N |}$ $| N |$ и первый бесконечный порядковый номер $ω {\ displaystyle \ omega}$ $\ omega$ канторианские), но это невозможно доказать в этой теории, что $T (n) = n {\ displaystyle T (n) = n}$ $T(n)=n$ . Однако здравый смысл подсказывает, что это должно быть правдой, и поэтому его можно принять как аксиому:

Аксиома счета Россера : для каждого натурального числа n $T (n) = n {\ displaystyle T (n) = n}$ $T(n)=n$ .

Одно естественное следствие этой аксиомы (и действительно ее исходной формулировки):

$| {1,…, n} | = п {\ Displaystyle | \ {1, \ ldots, n \} | = n}$ $| \ {1, \ ldots, n \} | = n$ для каждого натурального числа n.

Все, что можно доказать в NFU без подсчета это $| {1,…, n} | Знак равно Т 2 (N) {\ Displaystyle | \ {1, \ ldots, n \} | = T ^ {2} (n)}$ $| \ {1, \ ldots, n \} | = T ^ {2} (n)$ .

Следствие подсчета является то, что N - строго канторианское множество (опять же, это эквивалентное утверждение).

Свойства строго канторианских множеств

Тип любой переменной, ограниченный строго канторианским множеством A, может быть повышен или понижен по желанию путем замены ссылок на $a ∈ A {\ displaystyle a \ in A }$ $a \ in A$ со ссылками на $⋃ f (a) {\ displaystyle \ bigcup f (a)}$ $\ bigcup f (a)$ (тип поднятого; это предполагает, что известно, что a - набор; в в противном случае нужно сказать "элемент $f (a) {\ displaystyle f (a)}$ $f (a)$ ", чтобы получить этот эффект) или $f - 1 ({a}) {\ displaystyle f ^ {- 1} (\ {a \})}$ $f ^ {{- 1}} (\ {a \})$ (тип пониженного), где $f (a) = {a} {\ displaystyle f (a) = \ {a \}}$ $f (a) = \ {a \}$ для всех $a ∈ A {\ displaystyle a \ in A}$ $a \ in A$ , поэтому нет необходимости назначать типы переменных для целей стратификации.

Любое подмножество строго канторианского набора является строго канторианским. Набор мощности строго канторианской системы строго канторианский. Декартово произведение двух строго канторианских множеств является канторианским.

Введение аксиомы подсчета означает, что типам не нужно присваивать переменным, ограниченным N или P (N), R (набором вещественных чисел), или вообще любому набору, когда-либо рассматривавшимся в классической математике вне теории множеств..

В ZFC нет аналогичных явлений. См. Основную статью Новые основы для более сильных аксиом, которые могут быть присоединены к NFU для обеспечения «стандартного» поведения знакомых математических объектов.

Знакомые системы счисления: положительные рациональные числа, величина и действительные числа

Представьте положительные дроби как пары положительных натуральных чисел (0 исключен): $pq {\ displaystyle {\ frac {p} {q}}}$ ${\ frac pq}$ представлен парой $(p, q) {\ displaystyle (p, q)}$ $(p, q)$ . Чтобы сделать $pq = rs ↔ ps = qr {\ displaystyle {\ frac {p} {q}} = {\ frac {r} {s}} \ leftrightarrow ps = qr}$ ${\ frac pq} = { \ frac rs} \ leftrightarrow ps = qr$ , введите отношение $∼ {\ displaystyle \ sim}$ $\ sim$ определяется как $(p, q) ∼ (r, s) ↔ ps = qr {\ displaystyle (p, q) \ sim (r, s) \ leftrightarrow ps = qr}$ $(p, q) \ sim (r, s) \ leftrightarrow ps = qr$ . Доказано, что это отношение эквивалентности: определите положительные рациональные числа как классы эквивалентности пар положительных натуральных чисел при этом отношении. Арифметические операции над положительными рациональными числами и отношение порядка на положительных рациональных числах определены так же, как в начальной школе, и доказано (с некоторыми усилиями), что они обладают ожидаемыми свойствами.

Представьте величины (положительные действительные числа) как непустые собственные начальные сегменты положительных рациональных чисел без наибольшего элемента. Операции сложения и умножения величин осуществляются поэлементным сложением положительных рациональных элементов величин. Заказ реализован по мере включения.

Представьте действительные числа как разности $m - n {\ displaystyle mn}$ $mn$ величин: формально говоря, действительное число - это класс эквивалентности пар $(m, n) {\ displaystyle (m, n)}$ $(m, n)$ величин в соответствии с отношением эквивалентности $∼ {\ displaystyle \ sim}$ $\ sim$ , определенным в $( м, п) ∼ (г, s) ↔ м + s знак равно N + р {\ Displaystyle (м, п) \ sim (г, s) \ leftrightarrow м + s = п + г}$ $(m, n) \ sim (r, s) \ leftrightarrow m + s = n + r$ . Операции сложения и умножения действительных чисел определяются так же, как и следовало ожидать от алгебраических правил сложения и умножения разностей. Порядок трактуется также как в элементарной алгебре.

Это кратчайший набросок построек. Обратите внимание, что конструкции точно такие же в ZFC и в NFU, за исключением разницы в конструкциях натуральных чисел: поскольку все переменные ограничены строго канторианскими наборами, существует не нужно беспокоиться об ограничениях стратификации. Без Аксиомы счета, возможно, потребуется ввести некоторые приложения T при полном обсуждении этих конструкций.

Операции с индексированными семействами наборов

В этом классе конструкций оказывается, что ZFC имеет преимущество перед NFU : хотя конструкции явно выполнимые в NFU, они сложнее, чем в ZFC, по причинам, связанным с расслоением.

В этом разделе предполагается наличие упорядоченной пары на уровне типа. Определите $(x 1, x 2,…, xn) {\ displaystyle (x_ {1}, x_ {2}, \ ldots, x_ {n})}$ $(x_ {1}, x_ {2}, \ ldots, x_ {n})$ как $(x 1, (x 2,…, xn)) {\ displaystyle (x_ {1}, (x_ {2}, \ ldots, x_ {n}))}$ $(x_ {1}, (x_ {2}, \ ldots, x_ {n}))$ . Типоразмеры, связанные с типом, типоразмером, типоразмером, типоразмером, типоразмером, типоразмером, типоразмером. Здесь n-кортеж имеет тот же тип, что и каждая из его проекций.

Общие декартовы произведения определяются аналогично: $A 1 × A 2 ×… × A n = A 1 × (A 2 ×… × A n) {\ displaystyle A_ {1} \ times A_ { 2} \ times \ ldots \ times A_ {n} = A_ {1} \ times (A_ {2} \ times \ ldots \ times A_ {n})}$ $A_ {1} \ times A_ {2} \ times \ ldots \ times A_ {n} = A_ {1} \ times (A_ {2} \ times \ ldots \ times A_ {n })$

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

Теперь рассмотрим бесконечное декартово произведение $Π i ∈ I A i {\ displaystyle \ Pi _ {i \ in I} A_ {i}}$ $\ Pi _ {{i \ in I}} A_ {i}$ . В ZFC это определяется как набор всех функций f в области I таких, что $f (i) ∈ A i {\ displaystyle f (i) \ in A_ {i}}$ $f (i) \ in A_ {i}$ (где Неявно A понимается как функция, переводящая каждое i в $A i {\ displaystyle A_ {i}}$ $A_ {i}$ ).

В NFU это требует внимания к типу. Дан набор I и функция с заданным значением A, значение которой находится в ${i} {\ displaystyle \ {i \}}$ $\ {i \}$ в $P 1 (I) {\ displaystyle P_ {1} ( I)}$ $P_ {1} (I)$ записывается $A i {\ displaystyle A_ {i}}$ $A_ {i}$ , определить $Π i ∈ IA i {\ displaystyle \ Pi _ {i \ in I} A_ {i}}$ $\ Pi _ {{i \ in I}} A_ {i}$ как набор всех функций f с областью I, таких что $f (i) ∈ A i {\ displaystyle f (i) \ in A_ {i}}$ $f (i) \ in A_ {i}$ : обратите внимание, что $f (i) ∈ A i = A ({i}) {\ displaystyle f (i) \ in A_ {i} = A (\ {i \})}$ $f (i) \ in A_ {i} = A (\ {i \})$ стратифицирован из-за нашего соглашения о том, что A - это функция со значениями в синглетонах индексов. Обратите внимание, что самые большие семейства наборов (которые не могут быть проиндексированы синглтонов) не имеют декартовых произведений в соответствии с этим определением. Обратите внимание, что наборы $A i {\ displaystyle A_ {i}}$ $A_ {i}$ относятся к тому же типу, что и индексный набор I (поскольку на один тип выше, чем его элементы); продукт, как набор функций с доменом I (то есть того же типа, что и I), на один тип выше (при условии упорядоченной пары на уровне типа).

Теперь рассмотрим произведение $Π i ∈ I | A i | {\ displaystyle \ Pi _ {я \ in I} | A_ {i} |}$ $\ Pi _ {{i \ in I}} | A_ {i} |$ кардиналов этих множеств. Мощность | $Π i ∈ I A i {\ displaystyle \ Pi _ {i \ in I} A_ {i}}$ $\ Pi _ {{i \ in I}} A_ {i}$ | на один тип выше кардиналов $| A i | {\ displaystyle | A_ {i} |}$ $| A_ {i} |$ , поэтому правильное определение бесконечного произведения кардиналов: $T - 1 (| Π i ∈ IA i |) {\ displaystyle T ^ {- 1} (| \ Pi _ {i \ in I} A_ {i} |)}$ $T ^ {{- 1}} (| \ Pi _ {{i \ in I}} A_ {i} |)$ (поскольку обратное T не является полным, возможно, что этого не существует).

Повторите это для непересекающихся объединений семейств множеств и сумм семейств кардиналов. Опять же, пусть A будет многозначной функцией с доменом $P 1 (I) {\ displaystyle P_ {1} (I)}$ $P_ {1} (I)$ : write $A i {\ displaystyle A_ {i }}$ $A_ {i}$ для $A ({i}) {\ displaystyle A (\ {i \})}$ $A(\{i\})$ . Непересекающееся объединение $Σ i ∈ IA i {\ displaystyle \ Sigma _ {i \ in I} A_ {i}}$ $\ Sigma _ {{i \ in I} } A_ {i }$ - это множество ${(i, a) ∣ a ∈ A i} {\ displaystyle \ {(i, a) \ mid a \ in A_ {i} \}}$ $\ {(i, a) \ mid a \ in A_ {i} \}$ . Этот набор имеет тот же тип, что и наборы $A i {\ displaystyle A_ {i}}$ $A_ {i}$ .

Правильное определение суммы $Σ i ∈ I | A i | {\ displaystyle \ Sigma _ {я \ in I} | A_ {i} |}$ $\ Sigma _ {{i \ in I}} | A_ {i} |$ , таким образом, $| Σ i ∈ I A i | {\ displaystyle | \ Sigma _ {i \ in I} A_ {i} |}$ $| \ Sigma _ {{i \ in I}} A_ {i} |$ , поскольку смещения типа нет.

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

В ZFC определите непересекающееся объединение $Σ i ∈ IA i {\ displaystyle \ Sigma _ {i \ in I} A_ {i}}$ $\ Sigma _ {{i \ in I} } A_ {i }$ как ${( я, а) ∣ a ∈ A i} {\ displaystyle \ {(i, a) \ mid a \ in A_ {i} \}}$ $\ {(i, a) \ mid a \ in A_ {i} \}$ , где $A i {\ displaystyle A_ { i}}$ $A_ {i}$ сокращает $A (i) {\ displaystyle A (i)}$ $A (i)$ .

Методы перестановки могут использоваться, чтобы показать относительную согласованность с NFU утверждения, что для каждого строго канторианского множества A существует - это набор I того же размера, элементы которого являются самодостаточными: $i = {i} {\ displaystyle i = \ {i \}}$ $i = \ {i \}$ для каждого i в I.

Кумулятивная иерархия

В ZFC определите кумулятивную иерархию как последовательность наборов с порядковым индексом, удовлетворяющую следующим условиям: $V 0 = ∅ {\ displaystyle V_ {0 } = \ emptyset}$ $V_ {0} = \ emptyset$ ; $V α + 1 = P (V α) {\ displaystyle V _ {\ alpha +1} = P (V _ {\ alpha})}$ $V _ {{\ alpha +1}} = P (V _ {{\ alpha}})$ ; $V λ = ⋃ {V β ∣ β < λ } {\displaystyle V_{\lambda }=\bigcup \{V_{\beta }\mid \beta <\lambda \}}$ $V _ {{\ lambda}} = \ bigcup \ {V _ {{\ beta}} \ mid \ beta <\ lambda \}$ для предельных порядковых ном еров $λ {\ displaystyle \ lambda}$ $\ lambda$ . Это пример конструкции с помощью трансфинитной рекурсии. Ранг множества A называется $α {\ displaystyle \ alpha}$ $\ alpha$ тогда и только тогда, когда $A ∈ V α + 1 - V α {\ displaystyle A \ in V_ { \ alpha +1} -V _ {\ alpha}}$ $A \ in V _ {{\ alpha +1}} - V _ {{\ alpha}}$ . Существование рангов как множеств зависит от аксиомы замены на каждом предельном шаге (иерархия не может быть построена в теории множеств Цермело ); по аксиоме основания множеству принадлежит некоторому рангу.

Кардинал $| P (V ω + α) | {\ displaystyle | P (V _ {\ omega + \ alpha}) |}$ $| P (V _ {{\ omega + \ alpha}}) |$ называется $ℶ α {\ displaystyle \ beth _ {\ alpha}}$ $\ beth _ {\ alpha}$ .

Эта конструкция не может быть выполнена в NFU, поскольку операция набора мощности не является заданной функцией в NFU ( $P (A) {\ displaystyle P (A)}$ $P ( A)$ - это один тип выше, чем A для целей стратификации).

Последовательность кардиналов $ℶ α {\ displaystyle \ beth _ {\ alpha}}$ $\ beth _ {\ alpha}$ может быть реализована в NFU. Напомним, что $2 | А | {\ displaystyle 2 ^ {| A |}}$ $2 ^ {{| A |}}$ определяется как $T - 1 (| {0, 1} A |) {\ displaystyle T ^ {- 1} (| \ {0, 1 \} ^ {A} |)}$ $T ^ {{- 1}} (| \ { 0,1 \} ^ {A} |)$ , где ${0, 1} {\ displaystyle \ {0,1 \}}$ $\ {0,1 \}$ - удобный набор размеров 2 и $| {0, 1} A | = | P (A) | {\ Displaystyle | \ {0,1 \} ^ {A} | = | P (A) |}$ $| \ {0,1 \} ^ {A} | = | P (A) |$ . Пусть $ℶ {\ displaystyle \ beth}$ $\ beth$ будет наименьшим набором кардиналов, который содержит $| N | {\ displaystyle | N |}$ $| N |$ (мощность множества натуральных чисел), содержит кардинал $2 | А | {\ displaystyle 2 ^ {| A |}}$ $2 ^ {{| A |}}$ , если он содержит $| А | {\ displaystyle | A |}$ $| A |$ , который замкнут относительно супремумов множеств кардиналов.

Соглашение о порядковой индексации любого хорошо упорядоченного $W α {\ displaystyle W _ {\ alpha}}$ $W _ {\ альфа}$ определяется как элемент x поля $W {\ displaystyle W}$ $W$ таким образом, чтобы тип заказа с ограничением от $W {\ displaystyle W}$ $W$ до ${y ∣ y W x} {\ displaystyle \ {y \ mid yWx \}}$ $\ {y \ mid yWx \}$ равно $α {\ displaystyle \ alpha}$ $\ alpha$ ; затем определите $ℶ α {\ displaystyle \ beth _ {\ alpha}}$ $\ beth _ {\ alpha}$ как элемент с индексом $α {\ displaystyle \ alpha}$ $\ alpha$ в естественном порядке на элементы $ℶ {\ displaystyle \ beth}$ $\ beth$ . Кардинал $ℵ α {\ displaystyle \ aleph _ {\ alpha}}$ $\ aleph _ {\ alpha}$ - это элемент с индексом $α {\ displaystyle \ alpha}$ $\ alpha$ в естественном порядке на все бесконечные кардиналы (что хорошо упорядочено, см. выше). Обратите внимание, что $ℵ 0 = | N | {\ displaystyle \ aleph _ {0} = | N |}$ $\ алеф _ {0} = | N |$ непосредственно следует из этого определения. Обратите внимание, что во всех этих конструкциях тип индекса $α {\ displaystyle \ alpha}$ $\ alpha$ на два выше (с упорядоченной парой на уровне типов), чем тип $W α {\ displaystyle W _ {\ alpha}}$ $W _ {{\ alpha}}$ .

Каждый набор A ZFC имеет транзитивное замыкание $TC (A) {\ displaystyle TC (A)}$ $TC (A)$ (пересечение всех транзитивных наборов, содержащих A). Согласно аксиоме основания ограничение отношения принадлежности к транзитивному замыканию A является хорошо обоснованным отношением. Отношение $∈ ⌈ T C (A) {\ displaystyle \ in \ lceil TC (A)}$ $\ in \ lceil TC (A)$ либо пусто, либо имеет A в качестве верхнего элемента, поэтому это отношение является заданным изображением. В ZFC можно доказать, что каждое установленное изображение изоморфно некоторому $∈ ⌈ TC (A) {\ displaystyle \ in \ lceil TC (A)}$ $\ in \ lceil TC (A)$ .

Это предполагает, что (начальный сегмент) кумулятивной иерархии можно изучить, рассматривая классы изоморфизма изображений множества. Эти классы изоморфизма являются наборами и составляют набор в NFU. Существует естественное отношение множества, аналогичное членству в классах изоморфизма множества изображений: если $x {\ displaystyle x}$ $x$ является установленным изображением, напишите $[x] {\ displaystyle [x] }$ $[x]$ для своего класса изоморфизма и определите $[x] E [y] {\ displaystyle [x] E [y]}$ $[x] E [y]$ как содержащий if $[x] { \ displaystyle [x]}$ $[x]$ - это класс изоморфизма ограничения y на закрытие вниз одного из элементов прообраза под y верхнего элемента y. Отношение E - это установленное отношение, и легко доказать, что оно хорошо обосновано и экстенсионально. Если определение E сбивает с толку, это можно сделать из наблюдения, что оно вызвано именно отношением, которое имеет место между заданным изображением, связанным с A, и заданным изображением, связанным с B, когда $A ∈ B {\ displaystyle A \ in B}$ $A \ in B$ в обычной теории множеств.

Существует операция T над классами изоморфизма заданных изображений, аналогичная операции T над порядковыми числами: если x является заданным изображением, то $x ι = {({a}, {b}) ∣ (a, b) ∈ x} {\ displaystyle x ^ {\ iota} = \ {(\ {a \}, \ {b \}) \ mid (a, b) \ in x \}}$ $x ^ {{\ iota}} = \ {(\ {a \}, \ {b \}) \ mid (a, b) \ in x \}$ . Определите $T ([x]) {\ displaystyle T ([x])}$ $T ([x])$ как $[x ι] {\ displaystyle [x ^ {\ iota}]}$ $[x ^ {{\ iota}}]$ . Легко видеть, что $[x] E [y] ↔ T ([x]) = T ([y]) {\ displaystyle [x] E [y] \ leftrightarrow T ([x]) = T ([y])}$ $[x] E [y] \ leftrightarrow T ([x]) = T ([y])$ .

Аксиома экстенсиональности для этой смоделированной теории множеств следует из экстенсиональности E. Из его обоснованности следует аксиома основания. Остается вопрос, какое понимание может иметь аксиома E. Рассмотрим любую коллекцию заданных изображений ${x ι ∣ x ∈ S} {\ displaystyle \ {x ^ {\ iota} \ mid x \ in S \}}$ $\ {x ^ {{\ iota}} \ mid x \ in S \}$ (набор заданных изображений, поля которых полностью состоят из синглтонов). Поскольку каждый $x ι {\ displaystyle x ^ {\ iota}}$ $x ^ {{\ iota}}$ является на один тип выше, чем x (с использованием упорядоченной пары на уровне типа), заменяя каждый элемент ${a} {\ displaystyle \ {a \}}$ $\ {a \}$ поля каждого $x ι {\ displaystyle x ^ {\ iota}}$ $x ^ {{\ iota}}$ в коллекции с $(x, { a}) {\ displaystyle (x, \ {a \})}$ $(x, \ {a \})$ приводит к набору установленных изображений, изоморфных исходной коллекции, но с непересекающимися полями. Объединение этих изображений множества с новым верхним элементом дает изображение множества, тип изоморфизма которого будет иметь в качестве своих прообразов под E в точности элементы исходной коллекции. То есть для любого набора типов изоморфизма $[x ι] = T ([x]) {\ displaystyle [x ^ {\ iota}] = T ([x])}$ $[x ^ {{\ iota}}] = T ([x])$ существует является типом изоморфизма $[y] {\ displaystyle [y]}$ $[y]$ , чей прообраз под E является в точности этим набором.

В частности, будет тип изоморфизма [v], прообраз которого под E является набором всех T [x] (включая T [v]). Поскольку T [v] E v и E хорошо обоснованы, $T [v] ≠ v {\ displaystyle T [v] \ neq v}$ $T [v] \ neq v$ . Это похоже на разрешение парадокса Бурали – Форти, обсуждавшееся выше и в статье New Foundations, и фактически является локальным разрешением множества всех хорошо обоснованных множеств.

Существуют ранги классов изоморфизма образов множеств, точно так же, как существуют ранги множеств в обычной теории множеств. Для любого набора изображений множества A определите S (A) как множество всех классов изоморфизма изображений множества, чей прообраз под E является подмножеством A; назовите A "полным" набором, если каждое подмножество A является прообразом для E. Набор "рангов" - это наименьший набор, содержащий пустое множество и закрытый при операции S (которая является своего рода конструкцией набора мощности) и при союзы его подколлекций. Несложно доказать (как и в обычной теории множеств), что ранги хорошо упорядочены по включению, и поэтому ранги имеют индекс в этом хорошем порядке: обратитесь к рангу с индексом $α {\ displaystyle \ alpha}$ $\ alpha$ как $R α {\ displaystyle R _ {\ alpha}}$ $R _ {{\ alpha}}$ . Доказуемо, что $| R α | Знак равно ℶ α {\ Displaystyle | R _ {\ альфа } | = \ beth _ {\ alpha}}$ $| R _ {{\ alpha}} | = \ beth _ {{\ alpha}}$ для полных рангов $R α {\ displaystyle R _ {\ alpha}}$ $R _ {{\ alpha}}$ . Объединение полных рангов (которое будет первым неполным рангом) с отношением E выглядит как начальный сегмент вселенной теории множеств в стиле Цермело (не обязательно как полная совокупность ZFC, потому что она может быть недостаточно большим). Доказано, что если $R α {\ displaystyle R _ {\ alpha}}$ $R _ {{\ alpha}}$ является первым неполным рангом, то $RT (α) {\ displaystyle R_ {T (\ alpha)} }$ $R _ {{T (\ alpha)}}$ - полный ранг и, следовательно, $T (α) < α {\displaystyle T(\alpha)<\alpha }$ $T (\ alpha) <\ alpha$ . Итак, существует «ранг кумулятивной иерархии» с «внешним автоморфизмом» T, перемещающим ранг вниз, в точности условие нестандартной модели ранга в кумулятивной иерархии, при котором модель NFU строится в Статья New Foundations. Необходимо проверить технические детали, но есть интерпретация не только фрагмента ZFC, но и самого NFU в этой структуре с $[x] ∈ NFU [y ] {\ displaystyle [x] \ in _ {NFU} [y]}$ $[x] \ in _ {{NFU}} [y]$ определяется как $T ([x]) E [y] ∧ [y] ∈ RT (α) + 1 { \ displaystyle T ([x]) E [y] \ wedge [y] \ in R_ {T (\ alpha) +1}}$ $T ([x]) E [y] \ wedge [y] \ in R _ {{T (\ alpha) +1}}$ : это "отношение" $ENFU {\ displaystyle E_ { NFU}}$ $E _ {{NFU}}$ не является отношением набора, но имеет такое же смещение типов между своими аргументами, что и обычное отношение принадлежности $∈ {\ displaystyle \ in}$ $\ in$ .

Таким образом, внутри NFU существует естественная конструкция кумулятивная иерархия множеств, которая усваивает естественное построение модели NFU в теории множеств в стиле Цермело.

Согласно Аксиоме канторианских множеств, описанной в статье New Foundations, строго канторианская часть множества классов изоморфизма изображений множества с отношением E, когда членство становится (надлежащим классом) модель ZFC (в которой n- для каждого n; это расширение NFU строго сильнее, чем ZFC). Это правильная модель классов, потому что классы строго канторианского изоморфизма не составляют набор.

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

См. Также

Теория аксиоматических множеств

Ссылки

Кейт Девлин, 1994. Радость множеств, 2-е изд. Springer-Verlag.
Holmes, Randall, 1998. Теория элементарных множеств с универсальным множеством. Academia-Bruylant. Издатель любезно согласился разрешить распространение этого введения в NFU через Интернет. Авторские права защищены.
Поттер, Майкл, 2004. Теория множеств и ее философия, 2-е изд. Oxford Univ. Press.
Suppes, Patrick, 1972. Аксиоматическая теория множеств. Довер.
Турлакис, Джордж, 2003. Лекции по логике и теории множеств, Vol. 2. Cambridge Univ. Press.

Внешние ссылки

Метаматематика: Веб-сайт, посвященный продолжающемуся выведению математики из аксиом ZFC и логики первого порядка.
Стэнфордская энциклопедия философии :
- Quine's New Foundation - Томас Форстер.
- Альтернативные аксиоматические теории множеств - Рэндалл Холмс.
Рэндалл Холмс: Домашняя страница New Foundations