# Intersection/ union of a set of transitive relations

• Jan 7th 2009, 07:30 AM
Treblesteph
Intersection/ union of a set of transitive relations
Hi, I'm a bit stuck on the following question:

Assume $\mathcal{A}$ is a non-empty set, every member of which is a transitive relation. (a) Is the set $\bigcap\mathcal{A}$ a transitive relation?
(b) Is the set $\bigcup\mathcal{A}$ a transitive relation?

I started my solution with the following:

$R\in \mathcal{A} \Rightarrow (aRb \wedge bRc \Rightarrow aRc)$

$\bigcap \mathcal{A} = \{ a \mid \forall R \in \mathcal{A} , a \in R \} = \{ a \mid ( aRb \wedge bRc \Rightarrow aRc ) a \in R \}$

After that I don't really know what to do. Please could someone point me in the right direction?

Also one more problem:

Let $\mathcal{A}$ be a set of functions such that for any f and any g in $\mathcal{A}$, either $f \subseteq g$ or $g \subseteq f$. Show that $\bigcup \mathcal{A}$ is a function.

I'd really appreciate any help,
Many thanks steph
• Jan 7th 2009, 08:58 AM
HallsofIvy
Quote:

Originally Posted by Treblesteph
Hi, I'm a bit stuck on the following question:

Assume $\mathcal{A}$ is a non-empty set, every member of which is a transitive relation. (a) Is the set $\bigcap\mathcal{A}$ a transitive relation?
(b) Is the set $\bigcup\mathcal{A}$ a transitive relation?

I started my solution with the following:

$R\in \mathcal{A} \Rightarrow (aRb \wedge bRc \Rightarrow aRc)$

$\bigcap \mathcal{A} = \{ a \mid \forall R \in \mathcal{A} , a \in R \} = \{ a \mid ( aRb \wedge bRc \Rightarrow aRc ) a \in R \}$

After that I don't really know what to do. Please could someone point me in the right direction?

To prove $B= \bigcap\mathcal{A}$ is a transitive relation, you must show that if (a,b) and (b,c) are in B then (a,c) is also in B. That should be easy. If (a,b) and (b,c) are in B, then they are in EVERY relation in A, each of which is transitive: that means (a,c) is in every relation in A.

To prove that $C= \bigcup\mathcal{A}$ is a transitive relation you must show that if (a,b) and (b,c) are in C then (a,c) is also in C. If (a,b) and (b,c) are in C, then (a,b) is in SOME relation in A, (b,c) is in SOME relation in A, but not necessarily the same one!

Quote:

Also one more problem:

Let $\mathcal{A}$ be a set of functions such that for any f and any g in $\mathcal{A}$, either $f \subseteq g$ or $g \subseteq f$. Show that $\bigcup \mathcal{A}$ is a function.
A function is a set of ordered pairs such that no two distinct pairs have the same second member (in other words, you cannot have two pairs having different first members but the same second member).
I think indirect proof is best here. Suppose there were two pairs, say (a, b) and (c, b) having the same second member but distinct first members. Since every member of A is a function, that could only happen if (a,b) were in one function, say f, and (c, b) were in another, say g. But if either $f\subseteq g$ or $g\subseteq g$ one cannot contain a pair that is not in the other.
I'd really appreciate any help,
Many thanks steph[/QUOTE]