Переходный набор

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

• всякий раз , когда х ∈ , и у ∈ х , то у ∈ .
• всякий раз , когда х ∈ , а х не является урэлемент , то х является подмножеством из A .

Аналогичным образом , класс М является переходным , если каждый элемент М представляет собой подмножество М .

Примеры [ править ]

Используя определение порядковых чисел, предложенное Джоном фон Нейманом , порядковые числа определяются как наследственно транзитивные множества: порядковое число - это транзитивное множество, члены которого также транзитивны (и, следовательно, ординалы). Класс всех ординалов - это транзитивный класс.

Любой из этапов V _α и L _α, ведущих к построению универсума фон Неймана V и конструктивного универсума Гёделя L, являются транзитивными множествами. Сами вселенные L и V являются транзитивными классами.

Это полный список всех конечных транзитивных множеств, содержащий до 20 скобок: ^[1]

• ${\displaystyle \{\},}$
• ${\displaystyle \{\{\}\},}$
• ${\displaystyle \{\{\},\{\{\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\}\},\{\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\},\{\{\}\}\}\},\{\{\},\{\{\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\}\},\{\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\},\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\},\{\{\}\}\},\{\{\{\}\},\{\{\},\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\},\{\{\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\{\{\{\}\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\},\{\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\},\{\{\}\}\}\},\{\{\},\{\{\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\},\{\{\{\{\}\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\{\}\},\{\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\},\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\}\}\},\{\{\{\}\},\{\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\{\}\},\{\{\{\{\}\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\},\{\{\}\},\{\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\},\{\{\{\}\}\}\}\},\{\{\},\{\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\}\}\},\{\{\{\}\},\{\{\},\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\}\},\{\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\{\}\}\}\},\{\{\{\}\},\{\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\{\{\}\}\},\{\{\{\{\}\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\},\{\{\}\},\{\{\{\{\}\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\}\}\},\{\{\{\{\}\}\},\{\{\},\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\}\},\{\{\},\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\{\}\}\}\},\{\{\},\{\{\},\{\{\{\}\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\{\}\}\}\},\{\{\},\{\{\}\},\{\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\{\},\{\{\}\}\}\}\},\{\{\{\},\{\{\}\}\}\},\{\{\},\{\{\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\},\{\{\}\}\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\},\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\},\{\{\{\}\}\},\{\{\{\{\}\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\},\{\{\{\}\}\}\}\},\{\{\{\}\},\{\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\{\}\}\},\{\{\},\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\},\{\{\{\}\}\}\},\{\{\{\}\},\{\{\},\{\{\{\}\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\}\},\{\{\{\}\}\}\},\{\{\},\{\{\}\},\{\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\},\{\{\}\}\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\{\},\{\{\}\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\},\{\{\}\}\}\},\{\{\},\{\{\}\}\},\{\{\{\}\},\{\{\},\{\{\}\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\{\{\{\}\}\}\}\},\{\{\},\{\{\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\{\},\{\{\}\}\}\},\{\{\},\{\{\}\}\}\},}$
• ${\displaystyle \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\{\}\}\}\}\}.}$

Свойства [ править ]

Множество X транзитивно тогда и только тогда , когда это объединение всех элементов X , которые являются множеством, . ${\textstyle \bigcup X\subseteq X}$${\textstyle \bigcup X}$${\textstyle \bigcup X=\{y\mid \exists x\in X:y\in x\}}$

Если X транзитивен, то транзитивен. Если X и Y транзитивны, то X ∪ Y ∪ { X , Y } транзитивно. В общем, если X - класс, все элементы которого являются транзитивными множествами, то он транзитивен.${\textstyle \bigcup X}$${\textstyle X\cup \bigcup X}$

Множество X , который не содержит праэлементы транзитивно тогда и только тогда , когда оно является подмножеством своего собственного набора мощности , установленной мощности транзитивного множества без праэлементов транзитивно.${\textstyle X\subseteq {\mathcal {P}}(X).}$

