Транзитивное множество

Транзитивное множество — множество, включающее все свои неатомарные элементы в качестве подмножеств. Следующие определения множества $A$ как транзитивного эквивалентны:

• если $y\in x$ и $x\in A$, то $y\in A$;
• для любого $x\in A$, являющегося множеством, верно, что $x\subseteq A$;
• $\bigcup A\subseteq A$.
• $A\subseteq {\mathcal {P}}(A)$.

Аналогично определяется понятие транзитивного класса.

Понятие введено Бернайсом и Гёделем при построении теории порядковых чисел. Все ординалы (в стандартном определении фон Неймана) транзитивны, в частности, любое натуральное число (в определении фон Неймана) и множество натуральных чисел — транзитивны. Множество ${\mathcal {P}}(\mathbb {N} )$ — множество всех подмножеств натуральных чисел — также транзитивно. Класс всех ординалов — пример транзитивного собственного класса. Класс всех множеств — ещё один пример транзитивного собственного класса.

Если $A$ транзитивно, то также транзитивны множества $\bigcup A$ и ${\mathcal {P}}(A)$.

Множество $\{\{\},\{\{\}\},\{\{\{\}\}\}\}$ — простейший пример транзитивного множества, не являющегося ординалом.

Транзитивное замыкание

Транзитивное замыкание множества $A$ обозначается $\operatorname {tc} A$ и определяется как

$\operatorname {tc} A=A\cup \left(\bigcup A\right)\cup \left(\bigcup \bigcup A\right)\cup \left(\bigcup \bigcup \bigcup A\right)\cup \ldots$

Множество является транзитивным тогда и только тогда, когда оно совпадает с его транзитивным замыканием.

Транзитивное замыкание множества $A$ является наименьшим по включению транзитивным множеством, содержащим множество $A$. Оно также может быть определено как пересечение всех транзитивных множеств, включающих в себя $A$.

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

Наследственная транзитивность

Множество $A$ называется наследственно транзитивным, если оно транзитивно и все его элементы транзитивны. Это является частным случаем наследственно выполняющегося свойства для множества, если учесть, что транзитивное замыкание транзитивного множества совпадает с самим множеством.

При соблюдении аксиомы регулярности наследственно транзитивные множества есть в точности ординалы в определении фон Неймана. Для любого порядкового числа $\alpha$ существует и единственно транзитивное множество, упорядоченное отношением принадлежности по типу $\alpha$, причём такое множество является наследственно транзитивным. Обратно, наследственно транзитивное множество является вполне упорядоченным по отношению принадлежности (при соблюдении аксиомы регулярности). Отношение принадлежности здесь является строгим порядком.

Транзитивность множества совершенно не означает, что отношение принадлежности на нём транзитивно: есть не транзитивные множества с транзитивным отношением принадлежности (например $\{\{\{\}\}\}$) и транзитивные множества с нетранзитивным отношением принадлежности (например $\{\{\},\{\{\}\},\{\{\{\}\}\}\}$). Для того, чтобы транзитивное множество было наследственно транзитивным, необходимо и достаточно, чтобы отношение принадлежности было транзитивным.

Без аксиомы регулярности нетрудно придумать пример наследственно транзитивного множества, которое линейно упорядочено отношением принадлежности, но ординалом не является. Для этого нужно рассмотреть счётное множество $\{a_{1},a_{2},a_{3},a_{4},\ldots \}$ такое, что $a_{1}=\{a_{2},a_{3},a_{4},\ldots \}$, $a_{2}=\{a_{3},a_{4},\ldots \}$, $a_{3}=\{a_{4},\ldots \}$, …

Литература

• Френкель А., Бар-Хиллел И. Основания теории множеств. — М.: Мир, 1966. — 149 с.
• Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов. — М.: Наука, 1975. — 240 с.