Talk:Transitive closure

Minimal inverse

Is there an algorithm, that, given a transitive relation T, will return the smallest relation R such that the transitive closure of R is T? Is there such a smallest relation? I'm looking for such an algorithm, and this seems the most logical place to find a link to it. Luqui 10:55, July 19, 2005 (UTC)

Yes, and it's called transitive reduction, a concept that Wikipedia is not yet familiar with. Luqui 10:56, July 19, 2005 (UTC)

I dispute this. For finite sets, there are minimal such R, but they are not necessarily unique. If the relation T is, in addition, antisymmetric or asymmetric, then R is unique. However, there are minimal reductions of the full relation T on three elements (so that T has 9 pairs) with 3 and with 4 pairs. In addition, the order relation (<) on the rationals clearly cannot have any minimal reduction. Arthur Rubin 23:23, 15 August 2005 (UTC)

There is indeed a smallest one. To see that, consider that (1) the relation whereby every pair of members of the domain is related, is a transitive relation that is weaker than (i.e. that includes) T, and (2) the set of all such relations is closed under intersection, so the intersection of all such relations is another such relation; that intersection is therefore the smallest one. Michael Hardy 22:44, 19 July 2005 (UTC)

I dispute statement (2) here. Arthur Rubin 23:23, 15 August 2005 (UTC)

Sorry -- I read the question wrong. I thought it was asking whether, given R, there is a smallest T. Michael Hardy 01:40, 16 August 2005 (UTC)

The graphviz [1] tool tred computes a transitive reduction of a graph given as input. Directed graphs with no cycles (such as partial orders) have a unique transitive reduction. I have found this tool to be helpful for drawing Hasse diagrams. 69.180.211.147 23:23, 17 January 2006 (UTC)

The transitive reduction is not unique for cyclic graphs, but the differences between minimal transitive reductions are essentially unimportant: each strongly connected component is represented by a cycle, and if we contract each of these cycles to a vertex we will always get the same graph. We can attain a canonical form by numbering the vertices, promising that all edges not in the cycle go in and out from the lowest-numbered vertex, and choose the cycle to pass through the vertices in increasing number order (and back around from the largest to the smallest). Deco 23:43, 17 January 2006 (UTC)

So it's clear that there should be an article on transitive reduction. Should we move this bit of discussion there? 69.180.211.147 01:10, 18 January 2006 (UTC)

OK, i made my first article: transitive reduction Lyonsam 02:03, 18 January 2006 (UTC)

Good job! I'll add a bunch of stuff to it. Deco 03:12, 18 January 2006 (UTC)

*blink*

Would be really nice if this page could have a slightly less technical explanation too. The term "transitive closure" is sometimes used in less formal contexts, it would be nice to know what it meant! —The preceding unsigned comment was added by 80.111.233.163 (talk • contribs) 18:35, 04 September 2005 (UTC)

What do you have in mind? The first sentence seems to be a good non-technical summary. Arthur Rubin 18:35, 7 September 2005 (UTC)

This article is yet another good example that you can't learn something new by reading wikipedia articles unless you already know most of it already. You may want to consider giving a real example and to have linked articles for all the mathematical symbols you used —The preceding unsigned comment was added by 64.156.212.30 (talk • contribs) 05:53, 07 April 2006 (UTC)

Right. I came here after my textbook did a lousy job at explaining it, and this is even worse. Maybe it could do with some explanations that don't involve so many symbols. --BennyD 19:06, 16 December 2006 (UTC)

Putting the examples into the lead section might help to better convey the idea behind this first, before proceeding to the more formal stuff. — Matt Crypto 20:21, 10 January 2007 (UTC)

"Transitive closure" seems like a self-explanatory phrase: if you know what "transitive" means as applied to binary relations, and you know what "closure" typically means in mathematics, then you understand what a transitive closure is. I remember being taught "closure" in 7th grade: the positive integers are closed under addition and multiplication but not under division or subtraction; the integers (including 0 and negative integers) are closed under subtraction but not under division, etc. Michael Hardy (talk) 18:27, 5 December 2009 (UTC)

Transitive closure VS Transitive and reflexive closure

In this page, the Transitive Closure seems include a reflexive closure. In my mind we have to dissociate :

Transitive Closure: $R^{+}=\bigcup _{i\in \mathbb {N} _{1}}R^{i}$

Transitive and Reflexive Closure: $R^{*}=\bigcup _{i\in \mathbb {N} }R^{i}$

where $\mathbb {N} _{1}$ is the set of naturals without 0 ($\mathbb {N} _{1}=\mathbb {N} -\{0\}$)

What do you think about it ?

—The preceding unsigned comment was added by Nico S99 (talk • contribs) 09:29, December 27, 2006 (UTC)

nonmathematical

What set theory allows, for example, humans and airports to be members of sets? What a silly thing to say. —Preceding unsigned comment added by 24.61.183.197 (talk • contribs) 02:02, April 19, 2007

