Talk:Transitive set

This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Mathematics Low‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics Low This article has been rated as Low-priority on the project's priority scale.

A set A in not transitive iff ∈ is transitive on A. Example 1: A={0,{0},{{0}}} is a transitive set, but ∈ is not transitive on A. Example 2: ∈ is transitive on A={{0}}, but A is not a transitive set. -- EJ 13:18, 17 August 2005 (UTC)Reply

My mistake. I was trying to find justification for using the same word -- possibly historical justification. -- Arthur Rubin 14:06, 17 August 2005 (UTC)Reply

Well, the conditions look similar, at least if you strip all quantifiers and not bother much what letter denotes what. I am not sure if there is a more coherent justification of the name. -- EJ 14:24, 17 August 2005 (UTC)Reply

Explaining my revert: A urelement cannot be a subset of anything because it is not a set. -- Arthur Rubin 19:17, 24 September 2005 (UTC)Reply

Could this be a good place to elaborate on transitive closure rather than creating a separate article for it and have to repeat most of the context? If so a redirect will be needed to this page from Transitive closure. Vonkje 16:15, 8 September 2006 (UTC)Reply

You are welcome to elaborate on transitive closure here, especially because the current article is just a short stub. However, a redirect would be problematic, as transitive closure already exists, and describes a different but presumably more common usage of the term. -- EJ 17:05, 8 September 2006 (UTC)Reply

I added a disambiguation link from transitive closure to this article back in April 2006. JRSpriggs 07:05, 9 September 2006 (UTC)Reply

It would be quite interesting were transitive closure a universal object or other category construction. Does anyone know?Rich 01:34, 9 September 2006 (UTC)Reply

I doubt it is possible. Transitive sets and transitive closures are hopelessly non-invariant under isomorphism in any category I can think of. -- EJ 23:43, 9 September 2006 (UTC)Reply

Could some examples of transitive sets other than ordinals be added to the article? Thanks. 70.90.174.101 (talk) 04:00, 15 September 2009 (UTC)Reply

I couldn't find the definition in the article or a reference to its definition. franklin.vp  22:10, 23 November 2009 (UTC)Reply

See Union (set theory)#Infinite unions. To be specific,

${\displaystyle \bigcup X=\{y|(\exists x\in X)y\in x\}.}$

— Arthur Rubin (talk) 23:12, 23 November 2009 (UTC)Reply

Thanks. It is what I would denote as ${\displaystyle \bigcup _{x\in X}x}$. I added the definition to the article.  franklin.vp  12:01, 24 November 2009 (UTC)Reply

Only in set theory is an unadorned ${\displaystyle \bigcup }$ used; in other mathematical fields, such as universal algebra or lattice theory, the notation you indicate is used.

However, with the modifications made, it's more clear that there is a difference between the set and class definitions in the presence of urelements; transitive sets are allowed to have urelements, while transitive classes are not. Perhaps we should properly unify the definitions, or note that either definition may apply in some cases. — Arthur Rubin (talk) 19:24, 24 November 2009 (UTC)Reply

"In the superstructure approach to non-standard analysis, the non-standard universes satisfy strong transitivity, see (Goldblatt, 1998, p.161)."

To Tkuvho (talk · contribs): What does this mean? Even I have no idea what you are talking about. What is the "superstructure approach"? What is "strong transitivity"? You need to either define your terms or remove this sentence. And why is the sentence relevant to this article? JRSpriggs (talk) 02:00, 18 January 2011 (UTC)Reply

The universe of internal sets is strongly transitive. I will get back to this. Tkuvho (talk) 06:23, 18 January 2011 (UTC)Reply

According to this article, von Neumann defined an ordinal to be a hereditarily transitive set. According to Ordinal he defined each ordinal to be the set of all smaller ordinals. Which article is correct, and what did von Neumann have to say about the relationship between these two definitions? (This is a history question, not a mathematics question.)

Also, shouldn't "also transitive (and thus ordinals)" be "also hereditarily transitive (and thus ordinals)"? Inheritance itself should be transitive. --Vaughan Pratt (talk) 04:00, 27 March 2011 (UTC)Reply

You are referring to the first sentence in the section Transitive set#Examples which reads

"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)."

It is easy to show that the two definitions of "ordinal" are equivalent. So I would not be concerned about which precise wording he used. (I would guess that he used both.)

If all the elements of a transitive set are themselves transitive, then they must be hereditarily transitive (and thus ordinals). Suppose T is the given transitive set all of whose elements are transitive. Suppose s∈T, then s⊂T and thus every element of s is also transitive. Then it can be shown that T and all its elements (and their elements, etc.) are hereditarily transitive. We can argue by reductio ad absurdum — suppose to the contrary that some element of T is not hereditarily transitive. Using the axiom of separation, we form the (nonempty) subset of T consisting of such non-hereditarily transitive elements, call it N. Applying the axiom of regularity to N we get a set x∈N which is disjoint from N. Consider any y∈x, y∈T but y∉N. So y is hereditarily transitive. Since x is a transitive set of hereditarily transitive sets, then x is also hereditarily transitive. This contradicts the fact that x∈N, so we can conclude that all elements of T must be hereditarily transitive and thus T itself is hereditarily transitive. JRSpriggs (talk) 11:49, 27 March 2011 (UTC)Reply

Thank you but that's the answer to a mathematics question. I'd be very interested to know the answer to my history question.

