partitioning a set using a non-equivalence relation

223 Views Asked by At

I understand that a set can be partitioned into equivalence classes by an equivalence relation (wikipedia article).

However can we partition a set into a forest of trees by a relation that's simply transitive (and/or reflexive)?

E.g. assume the transitive, reflexive relation "is prefix of".

Then it seems natural that the set {"abc", "ab", c", "da", "dad", "dab"} can be "partitioned" into the following trees:

ab-->abc

da-->dad
  \->dab

c

Is the above conceptualization rigorous and what is the proper terminology to describe this kind of "partitioning" ??

1

There are 1 best solutions below

1
On

A relation that is reflexive and transitive but not necessarily symmetric is called a preorder. See this Wikipedia entry.