Transitive set

Last updated

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

Contents

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

Examples

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]

Properties

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 and are transitive. In general, if is a class all of whose elements are transitive sets, then and are transitive. (The first sentence in this paragraph is the case of .)

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 closure

The transitive closure of a set is the smallest (with respect to inclusion) transitive set that includes (i.e. ). [2] 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.

The transitive closure of a set can be expressed by a first-order formula: is a transitive closure of iff is an intersection of all transitive supersets of (that is, every transitive superset of contains as a subset).

Transitive models of set theory

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. [3]

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. Here, a class is defined to be strongly transitive if, for each set , there exists a transitive superset with . A strongly transitive class is automatically transitive. This strengthened transitivity assumption allows one to conclude, for instance, that contains the domain of every binary relation in . [4]

See also

Related Research Articles

<span class="mw-page-title-main">Subset</span> Set whose elements all belong to another set

In mathematics, a set A is a subset of a set B if all elements of A are also elements of B; B is then a superset of A. It is possible for A and B to be equal; if they are unequal, then A is a proper subset of B. The relationship of one set being a subset of another is called inclusion. A is a subset of B may also be expressed as B includes A or A is included in B. A k-subset is a subset with k elements.

In topology, the closure of a subset S of points in a topological space consists of all points in S together with all limit points of S. The closure of S may equivalently be defined as the union of S and its boundary, and also as the intersection of all closed sets containing S. Intuitively, the closure can be thought of as all the points that are either in S or "very near" S. A point which is in the closure of S is a point of closure of S. The notion of closure is in many ways dual to the notion of interior.

In mathematics, a topological vector space is one of the basic structures investigated in functional analysis. A topological vector space is a vector space that is also a topological space with the property that the vector space operations are also continuous functions. Such a topology is called a vector topology and every topological vector space has a uniform topological structure, allowing a notion of uniform convergence and completeness. Some authors also require that the space is a Hausdorff space. One of the most widely studied categories of TVSs are locally convex topological vector spaces. This article focuses on TVSs that are not necessarily locally convex. Other well-known examples of TVSs include Banach spaces, Hilbert spaces and Sobolev spaces.

In the mathematical discipline of set theory, forcing is a technique for proving consistency and independence results. Intuitively, forcing can be thought of as a technique to expand the set theoretical universe to a larger universe by introducing a new "generic" object .

<span class="mw-page-title-main">Symmetric difference</span> Elements in exactly one of two sets

In mathematics, the symmetric difference of two sets, also known as the disjunctive union and set sum, is the set of elements which are in either of the sets, but not in their intersection. For example, the symmetric difference of the sets and is .

In topology and related branches of mathematics, the Kuratowski closure axioms are a set of axioms that can be used to define a topological structure on a set. They are equivalent to the more commonly used open set definition. They were first formalized by Kazimierz Kuratowski, and the idea was further studied by mathematicians such as Wacław Sierpiński and António Monteiro, among others.

In mathematics, in set theory, the constructible universe, denoted by , is a particular class of sets that can be described entirely in terms of simpler sets. is the union of the constructible hierarchy. It was introduced by Kurt Gödel in his 1938 paper "The Consistency of the Axiom of Choice and of the Generalized Continuum-Hypothesis". In this paper, he proved that the constructible universe is an inner model of ZF set theory, and also that the axiom of choice and the generalized continuum hypothesis are true in the constructible universe. This shows that both propositions are consistent with the basic axioms of set theory, if ZF itself is consistent. Since many other theorems only hold in systems in which one or both of the propositions is true, their consistency is an important result.

In set theory and related branches of mathematics, the von Neumann universe, or von Neumann hierarchy of sets, denoted by V, is the class of hereditary well-founded sets. This collection, which is formalized by Zermelo–Fraenkel set theory (ZFC), is often used to provide an interpretation or motivation of the axioms of ZFC. The concept is named after John von Neumann, although it was first published by Ernst Zermelo in 1930.

In mathematics, a subset of a preordered set is said to be cofinal or frequent in if for every it is possible to find an element in that is "larger than ".

In functional analysis and related areas of mathematics, a set in a topological vector space is called bounded or von Neumann bounded, if every neighborhood of the zero vector can be inflated to include the set. A set that is not bounded is called unbounded.

In set theory, a prewellordering on a set is a preorder on that is strongly connected and well-founded in the sense that the induced relation defined by is a well-founded relation.

A Dynkin system, named after Eugene Dynkin, is a collection of subsets of another universal set satisfying a set of axioms weaker than those of 𝜎-algebra. Dynkin systems are sometimes referred to as 𝜆-systems or d-system. These set families have applications in measure theory and probability.

In topology and related fields of mathematics, a sequential space is a topological space whose topology can be completely characterized by its convergent/divergent sequences. They can be thought of as spaces that satisfy a very weak axiom of countability, and all first-countable spaces are sequential.

In mathematics, a filter on a set is a family of subsets such that:

  1. and
  2. if and , then
  3. If and , then

In mathematics, a cardinal function is a function that returns cardinal numbers.

In order theory, the Szpilrajn extension theorem, proved by Edward Szpilrajn in 1930, states that every partial order is contained in a total order. Intuitively, the theorem says that any method of comparing elements that leaves some pairs incomparable can be extended in such a way that every pair becomes comparable. The theorem is one of many examples of the use of the axiom of choice in the form of Zorn's lemma to find a maximal set with certain properties.

In mathematics, especially measure theory, a set function is a function whose domain is a family of subsets of some given set and that (usually) takes its values in the extended real number line which consists of the real numbers and

In universal algebra and lattice theory, a tolerance relation on an algebraic structure is a reflexive symmetric relation that is compatible with all operations of the structure. Thus a tolerance is like a congruence, except that the assumption of transitivity is dropped. On a set, an algebraic structure with empty family of operations, tolerance relations are simply reflexive symmetric relations. A set that possesses a tolerance relation can be described as a tolerance space. Tolerance relations provide a convenient general tool for studying indiscernibility/indistinguishability phenomena. The importance of those for mathematics had been first recognized by Poincaré.

<span class="mw-page-title-main">Filters in topology</span> Use of filters to describe and characterize all basic topological notions and results.

Filters in topology, a subfield of mathematics, can be used to study topological spaces and define all basic topological notions such as convergence, continuity, compactness, and more. Filters, which are special families of subsets of some given set, also provide a common framework for defining various types of limits of functions such as limits from the left/right, to infinity, to a point or a set, and many others. Special types of filters called ultrafilters have many useful technical properties and they may often be used in place of arbitrary filters.

References

  1. "Number of rooted identity trees with n nodes (rooted trees whose automorphism group is the identity group).", 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