Furthermore, since when is being an ancestor imply being a parent of said descendant? And certain a flight with a connection does not imply that it is a direct flight. These examples should be removed entirely MountainGoat8 (talk) 23:38, 19 October 2009 (UTC)

Being an ancestor does not, per the description, imply being a parent. You may be a parent of a parent and still fit the definition, an so on up to an arbitrary number of "parent-of"s. Can you point out where the description confused you? Perhaps distinction between R and the transitive closure of R was not strong enough? 129.93.158.25 (talk) 23:31, 24 October 2009 (UTC)

This is an encyclopedia, not a graduate text. The anonymous opinion above ascribing silliness (!) must be read in the light of well-established Wikipedia policy. Note, too, that the example is located in the article's lead, which is perhaps the least appropriate place to demand some Bourbaki-like Spartanism.—PaulTanenbaum (talk) 14:31, 26 October 2009 (UTC).

I don't understand MountainGoat8's comment in the first place. The article does not say that being an ancestor implies being a parent, nor that a direct flight may have a connection in it. — Carl (CBM · talk) 15:12, 26 October 2009 (UTC)

Trouble with recursive definition

The recursive definition in Existence and Description seems like it could be problematic for uncountably infinite sets. Can someone who plays with infinity more than I do check on this? In particular, I'm worried about the recursion needing an uncountably infinite number of steps to deduce the whole transitive closure. Thanks. 129.93.158.25 (talk) 23:37, 24 October 2009 (UTC)

As any specfic path is finite, the recursion closes after ω steps. — Arthur Rubin (talk) 00:25, 25 October 2009 (UTC)

And why must any specific path be finite? 129.93.158.2 (talk) 11:50, 25 October 2009 (UTC)

Two points: (1) What would a non-finite path look like? What would connect one end of the path with the other? (2) Once you've included all the paths of finite length, you've got a transitive relation that extends the relation that you started with. Therefore, the transitive closure cannot be more extensive than that. Michael Hardy (talk) 22:09, 25 October 2009 (UTC)

Informally, one definition of the transitive closure reads

$x{\bar {R}}y\equiv (\exists n\in \omega )(\exists z_{1})(\exists z_{2})\cdots (\exists z_{n})xRz_{1}Rz_{2}R\cdots Rz_{n}Ry.$

It can be seen that ${\bar {R}}$ is transitive, by combining the finite sequences from the two sets to a longer finite sequence.

Once you see that this works, you can see that the countable union of the single-step closures is the same set.

But, the second bullet point at the end of the section makes it clear:

$T=\bigcup _{i\in \mathbb {N} }R^{i}.$ is transitive. It follows that, even if you were to try transfinite recursion, $T=R^{\omega }$ is transitive, so $R^{\omega +1}=R^{\omega }$

The formal transfinite recursion would be written as follows:

Define

$R^{<\alpha }=\bigcup _{\beta <\alpha }R^{\beta }$

$S\circ T=\{(x,z)\mid (\exists y)xTySz\},$ the composition operator.

Then the unified transfinte recursion process becomes:

$R^{\alpha }=R\cup R^{<\alpha }\cup \left(R^{<\alpha }\circ R^{<\alpha }\right).$

However, the same argument shows that $R^{\alpha }=R^{\omega }$ if $\alpha \geq \omega .$ — Arthur Rubin (talk) 16:08, 25 October 2009 (UTC)

This is essentially the content of the Kleene fixed point theorem; the finitary nature of "transitive closure" makes the corresponding operator continuous. — Carl (CBM · talk) 21:53, 25 October 2009 (UTC)

Can you explain on a concrete example? Let us say that $R$ is a relation between sets of reals so that $aRb$ holds if and only if $a\subseteq b$ and $|b\setminus a|=1$; that is, $b$ is $a$ with one more real thrown in. As in the article, let $T$ be the transitive closure of $R$. Intuitively, $\varnothing T\mathbb {R}$ (with $\mathbb {R}$ designating all reals, as is usual), but are you saying this is not the case? 129.93.158.15 (talk) 17:56, 5 December 2009 (UTC)

Right, that is not the case. The transitive closure of a relation is the smallest transitive relation including the original one. In the example you described, the transitive closure will say that aTb if and only if a is a subset of b and |b \ a| is finite. In other words, two elements c and d related in the transitive closure of a relation R if and only if there is a finite list of elements e₁, ..., e_k such that cRe₁, e₁Re₂, ..., e_kRd. — Carl (CBM · talk) 18:08, 5 December 2009 (UTC)

Sorry, I don't know how to produce mathematical symbols.

Shouldn't the inductive definition of the transitive closure be : R^i = R^(i-1) UNION {(s1,s3) : exists s2 where (s1,s2) in R^(i-1), (s2,s3) in R}.

Using this definition, R^2= R UNION (R composition R) UNION (R composition R composition R), whereas using the definition given in the page R^2 = R UNION (R composition R) UNION (R composition R composition R) UNION (R composition R composition R composition R). In both cases R^0=R and R^1= R UNION (R composition R). By (R composition R) I mean {(s1,s3) : exists s2 where (s1,s2) in R, (s2,s3) in R}.

