Схема свёртывания - NiNa.Az

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

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

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

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

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

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

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

${\displaystyle \varphi :\leftrightarrow \lnot (x\in x)}$

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

${\displaystyle \forall x\ x\in A\leftrightarrow \lnot (x\in x)}$;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

1. Виноградов, 1977, стб. 105.
2. Виноградов, 1977, стб. 106.
3. Виноградов, 1977, стб. 107.

Литература

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