By way of background, back in June 2008 I largely rewrote the lead of Ordinal. But then six months later, at Talk:Ordinal_number#Replace_order_type_by_order_isomorphic.3F, I proposed another rewrite of the lead, with the first three sentences reading "In mathematics, an ordinal number, or just ordinal, is a transitive set of ordinals, or hereditarily transitive set. That is, every element of an ordinal is transitive and its elements in turn are transitive and so on down. The Axiom of regularity stops this recursion after finitely many steps, namely at the empty set." (Your argument above in a nutshell.) At that point Trovatore stepped in and objected that von Neumann's definition was only an encoding of the ordinals and not the ordinals themselves, which should be left as an intuitive notion. Trying to understand this, I questioned Trovatore about what struck me as a mystical position for a while until Christmas rolled around, at which point I decided I had better things to spend my time on than debate mysticism with Trovatore. (On Valentine's day I came up with an abstract definition of the ordinals less than any given regular cardinal κ by way making Trovatore's mysticism more mathematical, but by then I'd lost interest in trying to defend my proposed revision of Ordinal and quit working on the article.)

Two years later Ordinal still talks about hereditarily transitive sets and von Neumann's definition as though they had nothing to do with each other. Someone else will need to fix this as I decline to edit anything that requires first clearing it with Trovatore, there are more productive ways of spending time on Wikipedia. --Vaughan Pratt (talk) 20:48, 27 March 2011 (UTC)Reply

I cannot help you with the history — it would probably be easier for you to look it up than for me to do so.

As far as what Trovatore meant: One could define ordinals axiomatically (without using deep set theory), similarly to the way one defines various topologies or algebras. Then the von Neumann "definition" would just be a way of encoding (representing) ordinals within pure set theory. Indeed, since pure set theory (ZFC) is intended to implement the Von Neumann universe, it could be argued that ordinals should be defined before set theory. I think that that is what Trovatore was getting at. JRSpriggs (talk) 08:27, 28 March 2011 (UTC)Reply

Right - an ordinal number is fundamentally an equivalence class of well-orderings under order isomorphism, just like a cardinal number is an equivalence class of sets under set isomorphisms (bijections). This is often lost in ZFC treatments, where ordinals are defined as representatives for these equivalence classes and the equivalence classes themselves are de-emphasized.

It seems to me this is mentioned in the "ordinal" article, for example in the section "other definitions" and the two sections above it. — Carl (CBM · talk) 10:40, 28 March 2011 (UTC)Reply

Meanwhile I got back from PG and was able to check out the English translation of von Neumann's 1923 article and could find no mention of either inheritance or transitivity, as I had been expecting (which was why I raised the question here rather than at Talk:Ordinal). So I would say this article is misleading in suggesting that von Neumann used the concept of a transitive set. Martin Davis suggested to me that something after Goedel's 1938 paper on consistency of CH might be a more appropriate historic reference.

Regarding Trovatore's position, he argued at Talk:Ordinal, "So what I'm saying is, we should treat ordinals more or less as Cantor did." That's a fine argument, some Supreme Court justices use something like it in arguing that we should interpret the Constitution the way the founding fathers intended it. My understanding of the more modern view is that foundationally speaking sets precede ordinals and that an ordinal is a hereditarily transitive set rather than an isomorphism class. On the other hand category theorists seem to have no qualms about defining objects only up to isomorphism, so if Wikipedia wanted a modern justification for the order-type definition of ordinal it could side with the category theorists. Having satisfied myself that I could argue equally for either side I'm guess I'm happy at this point to drop out of that debate. --Vaughan Pratt (talk) 21:07, 29 March 2011 (UTC)Reply

You might like to read a section from the archives of our article on ordinals where I prove the equivalence of some definitions of ordinals. See Talk:Ordinal number/Archive 2#Proof and the discussion above it. JRSpriggs (talk) 18:44, 30 March 2011 (UTC)Reply

Currently the first statement reads as follows:

In set theory, a set A is transitive, if

   whenever x ∈ A, and y ∈ x, then y ∈ A

Would it not seem more natural to the notion of 'transitive relation < on a set' to write

   whenever y ∈ x, and x ∈ A, then y ∈ A

when defining 'transitive set A'? Said another way, does it really matter in set theory which way the two parts of the logical AND are written from left to right, and if not, why not write it as I did, which seems to me more natural and illuminating, and does writing it that way violate the set theoretic idea of a transitive set? Would someone please explain?

In Naive Set Theory, p.47, Halmos, P.R. says, "Sometimes a set with the property that it includes (set inclusion symbol) everything that it contains (∈) is called a transitive set. More precisely, to say that E is transitive means that if x ∈ y AND y ∈ E, then x ∈ E."

^[1]

In Elements of Set Theory, by H.B. Enderton, p.71, DEFINITION: A set A is said to be a transitive set iff every member of a member of A is itself a member of A:

                   x ∈ a ∈ A → x ∈ A.

To get to that definition, the author began with von Neumann's proposed method for representing the natural numbers with sets, and appealed to the Peano Postulates.

After stating that definition for transitive set, the author went on to state a couple of related theorems:

Theorem 4E: For a transitive set a, the union of (a union {a}) = a.

Theorem 4F: Every natural number is a transitive set.

Theorem 4G: The set ω (where ω is the set of natural numbers) is a transitive set.

Stated another way this theorem says "Every natural number is itself a set of natural numbers." and further says "We will later strengthen this to: Every natural number is the set of all smaller natural numbers."

^[2]

In McGraw-Hill Dictionary of Scientific and Technical Terms, Fifth Edition, p.2057, "transitive relation [Math] A relation < on a set such that if a < b and b < c, then a < c."

^[3]

Langing (talk) 20:03, 30 June 2011 (UTC)Reply