Mixing
How to prove the relation is transitive?
$begingroup$
Problem:
Consider the relation R on $N$ defined by
$x$R$y$ iff $2$ divides $x + y$.
Prove that R is an equivalent relation
My work:
I know that to prove that a relation is an equivalent relation, I have to show that it's reflexive, symmetric and transitive.
So first reflexive. Suppose there is an integer $a$ in $N$. Then $a + a = 2a$.
$2$ divides $2a$ because $2a = (2)(a)$. Therefore this relation is reflexive because $(a,a)$ will be in the relation.
For symmetric - Suppose there is an ordered pair $(a, b)$ for which $a$ and $b$ are both in $N$. If
$2 mid (a + b)$ then $2$ will also divide $b + a$ because of the commutative law of addition
Commutative Law. Therefore the ordered pair $(b, a)$ will also be in the relation and the relation will therefore be symmetric
For transitive,
Suppose $(a, b)$ and $(b, c)$ are in the relation. Now I have to show that $(a, c)$ will also be in the relation.
$a + b = 2k$ for some integer $k$, solving for $b$, we have
$b = 2k - a$.
$b + c = 2m$ for some integer $m$. Substituting for $b$, we have
$2k - a + c = 2m$
$c - a = 2(k + m)$
Algebraically I have shown the $2$ divides $c - a$. Is there some algebra step or trick I can use to show that $2$ will also divide $c + a$?
proof-verification proof-writing relations equivalence-relations
edited Feb 17 '16 at 1:34
Hanul Jeon
17.7k42881
asked Mar 7 '15 at 0:33
committedandroidercommittedandroider
97141837
$endgroup$
add a comment |
$begingroup$
Problem:
Consider the relation R on $N$ defined by
$x$R$y$ iff $2$ divides $x + y$.
Prove that R is an equivalent relation
My work:
I know that to prove that a relation is an equivalent relation, I have to show that it's reflexive, symmetric and transitive.
So first reflexive. Suppose there is an integer $a$ in $N$. Then $a + a = 2a$.
$2$ divides $2a$ because $2a = (2)(a)$. Therefore this relation is reflexive because $(a,a)$ will be in the relation.
For symmetric - Suppose there is an ordered pair $(a, b)$ for which $a$ and $b$ are both in $N$. If
$2 mid (a + b)$ then $2$ will also divide $b + a$ because of the commutative law of addition
Commutative Law. Therefore the ordered pair $(b, a)$ will also be in the relation and the relation will therefore be symmetric
For transitive,
Suppose $(a, b)$ and $(b, c)$ are in the relation. Now I have to show that $(a, c)$ will also be in the relation.
$a + b = 2k$ for some integer $k$, solving for $b$, we have
$b = 2k - a$.
$b + c = 2m$ for some integer $m$. Substituting for $b$, we have
$2k - a + c = 2m$
$c - a = 2(k + m)$
Algebraically I have shown the $2$ divides $c - a$. Is there some algebra step or trick I can use to show that $2$ will also divide $c + a$?
proof-verification proof-writing relations equivalence-relations
edited Feb 17 '16 at 1:34
Hanul Jeon
17.7k42881
asked Mar 7 '15 at 0:33
committedandroidercommittedandroider
97141837
$endgroup$
$begingroup$
Note that $c+a=(c-a)+2a$.
$endgroup$
– AMPerrine
Mar 7 '15 at 0:41
$begingroup$
@AMPerrine Damn that's clever. So you add 2a to both sides and you have 2(k + m + a) on the other?
$endgroup$
– committedandroider
Mar 7 '15 at 0:54
add a comment |
$begingroup$
Problem:
Consider the relation R on $N$ defined by
$x$R$y$ iff $2$ divides $x + y$.
Prove that R is an equivalent relation
My work:
I know that to prove that a relation is an equivalent relation, I have to show that it's reflexive, symmetric and transitive.
So first reflexive. Suppose there is an integer $a$ in $N$. Then $a + a = 2a$.
$2$ divides $2a$ because $2a = (2)(a)$. Therefore this relation is reflexive because $(a,a)$ will be in the relation.
For symmetric - Suppose there is an ordered pair $(a, b)$ for which $a$ and $b$ are both in $N$. If
$2 mid (a + b)$ then $2$ will also divide $b + a$ because of the commutative law of addition
Commutative Law. Therefore the ordered pair $(b, a)$ will also be in the relation and the relation will therefore be symmetric
For transitive,
Suppose $(a, b)$ and $(b, c)$ are in the relation. Now I have to show that $(a, c)$ will also be in the relation.
$a + b = 2k$ for some integer $k$, solving for $b$, we have
$b = 2k - a$.
$b + c = 2m$ for some integer $m$. Substituting for $b$, we have
$2k - a + c = 2m$
$c - a = 2(k + m)$
Algebraically I have shown the $2$ divides $c - a$. Is there some algebra step or trick I can use to show that $2$ will also divide $c + a$?
proof-verification proof-writing relations equivalence-relations
edited Feb 17 '16 at 1:34
Hanul Jeon
17.7k42881
asked Mar 7 '15 at 0:33
committedandroidercommittedandroider
97141837
$endgroup$
Problem:
Consider the relation R on $N$ defined by
$x$R$y$ iff $2$ divides $x + y$.
Prove that R is an equivalent relation
My work:
I know that to prove that a relation is an equivalent relation, I have to show that it's reflexive, symmetric and transitive.
So first reflexive. Suppose there is an integer $a$ in $N$. Then $a + a = 2a$.
$2$ divides $2a$ because $2a = (2)(a)$. Therefore this relation is reflexive because $(a,a)$ will be in the relation.
For symmetric - Suppose there is an ordered pair $(a, b)$ for which $a$ and $b$ are both in $N$. If
$2 mid (a + b)$ then $2$ will also divide $b + a$ because of the commutative law of addition
Commutative Law. Therefore the ordered pair $(b, a)$ will also be in the relation and the relation will therefore be symmetric
For transitive,
Suppose $(a, b)$ and $(b, c)$ are in the relation. Now I have to show that $(a, c)$ will also be in the relation.
$a + b = 2k$ for some integer $k$, solving for $b$, we have
$b = 2k - a$.
$b + c = 2m$ for some integer $m$. Substituting for $b$, we have
$2k - a + c = 2m$
$c - a = 2(k + m)$
Algebraically I have shown the $2$ divides $c - a$. Is there some algebra step or trick I can use to show that $2$ will also divide $c + a$?
proof-verification proof-writing relations equivalence-relations
proof-verification proof-writing relations equivalence-relations
edited Feb 17 '16 at 1:34
Hanul Jeon
17.7k42881
asked Mar 7 '15 at 0:33
committedandroidercommittedandroider
97141837
edited Feb 17 '16 at 1:34
Hanul Jeon
17.7k42881
asked Mar 7 '15 at 0:33
committedandroidercommittedandroider
97141837
edited Feb 17 '16 at 1:34
Hanul Jeon
17.7k42881
edited Feb 17 '16 at 1:34
Hanul Jeon
17.7k42881
edited Feb 17 '16 at 1:34
Hanul Jeon
17.7k42881
17.7k42881
asked Mar 7 '15 at 0:33
committedandroidercommittedandroider
97141837
asked Mar 7 '15 at 0:33
committedandroidercommittedandroider
97141837
asked Mar 7 '15 at 0:33
committedandroidercommittedandroider
97141837
97141837
$begingroup$
Note that $c+a=(c-a)+2a$.
$endgroup$
– AMPerrine
Mar 7 '15 at 0:41
$begingroup$
@AMPerrine Damn that's clever. So you add 2a to both sides and you have 2(k + m + a) on the other?
$endgroup$
– committedandroider
Mar 7 '15 at 0:54
add a comment |
$begingroup$
Note that $c+a=(c-a)+2a$.
$endgroup$
– AMPerrine
Mar 7 '15 at 0:41
$begingroup$
@AMPerrine Damn that's clever. So you add 2a to both sides and you have 2(k + m + a) on the other?
$endgroup$
– committedandroider
Mar 7 '15 at 0:54
$begingroup$
Note that $c+a=(c-a)+2a$.
$endgroup$
– AMPerrine
Mar 7 '15 at 0:41
$begingroup$
Note that $c+a=(c-a)+2a$.
$endgroup$
– AMPerrine
Mar 7 '15 at 0:41
$begingroup$
@AMPerrine Damn that's clever. So you add 2a to both sides and you have 2(k + m + a) on the other?
$endgroup$
– committedandroider
Mar 7 '15 at 0:54
$begingroup$
@AMPerrine Damn that's clever. So you add 2a to both sides and you have 2(k + m + a) on the other?
$endgroup$
– committedandroider
Mar 7 '15 at 0:54
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Start with the relationships, where $a,b,c,k,j in mathbb{Z}$:
$$a R b, bRc rightarrow 2|(a+b), 2|(b+c)$$
$$(a+b) = 2k, (b+c) = 2j$$
$$a+2b+c = 2(k+j)$$
$$a+c = 2(k+j)-2b$$
$$a+c = 2(k+j-b)$$
And thus $2$ divides $(a+c)$. Therefore, if $aRb,bRc$, then $aRc$, satisfying the definition of transitivity.
edited Feb 3 at 12:30
OmG
2,5371824
answered Mar 7 '15 at 0:37
TokenToucanTokenToucan
2,4171519
$endgroup$
$begingroup$
is it possible to do it with the substitution strategy I was using?
$endgroup$
– committedandroider
Mar 7 '15 at 0:41
$begingroup$
Sort of. Go from$2k-a+c = 2m$ to $2k+c = 2m +a$. Then take both sides mod 2; $2k+ctextrm{ mod }2 = 2m + atextrm{ mod }2$. Cancel the even numbers: $atextrm{ mod }2=ctextrm{ mod }2$. If they have the same parity, then their sum has an even parity.
$endgroup$
– TokenToucan
Mar 7 '15 at 0:43
add a comment |
$begingroup$
The sum of two numbers is even iff the numbers are the same parity, so $xRy$ is equivalent to "$x$ and $y$ have the same parity". Now transitivity is obvious.
answered Mar 7 '15 at 0:44
Jack MJack M
18.9k33883
$endgroup$
$begingroup$
You wouldn't have to do any proofs then would you?
$endgroup$
– committedandroider
Mar 7 '15 at 0:59
$begingroup$
@committedandroider You would probably want to prove that the sum of two numbers is even iff the numbers are the same parity (which would end up being as long as proving transitivity directly), but it has the advantage of making it clearer why the relation is transitive.
$endgroup$
– Jack M
Mar 7 '15 at 1:02
add a comment |
Your Answer
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%2f1178976%2fhow-to-prove-the-relation-is-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$
Start with the relationships, where $a,b,c,k,j in mathbb{Z}$:
$$a R b, bRc rightarrow 2|(a+b), 2|(b+c)$$
$$(a+b) = 2k, (b+c) = 2j$$
$$a+2b+c = 2(k+j)$$
$$a+c = 2(k+j)-2b$$
$$a+c = 2(k+j-b)$$
And thus $2$ divides $(a+c)$. Therefore, if $aRb,bRc$, then $aRc$, satisfying the definition of transitivity.
edited Feb 3 at 12:30
OmG
2,5371824
answered Mar 7 '15 at 0:37
TokenToucanTokenToucan
2,4171519
$endgroup$
$begingroup$
is it possible to do it with the substitution strategy I was using?
$endgroup$
– committedandroider
Mar 7 '15 at 0:41
$begingroup$
Sort of. Go from$2k-a+c = 2m$ to $2k+c = 2m +a$. Then take both sides mod 2; $2k+ctextrm{ mod }2 = 2m + atextrm{ mod }2$. Cancel the even numbers: $atextrm{ mod }2=ctextrm{ mod }2$. If they have the same parity, then their sum has an even parity.
$endgroup$
– TokenToucan
Mar 7 '15 at 0:43
add a comment |
$begingroup$
Start with the relationships, where $a,b,c,k,j in mathbb{Z}$:
$$a R b, bRc rightarrow 2|(a+b), 2|(b+c)$$
$$(a+b) = 2k, (b+c) = 2j$$
$$a+2b+c = 2(k+j)$$
$$a+c = 2(k+j)-2b$$
$$a+c = 2(k+j-b)$$
And thus $2$ divides $(a+c)$. Therefore, if $aRb,bRc$, then $aRc$, satisfying the definition of transitivity.
edited Feb 3 at 12:30
OmG
2,5371824
answered Mar 7 '15 at 0:37
TokenToucanTokenToucan
2,4171519
$endgroup$
$begingroup$
is it possible to do it with the substitution strategy I was using?
$endgroup$
– committedandroider
Mar 7 '15 at 0:41
$begingroup$
Sort of. Go from$2k-a+c = 2m$ to $2k+c = 2m +a$. Then take both sides mod 2; $2k+ctextrm{ mod }2 = 2m + atextrm{ mod }2$. Cancel the even numbers: $atextrm{ mod }2=ctextrm{ mod }2$. If they have the same parity, then their sum has an even parity.
$endgroup$
– TokenToucan
Mar 7 '15 at 0:43
add a comment |
$begingroup$
Start with the relationships, where $a,b,c,k,j in mathbb{Z}$:
$$a R b, bRc rightarrow 2|(a+b), 2|(b+c)$$
$$(a+b) = 2k, (b+c) = 2j$$
$$a+2b+c = 2(k+j)$$
$$a+c = 2(k+j)-2b$$
$$a+c = 2(k+j-b)$$
And thus $2$ divides $(a+c)$. Therefore, if $aRb,bRc$, then $aRc$, satisfying the definition of transitivity.
edited Feb 3 at 12:30
OmG
2,5371824
answered Mar 7 '15 at 0:37
TokenToucanTokenToucan
2,4171519
$endgroup$
Start with the relationships, where $a,b,c,k,j in mathbb{Z}$:
$$a R b, bRc rightarrow 2|(a+b), 2|(b+c)$$
$$(a+b) = 2k, (b+c) = 2j$$
$$a+2b+c = 2(k+j)$$
$$a+c = 2(k+j)-2b$$
$$a+c = 2(k+j-b)$$
And thus $2$ divides $(a+c)$. Therefore, if $aRb,bRc$, then $aRc$, satisfying the definition of transitivity.
edited Feb 3 at 12:30
OmG
2,5371824
answered Mar 7 '15 at 0:37
TokenToucanTokenToucan
2,4171519
edited Feb 3 at 12:30
OmG
2,5371824
edited Feb 3 at 12:30
OmG
2,5371824
edited Feb 3 at 12:30
OmG
2,5371824
2,5371824
answered Mar 7 '15 at 0:37
TokenToucanTokenToucan
2,4171519
answered Mar 7 '15 at 0:37
TokenToucanTokenToucan
2,4171519
answered Mar 7 '15 at 0:37
TokenToucanTokenToucan
2,4171519
2,4171519
$begingroup$
is it possible to do it with the substitution strategy I was using?
$endgroup$
– committedandroider
Mar 7 '15 at 0:41
$begingroup$
Sort of. Go from$2k-a+c = 2m$ to $2k+c = 2m +a$. Then take both sides mod 2; $2k+ctextrm{ mod }2 = 2m + atextrm{ mod }2$. Cancel the even numbers: $atextrm{ mod }2=ctextrm{ mod }2$. If they have the same parity, then their sum has an even parity.
$endgroup$
– TokenToucan
Mar 7 '15 at 0:43
add a comment |
$begingroup$
is it possible to do it with the substitution strategy I was using?
$endgroup$
– committedandroider
Mar 7 '15 at 0:41
$begingroup$
Sort of. Go from$2k-a+c = 2m$ to $2k+c = 2m +a$. Then take both sides mod 2; $2k+ctextrm{ mod }2 = 2m + atextrm{ mod }2$. Cancel the even numbers: $atextrm{ mod }2=ctextrm{ mod }2$. If they have the same parity, then their sum has an even parity.
$endgroup$
– TokenToucan
Mar 7 '15 at 0:43
$begingroup$
is it possible to do it with the substitution strategy I was using?
$endgroup$
– committedandroider
Mar 7 '15 at 0:41
$begingroup$
is it possible to do it with the substitution strategy I was using?
$endgroup$
– committedandroider
Mar 7 '15 at 0:41
$begingroup$
Sort of. Go from$2k-a+c = 2m$ to $2k+c = 2m +a$. Then take both sides mod 2; $2k+ctextrm{ mod }2 = 2m + atextrm{ mod }2$. Cancel the even numbers: $atextrm{ mod }2=ctextrm{ mod }2$. If they have the same parity, then their sum has an even parity.
$endgroup$
– TokenToucan
Mar 7 '15 at 0:43
$begingroup$
Sort of. Go from$2k-a+c = 2m$ to $2k+c = 2m +a$. Then take both sides mod 2; $2k+ctextrm{ mod }2 = 2m + atextrm{ mod }2$. Cancel the even numbers: $atextrm{ mod }2=ctextrm{ mod }2$. If they have the same parity, then their sum has an even parity.
$endgroup$
– TokenToucan
Mar 7 '15 at 0:43
add a comment |
$begingroup$
The sum of two numbers is even iff the numbers are the same parity, so $xRy$ is equivalent to "$x$ and $y$ have the same parity". Now transitivity is obvious.
answered Mar 7 '15 at 0:44
Jack MJack M
18.9k33883
$endgroup$
$begingroup$
You wouldn't have to do any proofs then would you?
$endgroup$
– committedandroider
Mar 7 '15 at 0:59
$begingroup$
@committedandroider You would probably want to prove that the sum of two numbers is even iff the numbers are the same parity (which would end up being as long as proving transitivity directly), but it has the advantage of making it clearer why the relation is transitive.
$endgroup$
– Jack M
Mar 7 '15 at 1:02
add a comment |
$begingroup$
The sum of two numbers is even iff the numbers are the same parity, so $xRy$ is equivalent to "$x$ and $y$ have the same parity". Now transitivity is obvious.
answered Mar 7 '15 at 0:44
Jack MJack M
18.9k33883
$endgroup$
$begingroup$
You wouldn't have to do any proofs then would you?
$endgroup$
– committedandroider
Mar 7 '15 at 0:59
$begingroup$
@committedandroider You would probably want to prove that the sum of two numbers is even iff the numbers are the same parity (which would end up being as long as proving transitivity directly), but it has the advantage of making it clearer why the relation is transitive.
$endgroup$
– Jack M
Mar 7 '15 at 1:02
add a comment |
$begingroup$
The sum of two numbers is even iff the numbers are the same parity, so $xRy$ is equivalent to "$x$ and $y$ have the same parity". Now transitivity is obvious.
answered Mar 7 '15 at 0:44
Jack MJack M
18.9k33883
$endgroup$
The sum of two numbers is even iff the numbers are the same parity, so $xRy$ is equivalent to "$x$ and $y$ have the same parity". Now transitivity is obvious.
answered Mar 7 '15 at 0:44
Jack MJack M
18.9k33883
answered Mar 7 '15 at 0:44
Jack MJack M
18.9k33883
answered Mar 7 '15 at 0:44
Jack MJack M
18.9k33883
answered Mar 7 '15 at 0:44
Jack MJack M
18.9k33883
18.9k33883
$begingroup$
You wouldn't have to do any proofs then would you?
$endgroup$
– committedandroider
Mar 7 '15 at 0:59
$begingroup$
@committedandroider You would probably want to prove that the sum of two numbers is even iff the numbers are the same parity (which would end up being as long as proving transitivity directly), but it has the advantage of making it clearer why the relation is transitive.
$endgroup$
– Jack M
Mar 7 '15 at 1:02
add a comment |
$begingroup$
You wouldn't have to do any proofs then would you?
$endgroup$
– committedandroider
Mar 7 '15 at 0:59
$begingroup$
@committedandroider You would probably want to prove that the sum of two numbers is even iff the numbers are the same parity (which would end up being as long as proving transitivity directly), but it has the advantage of making it clearer why the relation is transitive.
$endgroup$
– Jack M
Mar 7 '15 at 1:02
$begingroup$
You wouldn't have to do any proofs then would you?
$endgroup$
– committedandroider
Mar 7 '15 at 0:59
$begingroup$
You wouldn't have to do any proofs then would you?
$endgroup$
– committedandroider
Mar 7 '15 at 0:59
$begingroup$
@committedandroider You would probably want to prove that the sum of two numbers is even iff the numbers are the same parity (which would end up being as long as proving transitivity directly), but it has the advantage of making it clearer why the relation is transitive.
$endgroup$
– Jack M
Mar 7 '15 at 1:02
$begingroup$
@committedandroider You would probably want to prove that the sum of two numbers is even iff the numbers are the same parity (which would end up being as long as proving transitivity directly), but it has the advantage of making it clearer why the relation is transitive.
$endgroup$
– Jack M
Mar 7 '15 at 1:02
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%2f1178976%2fhow-to-prove-the-relation-is-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
$begingroup$
Note that $c+a=(c-a)+2a$.
$endgroup$
– AMPerrine
Mar 7 '15 at 0:41
$begingroup$
@AMPerrine Damn that's clever. So you add 2a to both sides and you have 2(k + m + a) on the other?
$endgroup$
– committedandroider
Mar 7 '15 at 0:54