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$)?
Best Answer
$(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.