Powers of relations problem

Question

In a discrete mathematics course, I stumbled upon the following problem. I have an idea how to solve the problem based on the fact that the power of a relation repeats after 3 consecutive powers; that is $R^1=R^4, R^2=R^5, R^3=R^6$, and so on. However, I cannot put it into words on a formal way. How would you approach it?

Problem

Let $R$ be the relation on the set of people with doctorates such that $(a, b) \in R$ if and only if $a$ was the thesis advisor of $b$. (You may assume that every person with a doctorate has a thesis advisor.)

When is an ordered pair $(a,b)$ in $R^2$?

When is an ordered pair $(a,b)$ in $R^n$, when $n$ is a positive integer?

I learned that if you represent a relation using a directed graph, those graph repeat after 3 consecutive powers. Did I understand it incorrectly? — Camilo Celis Guzman, Jun 10 '15 at 17:23
@CamiloCelisGuzman Your power relations trace lineages if I'm not mistaken. Lineages can be arbitrarily long so your "3 consecutive powers" rule probably can't hold. — user2566092, Jun 10 '15 at 17:25
Is my great-great-grandfather the same as my father? I hardly think so. — Robert Israel, Jun 10 '15 at 17:31
@RobertIsrael that is a great way to put it. It does help to understand the effect of power in relations, thank you. — Camilo Celis Guzman, Jun 10 '15 at 17:32

score 1 · Accepted Answer · answered Jun 10 '15 at 17:24

The problem is asking for an intepretation of when $(a,b)\in R^2$, and when $(a,b)\in R^n$, i.e. it is asking for an explanation in terms of people with doctorates and advisors.

That $(a,b)\in R^2$ means that there exists some $c$, such that $(a,c)\in R$ and $(c,b)\in R$. This means that $a$ was the thesis advisor of someone who was the thesis advisor of $b$.

Similarly, $(a,b)\in R^n$ means that $a$ was the thesis advisor of someone, who was the thesis advisor of someone who ... ($n-1$ times) ... who was the thesis advisor of $b$. You can say that $a$ is the mathematical great grandfather of $b$ in $n$ generations.

Powers of relations problem

1 Answers1