What are the equivalence classes of this relation?
$begingroup$
Let $f colon X → X$ be an injective function.
For $y, z ∈ X$, define $y sim z$ to mean there
exists an integer $n ≥ 0$ such that either $f^n(z) = y$ or $f^n(y) = z$. (Here $f^0(z) = z$ for all $z ∈ X$.)
Prove this is defines an equivalence relation on $X$.
Give a list of the different possibilities for the
resulting equivalence classes
My attempt: Proving it was an equivalence relation was simple as it involved only using definitions of the function, but I have no idea what the equivalence classes must be.
relations equivalence-relations
edited Dec 11 '18 at 23:11
egreg
183k1486204
asked Dec 11 '18 at 21:15
childishsadbinochildishsadbino
1148
$endgroup$
add a comment |
$begingroup$
Let $f colon X → X$ be an injective function.
For $y, z ∈ X$, define $y sim z$ to mean there
exists an integer $n ≥ 0$ such that either $f^n(z) = y$ or $f^n(y) = z$. (Here $f^0(z) = z$ for all $z ∈ X$.)
Prove this is defines an equivalence relation on $X$.
Give a list of the different possibilities for the
resulting equivalence classes
My attempt: Proving it was an equivalence relation was simple as it involved only using definitions of the function, but I have no idea what the equivalence classes must be.
relations equivalence-relations
edited Dec 11 '18 at 23:11
egreg
183k1486204
asked Dec 11 '18 at 21:15
childishsadbinochildishsadbino
1148
$endgroup$
$begingroup$
My guess is that you're being asked to describe the "shape" of the possible equivalence classes.
$endgroup$
– rogerl
Dec 11 '18 at 21:21
$begingroup$
I do not know how to even begin thinking about that, which is my main issue.
$endgroup$
– childishsadbino
Dec 11 '18 at 21:24
add a comment |
$begingroup$
Let $f colon X → X$ be an injective function.
For $y, z ∈ X$, define $y sim z$ to mean there
exists an integer $n ≥ 0$ such that either $f^n(z) = y$ or $f^n(y) = z$. (Here $f^0(z) = z$ for all $z ∈ X$.)
Prove this is defines an equivalence relation on $X$.
Give a list of the different possibilities for the
resulting equivalence classes
My attempt: Proving it was an equivalence relation was simple as it involved only using definitions of the function, but I have no idea what the equivalence classes must be.
relations equivalence-relations
edited Dec 11 '18 at 23:11
egreg
183k1486204
asked Dec 11 '18 at 21:15
childishsadbinochildishsadbino
1148
$endgroup$
Let $f colon X → X$ be an injective function.
For $y, z ∈ X$, define $y sim z$ to mean there
exists an integer $n ≥ 0$ such that either $f^n(z) = y$ or $f^n(y) = z$. (Here $f^0(z) = z$ for all $z ∈ X$.)
Prove this is defines an equivalence relation on $X$.
Give a list of the different possibilities for the
resulting equivalence classes
My attempt: Proving it was an equivalence relation was simple as it involved only using definitions of the function, but I have no idea what the equivalence classes must be.
relations equivalence-relations
relations equivalence-relations
edited Dec 11 '18 at 23:11
egreg
183k1486204
asked Dec 11 '18 at 21:15
childishsadbinochildishsadbino
1148
edited Dec 11 '18 at 23:11
egreg
183k1486204
asked Dec 11 '18 at 21:15
childishsadbinochildishsadbino
1148
edited Dec 11 '18 at 23:11
egreg
183k1486204
edited Dec 11 '18 at 23:11
egreg
183k1486204
edited Dec 11 '18 at 23:11
egreg
183k1486204
183k1486204
asked Dec 11 '18 at 21:15
childishsadbinochildishsadbino
1148
asked Dec 11 '18 at 21:15
childishsadbinochildishsadbino
1148
asked Dec 11 '18 at 21:15
childishsadbinochildishsadbino
1148
1148
$begingroup$
My guess is that you're being asked to describe the "shape" of the possible equivalence classes.
$endgroup$
– rogerl
Dec 11 '18 at 21:21
$begingroup$
I do not know how to even begin thinking about that, which is my main issue.
$endgroup$
– childishsadbino
Dec 11 '18 at 21:24
add a comment |
$begingroup$
My guess is that you're being asked to describe the "shape" of the possible equivalence classes.
$endgroup$
– rogerl
Dec 11 '18 at 21:21
$begingroup$
I do not know how to even begin thinking about that, which is my main issue.
$endgroup$
– childishsadbino
Dec 11 '18 at 21:24
$begingroup$
My guess is that you're being asked to describe the "shape" of the possible equivalence classes.
$endgroup$
– rogerl
Dec 11 '18 at 21:21
$begingroup$
My guess is that you're being asked to describe the "shape" of the possible equivalence classes.
$endgroup$
– rogerl
Dec 11 '18 at 21:21
$begingroup$
I do not know how to even begin thinking about that, which is my main issue.
$endgroup$
– childishsadbino
Dec 11 '18 at 21:24
$begingroup$
I do not know how to even begin thinking about that, which is my main issue.
$endgroup$
– childishsadbino
Dec 11 '18 at 21:24
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The question is asking for various possibilities for the equivalence classes. So
1). If $x in X$ is a fixed point of the function i.e. $f(x)=x$, then $[x]={x}$. Due to injectivity, no other element will map to $x$, so it is the only member in it’s class.
2). If there exists a finite sequence $x_1, x_2, ldots ,x_k$, such that $f(x_i)=x_{i+1}$ and $f(x_k)=x_1$. Then $[x_1]={x_1, x_2, ldots ,x_k }$.
3). Other possibility is to have infinite orbits.
answered Dec 11 '18 at 21:42
Anurag AAnurag A
26.2k12251
$endgroup$
$begingroup$
The "infinite orbit" case might also split into the case ${ ldots, x_{-2}, x_{-1}, x_0, x_1, x_2, ldots }$ where $x_{n+1} = f(x_n)$ for all $n in mathbb{Z}$, or the case ${ x_0, x_1, x_2, ldots }$ where $x_{n+1} = f(x_n)$ for all $n in mathbb{N}$ but $x_0$ is not in the image of $f$.
$endgroup$
– Daniel Schepler
Dec 11 '18 at 23:51
$begingroup$
I understand 1 and 2, but could you please explain what you mean by infinite orbits?
$endgroup$
– childishsadbino
Dec 12 '18 at 4:34
1
$begingroup$
@childishsadbino Here is an example that can help. Consider $f(x_{i})=x_{i+2}$. Then $f(x_1)=x_3, f(x_3)=x_5, ldots$ and $f(x_2)=x_4, f(x_4)=x_6, ldots$. Thus $[x_1]={x_1,x_3,x_5, ldots}$ and $[x_2]={x_2,x_4,x_6, ldots}$. So they are infinite orbits.
$endgroup$
– Anurag A
Dec 12 '18 at 4:51
$begingroup$
Are these the only possibilities?
$endgroup$
– childishsadbino
Dec 12 '18 at 4:54
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%2f3035832%2fwhat-are-the-equivalence-classes-of-this-relation%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$
The question is asking for various possibilities for the equivalence classes. So
1). If $x in X$ is a fixed point of the function i.e. $f(x)=x$, then $[x]={x}$. Due to injectivity, no other element will map to $x$, so it is the only member in it’s class.
2). If there exists a finite sequence $x_1, x_2, ldots ,x_k$, such that $f(x_i)=x_{i+1}$ and $f(x_k)=x_1$. Then $[x_1]={x_1, x_2, ldots ,x_k }$.
3). Other possibility is to have infinite orbits.
answered Dec 11 '18 at 21:42
Anurag AAnurag A
26.2k12251
$endgroup$
$begingroup$
The "infinite orbit" case might also split into the case ${ ldots, x_{-2}, x_{-1}, x_0, x_1, x_2, ldots }$ where $x_{n+1} = f(x_n)$ for all $n in mathbb{Z}$, or the case ${ x_0, x_1, x_2, ldots }$ where $x_{n+1} = f(x_n)$ for all $n in mathbb{N}$ but $x_0$ is not in the image of $f$.
$endgroup$
– Daniel Schepler
Dec 11 '18 at 23:51
$begingroup$
I understand 1 and 2, but could you please explain what you mean by infinite orbits?
$endgroup$
– childishsadbino
Dec 12 '18 at 4:34
1
$begingroup$
@childishsadbino Here is an example that can help. Consider $f(x_{i})=x_{i+2}$. Then $f(x_1)=x_3, f(x_3)=x_5, ldots$ and $f(x_2)=x_4, f(x_4)=x_6, ldots$. Thus $[x_1]={x_1,x_3,x_5, ldots}$ and $[x_2]={x_2,x_4,x_6, ldots}$. So they are infinite orbits.
$endgroup$
– Anurag A
Dec 12 '18 at 4:51
$begingroup$
Are these the only possibilities?
$endgroup$
– childishsadbino
Dec 12 '18 at 4:54
add a comment |
$begingroup$
The question is asking for various possibilities for the equivalence classes. So
1). If $x in X$ is a fixed point of the function i.e. $f(x)=x$, then $[x]={x}$. Due to injectivity, no other element will map to $x$, so it is the only member in it’s class.
2). If there exists a finite sequence $x_1, x_2, ldots ,x_k$, such that $f(x_i)=x_{i+1}$ and $f(x_k)=x_1$. Then $[x_1]={x_1, x_2, ldots ,x_k }$.
3). Other possibility is to have infinite orbits.
answered Dec 11 '18 at 21:42
Anurag AAnurag A
26.2k12251
$endgroup$
$begingroup$
The "infinite orbit" case might also split into the case ${ ldots, x_{-2}, x_{-1}, x_0, x_1, x_2, ldots }$ where $x_{n+1} = f(x_n)$ for all $n in mathbb{Z}$, or the case ${ x_0, x_1, x_2, ldots }$ where $x_{n+1} = f(x_n)$ for all $n in mathbb{N}$ but $x_0$ is not in the image of $f$.
$endgroup$
– Daniel Schepler
Dec 11 '18 at 23:51
$begingroup$
I understand 1 and 2, but could you please explain what you mean by infinite orbits?
$endgroup$
– childishsadbino
Dec 12 '18 at 4:34
1
$begingroup$
@childishsadbino Here is an example that can help. Consider $f(x_{i})=x_{i+2}$. Then $f(x_1)=x_3, f(x_3)=x_5, ldots$ and $f(x_2)=x_4, f(x_4)=x_6, ldots$. Thus $[x_1]={x_1,x_3,x_5, ldots}$ and $[x_2]={x_2,x_4,x_6, ldots}$. So they are infinite orbits.
$endgroup$
– Anurag A
Dec 12 '18 at 4:51
$begingroup$
Are these the only possibilities?
$endgroup$
– childishsadbino
Dec 12 '18 at 4:54
add a comment |
$begingroup$
The question is asking for various possibilities for the equivalence classes. So
1). If $x in X$ is a fixed point of the function i.e. $f(x)=x$, then $[x]={x}$. Due to injectivity, no other element will map to $x$, so it is the only member in it’s class.
2). If there exists a finite sequence $x_1, x_2, ldots ,x_k$, such that $f(x_i)=x_{i+1}$ and $f(x_k)=x_1$. Then $[x_1]={x_1, x_2, ldots ,x_k }$.
3). Other possibility is to have infinite orbits.
answered Dec 11 '18 at 21:42
Anurag AAnurag A
26.2k12251
$endgroup$
The question is asking for various possibilities for the equivalence classes. So
1). If $x in X$ is a fixed point of the function i.e. $f(x)=x$, then $[x]={x}$. Due to injectivity, no other element will map to $x$, so it is the only member in it’s class.
2). If there exists a finite sequence $x_1, x_2, ldots ,x_k$, such that $f(x_i)=x_{i+1}$ and $f(x_k)=x_1$. Then $[x_1]={x_1, x_2, ldots ,x_k }$.
3). Other possibility is to have infinite orbits.
answered Dec 11 '18 at 21:42
Anurag AAnurag A
26.2k12251
edited Dec 11 '18 at 22:48
answered Dec 11 '18 at 21:42
Anurag AAnurag A
26.2k12251
answered Dec 11 '18 at 21:42
Anurag AAnurag A
26.2k12251
answered Dec 11 '18 at 21:42
Anurag AAnurag A
26.2k12251
26.2k12251
$begingroup$
The "infinite orbit" case might also split into the case ${ ldots, x_{-2}, x_{-1}, x_0, x_1, x_2, ldots }$ where $x_{n+1} = f(x_n)$ for all $n in mathbb{Z}$, or the case ${ x_0, x_1, x_2, ldots }$ where $x_{n+1} = f(x_n)$ for all $n in mathbb{N}$ but $x_0$ is not in the image of $f$.
$endgroup$
– Daniel Schepler
Dec 11 '18 at 23:51
$begingroup$
I understand 1 and 2, but could you please explain what you mean by infinite orbits?
$endgroup$
– childishsadbino
Dec 12 '18 at 4:34
1
$begingroup$
@childishsadbino Here is an example that can help. Consider $f(x_{i})=x_{i+2}$. Then $f(x_1)=x_3, f(x_3)=x_5, ldots$ and $f(x_2)=x_4, f(x_4)=x_6, ldots$. Thus $[x_1]={x_1,x_3,x_5, ldots}$ and $[x_2]={x_2,x_4,x_6, ldots}$. So they are infinite orbits.
$endgroup$
– Anurag A
Dec 12 '18 at 4:51
$begingroup$
Are these the only possibilities?
$endgroup$
– childishsadbino
Dec 12 '18 at 4:54
add a comment |
$begingroup$
The "infinite orbit" case might also split into the case ${ ldots, x_{-2}, x_{-1}, x_0, x_1, x_2, ldots }$ where $x_{n+1} = f(x_n)$ for all $n in mathbb{Z}$, or the case ${ x_0, x_1, x_2, ldots }$ where $x_{n+1} = f(x_n)$ for all $n in mathbb{N}$ but $x_0$ is not in the image of $f$.
$endgroup$
– Daniel Schepler
Dec 11 '18 at 23:51
$begingroup$
I understand 1 and 2, but could you please explain what you mean by infinite orbits?
$endgroup$
– childishsadbino
Dec 12 '18 at 4:34
1
$begingroup$
@childishsadbino Here is an example that can help. Consider $f(x_{i})=x_{i+2}$. Then $f(x_1)=x_3, f(x_3)=x_5, ldots$ and $f(x_2)=x_4, f(x_4)=x_6, ldots$. Thus $[x_1]={x_1,x_3,x_5, ldots}$ and $[x_2]={x_2,x_4,x_6, ldots}$. So they are infinite orbits.
$endgroup$
– Anurag A
Dec 12 '18 at 4:51
$begingroup$
Are these the only possibilities?
$endgroup$
– childishsadbino
Dec 12 '18 at 4:54
$begingroup$
The "infinite orbit" case might also split into the case ${ ldots, x_{-2}, x_{-1}, x_0, x_1, x_2, ldots }$ where $x_{n+1} = f(x_n)$ for all $n in mathbb{Z}$, or the case ${ x_0, x_1, x_2, ldots }$ where $x_{n+1} = f(x_n)$ for all $n in mathbb{N}$ but $x_0$ is not in the image of $f$.
$endgroup$
– Daniel Schepler
Dec 11 '18 at 23:51
$begingroup$
The "infinite orbit" case might also split into the case ${ ldots, x_{-2}, x_{-1}, x_0, x_1, x_2, ldots }$ where $x_{n+1} = f(x_n)$ for all $n in mathbb{Z}$, or the case ${ x_0, x_1, x_2, ldots }$ where $x_{n+1} = f(x_n)$ for all $n in mathbb{N}$ but $x_0$ is not in the image of $f$.
$endgroup$
– Daniel Schepler
Dec 11 '18 at 23:51
$begingroup$
I understand 1 and 2, but could you please explain what you mean by infinite orbits?
$endgroup$
– childishsadbino
Dec 12 '18 at 4:34
$begingroup$
I understand 1 and 2, but could you please explain what you mean by infinite orbits?
$endgroup$
– childishsadbino
Dec 12 '18 at 4:34
1
1
$begingroup$
@childishsadbino Here is an example that can help. Consider $f(x_{i})=x_{i+2}$. Then $f(x_1)=x_3, f(x_3)=x_5, ldots$ and $f(x_2)=x_4, f(x_4)=x_6, ldots$. Thus $[x_1]={x_1,x_3,x_5, ldots}$ and $[x_2]={x_2,x_4,x_6, ldots}$. So they are infinite orbits.
$endgroup$
– Anurag A
Dec 12 '18 at 4:51
$begingroup$
@childishsadbino Here is an example that can help. Consider $f(x_{i})=x_{i+2}$. Then $f(x_1)=x_3, f(x_3)=x_5, ldots$ and $f(x_2)=x_4, f(x_4)=x_6, ldots$. Thus $[x_1]={x_1,x_3,x_5, ldots}$ and $[x_2]={x_2,x_4,x_6, ldots}$. So they are infinite orbits.
$endgroup$
– Anurag A
Dec 12 '18 at 4:51
$begingroup$
Are these the only possibilities?
$endgroup$
– childishsadbino
Dec 12 '18 at 4:54
$begingroup$
Are these the only possibilities?
$endgroup$
– childishsadbino
Dec 12 '18 at 4:54
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%2f3035832%2fwhat-are-the-equivalence-classes-of-this-relation%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$
My guess is that you're being asked to describe the "shape" of the possible equivalence classes.
$endgroup$
– rogerl
Dec 11 '18 at 21:21
$begingroup$
I do not know how to even begin thinking about that, which is my main issue.
$endgroup$
– childishsadbino
Dec 11 '18 at 21:24