# Definition of a hereditary relation

Sassone, V., Nielsen, M. and Winskel, G. (1996) Models for Concurrency: Towards a Classification. Theoretical Computer Science, 170 (1-2). pp. 297-348., p. 307:

Given a tree $S$, define … $\#$ is the least hereditary, symmetric, irreflexive relation on $Tran_S$ such that $(s,a,s')\#(s,b,s'')$ if $s'\neq s''$.

What is a hereditary relation? If I replace in the quote “the least hereditary, symmetric, irreflexive relation” with “the least hereditary relation”, do I get the equivalent statement?

• Hereditary Set – Kaveh Jun 13 '11 at 15:49
• @Kaveh: Your answer is not correct. – Dave Clarke Jun 13 '11 at 20:35
• @Dave, it isn't an answer, but historically this is where the word is coming. The one in your answer is a generalization, if you substitute the same relation for both $\leq$ and $\#$ (e.g. the set membership relation), then it is the same as the one in the WP article. – Kaveh Jun 14 '11 at 11:23
• @Kaveh: That's debatable – hereditary is a regular English word pertaining to inheritance – $\#$ is inherited along $\le$. – Dave Clarke Jun 14 '11 at 11:36
• @Kaveh: “if you substitute the same relation for both $\leq$ and $\#$” then it is transitivity. “hereditary relation”→“transitivity”→“hereditary set”? Or backwards? – beroal Jun 14 '11 at 14:58

In Definition 2.1 of Contextual Petri Nets, Asymmetric Event Structures, and Processes, Baldan, Corradini and Montanari are working in the setting of prime event structures, which consist of a set of events $E$ along with binary relations $\#$ and $\le$ on $E$, known as the conflict and causality relations, respectively. This is the close to what is going on in your your setting.
In this context, they state that the relation $\#$ is hereditary with respects to $\le$ whenever for all $e_0,e_1,e_2\in E$, if $e_0\#e_1$ and $e_1\le e_2$, then $e_0\#e_2$.