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

  • 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?2012-10-11
  • 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.2012-10-11
  • 0
    Composition of two functions is fog = f(g(x))2012-10-11
  • 0
    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?2012-10-11
  • 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.2012-10-11
  • 0
    Exactly. Now we need to define the composition of relations: for $R,S\subset A\times A$ (relations on $A$), $R\circ S \subset A\times A$ is defined by $(x,y)\in R\circ S$ if there's a $z$ such that $(x,z)\in S$ and $(z,y)\in R$. So it's just the same as function composition at the level of ordered pairs. Now that we've got the definitions straight, do you see anything to try with respect to your original problem?2012-10-11
  • 0
    Honestly, with what you just wrote, I'm more confused than I was before posting this.2012-10-11
  • 0
    Let's look at $A=\{x,y,z\}, R=\{(x,x),(x,z),(z,x),(y,y)\}$ and $S=\{(x,x),(y,z)\}$, and try to compute $R\circ S$. Firs we take an element of $S$ and match its second coordinate to the first coordinate of anything we can in $R:$ so $(x,x)$ matches with $(x,x)$ and $(x,z)$ while $(y,z)$ matches only with $(z,x)$. This means $R\circ S=\{(x,x),(x,z),(y,x)\}:$ when $s\in S$ matches with $r\in R$, the pair consisting of the first coordinate of $s$ and the first coordinate of $r$ is in $R\circ S$. Make any sense?2012-10-11
  • 0
    Yes, this makes sense I believe.2012-10-11
  • 0
    @KevinCarlson I'm still not seeing how this helps me solve the problem though in all honesty.2012-10-12

1 Answers 1