Inductive closure of a relation?

78 Views Asked by At

I did not really know whether to ask this here or in MathOverflow. On the one hand, I have a maths degree and this is part of my PhD research on computer science, and I am pretty sure this is not a widely known concept. On the other, I feel it is basic enough that anyone that has heard of it would probably feel comfortable answering it without having to be a complete expert on the topic.

Anyway, on topic. Of course, a typical thing when defining equivalence relations in mathematics is to define the basic cases of direct equivalence, and then say: "Define the equivalence relation by producing the reflexive, symmetric and transitive closure of these direct equivalences". For example, we can define direct equivalence between natural numbers $n$ and $m$ if $n = m + 2$, and then consider the reflexive, symmetric, transitive closure of this, which obviously is the parity relation and whose equivalence classes are even numbers and odd numbers.

In my particular situation right now I run very often into a slightly more complicated case, however, which I will intuitively call for now "inductive closure". My question really is very simple: Is there a generally accepted name for this? Of course if you see any problem with what I am saying you are welcome to let me know. Because it is not something I have heard of before, I am worried I might be overlooking something. I consider an "inductive closure" to be an extension of a relation between elements in an inductively defined set, where if two sub-elements $\alpha$ and $\beta$ are equivalent, then any two elements which are defined through the same induction rule but replacing $\alpha$ for $\beta$ in the rules must also be equivalent.

A bit more formally, and following the general idea that, for example, transitive closure is the smallest relation that contains another relation and is transitive. If we have induction rules $I_1,...,I_n$, each of which takes a sequence of elements and produces a new element: $I_i: S^{n_i} \rightarrow S$, then we can say a relation $\sim$ on $S$ respects induction rules $I_1,...,I_n$ if whenever $\alpha_j \sim \beta_j$, for $j \in 1...n_i$, then $I_i(\alpha_1,...,\alpha_{n_i}) \sim I_i(\beta_1,...,\beta_{n_i})$. Then, the "inductive closure" of a relation is the smallest relation that contains another relation and respects induction.

Of course, such relation is uniquely defined because, as usual, the intersection of two relations that respect induction also respects induction, and the relation that relates every pair respects induction, and so we can consider the intersection of all relations that respect induction and contain a given relation.

This feels like such a natural concept, but in all my years of mathematics studying and research I've never seen anyone give this a name! I would rather not have to define this in my PhD thesis since it seems highly off-topic, but I'd also rather not explicitly explain it every time I use it (which is more than five times).