Discrete Mathematics (Closure Problems)

Question

$R = \{(x, x+1)|x \in \mathbb{Z}\}$

$\mathbb{Z}$ is the integers and could be negative or positive.

Create the closure of the the following:

a. $t(R)$ --> transitive closure of R

b. $rt(R)$ --> reflexive transitive closure of R

c. $st(R)$ --> symmetric transitive closure of R

Answer 1

Hint: Work through some examples. Fix one integer and figure out everything it's related to. For example, consider $7$. We know that $(7, 8) \in t(R)$. But since $(8, 9) \in t(R)$, we know by transitivity that $(7, 9) \in t(R)$. But we can repeat this argument with $(9, 10) \in t(R)$ to get that $(7, 10) \in t(R)$. A simple induction argument would show that $(7, b) \in t(R)$ for all $b > 7$. Generalizing, we see that: $$ t(R) = \,<_\mathbb{Z}\, = \{(a, b) \in \mathbb Z \times \mathbb Z \mid a < b\} $$

See if you can figure out the other two closures.

Answer 2

You know that the transitive closure is $<$.

If a relation is reflexive then it must also contain $(x,x)$. Transitivity means it becomes $\le$.

if a relation is symmetric then if it contains $(x,y)$ then it must contain $(y,x)$. Transitivity means it becomes $\neq$.