Finding a the smallest partial order containing $R$
Let $R$ be a relation on $Bbb 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) What is the smallest partial order containing $R$?
(b) Using the reflexive, symmetric, and transitive closures, express the smallest equivalence relation containing an arbitrary relation.
I have tried to approach this problem many ways, but I cannot figure it out. How can I solve this?
discrete-mathematics relations
edited Nov 30 at 6:32
Tianlalu
3,12321038
asked Nov 30 at 6:29
Mustapha
1
|
show 5 more comments
Let $R$ be a relation on $Bbb 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) What is the smallest partial order containing $R$?
(b) Using the reflexive, symmetric, and transitive closures, express the smallest equivalence relation containing an arbitrary relation.
I have tried to approach this problem many ways, but I cannot figure it out. How can I solve this?
discrete-mathematics relations
edited Nov 30 at 6:32
Tianlalu
3,12321038
asked Nov 30 at 6:29
Mustapha
1
Can you do it for the case of just one prime, say $2$? What does that relation look like? You have $1R2, 2R4, 3R6,$ etc. What do you have to add to make it reflexive, symmetric, or transitive?
– Ross Millikan
Nov 30 at 6:49
I would have to add 2R1 4R2 6R3 1R1 2R2 3R3 4R4 6R6
– Mustapha
Nov 30 at 13:02
You were asked separately for each of reflexive, symmetric, and transitive. Reflexive just requires $xRx$, so you need to add $1R1,2R2,$ and so on. Any reflexive relation must include the identity and any relation can be made reflexive by adding the identity. Yes, you need $2R1,4R2,$ and so on but not $2R2$ and $4R4$ for symmetric. Transitive?
– Ross Millikan
Nov 30 at 14:29
Ah I see my apologies. Then for transitive you would need to add 1R4
– Mustapha
Nov 30 at 14:39
Yes, that is correct. Then you need $1R8, 1R16, 2R8, 2R16$ and so on. Then a partial order is just transitive and antisymmetric. We are already antisymmetric, so making it transitive is enough (and doesn't spoil the antisymmetry) to get a partial order.
– Ross Millikan
Nov 30 at 15:17
|
show 5 more comments
Let $R$ be a relation on $Bbb 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) What is the smallest partial order containing $R$?
(b) Using the reflexive, symmetric, and transitive closures, express the smallest equivalence relation containing an arbitrary relation.
I have tried to approach this problem many ways, but I cannot figure it out. How can I solve this?
discrete-mathematics relations
edited Nov 30 at 6:32
Tianlalu
3,12321038
asked Nov 30 at 6:29
Mustapha
1
Let $R$ be a relation on $Bbb 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) What is the smallest partial order containing $R$?
(b) Using the reflexive, symmetric, and transitive closures, express the smallest equivalence relation containing an arbitrary relation.
I have tried to approach this problem many ways, but I cannot figure it out. How can I solve this?
discrete-mathematics relations
discrete-mathematics relations
edited Nov 30 at 6:32
Tianlalu
3,12321038
asked Nov 30 at 6:29
Mustapha
1
edited Nov 30 at 6:32
Tianlalu
3,12321038
asked Nov 30 at 6:29
Mustapha
1
edited Nov 30 at 6:32
Tianlalu
3,12321038
edited Nov 30 at 6:32
Tianlalu
3,12321038
edited Nov 30 at 6:32
Tianlalu
3,12321038
3,12321038
asked Nov 30 at 6:29
Mustapha
1
asked Nov 30 at 6:29
Mustapha
1
asked Nov 30 at 6:29
Mustapha
1
1
Can you do it for the case of just one prime, say $2$? What does that relation look like? You have $1R2, 2R4, 3R6,$ etc. What do you have to add to make it reflexive, symmetric, or transitive?
– Ross Millikan
Nov 30 at 6:49
I would have to add 2R1 4R2 6R3 1R1 2R2 3R3 4R4 6R6
– Mustapha
Nov 30 at 13:02
You were asked separately for each of reflexive, symmetric, and transitive. Reflexive just requires $xRx$, so you need to add $1R1,2R2,$ and so on. Any reflexive relation must include the identity and any relation can be made reflexive by adding the identity. Yes, you need $2R1,4R2,$ and so on but not $2R2$ and $4R4$ for symmetric. Transitive?
– Ross Millikan
Nov 30 at 14:29
Ah I see my apologies. Then for transitive you would need to add 1R4
– Mustapha
Nov 30 at 14:39
Yes, that is correct. Then you need $1R8, 1R16, 2R8, 2R16$ and so on. Then a partial order is just transitive and antisymmetric. We are already antisymmetric, so making it transitive is enough (and doesn't spoil the antisymmetry) to get a partial order.
– Ross Millikan
Nov 30 at 15:17
|
show 5 more comments
Can you do it for the case of just one prime, say $2$? What does that relation look like? You have $1R2, 2R4, 3R6,$ etc. What do you have to add to make it reflexive, symmetric, or transitive?
– Ross Millikan
Nov 30 at 6:49
I would have to add 2R1 4R2 6R3 1R1 2R2 3R3 4R4 6R6
– Mustapha
Nov 30 at 13:02
You were asked separately for each of reflexive, symmetric, and transitive. Reflexive just requires $xRx$, so you need to add $1R1,2R2,$ and so on. Any reflexive relation must include the identity and any relation can be made reflexive by adding the identity. Yes, you need $2R1,4R2,$ and so on but not $2R2$ and $4R4$ for symmetric. Transitive?
– Ross Millikan
Nov 30 at 14:29
Ah I see my apologies. Then for transitive you would need to add 1R4
– Mustapha
Nov 30 at 14:39
Yes, that is correct. Then you need $1R8, 1R16, 2R8, 2R16$ and so on. Then a partial order is just transitive and antisymmetric. We are already antisymmetric, so making it transitive is enough (and doesn't spoil the antisymmetry) to get a partial order.
– Ross Millikan
Nov 30 at 15:17
Can you do it for the case of just one prime, say $2$? What does that relation look like? You have $1R2, 2R4, 3R6,$ etc. What do you have to add to make it reflexive, symmetric, or transitive?
– Ross Millikan
Nov 30 at 6:49
Can you do it for the case of just one prime, say $2$? What does that relation look like? You have $1R2, 2R4, 3R6,$ etc. What do you have to add to make it reflexive, symmetric, or transitive?
– Ross Millikan
Nov 30 at 6:49
I would have to add 2R1 4R2 6R3 1R1 2R2 3R3 4R4 6R6
– Mustapha
Nov 30 at 13:02
I would have to add 2R1 4R2 6R3 1R1 2R2 3R3 4R4 6R6
– Mustapha
Nov 30 at 13:02
You were asked separately for each of reflexive, symmetric, and transitive. Reflexive just requires $xRx$, so you need to add $1R1,2R2,$ and so on. Any reflexive relation must include the identity and any relation can be made reflexive by adding the identity. Yes, you need $2R1,4R2,$ and so on but not $2R2$ and $4R4$ for symmetric. Transitive?
– Ross Millikan
Nov 30 at 14:29
You were asked separately for each of reflexive, symmetric, and transitive. Reflexive just requires $xRx$, so you need to add $1R1,2R2,$ and so on. Any reflexive relation must include the identity and any relation can be made reflexive by adding the identity. Yes, you need $2R1,4R2,$ and so on but not $2R2$ and $4R4$ for symmetric. Transitive?
– Ross Millikan
Nov 30 at 14:29
Ah I see my apologies. Then for transitive you would need to add 1R4
– Mustapha
Nov 30 at 14:39
Ah I see my apologies. Then for transitive you would need to add 1R4
– Mustapha
Nov 30 at 14:39
Yes, that is correct. Then you need $1R8, 1R16, 2R8, 2R16$ and so on. Then a partial order is just transitive and antisymmetric. We are already antisymmetric, so making it transitive is enough (and doesn't spoil the antisymmetry) to get a partial order.
– Ross Millikan
Nov 30 at 15:17
Yes, that is correct. Then you need $1R8, 1R16, 2R8, 2R16$ and so on. Then a partial order is just transitive and antisymmetric. We are already antisymmetric, so making it transitive is enough (and doesn't spoil the antisymmetry) to get a partial order.
– Ross Millikan
Nov 30 at 15:17
|
show 5 more comments
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3019738%2ffinding-a-the-smallest-partial-order-containing-r%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3019738%2ffinding-a-the-smallest-partial-order-containing-r%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Can you do it for the case of just one prime, say $2$? What does that relation look like? You have $1R2, 2R4, 3R6,$ etc. What do you have to add to make it reflexive, symmetric, or transitive?
– Ross Millikan
Nov 30 at 6:49
I would have to add 2R1 4R2 6R3 1R1 2R2 3R3 4R4 6R6
– Mustapha
Nov 30 at 13:02
You were asked separately for each of reflexive, symmetric, and transitive. Reflexive just requires $xRx$, so you need to add $1R1,2R2,$ and so on. Any reflexive relation must include the identity and any relation can be made reflexive by adding the identity. Yes, you need $2R1,4R2,$ and so on but not $2R2$ and $4R4$ for symmetric. Transitive?
– Ross Millikan
Nov 30 at 14:29
Ah I see my apologies. Then for transitive you would need to add 1R4
– Mustapha
Nov 30 at 14:39
Yes, that is correct. Then you need $1R8, 1R16, 2R8, 2R16$ and so on. Then a partial order is just transitive and antisymmetric. We are already antisymmetric, so making it transitive is enough (and doesn't spoil the antisymmetry) to get a partial order.
– Ross Millikan
Nov 30 at 15:17