Binary relation, reflexive, symmetric and transitive
$begingroup$
I have a question regarding an image. I'm currently studying binary relations and the following image confused me:
What got me confused is that the page from which I got the link (http://www.cs.odu.edu/~toida/nerzic/content/relation/property/property.html) says that the graph in (a) is reflexive, symmetric and transitive.
According to what I've learned so far a set is reflexive if for all $x$, $x$ bears a relation to $x$, the graph has this property. Now, for the other two relations, symmetric and transitive, it does not hold. Because for it to be symmetric it would need a path from both points back to each other (because a relation is symmetric iff $x$ has a relation to $y$ and back). The transitive property also does not hold because there are only 2 points and transitivity needs at least three.
I would like some proof that explains why the graph is transitive and symmetric.
discrete-mathematics relations equivalence-relations
edited Jul 10 '14 at 17:59
Roy O.
722817
asked Jul 10 '14 at 13:17
KevinKevin
13915
$endgroup$
add a comment |
$begingroup$
I have a question regarding an image. I'm currently studying binary relations and the following image confused me:
What got me confused is that the page from which I got the link (http://www.cs.odu.edu/~toida/nerzic/content/relation/property/property.html) says that the graph in (a) is reflexive, symmetric and transitive.
According to what I've learned so far a set is reflexive if for all $x$, $x$ bears a relation to $x$, the graph has this property. Now, for the other two relations, symmetric and transitive, it does not hold. Because for it to be symmetric it would need a path from both points back to each other (because a relation is symmetric iff $x$ has a relation to $y$ and back). The transitive property also does not hold because there are only 2 points and transitivity needs at least three.
I would like some proof that explains why the graph is transitive and symmetric.
discrete-mathematics relations equivalence-relations
edited Jul 10 '14 at 17:59
Roy O.
722817
asked Jul 10 '14 at 13:17
KevinKevin
13915
$endgroup$
add a comment |
$begingroup$
I have a question regarding an image. I'm currently studying binary relations and the following image confused me:
What got me confused is that the page from which I got the link (http://www.cs.odu.edu/~toida/nerzic/content/relation/property/property.html) says that the graph in (a) is reflexive, symmetric and transitive.
According to what I've learned so far a set is reflexive if for all $x$, $x$ bears a relation to $x$, the graph has this property. Now, for the other two relations, symmetric and transitive, it does not hold. Because for it to be symmetric it would need a path from both points back to each other (because a relation is symmetric iff $x$ has a relation to $y$ and back). The transitive property also does not hold because there are only 2 points and transitivity needs at least three.
I would like some proof that explains why the graph is transitive and symmetric.
discrete-mathematics relations equivalence-relations
edited Jul 10 '14 at 17:59
Roy O.
722817
asked Jul 10 '14 at 13:17
KevinKevin
13915
$endgroup$
I have a question regarding an image. I'm currently studying binary relations and the following image confused me:
What got me confused is that the page from which I got the link (http://www.cs.odu.edu/~toida/nerzic/content/relation/property/property.html) says that the graph in (a) is reflexive, symmetric and transitive.
According to what I've learned so far a set is reflexive if for all $x$, $x$ bears a relation to $x$, the graph has this property. Now, for the other two relations, symmetric and transitive, it does not hold. Because for it to be symmetric it would need a path from both points back to each other (because a relation is symmetric iff $x$ has a relation to $y$ and back). The transitive property also does not hold because there are only 2 points and transitivity needs at least three.
I would like some proof that explains why the graph is transitive and symmetric.
discrete-mathematics relations equivalence-relations
discrete-mathematics relations equivalence-relations
edited Jul 10 '14 at 17:59
Roy O.
722817
asked Jul 10 '14 at 13:17
KevinKevin
13915
edited Jul 10 '14 at 17:59
Roy O.
722817
asked Jul 10 '14 at 13:17
KevinKevin
13915
edited Jul 10 '14 at 17:59
Roy O.
722817
edited Jul 10 '14 at 17:59
Roy O.
722817
edited Jul 10 '14 at 17:59
Roy O.
722817
722817
asked Jul 10 '14 at 13:17
KevinKevin
13915
asked Jul 10 '14 at 13:17
KevinKevin
13915
asked Jul 10 '14 at 13:17
KevinKevin
13915
13915
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
It's somewhat of a logical subtlety.
- A relation $R$ is transitive iff: $forall x,y,z : (xRy wedge yRz) Rightarrow xRz$.
- A relation $R$ is symmetric iff: $forall x,y : xRy Rightarrow yRx$.
Universally quantified formulas like 1 and 2 are only false if you can find a counter-example. This is because an implication $P Rightarrow Q$ is true whenever $P$ is false, irrespective of the truth value of $Q$. Since there are no counter-examples in (a), transitivity and symmetry are trivially true.
Similarly, and for your information, over an empty domain a relation $R$ would be trivially reflexive, since you would not be able to find an element $x$ for which $xRx$ does not hold.
answered Jul 10 '14 at 14:07
Roy O.Roy O.
722817
$endgroup$
add a comment |
$begingroup$
The relation $sim$ is reflexive if whenever $x sim y$, it is also true that $y sim x$. In other words, if there is no pair $x, y$ with $x sim y$ and $y notsim x$, then the relation is symmetric. Think of it this way: If there is no asymmetry, then it is symmetric. The same goes for transitivity. If there is no violation of transitivity, then the relation is transitive.
Consider this - do you agree that the relation in example $(e)$ is transitive? I am quite sure you do. But observe that the bottom element is not related to any other element. Is that a violation of transitivity? No, of course not. Similarly, even if no element is related to any other (like in $(a)$), there is no actual violation of transitivity.
answered Jul 10 '14 at 13:55
M. VinayM. Vinay
6,77822135
$endgroup$
add a comment |
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%2f863219%2fbinary-relation-reflexive-symmetric-and-transitive%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
It's somewhat of a logical subtlety.
- A relation $R$ is transitive iff: $forall x,y,z : (xRy wedge yRz) Rightarrow xRz$.
- A relation $R$ is symmetric iff: $forall x,y : xRy Rightarrow yRx$.
Universally quantified formulas like 1 and 2 are only false if you can find a counter-example. This is because an implication $P Rightarrow Q$ is true whenever $P$ is false, irrespective of the truth value of $Q$. Since there are no counter-examples in (a), transitivity and symmetry are trivially true.
Similarly, and for your information, over an empty domain a relation $R$ would be trivially reflexive, since you would not be able to find an element $x$ for which $xRx$ does not hold.
answered Jul 10 '14 at 14:07
Roy O.Roy O.
722817
$endgroup$
add a comment |
$begingroup$
It's somewhat of a logical subtlety.
- A relation $R$ is transitive iff: $forall x,y,z : (xRy wedge yRz) Rightarrow xRz$.
- A relation $R$ is symmetric iff: $forall x,y : xRy Rightarrow yRx$.
Universally quantified formulas like 1 and 2 are only false if you can find a counter-example. This is because an implication $P Rightarrow Q$ is true whenever $P$ is false, irrespective of the truth value of $Q$. Since there are no counter-examples in (a), transitivity and symmetry are trivially true.
Similarly, and for your information, over an empty domain a relation $R$ would be trivially reflexive, since you would not be able to find an element $x$ for which $xRx$ does not hold.
answered Jul 10 '14 at 14:07
Roy O.Roy O.
722817
$endgroup$
add a comment |
$begingroup$
It's somewhat of a logical subtlety.
- A relation $R$ is transitive iff: $forall x,y,z : (xRy wedge yRz) Rightarrow xRz$.
- A relation $R$ is symmetric iff: $forall x,y : xRy Rightarrow yRx$.
Universally quantified formulas like 1 and 2 are only false if you can find a counter-example. This is because an implication $P Rightarrow Q$ is true whenever $P$ is false, irrespective of the truth value of $Q$. Since there are no counter-examples in (a), transitivity and symmetry are trivially true.
Similarly, and for your information, over an empty domain a relation $R$ would be trivially reflexive, since you would not be able to find an element $x$ for which $xRx$ does not hold.
answered Jul 10 '14 at 14:07
Roy O.Roy O.
722817
$endgroup$
It's somewhat of a logical subtlety.
- A relation $R$ is transitive iff: $forall x,y,z : (xRy wedge yRz) Rightarrow xRz$.
- A relation $R$ is symmetric iff: $forall x,y : xRy Rightarrow yRx$.
Universally quantified formulas like 1 and 2 are only false if you can find a counter-example. This is because an implication $P Rightarrow Q$ is true whenever $P$ is false, irrespective of the truth value of $Q$. Since there are no counter-examples in (a), transitivity and symmetry are trivially true.
Similarly, and for your information, over an empty domain a relation $R$ would be trivially reflexive, since you would not be able to find an element $x$ for which $xRx$ does not hold.
answered Jul 10 '14 at 14:07
Roy O.Roy O.
722817
edited Jul 10 '14 at 14:21
answered Jul 10 '14 at 14:07
Roy O.Roy O.
722817
answered Jul 10 '14 at 14:07
Roy O.Roy O.
722817
answered Jul 10 '14 at 14:07
Roy O.Roy O.
722817
722817
add a comment |
add a comment |
$begingroup$
The relation $sim$ is reflexive if whenever $x sim y$, it is also true that $y sim x$. In other words, if there is no pair $x, y$ with $x sim y$ and $y notsim x$, then the relation is symmetric. Think of it this way: If there is no asymmetry, then it is symmetric. The same goes for transitivity. If there is no violation of transitivity, then the relation is transitive.
Consider this - do you agree that the relation in example $(e)$ is transitive? I am quite sure you do. But observe that the bottom element is not related to any other element. Is that a violation of transitivity? No, of course not. Similarly, even if no element is related to any other (like in $(a)$), there is no actual violation of transitivity.
answered Jul 10 '14 at 13:55
M. VinayM. Vinay
6,77822135
$endgroup$
add a comment |
$begingroup$
The relation $sim$ is reflexive if whenever $x sim y$, it is also true that $y sim x$. In other words, if there is no pair $x, y$ with $x sim y$ and $y notsim x$, then the relation is symmetric. Think of it this way: If there is no asymmetry, then it is symmetric. The same goes for transitivity. If there is no violation of transitivity, then the relation is transitive.
Consider this - do you agree that the relation in example $(e)$ is transitive? I am quite sure you do. But observe that the bottom element is not related to any other element. Is that a violation of transitivity? No, of course not. Similarly, even if no element is related to any other (like in $(a)$), there is no actual violation of transitivity.
answered Jul 10 '14 at 13:55
M. VinayM. Vinay
6,77822135
$endgroup$
add a comment |
$begingroup$
The relation $sim$ is reflexive if whenever $x sim y$, it is also true that $y sim x$. In other words, if there is no pair $x, y$ with $x sim y$ and $y notsim x$, then the relation is symmetric. Think of it this way: If there is no asymmetry, then it is symmetric. The same goes for transitivity. If there is no violation of transitivity, then the relation is transitive.
Consider this - do you agree that the relation in example $(e)$ is transitive? I am quite sure you do. But observe that the bottom element is not related to any other element. Is that a violation of transitivity? No, of course not. Similarly, even if no element is related to any other (like in $(a)$), there is no actual violation of transitivity.
answered Jul 10 '14 at 13:55
M. VinayM. Vinay
6,77822135
$endgroup$
The relation $sim$ is reflexive if whenever $x sim y$, it is also true that $y sim x$. In other words, if there is no pair $x, y$ with $x sim y$ and $y notsim x$, then the relation is symmetric. Think of it this way: If there is no asymmetry, then it is symmetric. The same goes for transitivity. If there is no violation of transitivity, then the relation is transitive.
Consider this - do you agree that the relation in example $(e)$ is transitive? I am quite sure you do. But observe that the bottom element is not related to any other element. Is that a violation of transitivity? No, of course not. Similarly, even if no element is related to any other (like in $(a)$), there is no actual violation of transitivity.
answered Jul 10 '14 at 13:55
M. VinayM. Vinay
6,77822135
answered Jul 10 '14 at 13:55
M. VinayM. Vinay
6,77822135
answered Jul 10 '14 at 13:55
M. VinayM. Vinay
6,77822135
answered Jul 10 '14 at 13:55
M. VinayM. Vinay
6,77822135
6,77822135
add a comment |
add a comment |
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.
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%2f863219%2fbinary-relation-reflexive-symmetric-and-transitive%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
