Finding the equivalence classes of a seemingly infinite set The 2019 Stack Overflow Developer Survey Results Are InWhich are the equivalence classes for the following relation?Trouble understanding equivalence relations and equivalence classesThe relationship between an equivalence relation, equivalence classes, and partitions?Equivalence relations and classesFinding distinct equivalence classesFind equivalence classesDefine equivalence relation on set of real numbers so distinct equivalence classes are $[2k,2k+2)$Finding a bijection between two equivalence classesHow do I describe the equivalence classes in $mathbfR$ of the relation $xmathsfRy$ if $x - y in mathbfZ$?Equivalence relation and equivalence classes specific question
Geography at the pixel level
Why hard-Brexiteers don't insist on a hard border to prevent illegal immigration after Brexit?
Why is the maximum length of OpenWrt’s root password 8 characters?
Why do we hear so much about the Trump administration deciding to impose and then remove tariffs?
How to deal with fear of taking dependencies
Button changing it's text & action. Good or terrible?
What is the closest word meaning "respect for time / mindful"
Can a rogue use sneak attack with weapons that have the thrown property even if they are not thrown?
Worn-tile Scrabble
When should I buy a clipper card after flying to OAK?
How to save as into a customized destination on macOS?
Aging parents with no investments
Have you ever entered Singapore using a different passport or name?
Identify boardgame from Big movie
Should I use my personal e-mail address, or my workplace one, when registering to external websites for work purposes?
FPGA - DIY Programming
Did 3000BC Egyptians use meteoric iron weapons?
What to do when moving next to a bird sanctuary with a loosely-domesticated cat?
Return to UK after being refused entry years previously
Multiply Two Integer Polynomials
Why not take a picture of a closer black hole?
What is the motivation for a law requiring 2 parties to consent for recording a conversation
Is an up-to-date browser secure on an out-of-date OS?
Is a "Democratic" Oligarchy-Style System Possible?
Finding the equivalence classes of a seemingly infinite set
The 2019 Stack Overflow Developer Survey Results Are InWhich are the equivalence classes for the following relation?Trouble understanding equivalence relations and equivalence classesThe relationship between an equivalence relation, equivalence classes, and partitions?Equivalence relations and classesFinding distinct equivalence classesFind equivalence classesDefine equivalence relation on set of real numbers so distinct equivalence classes are $[2k,2k+2)$Finding a bijection between two equivalence classesHow do I describe the equivalence classes in $mathbfR$ of the relation $xmathsfRy$ if $x - y in mathbfZ$?Equivalence relation and equivalence classes specific question
$begingroup$
I've encountered this question:
$A = mathbb Z$ and $R = , (x,y) mid x + x^2 = y + y^2 ,$ is an equivalence relation on $A$. What are its equivalence classes?
The relation is an equivalence relation. To my understanding, every pair $(x,x)$ should belong to $R$ and also the pair $(-1,0)$. What are my equivalence classes? are they not infinite? According to my understanding of the definition, they are, but I don't think that is the correct answer.
Thank you very much.
discrete-mathematics equivalence-relations
$endgroup$
add a comment |
$begingroup$
I've encountered this question:
$A = mathbb Z$ and $R = , (x,y) mid x + x^2 = y + y^2 ,$ is an equivalence relation on $A$. What are its equivalence classes?
The relation is an equivalence relation. To my understanding, every pair $(x,x)$ should belong to $R$ and also the pair $(-1,0)$. What are my equivalence classes? are they not infinite? According to my understanding of the definition, they are, but I don't think that is the correct answer.
Thank you very much.
discrete-mathematics equivalence-relations
$endgroup$
$begingroup$
I think that this question is best tackled by doing a bunch of calculations. Calculate $n + n^2$ for a bunch of integers, and you'll see what the equivalence classes are.
$endgroup$
– Mike Pierce
Mar 23 at 16:35
2
$begingroup$
Note that $x + x^2 = y + y^2 iff x - y = y^2 - x^2$. Does that suggest anything?
$endgroup$
– M. Vinay
Mar 23 at 16:37
$begingroup$
Thank you for your replies. I do understand which pairs belong in the relation, but I don't understand which equivalence classes work. Can you give me one more push to the right direction?
$endgroup$
– Omri. B
Mar 23 at 16:39
$begingroup$
Do you? $(-1, 0)$ is not the only pair in the relation other than the pairs of equal integers. So the equivalence class of $x$ contains $x$ itself and… .
$endgroup$
– M. Vinay
Mar 23 at 17:01
$begingroup$
Thank you! I'll crunch some numbers and see what i'm missing.
$endgroup$
– Omri. B
Mar 23 at 17:20
add a comment |
$begingroup$
I've encountered this question:
$A = mathbb Z$ and $R = , (x,y) mid x + x^2 = y + y^2 ,$ is an equivalence relation on $A$. What are its equivalence classes?
The relation is an equivalence relation. To my understanding, every pair $(x,x)$ should belong to $R$ and also the pair $(-1,0)$. What are my equivalence classes? are they not infinite? According to my understanding of the definition, they are, but I don't think that is the correct answer.
Thank you very much.
discrete-mathematics equivalence-relations
$endgroup$
I've encountered this question:
$A = mathbb Z$ and $R = , (x,y) mid x + x^2 = y + y^2 ,$ is an equivalence relation on $A$. What are its equivalence classes?
The relation is an equivalence relation. To my understanding, every pair $(x,x)$ should belong to $R$ and also the pair $(-1,0)$. What are my equivalence classes? are they not infinite? According to my understanding of the definition, they are, but I don't think that is the correct answer.
Thank you very much.
discrete-mathematics equivalence-relations
discrete-mathematics equivalence-relations
edited Mar 23 at 17:03
M. Vinay
7,35822136
7,35822136
asked Mar 23 at 16:27
Omri. BOmri. B
52
52
$begingroup$
I think that this question is best tackled by doing a bunch of calculations. Calculate $n + n^2$ for a bunch of integers, and you'll see what the equivalence classes are.
$endgroup$
– Mike Pierce
Mar 23 at 16:35
2
$begingroup$
Note that $x + x^2 = y + y^2 iff x - y = y^2 - x^2$. Does that suggest anything?
$endgroup$
– M. Vinay
Mar 23 at 16:37
$begingroup$
Thank you for your replies. I do understand which pairs belong in the relation, but I don't understand which equivalence classes work. Can you give me one more push to the right direction?
$endgroup$
– Omri. B
Mar 23 at 16:39
$begingroup$
Do you? $(-1, 0)$ is not the only pair in the relation other than the pairs of equal integers. So the equivalence class of $x$ contains $x$ itself and… .
$endgroup$
– M. Vinay
Mar 23 at 17:01
$begingroup$
Thank you! I'll crunch some numbers and see what i'm missing.
$endgroup$
– Omri. B
Mar 23 at 17:20
add a comment |
$begingroup$
I think that this question is best tackled by doing a bunch of calculations. Calculate $n + n^2$ for a bunch of integers, and you'll see what the equivalence classes are.
$endgroup$
– Mike Pierce
Mar 23 at 16:35
2
$begingroup$
Note that $x + x^2 = y + y^2 iff x - y = y^2 - x^2$. Does that suggest anything?
$endgroup$
– M. Vinay
Mar 23 at 16:37
$begingroup$
Thank you for your replies. I do understand which pairs belong in the relation, but I don't understand which equivalence classes work. Can you give me one more push to the right direction?
$endgroup$
– Omri. B
Mar 23 at 16:39
$begingroup$
Do you? $(-1, 0)$ is not the only pair in the relation other than the pairs of equal integers. So the equivalence class of $x$ contains $x$ itself and… .
$endgroup$
– M. Vinay
Mar 23 at 17:01
$begingroup$
Thank you! I'll crunch some numbers and see what i'm missing.
$endgroup$
– Omri. B
Mar 23 at 17:20
$begingroup$
I think that this question is best tackled by doing a bunch of calculations. Calculate $n + n^2$ for a bunch of integers, and you'll see what the equivalence classes are.
$endgroup$
– Mike Pierce
Mar 23 at 16:35
$begingroup$
I think that this question is best tackled by doing a bunch of calculations. Calculate $n + n^2$ for a bunch of integers, and you'll see what the equivalence classes are.
$endgroup$
– Mike Pierce
Mar 23 at 16:35
2
2
$begingroup$
Note that $x + x^2 = y + y^2 iff x - y = y^2 - x^2$. Does that suggest anything?
$endgroup$
– M. Vinay
Mar 23 at 16:37
$begingroup$
Note that $x + x^2 = y + y^2 iff x - y = y^2 - x^2$. Does that suggest anything?
$endgroup$
– M. Vinay
Mar 23 at 16:37
$begingroup$
Thank you for your replies. I do understand which pairs belong in the relation, but I don't understand which equivalence classes work. Can you give me one more push to the right direction?
$endgroup$
– Omri. B
Mar 23 at 16:39
$begingroup$
Thank you for your replies. I do understand which pairs belong in the relation, but I don't understand which equivalence classes work. Can you give me one more push to the right direction?
$endgroup$
– Omri. B
Mar 23 at 16:39
$begingroup$
Do you? $(-1, 0)$ is not the only pair in the relation other than the pairs of equal integers. So the equivalence class of $x$ contains $x$ itself and… .
$endgroup$
– M. Vinay
Mar 23 at 17:01
$begingroup$
Do you? $(-1, 0)$ is not the only pair in the relation other than the pairs of equal integers. So the equivalence class of $x$ contains $x$ itself and… .
$endgroup$
– M. Vinay
Mar 23 at 17:01
$begingroup$
Thank you! I'll crunch some numbers and see what i'm missing.
$endgroup$
– Omri. B
Mar 23 at 17:20
$begingroup$
Thank you! I'll crunch some numbers and see what i'm missing.
$endgroup$
– Omri. B
Mar 23 at 17:20
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
One way we can go about it is to pick a particular number, and find the numbers $R$-equivalent to it.
For example, if I want the numbers $R$-equivalent to $0,$ I need to find all $yinBbb Z$ such that $0+0^2=y+y^2,$ meaning that $0=y+y^2=y(y+1),$ so $y=0$ or $y+1=0,$ so $y=0$ or $y=-1.$ So, one $R$-equivalence class is $-1,0.$
How about another? We've already taken care of $0$ and $-1,$ so how about $1$? Well, for that, we want all $yinBbb Z$ such that $1+1^2=y+y^2,$ so $2=y+y^2,$ so $0=y^2+y-2=(y-1)(y+2),$ so $y-1=0$ or $y+2=0,$ and so another $R$-equivalence class is $-2,1.$
The more we try, the more we should see that each equivalence class has two elements, and that they follow a pattern. One key observation, though, is that we are always able to rearrange our equation into a form with the left-hand side equal to $0$ and the right-hand side a product of two distinct factors. This suggests that we might be able to do that ahead of time, and thereby find all equivalence classes at once!
Indeed, the following are equivalent: $$x+x^2=y+y^2\x-y=y^2-x^2\x-y=(y-x)(y+x)\0=(y-x)(y+x)+y-x\0=(y-x)(y+x+1)$$ Thus, $x$ and $y$ are $R$-equivalent if and only if one of the following equivalent conditions holds:
- $0=(y-x)(y+x+1)$
$y-x=0$ or $y+x+1=0$
$y=x$ or $y=-x-1$
From this last, we can show that every equivalence class has exactly two elements, and in particular that the equivalence classes will be the sets $x,-x-1$ for integers $xge 0.$
$endgroup$
$begingroup$
Thanks for the detailed answer!
$endgroup$
– Omri. B
Mar 23 at 19:03
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%2f3159519%2ffinding-the-equivalence-classes-of-a-seemingly-infinite-set%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$
One way we can go about it is to pick a particular number, and find the numbers $R$-equivalent to it.
For example, if I want the numbers $R$-equivalent to $0,$ I need to find all $yinBbb Z$ such that $0+0^2=y+y^2,$ meaning that $0=y+y^2=y(y+1),$ so $y=0$ or $y+1=0,$ so $y=0$ or $y=-1.$ So, one $R$-equivalence class is $-1,0.$
How about another? We've already taken care of $0$ and $-1,$ so how about $1$? Well, for that, we want all $yinBbb Z$ such that $1+1^2=y+y^2,$ so $2=y+y^2,$ so $0=y^2+y-2=(y-1)(y+2),$ so $y-1=0$ or $y+2=0,$ and so another $R$-equivalence class is $-2,1.$
The more we try, the more we should see that each equivalence class has two elements, and that they follow a pattern. One key observation, though, is that we are always able to rearrange our equation into a form with the left-hand side equal to $0$ and the right-hand side a product of two distinct factors. This suggests that we might be able to do that ahead of time, and thereby find all equivalence classes at once!
Indeed, the following are equivalent: $$x+x^2=y+y^2\x-y=y^2-x^2\x-y=(y-x)(y+x)\0=(y-x)(y+x)+y-x\0=(y-x)(y+x+1)$$ Thus, $x$ and $y$ are $R$-equivalent if and only if one of the following equivalent conditions holds:
- $0=(y-x)(y+x+1)$
$y-x=0$ or $y+x+1=0$
$y=x$ or $y=-x-1$
From this last, we can show that every equivalence class has exactly two elements, and in particular that the equivalence classes will be the sets $x,-x-1$ for integers $xge 0.$
$endgroup$
$begingroup$
Thanks for the detailed answer!
$endgroup$
– Omri. B
Mar 23 at 19:03
add a comment |
$begingroup$
One way we can go about it is to pick a particular number, and find the numbers $R$-equivalent to it.
For example, if I want the numbers $R$-equivalent to $0,$ I need to find all $yinBbb Z$ such that $0+0^2=y+y^2,$ meaning that $0=y+y^2=y(y+1),$ so $y=0$ or $y+1=0,$ so $y=0$ or $y=-1.$ So, one $R$-equivalence class is $-1,0.$
How about another? We've already taken care of $0$ and $-1,$ so how about $1$? Well, for that, we want all $yinBbb Z$ such that $1+1^2=y+y^2,$ so $2=y+y^2,$ so $0=y^2+y-2=(y-1)(y+2),$ so $y-1=0$ or $y+2=0,$ and so another $R$-equivalence class is $-2,1.$
The more we try, the more we should see that each equivalence class has two elements, and that they follow a pattern. One key observation, though, is that we are always able to rearrange our equation into a form with the left-hand side equal to $0$ and the right-hand side a product of two distinct factors. This suggests that we might be able to do that ahead of time, and thereby find all equivalence classes at once!
Indeed, the following are equivalent: $$x+x^2=y+y^2\x-y=y^2-x^2\x-y=(y-x)(y+x)\0=(y-x)(y+x)+y-x\0=(y-x)(y+x+1)$$ Thus, $x$ and $y$ are $R$-equivalent if and only if one of the following equivalent conditions holds:
- $0=(y-x)(y+x+1)$
$y-x=0$ or $y+x+1=0$
$y=x$ or $y=-x-1$
From this last, we can show that every equivalence class has exactly two elements, and in particular that the equivalence classes will be the sets $x,-x-1$ for integers $xge 0.$
$endgroup$
$begingroup$
Thanks for the detailed answer!
$endgroup$
– Omri. B
Mar 23 at 19:03
add a comment |
$begingroup$
One way we can go about it is to pick a particular number, and find the numbers $R$-equivalent to it.
For example, if I want the numbers $R$-equivalent to $0,$ I need to find all $yinBbb Z$ such that $0+0^2=y+y^2,$ meaning that $0=y+y^2=y(y+1),$ so $y=0$ or $y+1=0,$ so $y=0$ or $y=-1.$ So, one $R$-equivalence class is $-1,0.$
How about another? We've already taken care of $0$ and $-1,$ so how about $1$? Well, for that, we want all $yinBbb Z$ such that $1+1^2=y+y^2,$ so $2=y+y^2,$ so $0=y^2+y-2=(y-1)(y+2),$ so $y-1=0$ or $y+2=0,$ and so another $R$-equivalence class is $-2,1.$
The more we try, the more we should see that each equivalence class has two elements, and that they follow a pattern. One key observation, though, is that we are always able to rearrange our equation into a form with the left-hand side equal to $0$ and the right-hand side a product of two distinct factors. This suggests that we might be able to do that ahead of time, and thereby find all equivalence classes at once!
Indeed, the following are equivalent: $$x+x^2=y+y^2\x-y=y^2-x^2\x-y=(y-x)(y+x)\0=(y-x)(y+x)+y-x\0=(y-x)(y+x+1)$$ Thus, $x$ and $y$ are $R$-equivalent if and only if one of the following equivalent conditions holds:
- $0=(y-x)(y+x+1)$
$y-x=0$ or $y+x+1=0$
$y=x$ or $y=-x-1$
From this last, we can show that every equivalence class has exactly two elements, and in particular that the equivalence classes will be the sets $x,-x-1$ for integers $xge 0.$
$endgroup$
One way we can go about it is to pick a particular number, and find the numbers $R$-equivalent to it.
For example, if I want the numbers $R$-equivalent to $0,$ I need to find all $yinBbb Z$ such that $0+0^2=y+y^2,$ meaning that $0=y+y^2=y(y+1),$ so $y=0$ or $y+1=0,$ so $y=0$ or $y=-1.$ So, one $R$-equivalence class is $-1,0.$
How about another? We've already taken care of $0$ and $-1,$ so how about $1$? Well, for that, we want all $yinBbb Z$ such that $1+1^2=y+y^2,$ so $2=y+y^2,$ so $0=y^2+y-2=(y-1)(y+2),$ so $y-1=0$ or $y+2=0,$ and so another $R$-equivalence class is $-2,1.$
The more we try, the more we should see that each equivalence class has two elements, and that they follow a pattern. One key observation, though, is that we are always able to rearrange our equation into a form with the left-hand side equal to $0$ and the right-hand side a product of two distinct factors. This suggests that we might be able to do that ahead of time, and thereby find all equivalence classes at once!
Indeed, the following are equivalent: $$x+x^2=y+y^2\x-y=y^2-x^2\x-y=(y-x)(y+x)\0=(y-x)(y+x)+y-x\0=(y-x)(y+x+1)$$ Thus, $x$ and $y$ are $R$-equivalent if and only if one of the following equivalent conditions holds:
- $0=(y-x)(y+x+1)$
$y-x=0$ or $y+x+1=0$
$y=x$ or $y=-x-1$
From this last, we can show that every equivalence class has exactly two elements, and in particular that the equivalence classes will be the sets $x,-x-1$ for integers $xge 0.$
edited Mar 24 at 12:55
answered Mar 23 at 18:40
Cameron BuieCameron Buie
86.7k773161
86.7k773161
$begingroup$
Thanks for the detailed answer!
$endgroup$
– Omri. B
Mar 23 at 19:03
add a comment |
$begingroup$
Thanks for the detailed answer!
$endgroup$
– Omri. B
Mar 23 at 19:03
$begingroup$
Thanks for the detailed answer!
$endgroup$
– Omri. B
Mar 23 at 19:03
$begingroup$
Thanks for the detailed answer!
$endgroup$
– Omri. B
Mar 23 at 19:03
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%2f3159519%2ffinding-the-equivalence-classes-of-a-seemingly-infinite-set%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$
I think that this question is best tackled by doing a bunch of calculations. Calculate $n + n^2$ for a bunch of integers, and you'll see what the equivalence classes are.
$endgroup$
– Mike Pierce
Mar 23 at 16:35
2
$begingroup$
Note that $x + x^2 = y + y^2 iff x - y = y^2 - x^2$. Does that suggest anything?
$endgroup$
– M. Vinay
Mar 23 at 16:37
$begingroup$
Thank you for your replies. I do understand which pairs belong in the relation, but I don't understand which equivalence classes work. Can you give me one more push to the right direction?
$endgroup$
– Omri. B
Mar 23 at 16:39
$begingroup$
Do you? $(-1, 0)$ is not the only pair in the relation other than the pairs of equal integers. So the equivalence class of $x$ contains $x$ itself and… .
$endgroup$
– M. Vinay
Mar 23 at 17:01
$begingroup$
Thank you! I'll crunch some numbers and see what i'm missing.
$endgroup$
– Omri. B
Mar 23 at 17:20