Transitive set

In set theory, a branch of mathematics, a set is called transitive if either of the following equivalent conditions hold:

  • whenever , and , then .
  • whenever , and is not an urelement, then is a subset of .

Similarly, a class is transitive if every element of is a subset of .

ExamplesEdit

Using the definition of ordinal numbers suggested by John von Neumann, ordinal numbers are defined as hereditarily 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 stages   and   leading to the construction of the von Neumann universe   and Gödel's constructible universe   are transitive sets. The universes   and   themselves are transitive classes.

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

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  

PropertiesEdit

A set   is transitive if and only if  , where   is the union of all elements of   that are sets,  .

If   is transitive, then   is transitive. If   and   are transitive, then   is transitive. In general, if   is a class all of whose elements are transitive sets, then   is transitive.

A set   that does not contain urelements is transitive if and only if it is a subset of its own power set,   The power set of a transitive set without urelements is transitive.

Transitive closureEdit

The transitive closure of a set   is the smallest (with respect to inclusion) transitive set that includes  . Suppose one is given a set  , then the transitive closure of   is

 

Proof. Denote   and  . Then we claim that the set

 

is transitive, and whenever   is a transitive set including   then  .

Assume  . Then   for some   and so  . Since  ,  . Thus   is transitive.

Now let   be as above. We prove by induction that   for all  , thus proving that  : The base case holds since  . Now assume  . Then  . But   is transitive so  , hence  . This completes the proof.

Note that this is the set of all of the objects related to   by the transitive closure of the membership relation, since the union of a set can be expressed in terms of the relative product of the membership relation with itself.

Transitive models of set theoryEdit

Transitive classes are often used for construction of interpretations of set theory in itself, usually called inner models. The reason is that properties defined by bounded formulas are absolute for transitive classes.

A transitive set (or class) that is a model of a formal system of set theory is called a transitive 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 to non-standard analysis, the non-standard universes satisfy strong transitivity.[clarification needed][2]

See alsoEdit

ReferencesEdit

  1. ^ "Number of rooted identity trees with n nodes (rooted trees whose automorphism group is the identity group)". OEIS.
  2. ^ Goldblatt (1998) p.161

External linksEdit