2
$\begingroup$

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" ??

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.