Transitive Closure and Composite relations in set builder notation

Question

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!

Answer 1

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\}$.

Answer 2

Note that even if you correct $R^t=\{(x,y,z) \mid (y-x>0)\land(z-y>0)\}$ to $\{(x,y):\exists z(y-z>0 \wedge z-x>0)\}$, this only gives you a transitive relation because you already knew it was transitive. If you started instead with $R':=\{(x,y):y=x+1\}$, the analogous construction would only ensure that the resulting relation held for numbers whose difference was one, and those whose difference was two; $1\:R'^t\:5$ wouldn't hold.

Instead, you want to know that chains like $x_1 R x_2 \wedge x_2Rx_3 \ldots\wedge x_{n-1}Rx_n$ always give you $x_1Rx_n$. To get at this, think about a set $X$ such that $X$ contains $x_1$ from the above list, and for all $y\in X$ and all $z$, if $yRz$ then $z\in X$. It should be clear that $x_n$ from the above list is also in $X$. In fact for absolutely any set with the property we've described for $X$, $x_n$ will be a member, even if it contains extra junk like elements that $R$ doesn't relate to anything. So you want to translate these two facts into logical notation to get the transitive closure.

As for the composite, it really depends on exactly what's being asked. The half-repaired version of the "transitive closure" I gave in the first paragraph is exactly $R^2$. That will tell you how to generalize it to more terms. I don't know if you're supposed to know anything about recursion at this point, but there is also a recursive definition that will give you a way to define it for every $n$ at once, too. But that'd be a mouthful and I'm not sure if that's what's being asked for.