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

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

• если $y\in <!--\; \in \; -->x$$y\in x$ и $x\in <!--\; \in \; -->A$$x\in A$, то $x\in <!--\; \in \; -->A$$x\in A$;
• для любого $x\in <!--\; \in \; -->A$$x\in A$ верно $x\subseteq <!--\; \subseteq \; -->A$$x\subseteq A$;
• $\bigcup <!--\; \bigcup \; -->A\subseteq <!--\; \subseteq \; -->A$$\bigcup A\subseteq A$.

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

Понятие транзитивного множества было введено в математику П. Бернайсом и К. Гёделем при построении теории порядковых чисел.

ПримерыПравить

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

СвойстваПравить

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

Множество $A$$A$  транзитивно тогда и только тогда, когда $A\subseteq <!--\; \subseteq \; -->\mathcal{P}(A)$$A\subseteq {\mathcal {P}}(A)$ .

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

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

$\mathrm{tc}<!--\; \; -->A=A\cup <!--\; \cup \; -->\left(\bigcup <!--\; \bigcup \; -->A\right)\cup <!--\; \cup \; -->\left(\bigcup <!--\; \bigcup \; -->\bigcup <!--\; \bigcup \; -->A\right)\cup <!--\; \cup \; -->\left(\bigcup <!--\; \bigcup \; -->\bigcup <!--\; \bigcup \; -->\bigcup <!--\; \bigcup \; -->A\right)\cup <!--\; \cup \; -->\dots <!--\; \dots \; -->$$\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$ . Оно также может быть определено как пересечение всех транзитивных множеств, включающих в себя $A$$A$ .

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

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

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

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

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

Без аксиомы регулярности нетрудно придумать пример множества, которое линейно упорядочено отношением принадлежности, но ординалом не является. Для этого нужно рассмотреть счётное множество $\{a_1,a_2,a_3,\dots <!--\; \dots \; -->\}$$\{a_{1},a_{2},a_{3},\ldots \}$  такое, что $a_1=\{a_2\}$$a_{1}=\{a_{2}\}$ , $a_2=\{a_3\}$$a_{2}=\{a_{3}\}$ , $a_3=\{a_4\}$$a_{3}=\{a_{4}\}$ , ...

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

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