Definition talk:Transitive Closure (Relation Theory)

From ProofWiki
Jump to navigation Jump to search

Even this term is somewhat ambiguous. Transitive closure may also refer to the smallest transitive set containing a given set. --Andrew Salmon 06:04, 26 July 2012 (UTC)

We could then make Definition:Transitive Closure (Set Theory) and Definition:Transitive Closure (Relation Theory). As it stands I imagine the former instantiates the latter, but I'm not entirely sure. --Lord_Farin 10:31, 2 August 2012 (UTC)
I just realized that a class $A$ is a transitive class iff $\Epsilon \restriction A$ is a transitive relation. This provides a clear connection between transitive classes and transitive relations. Perhaps this could make the proof that every set has a transitive closure slightly easier. Just take the domain of the transitive closure of the relation $\Epsilon \restriction A$ and you have the smallest transitive set containing $A$! --Andrew Salmon 02:27, 15 August 2012 (UTC)
That appears to work indeed; of course, some work is to be done to extend the 'Transitive Closure Exists' theorem to class relations. --Lord_Farin 07:16, 15 August 2012 (UTC)

Transitive Reduction

What sense can be made of this idea I wonder? --Jshflynn (talk) 18:30, 2 March 2013 (UTC)

It's just as senseless as Symmetric Reduction IMO, on the same grounds. — Lord_Farin (talk) 18:39, 2 March 2013 (UTC)
I don't think it is as senseless as that one LF. For example suppose we have the following relation:
$\mathcal R = \{(x, y), (y, z)\}$
$\mathcal R^+ = \{(x, y), (y, z), (x, z) \}$
Now if we try to remove all traces of transitivity from $\mathcal R^+$ we get back $\mathcal R$. --Jshflynn (talk) 18:46, 2 March 2013 (UTC)
Oh damn, I just realised we get every other subset too :( --Jshflynn (talk) 18:49, 2 March 2013 (UTC)
I'd be impressed at a sensible definition of the transitive reduction of the trivial relation $S \times S$ for arbitrary $S$. — Lord_Farin (talk) 19:23, 2 March 2013 (UTC)
Okay, how about this then!


Let $\mathcal R$ and $\mathcal S$ be endorelations on a set $T$ such that $\mathcal S$ is antitransitive.

Then $\mathcal S$ is an antitransitive root of $\mathcal R$ iff:

$\mathcal S^+ = \mathcal R^+$


This means I see reflexive closure and reduction as like the floor and ceiling operators and transitive closure and "reduction" as squaring and finding the square root.

I know it is not the PW way but I see no harm in contemplating the notion on this island of the wiki. --Jshflynn (talk) 19:51, 2 March 2013 (UTC)

Okay, fairly nice. Please continue contemplating these things. One thing you could try is proving the existence of such roots... It seems nontrivial to me, if it is even true to begin with. — Lord_Farin (talk) 19:59, 2 March 2013 (UTC)


If the subpages themselves don't have numbers, but instead have descriptive names, is there any point in using numbers at all? If the currently fashionable paradigm of subpage maintenance is to arbitrarily change the ordering of subpages according to an aesthetically-inspired and imprecisely defined notion of worthiness, then the consistency of interpage linking based on a numerical-order-based system will be in danger of being compromised. OTOH if the subpages are uniquely referred to by their full "descriptive" names, then no such danger exists and any user can rearrange the order according to their own personal whim to their heart's content with no potentially damaging effects to the database. --prime mover (talk) 07:00, 3 March 2013 (UTC)

The numbers can in such cases be avoided. However it is in general not quite the case that descriptive names can be crafted. Very long titles IMO are not better than numbered definitions. But we've been there before, so I'll shut up. — Lord_Farin (talk) 08:36, 4 March 2013 (UTC)


Reference is made to the Mac Lane and Birkhoff "Algebra" book. This needs to be entered into the Books namespace. --prime mover (talk) 07:06, 3 March 2013 (UTC)

...I've added the stub. --prime mover (talk) 07:14, 3 March 2013 (UTC)
Excellent. — Lord_Farin (talk) 08:36, 4 March 2013 (UTC)