Also, as far as the proof that R^+ is transitive goes, it is completely unclear why, (s1,s2) in R^j and (s2,s3) in R^k makes (s1,s2) in R^(max(j,k)+1) and not R^(j+k). The way I see it, assuming R is x R a1 R a2 R a3 R y R a5 R z (that is x R^4 y and y R^2 z), it is not x R^(max(4,2)+1)=R^5 z, but x R^6 z. Of course, even in this case, (x,z) in R^+ , which proves that R^+ is transitive. —Preceding unsigned comment added by 188.4.84.165 (talk) 18:31, 25 May 2010 (UTC)

I made the change suggested and mentioned that it's due to associativity. Neonfreon (talk) 05:31, 19 August 2010 (UTC)

How is this definition related to the definition of "closure"?

It would be helpful to relate this definition to the definition of closure, which uses the example of subtraction over the real numbers (applying it to any two elements in that set yields a result that is also in that set.)

For example, if we start from a specific city x and apply the given transitive closure to yield the set of cities that can be reached from x, this set is closed in the sense that applying the same relation to any of those cities yields the same set again: you can't get to any other city but those in the set. But it's not quite the same, because the relation for cities operates on a single city, and yields a set, which are different kinds of things. In contrast, subtraction operates on, and yields, single elements of the set of real numbers.

Is the resolution to this to start with a set of cities (instead of a city), and define the domain as the set of sets of cities?

203.217.66.200 (talk) 07:13, 13 May 2010 (UTC)

The two meanings are rather distinct; note the lack of "transitive" when one speaks of binary operations. Any function is also a relation. If x + y is closed to a subset, say Z of integers, then +(x, y, z), where z = x + y, is a relation on Z. But it's a ternary rather than a binary one, so there's not much else that can be said. I don't think one can define a meaningful notion of transitive closure for n-ary, n>2 relations or equivalently for hypergraphs, even though the latter can be embedded in Levi graphs. If you apply the transitive closure notion to the Levi graph of addition, you simply say that 1+3 = 4 = 2+2 for instance, because there's an edge from (1,3) to 4 and another from (2, 2) to 4. Tijfo098 (talk) 10:15, 11 November 2012 (UTC)

'Minimal' vs 'smallest'

The intro currently reads '...is the transitive relation R+ on set X such that R+ contains R and R+ is minimal'.

Before this change, it said '...is the smallest transitive relation on X that contains R'.

I find the old version much better. The word 'minimal' is confusing - to me it sounds like being minimal is an absolute property of a relation, although it is just relative to other transitive relations that contain R.

If no-one objects, I'll change it back soon.

Chrisahn (talk) 21:58, 15 May 2012 (UTC)

Smallest with respect to cardinality

The opening paragraph contains the sentence "In set theory, binary relations are represented as sets, hence "smallest" pertains to set cardinality."

This is just complete nonsense, in general there is no "smallest" subset of a set in terms of cardinality. In particular, for any infinite set, adding a single element will lead to a set of equal cardinality.

Therefore, this wrong sentence should either be removed or replaced by the correct statement that the term "minimal" here is taken with respect to the partial ordering of "being subset of". Since being transitive is closed under intersection, the minimal element is actually a minimum and thus well-defined.

84.156.209.58 (talk) 11:00, 20 March 2021 (UTC)

 Done - I agree with you in that "cardinality" shouldn't appear here. However, I hesitated to put your explanation about uniqueness in the very first sentence of the lead. The same applies for the explanation about relations being (implemented as) sets. Therefore, I used "material implication" (with a slightly WP:EASTEREGGy link) as ordering relation. - Jochen Burghardt (talk) 16:59, 20 March 2021 (UTC)

I think that is totally confusing as an explanation of what smallest means. What is implying what? How does material implication define an ordering on things? The simpler explanation is that it is the unique minimal relation. —David Eppstein (talk) 21:00, 20 March 2021 (UTC)

Existence

Is "power set of" missing in "Furthermore, there exists at least one transitive relation containing R, namely the trivial one: X × X." ? --Rainald62 (talk) 20:28, 22 July 2023 (UTC)

No, it isn't. If X = {1,2}, then X×X = {(1,1),(1,2),(2,1),(2,2)} is the relation that relates every member of X with every member of X. The power set of X×X is the set of all 16 subsets of X×X, viz. { {}, {(1,1)}, {(1,2)}, {(2,1)}, {(2,2)}, {(1,1),(1,2)}, {(1,1),(2,1)}, {(1,1),(2,2)}, {(1,2),(2,1)}, {(1,2),(2,2)}, {(2,1),(2,2)}, {(1,1),(1,2),(2,1)}, {(1,1),(1,2),(2,2)}, {(1,1),(2,1),(2,2)}, {(1,2),(2,1),(2,2)}, {(1,1),(1,2),(2,1),(2,2)} }. This is a set of relations, but not a relation. - Jochen Burghardt (talk) 10:59, 23 July 2023 (UTC)