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

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (15)

Related courses (1)

Related lectures (11)

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a

Grothendieck universe

In mathematics, a Grothendieck universe is a set U with the following properties: If x is an element of U and if y is an element of x, then y is also an element of U. (U is a transitive set.) If x and y are both elements of U, then is an element of U. If x is an element of U, then P(x), the power set of x, is also an element of U. If is a family of elements of U, and if I is an element of U, then the union is an element of U. A Grothendieck universe is meant to provide a set in which all of mathematics can be performed.

Inner model

In set theory, a branch of mathematical logic, an inner model for a theory T is a substructure of a model M of a set theory that is both a model for T and contains all the ordinals of M. Let be the language of set theory. Let S be a particular set theory, for example the ZFC axioms and let T (possibly the same as S) also be a theory in . If M is a model for S, and N is an -structure such that N is a substructure of M, i.e. the interpretation of in N is N is a model for T the domain of N is a transitive class of M N contains all ordinals of M then we say that N is an inner model of T (in M).

Von Neumann universe

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. The rank of a well-founded set is defined inductively as the smallest ordinal number greater than the ranks of all members of the set.

Logic and Algorithms CS-101: Advanced information, computation, communication I

Covers logic, mathematical reasoning, basic structures, and algorithms, exploring proofs, sets, functions, and recursion.

Relations in Computer Science CS-101: Advanced information, computation, communication I

Explores the properties of relations in computer science, including equivalence relations and the partition of a set.

Equidistribution of CM Points

Explores the joint equidistribution of CM points for cubic fields, emphasizing periodic orbits and quadratic algebraic forms.