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.

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

share|improve this question
2  
The first thing to do is to write down the definition of a relation, then that of a composition of two relations, and finally the definitions of "reflexive" and "transitive" relations. Do you know all these? –  Kevin Carlson Oct 11 '12 at 19:17
1  
An equivalence relation on a set A is a binary relation R on A iff it is reflexive, symmetric, and transitive. a is related to a for all a that are elements of A means reflexive. if a,b,c are elements of A and a is related to b and b is related to c, then a is related to c means transitive. –  Requiem Oct 11 '12 at 19:22
    
Composition of two functions is fog = f(g(x)) –  Requiem Oct 11 '12 at 19:23
    
You got the definition of equivalence relation backwards: it's that a binary relation is an equivalence relation if it satisfies those three properties. Every equivalence relation is a binary relation, which is also just called a relation. So, we need a definition of *relation on $A$*: it's simply a subset of $A\times A$. The important thing is that a binary relation is not necessarily a function. As a trivial example, the whole set $A\times A$ is a binary relation on $A$, and this certainly isn't a function $A\to A$-right? –  Kevin Carlson Oct 11 '12 at 19:26
1  
It isn't because if A = {1,2}, then AxA = {(1,1),(1,2),(2,1),(2,2)} and 1 is mapping to two elements and so is 2. –  Requiem Oct 11 '12 at 19:31
show 5 more comments

1 Answer 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.

share|improve this answer
add comment

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.