Movatterモバイル変換

[0]ホーム
URL:

Jump to content
WikipediaThe Free Encyclopedia
Search

Transitive set

From Wikipedia, the free encyclopedia
Class of mathematical set whose elements are all subsets

Inset theory, a branch ofmathematics, asetA{\displaystyle A} is calledtransitive if either of the following equivalent conditions holds:

Similarly, aclassM{\displaystyle M} is transitive if every element ofM{\displaystyle M} is a subset ofM{\displaystyle M}.

Examples

[edit]

Using the definition ofordinal numbers suggested byJohn von Neumann, ordinal numbers are defined ashereditarily transitive sets: an ordinal number is a transitive set whose members are also transitive (and thus ordinals). The class of all ordinals is a transitive class.

Any of the stagesVα{\displaystyle V_{\alpha }} andLα{\displaystyle L_{\alpha }} leading to the construction of thevon Neumann universeV{\displaystyle V} andGödel's constructible universeL{\displaystyle L} are transitive sets. TheuniversesV{\displaystyle V} andL{\displaystyle L} themselves are transitive classes.

This is a complete list of all finite transitive sets with up to 20 pairs of brackets:[1]

Properties

[edit]

A setX{\displaystyle X} is transitive if and only if⋃X⊆X{\textstyle \bigcup X\subseteq X}, where⋃X{\textstyle \bigcup X} is theunion of all elements ofX{\displaystyle X} that are sets,⋃X={y∣∃x∈X:y∈x}{\textstyle \bigcup X=\{y\mid \exists x\in X:y\in x\}}.

IfX{\displaystyle X} is transitive, then⋃X{\textstyle \bigcup X} is transitive.

IfX{\displaystyle X} andY{\displaystyle Y} are transitive, thenX∪Y{\displaystyle X\cup Y} andX∪Y∪{X,Y}{\displaystyle X\cup Y\cup \{X,Y\}} are transitive. In general, ifZ{\displaystyle Z} is a class all of whose elements are transitive sets, then⋃Z{\textstyle \bigcup Z} andZ∪⋃Z{\textstyle Z\cup \bigcup Z} are transitive. (The first sentence in this paragraph is the case ofZ={X,Y}{\displaystyle Z=\{X,Y\}}.)

A setX{\displaystyle X} that does not contain urelements is transitive if and only if it is a subset of its ownpower set,X⊆P(X).{\textstyle X\subseteq {\mathcal {P}}(X).} The power set of a transitive set without urelements is transitive.

Transitive closure

[edit]

Thetransitive closure of a setX{\displaystyle X} is the smallest (with respect to inclusion) transitive set that includesX{\displaystyle X} (i.e.X⊆TC⁡(X){\textstyle X\subseteq \operatorname {TC} (X)}).[2] Suppose one is given a setX{\displaystyle X}, then the transitive closure ofX{\displaystyle X} is

TC⁡(X)=⋃{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\}.}

Proof. DenoteX0=X{\textstyle X_{0}=X} andXn+1=⋃Xn{\textstyle X_{n+1}=\bigcup X_{n}}. Then we claim that the set

T=TC⁡(X)=⋃n=0∞Xn{\displaystyle T=\operatorname {TC} (X)=\bigcup _{n=0}^{\infty }X_{n}}

is transitive, and wheneverT1{\textstyle T_{1}} is a transitive set includingX{\textstyle X} thenT⊆T1{\textstyle T\subseteq T_{1}}.

Assumey∈x∈T{\textstyle y\in x\in T}. Thenx∈Xn{\textstyle x\in X_{n}} for somen{\textstyle n} and soy∈⋃Xn=Xn+1{\textstyle y\in \bigcup X_{n}=X_{n+1}}. SinceXn+1⊆T{\textstyle X_{n+1}\subseteq T},y∈T{\textstyle y\in T}. ThusT{\textstyle T} is transitive.

Now letT1{\textstyle T_{1}} be as above. We prove by induction thatXn⊆T1{\textstyle X_{n}\subseteq T_{1}} for alln{\displaystyle n}, thus proving thatT⊆T1{\textstyle T\subseteq T_{1}}: The base case holds sinceX0=X⊆T1{\textstyle X_{0}=X\subseteq T_{1}}. Now assumeXn⊆T1{\textstyle X_{n}\subseteq T_{1}}. ThenXn+1=⋃Xn⊆⋃T1{\textstyle X_{n+1}=\bigcup X_{n}\subseteq \bigcup T_{1}}. ButT1{\textstyle T_{1}} is transitive so⋃T1⊆T1{\textstyle \bigcup T_{1}\subseteq T_{1}}, henceXn+1⊆T1{\textstyle X_{n+1}\subseteq T_{1}}. This completes the proof.

Note that this is the set of all of the objects related toX{\displaystyle X} by thetransitive closure of the membership relation, since the union of a set can be expressed in terms of therelative product of the membership relation with itself.

The transitive closure of a set can be expressed by a first-order formula:x{\displaystyle x} is a transitive closure ofy{\displaystyle y}iffx{\displaystyle x} is an intersection of all transitivesupersets ofy{\displaystyle y} (that is, every transitive superset ofy{\displaystyle y} containsx{\displaystyle x} as a subset).

Transitive models of set theory

[edit]

Transitive classes are often used for construction ofinterpretations of set theory in itself, usually calledinner models. The reason is that properties defined bybounded formulas areabsolute for transitive classes.[3]

A transitive set (or class) that is a model of aformal system of set theory is called atransitive model of the system (provided that the element relation of the model is the restriction of the true element relation to the universe of the model). Transitivity is an important factor in determining the absoluteness of formulas.

In the superstructure approach tonon-standard analysis, the non-standard universes satisfystrong transitivity. Here, a classC{\displaystyle {\mathcal {C}}} is defined to be strongly transitive if, for each setS∈C{\displaystyle S\in {\mathcal {C}}}, there exists a transitive supersetT{\displaystyle T} withS⊆T⊆C{\displaystyle S\subseteq T\subseteq {\mathcal {C}}}. A strongly transitive class is automatically transitive. This strengthened transitivity assumption allows one to conclude, for instance, thatC{\displaystyle {\mathcal {C}}} contains the domain of everybinary relation inC{\displaystyle {\mathcal {C}}}.[4]

See also

[edit]

References

[edit]
  1. ^"Number of transitive finitary sets with n brackets. Number of transitive rooted identity trees with n nodes.",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 (November 2003), "The cumulative hierarchy and the constructible universe of ZFA",Mathematical Logic Quarterly,50 (1), Wiley:99–103,doi:10.1002/malq.200310080
  4. ^Goldblatt (1998) p.161
Overview
Venn diagram of set intersection
Axioms
Operations
  • Concepts
  • Methods
Set types
Theories
Set theorists
General
Theorems (list)
 and paradoxes
Logics
Traditional
Propositional
Predicate
Set theory
Types ofsets
Maps and cardinality
Set theories
Formal systems (list),
language and syntax
Example axiomatic
systems (list)
Proof theory
Model theory
Computability theory
Related
Retrieved from "https://en.wikipedia.org/w/index.php?title=Transitive_set&oldid=1324132604"
Category:
Hidden categories:
[8]ページ先頭
©2009-2025 Movatter.jp