Generating a minimal transitive relation containing a given collection of transitive relations

Question

Suppose I have a collection $U$ of transitive binary relations on an arbitrary set $A$; elements of $U$ are subsets $S$ of $A \times A$ such that if $(a,b) \in S$ and $(b,c) \in S$ then $(a,c) \in S$ also.

Does it make sense for me to define a set $T$ to be the minimal transitive set containing $ \cup_{S \in U} S$? I'm thinking of this as taking $\cup S$ and adding in all necessary pairs to make it transitive. But I'm worried there are problems with countability. How does the cardinality of $U$ (obviously this is restricted by that of $A$) affect my ability to do this?

Thanks,

Answer 1

Note that transitive set has a different meaning, it means that $x\in T$ then $x\subseteq T$ (recall that everything is a set in the universe of set theory).

Generally speaking now, $S$ is a relation on $A$ if $S\subseteq A\times A$. It is easy to see that the union of relations on $A$ is also a relation on $A$. Therefore in your definition we can automatically assume that $U$ is a single relation.

What you look for is given a relation $S$ we can define the transitive closure of $S$, $S^\ast$ as the minimal transitive relation containing $S$.

This can be defined internally and externally (like many other constructions in mathematics, such as topological closure, and such). The external definition is somewhat simpler: $$S^\ast = \bigcap\{T\subseteq A\times A\mid S\subseteq T\land T\text{ is transitive}\}$$

Since transitive relations intersect at a transitive relation, this is a good definition.

The second construction is internal, we start from $S$ and just add all the pairs needed for the transitivity. This is defined as $(a,b)\in S^\ast$ if and only if there is a finite sequence $a_0,\ldots, a_n$ such that $(a_i,a_{i+1})\in S$ for all $i<n$. If we allow $n=0$ then the result is reflexive as well.

Note that both the constructions did not care for the cardinality of $A$. The cardinality of $U$ is only limited by how many transitive relations there are to begin with, which can be fairly a lot for infinite sets.

Answer 2

Note that the intersection of any nonempty family of transitive relations on $A$ is itself a transitive relation on $A$: indeed, if $S_i$, $i\in I$, is a nonempty family of transitive relations on $A$, and $T=\cap_{i\in I}S_i$, then $T$ is a relation on $A$; and if $(a,b),(b,c)\in T$, then for every $i\in I$ we have $(a,b),(b,c)\in S_i$. Since each $S_i$ is transitive, then $(a,c)\in S_i$ for each $i$, hence $(a,c)\in \cap_{i\in I}S_i = T$. Thus, $T$ is a transitive relation.

That means that you can let $$T = \bigcap \bigl\{ R\subseteq A\times A \bigm| \cup_{S\in U}S\subseteq R\text{ and }R\text{ is transitive}\bigr\}.$$ Since $A\times A$ is an element of this set, the intersection is well-defined, and $T$ is the smallest relation on $A$ that is transitive and contains each $S_i$.

The relation $T$ is called the "transitive closure of $\cup_{S\in U}S$". The cardinality of $U$ is irrelevant.

That's the "top-down" construction. The "bottoms up" construction is that you need to take all pairs $(a,b)$ such that there exists a positive integer $n$, and elements $x_1,\ldots,x_n\in A$ (not necessarily distinct), and relations $S_{1},\ldots,S_n$ in $U$ (not necessarily distinct) such that $(a,x_1)\in S_1$, $(x_1,x_2)\in S_2,\ldots, (x_{n-1},x_n)\in S_n$, and $x_n=b$. Then it is an easy exercise to show that this set contains each $S_i$ and is transitive, and that any transitive relation on $A$ that contains each $S_i$ must contain this set, so this set is the transitive closure of the $S_i$. Note that the construction only uses finitely many elements of $U$ at a time, so the cardinality of $U$ is irrelevant: it can be as large as you want.

Answer 3

Let $$T=\bigcap\left\{R\subseteq A\times A:R\supseteq\bigcup_{S\in U}S\text{ and }R\text{ is transitive}\right\}\;;$$

then $T$ is the transitive closure of $\bigcup\limits_{S\in U}S$, i.e., the smallest transitive relation on $A$ containing $\bigcup\limits_{S\in U}S$. (You should verify that $T$ is transitive; this is an easy exercise.) The cardinalities of $U$ and $A$ don’t matter. In general this approach is simpler than trying to build out from $\bigcup\limits_{S\in U}S$, thouth that can also be done.

Added: Arturo and Asaf have shown how to build out from $\bigcup\limits_{S\in U}S$ in one step; there’s an alternative approach that I find simpler to think about.

Let $T_0=\bigcup\limits_{S\in U}S$. Given $T_n$ for some $n\in\mathbb{N}$, let

$$T_{n+1}=T_n\cup\left\{\langle a,c\rangle\in A\times A:\exists a,b,c\in A\big(\langle a,b\rangle,\langle b,c\rangle\in T_n\big)\right\}\;;$$

in other words, $T_{n+1}$ adds to $T_n$ any pairs that are needed for transitivity. Of course, this may create new missing pairs, but those will be picked up in $T_{n+2}$, and so on. Finally, let $$T=\bigcup_{n\in\mathbb{N}}T_n\;;$$ it’s a straightforward exercise to check that $T$ is the smallest transitive relation containing $\bigcup\limits_{S\in U}S$.