My level is undergrad-master with little or no formal knowledge of relation or order theory, but with some graph theory.
Let $R$ be a binary relation on a finite set $X$. I was looking for terminology and notation for describing a set like
$P=\{(x_1,x_2),(x_2,x_3),(x_3,x_4),\dots,(x_{k-1},x_k)\}$,
i.e. in a sense a directed path if this was graph theory.
For orders I've heard of chains being sets of pairwise comparable elements. But, as I understand it this requires transitivity, e.g. $P$ above is not a chain. I thus see chain mostly (if not only) defined for partial orders, which makes sense.
I also found the definition of a fence in for example Schroeder's Ordered Sets (Def. 2.37). He mentions that they can be seen as analogues to paths in graph theory. However, they are paths with alternating orientation. I guess what I was after was an analogue of a directed path, that does not require transitivity.
Questions:
- Is there a terminology and/or notation for sets like $P$ above purely for relations, akin to the one of directed paths in a graph? Preferably, I'd simply denote it as $x_1x_2x_3\dots x_{k-1}x_k$, and even concatenate elements and "paths" into new ones like $yPz$, similar to the notation used in e.g. Diestel's Graph Theory.
- Would anyone recommend a good (preferably introductory) treatment on the correspondence between relations, orders and graphs?
Most books for undergrads focus more on order and specifically partial orders. Books I found on more pure relations have either not explicitly contained such definitions, or have been a bit too advanced for me to notice. Also, the abundance of terms for the same things sometimes makes it hard to find what I want, e.g. chain, total order, linear order, simple order, connex order, etc. I looked in e.g. Steven Givant's Relation Algebras, but did not find any such notation.
Sometimes "graph" is used to mean exactly the same thing as a binary relation on a set (a directed graph without multiple edges but where loops are permitted), but of course not always. It seems to make good sense to talk about a "path" in a relation, although "directed path" would be ok for emphasis. Maybe a "path" would be a directed path in the symmetric closure of the relation. While it is important to respect existing terminology, especially when talking to a specific audience, mathematics has a culture of generalizing the meaning of terms. If this is done thoughtfully, the freedom to do so is part of the creativity of the subject. Feel free to develop the terminology and probably writing the precise definitions will be an important part of learning. For example: it's not clear that the set $P$ is quite right in the question (what if the path contains cycles?); should it be a sequence not a set? is it the sequence of pairs in $X \times X$ or the sequence of elements of $X$ that matters most?
From a purely relational point of view (in the Relation Algebra setting of Givant's book you mention) the emphasis is more on the properties of $R$ as a whole, rather than the individual elements (we might call them arrows or pairs) in the relation. In fact, there are models of the relation algebra axioms that cannot be represented as concrete relations on a set (non-representable relation algebras). Thus if your application needs to talk explicitly about the pairs in the relation there must be something involved that goes beyond the operations in a relation algebra.
Composition of $R$ with itself "forgets" the route used between the two endpoints and only measures the existence of a route. To get involved with different routes between the same endpoints, you might need to bring in category theory. See, for example, the wiring diagrams on p42 of Fong and Spivak An Invitation to Applied Category Theory (2019).
For other sources of information on relations, there is Gunther Schmidt's Relational Mathematics (2011) and possibly Schmidt and Strohlein Relations and Graphs (1993).