Схема свёртывания

Схема свёртывания (англ. Comprehension Scheme) — схема аксиом наивной теории множеств. Неформально она говорит о том, что для каждого свойства существует множество, состоящее в точности из тех элементов, что удовлетворяют этому свойству. Схема свёртывания формализует известное школьное определение множества, гласящее, что «множество — это совокупность элементов, обладающих общим свойством». На языке логики предикатов схема свёртывания записывается следующим образом:

$\mathrm{\exists <!--\; \exists \; -->}A\mathrm{\forall <!--\; \forall \; -->}x(x\in <!--\; \in \; -->A\leftrightarrow <!--\; \leftrightarrow \; -->\mathrm{\phi <!--\; \phi \; -->})$$\exists A\ \forall x\ (x\in A\leftrightarrow \varphi )$

Здесь под $\mathrm{\phi <!--\; \phi \; -->}$$\varphi$ понимается любая формула языка логики предикатов с равенством и двуместным предикатным символом $\in <!--\; \in \; -->$$\in$, в которую не входит свободно переменная $A$$A$. Таким образом, схема представляет собой набор аксиом по одной для каждой конкретной формулы $\mathrm{\phi <!--\; \phi \; -->}$$\varphi$.

Схема свёртывания является противоречивой. Для вывода противоречия в наивной теории множеств даже не нужно использовать аксиому объёмности: схема свёртывания сама по себе противоречива.

ПротиворечивостьПравить

Из схемы свёртывания можно вывести противоречие. Одно из наиболее известных выводимых из неё противоречий называется парадоксом Рассела.

Рассмотрим формулу

$\mathrm{\phi <!--\; \phi \; -->}:\leftrightarrow <!--\; \leftrightarrow \; -->\mathrm{\neg <!--\; \neg \; -->}(x\in <!--\; \in \; -->x)$$\varphi :\leftrightarrow \lnot (x\in x)$ 

Схема свёртывания утверждает, что существует такое множество $A$$A$ , что

$\mathrm{\forall <!--\; \forall \; -->}xx\in <!--\; \in \; -->A\leftrightarrow <!--\; \leftrightarrow \; -->\mathrm{\neg <!--\; \neg \; -->}(x\in <!--\; \in \; -->x)$$\forall x\ x\in A\leftrightarrow \lnot (x\in x)$ 

Возьмём $x$$x$  равный $A$$A$ . Тогда

$A\in <!--\; \in \; -->A\leftrightarrow <!--\; \leftrightarrow \; -->\mathrm{\neg <!--\; \neg \; -->}(A\in <!--\; \in \; -->A)$$A\in A\leftrightarrow \lnot (A\in A)$  — противоречие.

Также есть и другие известные противоречия, например парадокс Кантора или парадокс Бурали-Форти.

Вариации и обобщенияПравить

Есть различные модифиации схемы свёртывания для того, чтобы избавить её от противоречий.

Схема выделенияПравить

Основная статья: Схема выделения

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

$\mathrm{\forall <!--\; \forall \; -->}B\mathrm{\exists <!--\; \exists \; -->}A\mathrm{\forall <!--\; \forall \; -->}x(x\in <!--\; \in \; -->A\leftrightarrow <!--\; \leftrightarrow \; -->x\in <!--\; \in \; -->B\wedge <!--\; \wedge \; -->\mathrm{\phi <!--\; \phi \; -->})$$\forall B\ \exists A\ \forall x\ (x\in A\leftrightarrow x\in B\land \varphi )$ 

Данная схема является основным способом построения множеств в теориях множеств Цермело и Цермело-Френкеля. Полную схему свёртывания иногда называют схемой неограниченного свёртывания или схемой неограниченного выделения.

Схема свёртывания классовПравить

В теории множеств фон Неймана-Бернайса-Гёделя кроме множеств присутствуют также классы. Классы могут состоять из всех множеств, удовлетворяющих некоторому свойству, что и утверждает данный аналог схемы свёртывания:

$\mathrm{\exists <!--\; \exists \; -->}A\mathrm{\forall <!--\; \forall \; -->}x(x\in <!--\; \in \; -->A\leftrightarrow <!--\; \leftrightarrow \; -->\mathrm{\phi <!--\; \phi \; -->})$$\exists A\ \forall x\ (x\in A\leftrightarrow \varphi )$ 

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

Схема свёртывания в теории типовПравить

В простой теории типов схема свёртывания выглядит следующим образом:

$\mathrm{\exists <!--\; \exists \; -->}{A}_{n+1}\mathrm{\forall <!--\; \forall \; -->}{x}_n(x_n\in <!--\; \in \; -->A_{n+1}\leftrightarrow <!--\; \leftrightarrow \; -->\mathrm{\phi <!--\; \phi \; -->})$$\exists A_{n+1}\ \forall x_{n}\ (x_{n}\in A_{n+1}\leftrightarrow \varphi )$ 

Здесь индекс переменных обозначаеи их тип. В теории типов множеству типа $n+1$$n+1$  позволяется иметь лишь элементы типа $n$$n$ , поэтому формулы вида $x\in <!--\; \in \; -->x$$x\in x$  просто не допускаются.

Схема свёртывания для стратифицируемых формулПравить

В новых основаниях Куайна используется иной подход для борьбы с противоречивостью схемы свёртывания. В отличие от схемы выделения, где ограничения накладываются на элементы, в новых основаниях оганичения накладываются на формулы. Требуется, чтобы формула была стратифицируемой, то есть чтобы было возможно расставить в ней для каждой переменной типы так, чтобы это была корректная формула простой теории типов. Схема свёртывания имеет такой вид:

$\mathrm{\exists <!--\; \exists \; -->}A\mathrm{\forall <!--\; \forall \; -->}x(x\in <!--\; \in \; -->A\leftrightarrow <!--\; \leftrightarrow \; -->\mathrm{\phi <!--\; \phi \; -->})$$\exists A\ \forall x\ (x\in A\leftrightarrow \varphi )$ ,

где $\mathrm{\phi <!--\; \phi \; -->}$$\varphi$  — стратифицируемая формула.

См. такжеПравить

• Наивная теория множеств
• Аксиома объёмности
• Схема выделения

ЛитератураПравить

И. М. Виноградов. Математическая энциклопедия (рус.). — М.: Советская Энциклопедия, 1977. — Т. 1. — Стб. 1152. — 150 000 экз.