Definition talk:Transitive Closure (Relation Theory)

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)\}$

Then:

$\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!

Definition

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^+$

Analogy:

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)