Переходное закрытие [ править ]

Транзитивное замыкание некоторого множества X является наименьшим (по включению) переходной набор , который содержит X . Предположим, что дано множество X , тогда транзитивное замыкание X есть

${\displaystyle \operatorname {TC} (X)=\bigcup \left\{X,\;\bigcup X,\;\bigcup \bigcup X,\;\bigcup \bigcup \bigcup X,\;\bigcup \bigcup \bigcup \bigcup X,\ldots \right\}.}$

Доказательство. Обозначим и . Затем мы утверждаем, что множество ${\textstyle X_{0}=X}$${\textstyle X_{n+1}=\bigcup X_{n}}$

${\displaystyle T=\operatorname {TC} (X)=\bigcup _{n=0}^{\infty }X_{n}}$

транзитивно, и всякий раз, когда является транзитивным множеством, содержащим then .${\textstyle T_{1}}$${\textstyle X}$${\textstyle T\subseteq T_{1}}$

Допустим . Потом для некоторых и так . Так , . Таким образом , переходный.${\textstyle y\in x\in T}$${\textstyle x\in X_{n}}$${\textstyle n}$${\textstyle y\in \bigcup X_{n}=X_{n+1}}$${\textstyle X_{n+1}\subseteq T}$${\textstyle y\in T}$${\textstyle T}$

Теперь пусть будет так, как указано выше. Мы доказываем по индукции, что для всех , тем самым доказывая, что : Базовый случай имеет место, поскольку . Теперь предположим . Тогда . Но переходно так откуда . Это завершает доказательство.${\textstyle T_{1}}$${\textstyle X_{n}\subseteq T_{1}}$${\displaystyle n}$${\textstyle T\subseteq T_{1}}$${\textstyle X_{0}=X\subseteq T_{1}}$${\textstyle X_{n}\subseteq T_{1}}$${\textstyle X_{n+1}=\bigcup X_{n}\subseteq \bigcup T_{1}}$${\textstyle T_{1}}$${\textstyle \bigcup T_{1}\subseteq T_{1}}$${\textstyle X_{n+1}\subseteq T_{1}}$

Обратите внимание , что это совокупность всех объектов , связанных с X по транзитивного замыкания Членскому отношения, так как объединение множества может быть выражено в терминах относительного продукта от членства отношения с самим собой.

Переходные модели теории множеств [ править ]

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

Транзитивное множество (или класс), которое является моделью формальной системы теории множеств, называется транзитивной моделью системы (при условии, что отношение элементов модели является ограничением истинного отношения элементов к универсуму модели). . Транзитивность - важный фактор в определении абсолютности формул.

В подходе надстройки к нестандартному анализу нестандартные вселенные удовлетворяют сильной транзитивности. ^{[ требуется разъяснение ] [2]}

См. Также [ править ]

• Конец расширения
• Переходное отношение
• Сверхтранзитивный класс

Ссылки [ править ]

• Ciesielski, Krzysztof (1997), теория множеств для работающего математика , London Mathematical Society Student Texts, 39 , Cambridge: Cambridge University Press , ISBN 0-521-59441-3, Zbl  0938,03067
• Голдблатт, Роберт (1998), Лекции по гиперреалам. Введение в нестандартный анализ , Graduate Texts in Mathematics , 188 , New York, NY: Springer-Verlag , ISBN 0-387-98464-X, Zbl  0911,03032
• Jech, Thomas (2008) [первоначально опубликовано в 1973 году], Axiom of Choice , Dover Publications , ISBN 0-486-46624-8, Zbl  0259,02051

Внешние ссылки [ править ]

• Вайсштейн, Эрик В. «Переходный» . MathWorld .
• Вайсштейн, Эрик В. «Переходное замыкание» . MathWorld .
• Вайсштейн, Эрик В. «Переходная редукция» . MathWorld .