# Multiple choice questions on relations and some of their properties

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$)?

-

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

-
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