Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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,

share|improve this question

3 Answers 3

up vote 1 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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