0

Let R be a relation on N defined by (x, y) ∈ R iff there is a prime p such that y = px. Describe in words the reflexive, symmetric and transitive closures of R, denoted by r, s and t, respectively

(a) Which of the following are true:

r(s(R)) = s(r(R))

<p>r(t(R)) = t(r(R))</p>

<p>s(t(R)) = t(s(R))</p>

(b) Which of them hold for all relations on N?

(c) Using the reflexive, symmetric, and transitive closures, express the smallest equivalence relation containing an arbitrary relation.

(d) What is the smallest partial order containing R?

Help needed, I don't even know how to start at all!

Edit: Attempt on defining the relation r(R)= {(x,x) ∈ NxN| There is a prime such that x=px} s(R)={(x,y)∈ NxN| There is a prime such that y=px} v {(y,x) ∈ NxN| There is a prime such that x=py} t(R)= {(x,y ∈ nxN| There is a prime such that y=px}^{(y,z ∈ NxN| There is a prime such that z=yx}

Dark of the knight
  • 1
  • 1
    Start by describing, in words, the reflexive, symmetric and transitive closures of $R$, denoted by $r, s$ and $t$, respectively . eg: "$\langle x,y\rangle\in r(R)$ iff…." – Graham Kemp Dec 10 '19 at 07:18
  • Hi I attempted to define, can you help me check for any sorts of error? Thanks how do you even proof for part A? – Dark of the knight Dec 10 '19 at 20:33

1 Answers1

1

A closure of $R$ is the smallest relation with the indicated property that contains $R$.

You must determine the minimum amount that needs to be added to $R$ until it has the required property.

Thus, $r(R)$ is the smallest reflexive relation on $\Bbb N$ that contains $R$, so:.$$r(R)=R\cup\{\langle x,x\rangle:x\in\Bbb N\}$$

Now, describe this in words.

And so on.

Graham Kemp
  • 129,094