Insieme transitivo

In matematica, e in particolare in teoria degli insiemi, un insieme ${\displaystyle A}$ si dice transitivo se vale una delle seguenti condizioni equivalenti:

• se ${\displaystyle x\in A}$ e ${\displaystyle y\in x}$, allora ${\displaystyle y\in A}$ .
• se ${\displaystyle x\in A}$ e ${\displaystyle x}$ non è un Ur-elemento, allora ${\displaystyle x}$ è un sottoinsieme di ${\displaystyle A}$ .

Allo stesso modo, una classe ${\displaystyle M}$ è detta transitiva se ogni elemento di ${\displaystyle M}$ è un sottoinsieme di ${\displaystyle M}$ .

Un insieme è detto numero ordinale se è transitivo e totalmente ordinato dall'appartenenza. La classe di tutti gli ordinali è una classe transitiva.

Uno qualsiasi dei livelli ${\displaystyle V_{\alpha }}$ e ${\displaystyle L_{\alpha }}$ che portano alla costruzione dell'universo di von Neumann ${\displaystyle V}$ e dell'universo costruibile di Gödel ${\displaystyle L}$ sono insiemi transitivi. Gli universi ${\displaystyle V}$ e ${\displaystyle L}$ sono essi stessi classi transitive.

Quello che segue è un elenco completo di tutti gli insiemi transitivi finiti con un massimo di 20 parentesi: ^[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 \{\{\},\{\{\}\},\{\{\{\}\}\},\{\{\{\{\}\}\}\},\{\{\},\{\{\}\}\},\{\{\},\{\{\{\}\}\}\}\}.}$

Un insieme ${\displaystyle X}$ è transitivo se e solo se ${\textstyle \bigcup X\subseteq X}$, dove ${\textstyle \bigcup X}$ è l'unione di tutti gli elementi di ${\displaystyle X}$ che sono insiemi, ${\textstyle \bigcup X=\{y\mid \exists x\in X:y\in x\}}$.

Se ${\displaystyle X}$ è transitivo, anche ${\textstyle \bigcup X}$ è transitivo.

Se ${\displaystyle X}$ e ${\displaystyle Y}$ sono transitivi, ${\displaystyle X\cup Y}$ e ${\displaystyle X\cup Y\cup \{X,Y\}}$ sono transitivi. In generale, se ${\displaystyle Z}$ è una classe i cui elementi sono insiemi transitivi, allora ${\textstyle \bigcup Z}$ e ${\textstyle Z\cup \bigcup Z}$ sono transitivi. (La prima affermazione di questo paragrafo si ottiene nel caso di ${\displaystyle Z=\{X,Y\}}$.)

Un insieme ${\displaystyle X}$ che non contiene Ur-elementi è transitivo se e solo se è un sottoinsieme del proprio insieme potenza, ${\textstyle X\subseteq {\mathcal {P}}(X).}$ L'insieme potenza di un insieme transitivo senza Ur-elementi è transitivo.

La chiusura transitiva ${\displaystyle \operatorname {TC} (X)}$ di un insieme ${\displaystyle X}$ è il più piccolo insieme transitivo che contiene ${\displaystyle X}$ come sottoinsieme, ${\textstyle X\subseteq \operatorname {TC} (X)}$.^[2] Dato l'insieme ${\displaystyle X}$, la sua chiusura transitiva risulta essere

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

Infatti, denotando ${\textstyle X_{0}=X}$ e ${\textstyle X_{n+1}=\bigcup X_{n}}$, vogliamo mostrare che l'insieme

$${\displaystyle T=\bigcup _{n=0}^{\infty }X_{n}}$$

è transitivo e che per ogni ${\textstyle T_{1}}$ insieme transitivo che contiene ${\textstyle X}$ come sottoinsieme, si abbia ${\textstyle T\subseteq T_{1}}$.

Mostriamo che ${\displaystyle T}$ è transitivo. Siano ${\textstyle y\in x\in T}$. Ma allora esiste ${\textstyle n}$ tale che ${\textstyle x\in X_{n}}$ e pertanto ${\textstyle y\in \bigcup X_{n}=X_{n+1}}$. Poiché ${\textstyle X_{n+1}\subseteq T}$, si ha ${\textstyle y\in T}$ e ${\textstyle T}$ è transitivo.

Sia ora ${\textstyle T_{1}}$ come sopra. Mostriamo per induzione che ${\textstyle X_{n}\subseteq T_{1}}$ per ogni ${\displaystyle n}$ e dunque che ${\textstyle T\subseteq T_{1}}$. Il caso base vale essendo per ipotesi ${\textstyle X_{0}=X\subseteq T_{1}}$. Ora supponiamo ${\textstyle X_{n}\subseteq T_{1}}$. Allora ${\textstyle X_{n+1}=\bigcup X_{n}\subseteq \bigcup T_{1}}$. Ma ${\textstyle T_{1}}$ è transitivo, quindi ${\textstyle \bigcup T_{1}\subseteq T_{1}}$ e dunque ${\textstyle X_{n+1}\subseteq T_{1}}$ . Questo completa la dimostrazione.

Questa sezione sull'argomento matematica è ancora vuota. Aiutaci a scriverla!

• Relazione transitiva