1
$\begingroup$

I just started working with functions in my discrete mathematics class and we got presented with these two problems to think about at home. If anybody could help me out with them and explain, I'd greatly appreciate it.

Problem 1
Let $R$ be a relation on a set $A$. Then $R$ is transitive iff $R\circ R$ is a subset of $R$.

Problem 2
Suppose that $R$ is a relation on a set $A$ which is reflexive and transitive.
Then $R\circ R = R$.

  • 0
    @KevinCarlson I'm still not seeing how this helps me solve the problem though in all honesty.2012-10-12

1 Answers 1

1

How does an ordered pair $\langle a,b\rangle\in A\times A$ get into $R\circ R$? By the definition of composition,

$\langle a,b\rangle\in R\circ R\quad\text{iff}\quad\exists x\in A\Big(\langle a,x\rangle\in R\text{ and }\langle x,b\rangle\in R\Big)\;.\tag{1}$

Suppose that $R\circ R\subseteq R$. Suppose further that $a,b,c\in A$, $\langle a,b\rangle\in R$, and $\langle b,c\rangle\in R$. Then it’s true that

$\exists x\in A\Big(\langle a,x\rangle\in R\text{ and }\langle x,c\rangle\in R\Big)\;,$

because we can take $x=c$, so by $(1)$ we know that $\langle a,c\rangle\in R\circ R$. By hypothesis $R\circ R\subseteq R$, so $\langle a,c\rangle\in R$. In other words, we’ve just shown that if $\langle a,b\rangle\in R$ and $\langle b,c\rangle\in R$, then $\langle a,c\rangle\in R$, which is exactly what it means to say that $R$ is transitive. In short, we’ve proved that if $R\circ R\subseteq R$, then $R$ is transitive.

You can prove the opposite implication directly, but I think that it’s easier to prove the contrapositive: if $R\circ R\nsubseteq R$, then $R$ is not transitive. If $R\circ R\nsubseteq R$, there is some $\langle a,b\rangle\in(R\circ R)\setminus R$. Since $\langle a,b\rangle\in R\circ R$, we know from $(1)$ that there is an $x\in A$ such that $\langle a,x\rangle\in R$ and $\langle x,b\rangle\in R$. But by hypothesis $\langle a,b\rangle\notin R$, so clearly $R$ is not transitive: we’ve just produced a counterexample to transitivity.

The second problem, showing that if $R$ is reflexive and transitive, then $R\circ R=R$, is fairly straightforward once you have the first, so I’ll leave it to you for now.