Every relation on a set has reflexive closure.
$begingroup$
Proof Attempt: Suppose $R$ is a relation on set $A$; $R=R_1 times R_2 subset A times A$. We assert $S = R cup i_{R_1 times R_1}$ to be the closure of $R$ such that $i_{R_1 times R_1}={(x,x) vert x in R_1}$. We want to show $S$ is reflexive. Let $(r,r')in S$. Then either $(r,r')in R_1 times R_2$ or $(r,r')in i_{R_1 times R_1}$. If $(r,r')in R_1times R_1$, then $rin R_1$ so $(r,r)in i_{R_1times R_1}$. If $(r,r')in i_{R_1times R_1}$, then $r=r'$. In any case, $(r,r)in S$ so $S$ is reflexive. Moreover, to show $S$ is the smallest reflexive relation that contains $R$, suppose $T=T_1times T_2 supseteq R$ and $T$ is reflexive. Then $(r,r')in R Rightarrow (r,r')in T_1times T_2 Rightarrow rin T_1 land r'in T_2$. Since $T$ is reflexive, then $(r,r)in T_1times T_2$ which means $rin T_2$ and that implies $T_1 subseteq T_2$. Furthermore, we have $R_1subseteq T_1$ so $R_1 subseteq T_2$. Thus, $i_{R_1times R_1}subseteq T_1times T_2$. Therefore, $S=R_1times R_2 cup i_{R_1 times R_2}subseteq T$. Clearly, $Rsubseteq S$ so S is the reflexive closure of $R$.
My concern: Is my argument correct? I was reading Velleman's text and he instead had $S=R cup i_A$, which is what I don't understand why.
proof-verification elementary-set-theory relations
asked Jan 25 at 2:53
TheLast CipherTheLast Cipher
708715
$endgroup$
add a comment |
$begingroup$
Proof Attempt: Suppose $R$ is a relation on set $A$; $R=R_1 times R_2 subset A times A$. We assert $S = R cup i_{R_1 times R_1}$ to be the closure of $R$ such that $i_{R_1 times R_1}={(x,x) vert x in R_1}$. We want to show $S$ is reflexive. Let $(r,r')in S$. Then either $(r,r')in R_1 times R_2$ or $(r,r')in i_{R_1 times R_1}$. If $(r,r')in R_1times R_1$, then $rin R_1$ so $(r,r)in i_{R_1times R_1}$. If $(r,r')in i_{R_1times R_1}$, then $r=r'$. In any case, $(r,r)in S$ so $S$ is reflexive. Moreover, to show $S$ is the smallest reflexive relation that contains $R$, suppose $T=T_1times T_2 supseteq R$ and $T$ is reflexive. Then $(r,r')in R Rightarrow (r,r')in T_1times T_2 Rightarrow rin T_1 land r'in T_2$. Since $T$ is reflexive, then $(r,r)in T_1times T_2$ which means $rin T_2$ and that implies $T_1 subseteq T_2$. Furthermore, we have $R_1subseteq T_1$ so $R_1 subseteq T_2$. Thus, $i_{R_1times R_1}subseteq T_1times T_2$. Therefore, $S=R_1times R_2 cup i_{R_1 times R_2}subseteq T$. Clearly, $Rsubseteq S$ so S is the reflexive closure of $R$.
My concern: Is my argument correct? I was reading Velleman's text and he instead had $S=R cup i_A$, which is what I don't understand why.
proof-verification elementary-set-theory relations
asked Jan 25 at 2:53
TheLast CipherTheLast Cipher
708715
$endgroup$
add a comment |
$begingroup$
Proof Attempt: Suppose $R$ is a relation on set $A$; $R=R_1 times R_2 subset A times A$. We assert $S = R cup i_{R_1 times R_1}$ to be the closure of $R$ such that $i_{R_1 times R_1}={(x,x) vert x in R_1}$. We want to show $S$ is reflexive. Let $(r,r')in S$. Then either $(r,r')in R_1 times R_2$ or $(r,r')in i_{R_1 times R_1}$. If $(r,r')in R_1times R_1$, then $rin R_1$ so $(r,r)in i_{R_1times R_1}$. If $(r,r')in i_{R_1times R_1}$, then $r=r'$. In any case, $(r,r)in S$ so $S$ is reflexive. Moreover, to show $S$ is the smallest reflexive relation that contains $R$, suppose $T=T_1times T_2 supseteq R$ and $T$ is reflexive. Then $(r,r')in R Rightarrow (r,r')in T_1times T_2 Rightarrow rin T_1 land r'in T_2$. Since $T$ is reflexive, then $(r,r)in T_1times T_2$ which means $rin T_2$ and that implies $T_1 subseteq T_2$. Furthermore, we have $R_1subseteq T_1$ so $R_1 subseteq T_2$. Thus, $i_{R_1times R_1}subseteq T_1times T_2$. Therefore, $S=R_1times R_2 cup i_{R_1 times R_2}subseteq T$. Clearly, $Rsubseteq S$ so S is the reflexive closure of $R$.
My concern: Is my argument correct? I was reading Velleman's text and he instead had $S=R cup i_A$, which is what I don't understand why.
proof-verification elementary-set-theory relations
asked Jan 25 at 2:53
TheLast CipherTheLast Cipher
708715
$endgroup$
Proof Attempt: Suppose $R$ is a relation on set $A$; $R=R_1 times R_2 subset A times A$. We assert $S = R cup i_{R_1 times R_1}$ to be the closure of $R$ such that $i_{R_1 times R_1}={(x,x) vert x in R_1}$. We want to show $S$ is reflexive. Let $(r,r')in S$. Then either $(r,r')in R_1 times R_2$ or $(r,r')in i_{R_1 times R_1}$. If $(r,r')in R_1times R_1$, then $rin R_1$ so $(r,r)in i_{R_1times R_1}$. If $(r,r')in i_{R_1times R_1}$, then $r=r'$. In any case, $(r,r)in S$ so $S$ is reflexive. Moreover, to show $S$ is the smallest reflexive relation that contains $R$, suppose $T=T_1times T_2 supseteq R$ and $T$ is reflexive. Then $(r,r')in R Rightarrow (r,r')in T_1times T_2 Rightarrow rin T_1 land r'in T_2$. Since $T$ is reflexive, then $(r,r)in T_1times T_2$ which means $rin T_2$ and that implies $T_1 subseteq T_2$. Furthermore, we have $R_1subseteq T_1$ so $R_1 subseteq T_2$. Thus, $i_{R_1times R_1}subseteq T_1times T_2$. Therefore, $S=R_1times R_2 cup i_{R_1 times R_2}subseteq T$. Clearly, $Rsubseteq S$ so S is the reflexive closure of $R$.
My concern: Is my argument correct? I was reading Velleman's text and he instead had $S=R cup i_A$, which is what I don't understand why.
proof-verification elementary-set-theory relations
proof-verification elementary-set-theory relations
asked Jan 25 at 2:53
TheLast CipherTheLast Cipher
708715
asked Jan 25 at 2:53
TheLast CipherTheLast Cipher
708715
asked Jan 25 at 2:53
TheLast CipherTheLast Cipher
708715
asked Jan 25 at 2:53
TheLast CipherTheLast Cipher
708715
asked Jan 25 at 2:53
TheLast CipherTheLast Cipher
708715
708715
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
There are a few problems here.
First and foremost you seem to using a rather non-standard meaning of the word "reflexive". (Which is a polite way of saying I think you're misunderstanding what it means).
The usual definition is
A relation $R$ on $A$ is called reflexive if: For every $ain A$ it holds that $(a,a)in R$.
Your proof looks like you think it is something like
... if: For every $(a,b)in R$ it holds that $(a,a)in R$.
which is wrong. Do you see the difference? This misunderstanding dooms your attempt from the outset.
But there's more: You're assuming that $R$ is an arbitrary relation and then immediately write $R=R_1times R_2$. Later you're writing $T=T_1times T_2$ for an arbitrary $T$. But you can't assume that a random relation can be written as a cartesian product!
As a simple example, $R={(1,2),(3,4)}$ cannot be written as $R_1times R_2$ for any $R_1$ and $R_2$. Namely, $(1,2)in R_1times R_2$ can only be true $1in R_1$. And $(3,4)in R_1times R_2$ can only be true if $4in R_2$. But then certainly $(1,4)in R_1times R_2$, but $(1,4)$ is not in my $R$, so this $R$ cannot be $R_1times R_2$.
answered Jan 25 at 3:49
Henning MakholmHenning Makholm
241k17308549
$endgroup$
$begingroup$
That definition is completely different! Thank you for the corrections!
$endgroup$
– TheLast Cipher
Jan 25 at 4:07
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%2f3086645%2fevery-relation-on-a-set-has-reflexive-closure%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
There are a few problems here.
First and foremost you seem to using a rather non-standard meaning of the word "reflexive". (Which is a polite way of saying I think you're misunderstanding what it means).
The usual definition is
A relation $R$ on $A$ is called reflexive if: For every $ain A$ it holds that $(a,a)in R$.
Your proof looks like you think it is something like
... if: For every $(a,b)in R$ it holds that $(a,a)in R$.
which is wrong. Do you see the difference? This misunderstanding dooms your attempt from the outset.
But there's more: You're assuming that $R$ is an arbitrary relation and then immediately write $R=R_1times R_2$. Later you're writing $T=T_1times T_2$ for an arbitrary $T$. But you can't assume that a random relation can be written as a cartesian product!
As a simple example, $R={(1,2),(3,4)}$ cannot be written as $R_1times R_2$ for any $R_1$ and $R_2$. Namely, $(1,2)in R_1times R_2$ can only be true $1in R_1$. And $(3,4)in R_1times R_2$ can only be true if $4in R_2$. But then certainly $(1,4)in R_1times R_2$, but $(1,4)$ is not in my $R$, so this $R$ cannot be $R_1times R_2$.
answered Jan 25 at 3:49
Henning MakholmHenning Makholm
241k17308549
$endgroup$
$begingroup$
That definition is completely different! Thank you for the corrections!
$endgroup$
– TheLast Cipher
Jan 25 at 4:07
add a comment |
$begingroup$
There are a few problems here.
First and foremost you seem to using a rather non-standard meaning of the word "reflexive". (Which is a polite way of saying I think you're misunderstanding what it means).
The usual definition is
A relation $R$ on $A$ is called reflexive if: For every $ain A$ it holds that $(a,a)in R$.
Your proof looks like you think it is something like
... if: For every $(a,b)in R$ it holds that $(a,a)in R$.
which is wrong. Do you see the difference? This misunderstanding dooms your attempt from the outset.
But there's more: You're assuming that $R$ is an arbitrary relation and then immediately write $R=R_1times R_2$. Later you're writing $T=T_1times T_2$ for an arbitrary $T$. But you can't assume that a random relation can be written as a cartesian product!
As a simple example, $R={(1,2),(3,4)}$ cannot be written as $R_1times R_2$ for any $R_1$ and $R_2$. Namely, $(1,2)in R_1times R_2$ can only be true $1in R_1$. And $(3,4)in R_1times R_2$ can only be true if $4in R_2$. But then certainly $(1,4)in R_1times R_2$, but $(1,4)$ is not in my $R$, so this $R$ cannot be $R_1times R_2$.
answered Jan 25 at 3:49
Henning MakholmHenning Makholm
241k17308549
$endgroup$
$begingroup$
That definition is completely different! Thank you for the corrections!
$endgroup$
– TheLast Cipher
Jan 25 at 4:07
add a comment |
$begingroup$
There are a few problems here.
First and foremost you seem to using a rather non-standard meaning of the word "reflexive". (Which is a polite way of saying I think you're misunderstanding what it means).
The usual definition is
A relation $R$ on $A$ is called reflexive if: For every $ain A$ it holds that $(a,a)in R$.
Your proof looks like you think it is something like
... if: For every $(a,b)in R$ it holds that $(a,a)in R$.
which is wrong. Do you see the difference? This misunderstanding dooms your attempt from the outset.
But there's more: You're assuming that $R$ is an arbitrary relation and then immediately write $R=R_1times R_2$. Later you're writing $T=T_1times T_2$ for an arbitrary $T$. But you can't assume that a random relation can be written as a cartesian product!
As a simple example, $R={(1,2),(3,4)}$ cannot be written as $R_1times R_2$ for any $R_1$ and $R_2$. Namely, $(1,2)in R_1times R_2$ can only be true $1in R_1$. And $(3,4)in R_1times R_2$ can only be true if $4in R_2$. But then certainly $(1,4)in R_1times R_2$, but $(1,4)$ is not in my $R$, so this $R$ cannot be $R_1times R_2$.
answered Jan 25 at 3:49
Henning MakholmHenning Makholm
241k17308549
$endgroup$
There are a few problems here.
First and foremost you seem to using a rather non-standard meaning of the word "reflexive". (Which is a polite way of saying I think you're misunderstanding what it means).
The usual definition is
A relation $R$ on $A$ is called reflexive if: For every $ain A$ it holds that $(a,a)in R$.
Your proof looks like you think it is something like
... if: For every $(a,b)in R$ it holds that $(a,a)in R$.
which is wrong. Do you see the difference? This misunderstanding dooms your attempt from the outset.
But there's more: You're assuming that $R$ is an arbitrary relation and then immediately write $R=R_1times R_2$. Later you're writing $T=T_1times T_2$ for an arbitrary $T$. But you can't assume that a random relation can be written as a cartesian product!
As a simple example, $R={(1,2),(3,4)}$ cannot be written as $R_1times R_2$ for any $R_1$ and $R_2$. Namely, $(1,2)in R_1times R_2$ can only be true $1in R_1$. And $(3,4)in R_1times R_2$ can only be true if $4in R_2$. But then certainly $(1,4)in R_1times R_2$, but $(1,4)$ is not in my $R$, so this $R$ cannot be $R_1times R_2$.
answered Jan 25 at 3:49
Henning MakholmHenning Makholm
241k17308549
answered Jan 25 at 3:49
Henning MakholmHenning Makholm
241k17308549
answered Jan 25 at 3:49
Henning MakholmHenning Makholm
241k17308549
answered Jan 25 at 3:49
Henning MakholmHenning Makholm
241k17308549
241k17308549
$begingroup$
That definition is completely different! Thank you for the corrections!
$endgroup$
– TheLast Cipher
Jan 25 at 4:07
add a comment |
$begingroup$
That definition is completely different! Thank you for the corrections!
$endgroup$
– TheLast Cipher
Jan 25 at 4:07
$begingroup$
That definition is completely different! Thank you for the corrections!
$endgroup$
– TheLast Cipher
Jan 25 at 4:07
$begingroup$
That definition is completely different! Thank you for the corrections!
$endgroup$
– TheLast Cipher
Jan 25 at 4:07
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%2f3086645%2fevery-relation-on-a-set-has-reflexive-closure%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
