"Transitive closure"-like relation [Math]

From: In-Betweener on 6 Jul 2010 18:59

One possible definition of the transitive closure R+ of a relation R is

(R subset R+) and (R+ is transitive) and (for all R': R subset R' and
R' is transitive ==> R+ subset R')

While specifying some operations for a set-theory software library, I
stumbled with the need to define a relation that I will call R- :

(R- subset R) and (R- is transitive) and (for all R': R' subset R and
R' is transitive ==> R' subset R-)

It is a kind of "transitive closure" in reverse direction i.e., R- is
the *greatest* transitive relation that is a subset of R.

But to this date I have never heard of a name for such a derived
relation. It is not a transitive reduction, which is a very different thing.

Does any one which name the math terminology assign to this relation? I
couldn't find one so far.

Thanks in advance.

From: Tim Little on 6 Jul 2010 20:03

On 2010-07-06, In-Betweener <In-Betweener(a)chaos.order.mrvl> wrote:
> While specifying some operations for a set-theory software library, I
> stumbled with the need to define a relation that I will call R- :
>
> (R- subset R) and (R- is transitive) and (for all R': R' subset R and
> R' is transitive ==> R' subset R-)

I don't see how this is well-defined. For example, suppose
R = {(a,b), (b,c)}. What is R-?

- Tim

From: In-Betweener on 6 Jul 2010 20:51

Em 06/07/2010 21:03, Tim Little wrote:
> On 2010-07-06, In-Betweener<In-Betweener(a)chaos.order.mrvl> wrote:
>> While specifying some operations for a set-theory software library, I
>> stumbled with the need to define a relation that I will call R- :
>>
>> (R- subset R) and (R- is transitive) and (for all R': R' subset R and
>> R' is transitive ==> R' subset R-)
>
> I don't see how this is well-defined. For example, suppose
> R = {(a,b), (b,c)}. What is R-?
>
>
> - Tim

You're right. In this case, R has trivially two disjoint transitive
sub-relations. So R- isn't well defined.

Well, back to the studies...

Thank you very much.

From: Ken Pledger on 6 Jul 2010 20:52

In article <i10cfp$ahk$1(a)speranza.aioe.org>,
In-Betweener <In-Betweener(a)chaos.order.mrvl> wrote:

> One possible definition of the transitive closure R+ of a relation R is
>
> (R subset R+) and (R+ is transitive) and (for all R': R subset R' and
> R' is transitive ==> R+ subset R')

Yes. This works because the intersection of any set of transitive
relations is transitive. Your R+ ca be defined as the intersection of
all transitive relations which contain R.

> While specifying some operations for a set-theory software library, I
> stumbled with the need to define a relation that I will call R- :
>
> (R- subset R) and (R- is transitive) and (for all R': R' subset R and
> R' is transitive ==> R' subset R-) ....

No. Such an R- would have to be the union of all transitive
relations contained in R, but the union of transitive relations (unlike
the intersection) need not be transitive. For example {(a,b)} and
{(b,c)} are both transitive, but their union is not. A less trivial
example uses
R_1 = {(a,a), (a,b), (b,a), (b,b)}
R_2 = {(b,b), (b,c), (c,b), (c,c)}
which are both transitive (indeed, equivalence relations), but their
union is not. So if R = R_1 U R_2 then R has two different maximal
transitive subrelations, neither contained in the other. Your R- is
then undefined.

(Mind you, if it _were_ defined, I'd call it the "transitive
interior" of R: a nice name for something that doesn't exist. :-)

Ken Pledger.

From: William Elliot on 7 Jul 2010 04:31

On Tue, 6 Jul 2010, In-Betweener wrote:

> One possible definition of the transitive closure R+ of a relation R is
>
> (R subset R+) and (R+ is transitive) and (for all R': R subset R' and R' is
> transitive ==> R+ subset R')
>
transitive closure R = /\{ T | R subset T, T transitive }
because intersections of transitive sets are transitive.

> While specifying some operations for a set-theory software library, I
> stumbled with the need to define a relation that I will call R- :
>
> (R- subset R) and (R- is transitive) and (for all R': R' subset R and R' is
> transitive ==> R' subset R-)

> Does any one which name the math terminology assign to this relation? I
> couldn't find one so far.

I like Ken's suggestion of "transitive interior". As was pointed out
that definition doesn't define a unique relation. Accordingly, the
definition of transitive interior needs to be recast as follows.

T is _a_ transitive interior of R when T is transitive subset of
R and for all transitive S subset R, T subset S implies T = S.

In other words, the transitive interiors of R,
are the maximal transitive subsets of R.

On the other hand, the transitive closure of R,
is the minimum transitive set containing R.

The transitive interiors of R aren't a partition. For example.
{ (b,b), (a,b), (b,c) } has two intersecting transitive interiors.

The transitive subsets of R form a lattice of which the transitive
interiors are the maximal elements. In fact they form a
bounded-complete lattice, ie a lattice with the lower bound (or
equivalently, upper bound) principle. The minimal transitive
subsets (discounting empty relation) of R are the singletons of
each element of R. The empty relation, the transitive subsets
of R and the transitive closure of R form a complete lattice.

Exercise. R is the union of the transitive interiors of R.

----