I'm having some trouble with a couple of questions on relations:
Let $R$ be the relation on positive integers defined by $xRy \iff x < y$.
Then, in the Set Builder Notation, $R = \{(x, y) \mid y − x > 0\}.$
(a) Use the Set Builder Notation to express the transitive closure of $R$.
Not sure quite what to do here: isn't $R$ already transitive? If $x < y$ and $y < z$ then of course $x < z$.
Do I need to write $R^t=\{(x,y,z) \mid (y-x>0)\land(z-y>0)\}$ ?
(b) Use the Set Builder Notation to express the composite relation $R^n$, where $n$ is a positive integer.*
Totally clueless on this one. I've looked around but haven't been able to find any examples on how to approach this sort of question. Any tips are appreciated!
Best Answer
Let $\mathbb N$ be the set of positive integers. Formally the transitive closure of $R$ is defined as
$R^t=\bigcup_{n\in \mathbb N} R^n$.
Since $R$ is transitive, we have $R^2\subset R$, and by induction $R^n\subset R$, hence $R^t=\bigcup_{n\in \mathbb N} R^n=R$.
To find $R^2$ note that $R$ could be rewritten as
$R = \{(x, y)\in \mathbb N^2 \mid y − x \ge 1\}.$
$R^2=R\circ R= \{(x,z)\in\mathbb N^2 \mid \exists y\in\mathbb N, (y-x\ge1)\land(z-y\ge1)\}$.
Therefore it is easily seen that $R^2=\{(x,z)\in\mathbb N^2 \mid z-x\ge2\}$, and by induction,
$R^n=\{(x,z)\in\mathbb N^2 \mid z-x\ge n\}$.