Isomorphic equivalence relations and partitions
Let $R_1$, $R_2$ ∈ R(X) be equivalence relations on X. Define $R_1$ and $R_2$ to be isomorphic
if there exists a bijection f : X → X such that the following holds:
For all y, z ∈ X : (y, z) ∈ $R_1$ if and only if (f(y), f(z)) ∈ $R_2$.
(a) Define what it means for two partitions P1, P2 ∈ P(X) to be isomorphic. (An answer to this
is correct if it lets you prove the next part.)
(b) Prove two equivalence relations $R_1 and R_2$ are isomorphic if and only if the partitions φ($R_1$)
and φ($R_2$) are isomorphic. (Here φ is the bijection from the previous problem.)
(c) Let X = {1, 2, 3, 4, 5}. Up to isomorphism, how many equivalence relations are there on X?
My attempt:
As I understand it, equivalence relations can be put in a bijection with partitions, and so if there is a bijection between elements of one relation to another, then there is a bijection between elements of one partition with another. This would make the partitions fit the definition of isomorphism mentioned in the question, therefore proving (b).
I do not understand what (c) is asking at all, and I am looking for a formal proof/way to write what I am thinking, if what I'm thinking is correct at all.
elementary-set-theory relations equivalence-relations
asked Dec 12 '18 at 7:59
childishsadbinochildishsadbino
1148
add a comment |
Let $R_1$, $R_2$ ∈ R(X) be equivalence relations on X. Define $R_1$ and $R_2$ to be isomorphic
if there exists a bijection f : X → X such that the following holds:
For all y, z ∈ X : (y, z) ∈ $R_1$ if and only if (f(y), f(z)) ∈ $R_2$.
(a) Define what it means for two partitions P1, P2 ∈ P(X) to be isomorphic. (An answer to this
is correct if it lets you prove the next part.)
(b) Prove two equivalence relations $R_1 and R_2$ are isomorphic if and only if the partitions φ($R_1$)
and φ($R_2$) are isomorphic. (Here φ is the bijection from the previous problem.)
(c) Let X = {1, 2, 3, 4, 5}. Up to isomorphism, how many equivalence relations are there on X?
My attempt:
As I understand it, equivalence relations can be put in a bijection with partitions, and so if there is a bijection between elements of one relation to another, then there is a bijection between elements of one partition with another. This would make the partitions fit the definition of isomorphism mentioned in the question, therefore proving (b).
I do not understand what (c) is asking at all, and I am looking for a formal proof/way to write what I am thinking, if what I'm thinking is correct at all.
elementary-set-theory relations equivalence-relations
asked Dec 12 '18 at 7:59
childishsadbinochildishsadbino
1148
add a comment |
Let $R_1$, $R_2$ ∈ R(X) be equivalence relations on X. Define $R_1$ and $R_2$ to be isomorphic
if there exists a bijection f : X → X such that the following holds:
For all y, z ∈ X : (y, z) ∈ $R_1$ if and only if (f(y), f(z)) ∈ $R_2$.
(a) Define what it means for two partitions P1, P2 ∈ P(X) to be isomorphic. (An answer to this
is correct if it lets you prove the next part.)
(b) Prove two equivalence relations $R_1 and R_2$ are isomorphic if and only if the partitions φ($R_1$)
and φ($R_2$) are isomorphic. (Here φ is the bijection from the previous problem.)
(c) Let X = {1, 2, 3, 4, 5}. Up to isomorphism, how many equivalence relations are there on X?
My attempt:
As I understand it, equivalence relations can be put in a bijection with partitions, and so if there is a bijection between elements of one relation to another, then there is a bijection between elements of one partition with another. This would make the partitions fit the definition of isomorphism mentioned in the question, therefore proving (b).
I do not understand what (c) is asking at all, and I am looking for a formal proof/way to write what I am thinking, if what I'm thinking is correct at all.
elementary-set-theory relations equivalence-relations
asked Dec 12 '18 at 7:59
childishsadbinochildishsadbino
1148
Let $R_1$, $R_2$ ∈ R(X) be equivalence relations on X. Define $R_1$ and $R_2$ to be isomorphic
if there exists a bijection f : X → X such that the following holds:
For all y, z ∈ X : (y, z) ∈ $R_1$ if and only if (f(y), f(z)) ∈ $R_2$.
(a) Define what it means for two partitions P1, P2 ∈ P(X) to be isomorphic. (An answer to this
is correct if it lets you prove the next part.)
(b) Prove two equivalence relations $R_1 and R_2$ are isomorphic if and only if the partitions φ($R_1$)
and φ($R_2$) are isomorphic. (Here φ is the bijection from the previous problem.)
(c) Let X = {1, 2, 3, 4, 5}. Up to isomorphism, how many equivalence relations are there on X?
My attempt:
As I understand it, equivalence relations can be put in a bijection with partitions, and so if there is a bijection between elements of one relation to another, then there is a bijection between elements of one partition with another. This would make the partitions fit the definition of isomorphism mentioned in the question, therefore proving (b).
I do not understand what (c) is asking at all, and I am looking for a formal proof/way to write what I am thinking, if what I'm thinking is correct at all.
elementary-set-theory relations equivalence-relations
elementary-set-theory relations equivalence-relations
asked Dec 12 '18 at 7:59
childishsadbinochildishsadbino
1148
asked Dec 12 '18 at 7:59
childishsadbinochildishsadbino
1148
asked Dec 12 '18 at 7:59
childishsadbinochildishsadbino
1148
asked Dec 12 '18 at 7:59
childishsadbinochildishsadbino
1148
asked Dec 12 '18 at 7:59
childishsadbinochildishsadbino
1148
1148
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
Hint: notice that with your definition in place two partitions in sets $A_1,..,A_n$ and $B_1,..,B_n$ are isomorphic iff when ordered in ascending order by their number of elements they give the same sequence
answered Dec 12 '18 at 8:11
Μάρκος ΚαραμέρηςΜάρκος Καραμέρης
48410
add a comment |
Hint: In c) one requires to enumerate all partitions of the set $X$ (up to isomorphism). First calculate the number of partitions of $X$. This is the Bell number $B(5)$, where $B(n) = sum_{k=1}^n S(n,k)$ and $S(n,k)$ is the number of partitions of $n$ into $k$ parts (Stirling number of the 2nd kind).
We have $B(1)=1$, with partition ${{1}}$,
$B(2)=2$ with partitions ${{1,2}}$, ${{1},{2}}$,
$B(3)=5$ with partitions ${{1},{{2},{3}}$, ${{1,2},{3}}$, ${{1,3},{2}}$, ${{2,3},{1}}$, ${{1,2,3}}$, and so on.
In view of the isomorphism classes, you just need to consider the types of partitions (see comment below).
BY REQUEST: For instance, take the bijection $f=left(begin{array}{ccc}1&2&3\2&3&1end{array}right)$. Then the partition ${{1,2},{3}}$ is mapped to the partition ${{f(1),f(2)},{f(3)}} = {{2,3},{1}}$.
answered Dec 12 '18 at 8:11
WuestenfuxWuestenfux
3,7061411
Note that c) asks for all isomorphic partitions. This means that the second, third and fourth example in $B(3)$ are the same
– Μάρκος Καραμέρης
Dec 12 '18 at 8:23
True, but I'd start with $B(n)$.
– Wuestenfux
Dec 12 '18 at 8:26
Can you please explain what it means for partitions to be isomorphic?
– childishsadbino
Dec 14 '18 at 4:12
See example at the end.
– Wuestenfux
Dec 14 '18 at 9:27
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%2f3036384%2fisomorphic-equivalence-relations-and-partitions%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
Hint: notice that with your definition in place two partitions in sets $A_1,..,A_n$ and $B_1,..,B_n$ are isomorphic iff when ordered in ascending order by their number of elements they give the same sequence
answered Dec 12 '18 at 8:11
Μάρκος ΚαραμέρηςΜάρκος Καραμέρης
48410
add a comment |
Hint: notice that with your definition in place two partitions in sets $A_1,..,A_n$ and $B_1,..,B_n$ are isomorphic iff when ordered in ascending order by their number of elements they give the same sequence
answered Dec 12 '18 at 8:11
Μάρκος ΚαραμέρηςΜάρκος Καραμέρης
48410
add a comment |
Hint: notice that with your definition in place two partitions in sets $A_1,..,A_n$ and $B_1,..,B_n$ are isomorphic iff when ordered in ascending order by their number of elements they give the same sequence
answered Dec 12 '18 at 8:11
Μάρκος ΚαραμέρηςΜάρκος Καραμέρης
48410
Hint: notice that with your definition in place two partitions in sets $A_1,..,A_n$ and $B_1,..,B_n$ are isomorphic iff when ordered in ascending order by their number of elements they give the same sequence
answered Dec 12 '18 at 8:11
Μάρκος ΚαραμέρηςΜάρκος Καραμέρης
48410
edited Dec 12 '18 at 8:30
answered Dec 12 '18 at 8:11
Μάρκος ΚαραμέρηςΜάρκος Καραμέρης
48410
answered Dec 12 '18 at 8:11
Μάρκος ΚαραμέρηςΜάρκος Καραμέρης
48410
answered Dec 12 '18 at 8:11
Μάρκος ΚαραμέρηςΜάρκος Καραμέρης
48410
48410
add a comment |
add a comment |
Hint: In c) one requires to enumerate all partitions of the set $X$ (up to isomorphism). First calculate the number of partitions of $X$. This is the Bell number $B(5)$, where $B(n) = sum_{k=1}^n S(n,k)$ and $S(n,k)$ is the number of partitions of $n$ into $k$ parts (Stirling number of the 2nd kind).
We have $B(1)=1$, with partition ${{1}}$,
$B(2)=2$ with partitions ${{1,2}}$, ${{1},{2}}$,
$B(3)=5$ with partitions ${{1},{{2},{3}}$, ${{1,2},{3}}$, ${{1,3},{2}}$, ${{2,3},{1}}$, ${{1,2,3}}$, and so on.
In view of the isomorphism classes, you just need to consider the types of partitions (see comment below).
BY REQUEST: For instance, take the bijection $f=left(begin{array}{ccc}1&2&3\2&3&1end{array}right)$. Then the partition ${{1,2},{3}}$ is mapped to the partition ${{f(1),f(2)},{f(3)}} = {{2,3},{1}}$.
answered Dec 12 '18 at 8:11
WuestenfuxWuestenfux
3,7061411
Note that c) asks for all isomorphic partitions. This means that the second, third and fourth example in $B(3)$ are the same
– Μάρκος Καραμέρης
Dec 12 '18 at 8:23
True, but I'd start with $B(n)$.
– Wuestenfux
Dec 12 '18 at 8:26
Can you please explain what it means for partitions to be isomorphic?
– childishsadbino
Dec 14 '18 at 4:12
See example at the end.
– Wuestenfux
Dec 14 '18 at 9:27
add a comment |
Hint: In c) one requires to enumerate all partitions of the set $X$ (up to isomorphism). First calculate the number of partitions of $X$. This is the Bell number $B(5)$, where $B(n) = sum_{k=1}^n S(n,k)$ and $S(n,k)$ is the number of partitions of $n$ into $k$ parts (Stirling number of the 2nd kind).
We have $B(1)=1$, with partition ${{1}}$,
$B(2)=2$ with partitions ${{1,2}}$, ${{1},{2}}$,
$B(3)=5$ with partitions ${{1},{{2},{3}}$, ${{1,2},{3}}$, ${{1,3},{2}}$, ${{2,3},{1}}$, ${{1,2,3}}$, and so on.
In view of the isomorphism classes, you just need to consider the types of partitions (see comment below).
BY REQUEST: For instance, take the bijection $f=left(begin{array}{ccc}1&2&3\2&3&1end{array}right)$. Then the partition ${{1,2},{3}}$ is mapped to the partition ${{f(1),f(2)},{f(3)}} = {{2,3},{1}}$.
answered Dec 12 '18 at 8:11
WuestenfuxWuestenfux
3,7061411
Note that c) asks for all isomorphic partitions. This means that the second, third and fourth example in $B(3)$ are the same
– Μάρκος Καραμέρης
Dec 12 '18 at 8:23
True, but I'd start with $B(n)$.
– Wuestenfux
Dec 12 '18 at 8:26
Can you please explain what it means for partitions to be isomorphic?
– childishsadbino
Dec 14 '18 at 4:12
See example at the end.
– Wuestenfux
Dec 14 '18 at 9:27
add a comment |
Hint: In c) one requires to enumerate all partitions of the set $X$ (up to isomorphism). First calculate the number of partitions of $X$. This is the Bell number $B(5)$, where $B(n) = sum_{k=1}^n S(n,k)$ and $S(n,k)$ is the number of partitions of $n$ into $k$ parts (Stirling number of the 2nd kind).
We have $B(1)=1$, with partition ${{1}}$,
$B(2)=2$ with partitions ${{1,2}}$, ${{1},{2}}$,
$B(3)=5$ with partitions ${{1},{{2},{3}}$, ${{1,2},{3}}$, ${{1,3},{2}}$, ${{2,3},{1}}$, ${{1,2,3}}$, and so on.
In view of the isomorphism classes, you just need to consider the types of partitions (see comment below).
BY REQUEST: For instance, take the bijection $f=left(begin{array}{ccc}1&2&3\2&3&1end{array}right)$. Then the partition ${{1,2},{3}}$ is mapped to the partition ${{f(1),f(2)},{f(3)}} = {{2,3},{1}}$.
answered Dec 12 '18 at 8:11
WuestenfuxWuestenfux
3,7061411
Hint: In c) one requires to enumerate all partitions of the set $X$ (up to isomorphism). First calculate the number of partitions of $X$. This is the Bell number $B(5)$, where $B(n) = sum_{k=1}^n S(n,k)$ and $S(n,k)$ is the number of partitions of $n$ into $k$ parts (Stirling number of the 2nd kind).
We have $B(1)=1$, with partition ${{1}}$,
$B(2)=2$ with partitions ${{1,2}}$, ${{1},{2}}$,
$B(3)=5$ with partitions ${{1},{{2},{3}}$, ${{1,2},{3}}$, ${{1,3},{2}}$, ${{2,3},{1}}$, ${{1,2,3}}$, and so on.
In view of the isomorphism classes, you just need to consider the types of partitions (see comment below).
BY REQUEST: For instance, take the bijection $f=left(begin{array}{ccc}1&2&3\2&3&1end{array}right)$. Then the partition ${{1,2},{3}}$ is mapped to the partition ${{f(1),f(2)},{f(3)}} = {{2,3},{1}}$.
answered Dec 12 '18 at 8:11
WuestenfuxWuestenfux
3,7061411
edited Dec 14 '18 at 9:26
answered Dec 12 '18 at 8:11
WuestenfuxWuestenfux
3,7061411
answered Dec 12 '18 at 8:11
WuestenfuxWuestenfux
3,7061411
answered Dec 12 '18 at 8:11
WuestenfuxWuestenfux
3,7061411
3,7061411
Note that c) asks for all isomorphic partitions. This means that the second, third and fourth example in $B(3)$ are the same
– Μάρκος Καραμέρης
Dec 12 '18 at 8:23
True, but I'd start with $B(n)$.
– Wuestenfux
Dec 12 '18 at 8:26
Can you please explain what it means for partitions to be isomorphic?
– childishsadbino
Dec 14 '18 at 4:12
See example at the end.
– Wuestenfux
Dec 14 '18 at 9:27
add a comment |
Note that c) asks for all isomorphic partitions. This means that the second, third and fourth example in $B(3)$ are the same
– Μάρκος Καραμέρης
Dec 12 '18 at 8:23
True, but I'd start with $B(n)$.
– Wuestenfux
Dec 12 '18 at 8:26
Can you please explain what it means for partitions to be isomorphic?
– childishsadbino
Dec 14 '18 at 4:12
See example at the end.
– Wuestenfux
Dec 14 '18 at 9:27
Note that c) asks for all isomorphic partitions. This means that the second, third and fourth example in $B(3)$ are the same
– Μάρκος Καραμέρης
Dec 12 '18 at 8:23
Note that c) asks for all isomorphic partitions. This means that the second, third and fourth example in $B(3)$ are the same
– Μάρκος Καραμέρης
Dec 12 '18 at 8:23
True, but I'd start with $B(n)$.
– Wuestenfux
Dec 12 '18 at 8:26
True, but I'd start with $B(n)$.
– Wuestenfux
Dec 12 '18 at 8:26
Can you please explain what it means for partitions to be isomorphic?
– childishsadbino
Dec 14 '18 at 4:12
Can you please explain what it means for partitions to be isomorphic?
– childishsadbino
Dec 14 '18 at 4:12
See example at the end.
– Wuestenfux
Dec 14 '18 at 9:27
See example at the end.
– Wuestenfux
Dec 14 '18 at 9:27
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3036384%2fisomorphic-equivalence-relations-and-partitions%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
