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

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

$\exists A\ \forall x\ (x\in A\leftrightarrow \varphi )$,

где $\varphi$ — любая формула языка логики предикатов с равенством и двуместным предикатным символом $\in$, в которую не входит свободно переменная $A$. Таким образом, схема представляет собой набор аксиом по одной для каждой конкретной формулы $\varphi$.

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

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

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

Например, для формулы:

$\varphi :\leftrightarrow \lnot (x\in x)$

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

$\forall x\ x\in A\leftrightarrow \lnot (x\in x)$;

если взять $x$ равный $A$, то:

$A\in A\leftrightarrow \lnot (A\in A)$ — противоречие.

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

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

Схема выделения

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

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

$\forall B\ \exists A\ \forall x\ (x\in A\leftrightarrow x\in B\land \varphi )$

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

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

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

$\exists A\ \forall x\ (x\in A\leftrightarrow \varphi )$.

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

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

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

$\exists A_{n+1}\ \forall x_{n}\ (x_{n}\in A_{n+1}\leftrightarrow \varphi )$,

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

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

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

$\exists A\ \forall x\ (x\in A\leftrightarrow \varphi )$,

где $\varphi$ — стратифицируемая формула.

Литература

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