0
$\begingroup$

Can't seem to figure this one out. Could anyone help me out and explain it to me?
Thank you.

Let $P$ and $Q$ be relations on $Z$ by x$P$y iff x + 1 <= y and a$Q$b iff a + 2 <= b. Prove that P $\circ$ Q = {(p,q) belonging to ZxZ | p + 3 <= q}

2 Answers 2

1

The composite of two relations $P$ and $Q$ is given by $ (p,q) \in P\circ Q \Leftrightarrow \text{ there exists } r\in \mathbb{Z}\text{ such that } pPr \text{ and }rQq.$ [Note: depending on your convention, this may be $Q\circ P$ instead. For this problem, they come out to the same thing.] When is $(p,q)\in P\circ Q$ for the given $P$ and $Q$? The claim is that $p(P\circ Q)q$ holds iff $p+3\leq q$.

Suppose $p(P\circ Q)q$. Then $pPr$ and $rQq$ for some $r\in \mathbb{Z}$. According to the definitions, this means that $p+1\leq r$ and $r+2\leq q$. Therefore $p+3=(p+1)+2\leq r+2\leq q$ as desired.

Conversely, suppose $p+3\leq q$. Then if we define $r:= p+1$, we have $p+1\leq r$ (because equality holds), so $pPr$. And we also have $p+3 = (p+1)+2 = r+2 \leq q$, so $rQq$. Therefore there exists $r$ such that $pPr$ and $rQq$, so $(p,q)\in P\circ Q$.

1

By definition, $P$ sends $x$ to $[x+1,\infty)\cap \Bbb Z$. So $P$ sends $[x+2,\infty)\cap \Bbb Z$ to $[x+3,\infty)\cap \Bbb Z$. Also $Q$ sends $p$ to $[p+2,\infty)\cap \Bbb Z$. So any $p$ is sent by $P∘Q$ to $[p+3,\infty)\cap \Bbb Z$. Therefore $P∘Q=\{(p,q):q\in [p+3,\infty)\cap \Bbb Z\}$ which is the set you mentioned.