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'm confused about these 3 selected problems. I have the solutions for each, if necessary, but I'm much more interested in understanding the material. If anyone can offer a clear, concise, and intuitive explanation for each- or even just one- I'd be entirely grateful.

Let $R$ be the relation on the set of people consisting of $(a,b)$ where $a$ is the parent of $b$. Let $S$ be the relation on the set of people consisting of $(a,b)$ where $a$ and $b$ are siblings. What are $S\circ R$ and $R\circ S$?

A) $(a,b)$ where $a$ is a parent of $b$ and $b$ has a sibling; $(a,b)$ where $a$ is the aunt or uncle of $b$.

B) $(a,b)$ where $a$ is the parent of $b$ and $a$ has a sibling; $(a,b)$ where $a$ is the aunt or uncle of $b$.

C) $(a,b)$ where $a$ is the sibling of $b$'s parents; $(a,b)$ where $a$ is $b$'s niece or nephew.

D) $(a,b)$ where $a$ is the parent of $b$; $(a,b)$ where $a$ is the aunt or uncle of $b$.

On the set of all integers, let $(x,y) \in R$ iff $xy \geq 1$. Is relation R reflexive, symmetric, antisymmetric, transitive?

A) Yes, No, No, Yes

B) No, Yes, No, Yes

C) No, No, No, Yes

D) No, Yes, Yes, Yes

E) No, No, Yes, No

At what smallest power of R do we find the connectivity relation R* in this diagram?

A) $R^* = R$

B) $R^* = \bigcup_{k=1}^2 R^k$

C) $R^* = \bigcup_{k=1}^3 R^k$

D) $R^* = \bigcup_{k=1}^4 R^k$

E) $R^* = \bigcup_{k=1}^5 R^k$

EDIT: I understand the first two pretty well. That is, I know what they're asking for, but my path to the solution doesn't seem to be correct. For the first one, what do I need to know about the way relational compositions work that will make this problem more manageable? For the second, I need help with the symmetric and antisymmetric part (how does it work here)? And the third, which I'm having the most trouble with- what exactly is $R^*$, and how does it relate to the notation in each of the answers ($\bigcup$)?

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

$(a,b)\in S\circ R$ if there is some $c$ such that $(a,c)\in R$ and $(c,b)\in S$. That is, $a$ is a parent of $c$ and $c$ is a sibling of $b$--equivalently, $a$ is a parent of $b$ and $b$ has a sibling. $(a,b)\in R\circ S$ if there is some $c$ such that $(a,c)\in S$ and $(c,b)\in R$. That is, $a$ is a sibling of $c$ and $c$ is a parent of $b$--equivalently, $a$ is an aunt or uncle of $b$.


To determine if $R$ is reflexive, we need to determine if $x^2\geq 1$ for all integers $x$; symmetric, if $yx\geq 1$ whenever $xy\geq 1$; antisymmetric, if $xy\geq 1$ and $yx\geq 1$ together imply $x=y$; transitive, if $xy\geq 1$ and $yz\geq 1$ together implies $xz\geq 1$.

The first three are almost trivial to prove or find counterexamples for. For the last, note that $xy\geq 1$ if and only if $x,y$ are non-zero and have the same sign. Does it follow then that $xy\geq 1$ and $yz\geq 1$ implies $xz\geq 1$?


For the last, we need to look at each pair of nodes $(x,y)$--where $x$ and $y$ may be the same--and determine the fewest arrows we need to travel to get from $x$ to $y$. Call this number $\ell(x,y)$. The maximum of $\ell(x,y)$ over all $25$ pairs $(x,y)$ will give you the least $n$ that you'll need to get $R^*=\bigcup_{k=1}^nR^k$. But why is this? Let me dig into the definitions of $R^k$ and $R^*$ to make this clearer.

In general, $R^k$ is alternative notation for repeated composition--e.g.: $R^1=R$, $R^2=R\circ R$, $R^3=R\circ R\circ R$, etc. In this circumstance, $R^k$ is the set of all vertex pairs $(x,y)$ such that we can travel from $x$ to $y$ along a path composed of exactly $k$ of the arrows in the given diagram. (Do you see why?) For example, $$R^1=\bigl\{(A,D),(B,A),(B,C),(C,B),(C,E),(D,C),(D,E),(E,B)\bigr\}$$ $$R^2=\bigl\{(A,C),(A,E),(B,B),(B,D),(B,E),(C,A),(C,B),(C,C),(D,B),(E,A),(E,B)\bigr\}$$

In general, $R^*$ is the least reflexive transitive relation containing $R$. In this circumstance, any transitive relation containing $R$ will contain all pairs of nodes $(x,y)$ such that there is some path from $x$ to $y$ in the given diagram. Observe that we can start at any node and follow a circuit to get back to the starting node, and we can start at any node and travel to any other node. The least transitive relation containing $R$, then, will be the set of all vertex pairs $(x,y)$ (including those with $x=y$). Then $R^*=\bigcup_{k=1}^\infty R^k$, but we don't need arbitrarily long paths to get the job done. In fact, none of the paths we need are any longer than $4$, so we can rule out E, but the only simple circuit starting at and returning to A has length $4$, so the answer is D.

share|improve this answer
    
Thanks so much for the response. Do you mind just elaborating on the third one some more? I'm having trouble understanding $R^*$'s use and it's relation with the $\bigcup$ notation. –  Bob John Nov 13 '12 at 21:09
    
Thanks, really appreciate it. –  Bob John Nov 13 '12 at 21:32
    
I've elaborated on the third one. Does that help? –  Cameron Buie Nov 13 '12 at 22:04
    
So for $R^*$ to be "fulfilled" we need to find some $n$ for $\bigcup_{k=1}^n R^k$ such that if we start at $\bf{any}$ vertex we're able to return to that same vertex by travelling through exactly (at least?) k arrows, but never more? –  user1038665 Nov 14 '12 at 12:13
    
@user1038665: Very close. We need to be able to start at any vertex and get to any vertex (possibly the same one) by travelling through at least $1$ arrow and at most $n$ arrows--that is, exactly $k$ arrows for some $1\leq k\leq n$, which is where the union from $k=1$ to $k=n$ comes in. –  Cameron Buie Nov 14 '12 at 12:31
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.