Prove the intersection of transitive relations is transitive.

747 Views Asked by At

Prove the intersection of transitive relations is transitive.

Let $\left\{\mathcal\ R_{i}:i\ \in\ \mathcal I\right\}$ be the set of transitive relations on $A$ indexed by $\mathcal I$,it should be shown that:

$$ (\forall i :i\in \mathcal I \implies\mathcal R_i \text{ is transitive}) \implies \bigcap_{i \in \mathcal I}\mathcal R_i \;\text{ is transitive}$$

This can be proved by induction on the number of elements in $\mathcal I$.

Let $\left|\mathcal I\right|=0$,then:

$$ (\forall i :i\in \varnothing \implies\mathcal R_i \text{ is transitive}) \implies \bigcap_{i \in \mathcal I}\mathcal R_i =A \times A $$

Which by the definition of Cartesian product implies $A \times A $ is transitive.

Assume the theorem is true for $\left|\mathcal I\right|=n$ and consider $\left|\mathcal I\right|=n+1$:

Assume $ (\forall i :i\in \mathcal I \implies\mathcal R_i \text{ is transitive}) $ $$\bigcap_{i \in \mathcal I}\mathcal R_i =\bigcap_{i \in \mathcal I \setminus \left\{n+1\right\} }\mathcal R_i \; \cap \mathcal R_{n+1}$$

By the induction hypothesis and the assumption that $\mathcal R_{n+1}$ is transitive it implies that:

$$\bigcap_{i \in \mathcal I \setminus \left\{n+1\right\} }\mathcal R_i \; \cap \mathcal R_{n+1}$$

Is transitive.


Is what have I done true?Also can the index set be an infinite one? And is it necessary for the transitive relations to be over the same set?if yes then why?

1

There are 1 best solutions below

0
On

Unfortunately, your proof doesn't work. Your inductive proof only shows that if any intersection of $n$ transitive relations is transitive, then any intersection of $n+1$ transitive relations can be represented as an intersection of $2$ transitive relations. However, your argument fails to show that an intersection of $2$ transitive relations is transitive, hence the result doesn't follow.

Also, standard induction can't work for infinite families.

The simplest proof would involve going back to the definition of transitivity: if $(x,y), (y,z) \in R$ then $(x,z) \in \mathcal R$.

Assume that $(x,y),(y,z) \in \bigcap_{i \in \mathcal I} \mathcal R_i$. By the definition of intersection, this means that, for each $i \in \mathcal I$, $(x,y),(y,z) \in \mathcal R_i$. Since each $\mathcal R_i$ is transitive, that means that $(x,z) \in \mathcal R_i$ for each $i \in \mathcal I$. Again, by the definition of intersection,this means that $(x,z) \in \bigcap_{i \in \mathcal I} \mathcal R_i$.

So $(x,y),(y,z) \in \bigcap_{i \in \mathcal I} \mathcal R_i$ implies $(x,z) \in \bigcap_{i \in \mathcal I}$. Therefore $\bigcap_\mathcal{i \in \mathcal I} \mathcal R_i$ is transitive.

Note that this proof can be generalized way further. Let $\{S_i : i \in I\}\subseteq 2^X$. Let $A \subseteq 2^X$. Let $\phi: A \rightarrow 2^X$. The argument above shows that if any family $S_i$ satisfies the condition:

For any $S \subseteq S_i: S \in A$, $\phi(S) \subseteq S_i$.

Then $\bigcap_{i \in I} S_i$ satisfies it as well.