推移集合

数学の一分野である集合論 では、次の同等の条件のいずれかが成り立つ場合 、集合は推移的であると呼ばれます。 ${\displaystyle A}$

• 、および の場合はいつでも、。${\displaystyle x\in A}$ ${\displaystyle y\in x}$ ${\displaystyle y\in A}$
• であり、がureelementでない場合は、は のサブセットです。${\displaystyle x\in A}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle A}$

同様に、のすべての要素が のサブセットである場合、クラスは 推移的です。 ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle M}$

例

ジョン・フォン・ノイマンによって提唱された順序数の定義を用いると、順序数は遺伝的に推移的な集合として定義されます。順序数は推移的な集合であり、その要素も推移的（したがって順序数）です。すべての順序数のクラスは推移的なクラスです。

フォン・ノイマン宇宙とゲーデルの構成可能宇宙の構築に至る段階と過程はいずれも推移的集合である。宇宙とそれ自体は推移的類である。 ${\displaystyle V_{\alpha }}$ ${\displaystyle L_{\alpha }}$ ${\displaystyle V}$ ${\displaystyle L}$ ${\displaystyle V}$ ${\displaystyle L}$

これは最大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 \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\{\}\}\}\}\}.}$

プロパティ

集合 が推移的であるとは、が集合であるすべての要素の和集合である場合に限ります。 ${\displaystyle X}$ ${\textstyle \bigcup X\subseteq X}$ ${\textstyle \bigcup X}$ ${\displaystyle X}$ ${\textstyle \bigcup X=\{y\mid \exists x\in X:y\in x\}}$

が推移的であれば、は推移的です。 ${\displaystyle X}$ ${\textstyle \bigcup X}$

とが推移的であれば、と も推移的です。一般に、がすべての要素が推移的集合であるクラスである場合、と も推移的です。（この段落の最初の文は の場合です。） ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X\cup Y}$ ${\displaystyle X\cup Y\cup \{X,Y\}}$ ${\displaystyle Z}$ ${\textstyle \bigcup Z}$ ${\textstyle Z\cup \bigcup Z}$ ${\displaystyle Z=\{X,Y\}}$

固有元を含まない集合は、それが自身のべき集合の部分集合である場合に限り推移的である。固有元を含まない推移的集合のべき集合は推移的である。 ${\displaystyle X}$ ${\textstyle X\subseteq {\mathcal {P}}(X).}$

推移閉包

集合の推移閉包とは、（包含に関して）最小の推移集合（すなわち）である。^[2] 集合 が与えられたとすると、 の推移閉包は ${\displaystyle X}$ ${\displaystyle X}$ ${\textstyle X\subseteq \operatorname {TC} (X)}$ ${\displaystyle X}$ ${\displaystyle 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}}$$

は推移的であり、がを含む推移集合である場合はいつでも となります。 ${\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}}$

セットの和集合は、メンバーシップ関係とそれ自体の 相対積で表現できるため、これはメンバーシップ関係の推移閉包によって関連付けられるすべてのオブジェクトのセットであることに注意してください。${\displaystyle X}$

集合の推移閉包は、第一階の式で表現できます。がの推移閉包である場合、かつは のすべての推移スーパーセットの共通部分です(つまり、 のすべての推移スーパーセットには がサブセットとして 含まれています)。${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle x}$

集合論の推移モデル

推移クラスは、集合論自体の解釈（通常は内部モデルと呼ばれる）の構築によく用いられる。これは、有界式によって定義される性質が推移クラスにとって絶対的であるためである。 ^[3]

集合論の形式体系のモデルである推移的な集合（またはクラス）は、その体系の推移モデルと呼ばれる（ただし、モデルの要素関係が、モデルの宇宙に対する真の要素関係の制約である場合）。推移性は、式の絶対性を決定する重要な要素である。

非標準解析における上部構造アプローチでは、非標準宇宙は強い推移性を満たす。ここで、各集合 に対して、 を満たす推移的な上位集合が存在する場合、クラスは強く推移的であると定義される。強く推移的なクラスは自動的に推移的である。この強化された推移性仮定により、例えばが におけるすべての二項関係の領域を含むと結論付けることができる。^[4]${\displaystyle {\mathcal {C}}}$ ${\displaystyle S\in {\mathcal {C}}}$ ${\displaystyle T}$ ${\displaystyle S\subseteq T\subseteq {\mathcal {C}}}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle {\mathcal {C}}}$

参照

• 延長終了
• 推移関係
• 超推移クラス

参考文献

1. 「n個のノードを持つ根付き恒等木（自己同型群が恒等群である根付き木）の数」、OEIS
2. Ciesielski, Krzysztof (1997), Set theory for the working mathematician , Cambridge: Cambridge University Press, p. 164, ISBN 978-1-139-17313-1、OCLC  817922080
3. Viale, Matteo (2003年11月)、「累積階層とZFAの構築可能な宇宙」、Mathematical Logic Quarterly、50 (1)、Wiley: 99–103、doi :10.1002/malq.200310080
4. ゴールドブラット（1998）p.161

• Ciesielski, Krzysztof (1997), Set theory for the working mathematician , London Mathematical Society Student Texts, vol. 39, Cambridge: Cambridge University Press , ISBN 0-521-59441-3、Zbl  0938.03067
• ゴールドブラット、ロバート（1998）「超実数に関する講義。非標準解析入門」、Graduate Texts in Mathematics、第188巻、ニューヨーク、NY：Springer-Verlag、ISBN 0-387-98464-X、Zbl  0911.03032
• ジェック、トーマス（2008）[初版1973年]、選択の公理、ドーバー出版、ISBN 978-0-486-46624-8、Zbl  0259.02051