Mixing
Find the symmetric subsets of $B = {1,2,3,4}$
$begingroup$
I came across this weird question in a question paper :
$B =lbrace1,2,3,4rbrace . text{ A set } Ssubseteq Btimes B text{ is called symmetric set iff, for all x,y } in S \
qquadqquadqquadqquadqquadqquad (x,y) in S Rightarrow (y,x) in S $ .
Find the number of symmetric sets of B.
At first , I thought the answer is $4.quad[(1,1),(2,2),(3,3),(4,4,)]$.
Now the question begs if an empty set "$emptyset$" can be included to the list?
What is the answer?
combinatorics elementary-set-theory
edited Feb 2 at 22:23
Maria Mazur
50k1361125
asked Oct 20 '18 at 21:43
DRPRDRPR
448412
$endgroup$
|
show 1 more comment
$begingroup$
I came across this weird question in a question paper :
$B =lbrace1,2,3,4rbrace . text{ A set } Ssubseteq Btimes B text{ is called symmetric set iff, for all x,y } in S \
qquadqquadqquadqquadqquadqquad (x,y) in S Rightarrow (y,x) in S $ .
Find the number of symmetric sets of B.
At first , I thought the answer is $4.quad[(1,1),(2,2),(3,3),(4,4,)]$.
Now the question begs if an empty set "$emptyset$" can be included to the list?
What is the answer?
combinatorics elementary-set-theory
edited Feb 2 at 22:23
Maria Mazur
50k1361125
asked Oct 20 '18 at 21:43
DRPRDRPR
448412
$endgroup$
4
$begingroup$
You've got the wrong idea about what "symmetric" means. It isn't that $x=y$. For example $S={(1,2),(2,1)}$ is symmetric, because $(x,y)in Simplies (y,x)in S$
$endgroup$
– saulspatz
Oct 20 '18 at 21:47
1
$begingroup$
What saulspatz says - but regarding your concrete question: Yes, the empty set is vacuously symmetric
$endgroup$
– Hagen von Eitzen
Oct 20 '18 at 21:49
1
$begingroup$
If $S subset Btimes B$ then what does "symmetric set of B" mean?
$endgroup$
– fleablood
Oct 20 '18 at 21:58
$begingroup$
Then it should be 4*4= 16., Which is not the same as $2^{10}$,according to greedoid's answer. Am I missing anything?
$endgroup$
– DRPR
Oct 20 '18 at 22:06
$begingroup$
Are you looking for all symmetric relations on B?: meaning all symmetric relations that are subsets of $B times B$? The set you found constitutes one symmetric relation on $B$. ${(1, 2), (2, 1)}$ is another. ${(3, 4), (4, 3)}$ is yet another symmetric relation on $B$. There are many more.
$endgroup$
– Namaste
Oct 20 '18 at 22:07
|
show 1 more comment
$begingroup$
I came across this weird question in a question paper :
$B =lbrace1,2,3,4rbrace . text{ A set } Ssubseteq Btimes B text{ is called symmetric set iff, for all x,y } in S \
qquadqquadqquadqquadqquadqquad (x,y) in S Rightarrow (y,x) in S $ .
Find the number of symmetric sets of B.
At first , I thought the answer is $4.quad[(1,1),(2,2),(3,3),(4,4,)]$.
Now the question begs if an empty set "$emptyset$" can be included to the list?
What is the answer?
combinatorics elementary-set-theory
edited Feb 2 at 22:23
Maria Mazur
50k1361125
asked Oct 20 '18 at 21:43
DRPRDRPR
448412
$endgroup$
I came across this weird question in a question paper :
$B =lbrace1,2,3,4rbrace . text{ A set } Ssubseteq Btimes B text{ is called symmetric set iff, for all x,y } in S \
qquadqquadqquadqquadqquadqquad (x,y) in S Rightarrow (y,x) in S $ .
Find the number of symmetric sets of B.
At first , I thought the answer is $4.quad[(1,1),(2,2),(3,3),(4,4,)]$.
Now the question begs if an empty set "$emptyset$" can be included to the list?
What is the answer?
combinatorics elementary-set-theory
combinatorics elementary-set-theory
edited Feb 2 at 22:23
Maria Mazur
50k1361125
asked Oct 20 '18 at 21:43
DRPRDRPR
448412
edited Feb 2 at 22:23
Maria Mazur
50k1361125
asked Oct 20 '18 at 21:43
DRPRDRPR
448412
edited Feb 2 at 22:23
Maria Mazur
50k1361125
edited Feb 2 at 22:23
Maria Mazur
50k1361125
edited Feb 2 at 22:23
Maria Mazur
50k1361125
50k1361125
asked Oct 20 '18 at 21:43
DRPRDRPR
448412
asked Oct 20 '18 at 21:43
DRPRDRPR
448412
asked Oct 20 '18 at 21:43
DRPRDRPR
448412
448412
4
$begingroup$
You've got the wrong idea about what "symmetric" means. It isn't that $x=y$. For example $S={(1,2),(2,1)}$ is symmetric, because $(x,y)in Simplies (y,x)in S$
$endgroup$
– saulspatz
Oct 20 '18 at 21:47
1
$begingroup$
What saulspatz says - but regarding your concrete question: Yes, the empty set is vacuously symmetric
$endgroup$
– Hagen von Eitzen
Oct 20 '18 at 21:49
1
$begingroup$
If $S subset Btimes B$ then what does "symmetric set of B" mean?
$endgroup$
– fleablood
Oct 20 '18 at 21:58
$begingroup$
Then it should be 4*4= 16., Which is not the same as $2^{10}$,according to greedoid's answer. Am I missing anything?
$endgroup$
– DRPR
Oct 20 '18 at 22:06
$begingroup$
Are you looking for all symmetric relations on B?: meaning all symmetric relations that are subsets of $B times B$? The set you found constitutes one symmetric relation on $B$. ${(1, 2), (2, 1)}$ is another. ${(3, 4), (4, 3)}$ is yet another symmetric relation on $B$. There are many more.
$endgroup$
– Namaste
Oct 20 '18 at 22:07
|
show 1 more comment
4
$begingroup$
You've got the wrong idea about what "symmetric" means. It isn't that $x=y$. For example $S={(1,2),(2,1)}$ is symmetric, because $(x,y)in Simplies (y,x)in S$
$endgroup$
– saulspatz
Oct 20 '18 at 21:47
1
$begingroup$
What saulspatz says - but regarding your concrete question: Yes, the empty set is vacuously symmetric
$endgroup$
– Hagen von Eitzen
Oct 20 '18 at 21:49
1
$begingroup$
If $S subset Btimes B$ then what does "symmetric set of B" mean?
$endgroup$
– fleablood
Oct 20 '18 at 21:58
$begingroup$
Then it should be 4*4= 16., Which is not the same as $2^{10}$,according to greedoid's answer. Am I missing anything?
$endgroup$
– DRPR
Oct 20 '18 at 22:06
$begingroup$
Are you looking for all symmetric relations on B?: meaning all symmetric relations that are subsets of $B times B$? The set you found constitutes one symmetric relation on $B$. ${(1, 2), (2, 1)}$ is another. ${(3, 4), (4, 3)}$ is yet another symmetric relation on $B$. There are many more.
$endgroup$
– Namaste
Oct 20 '18 at 22:07
4
4
$begingroup$
You've got the wrong idea about what "symmetric" means. It isn't that $x=y$. For example $S={(1,2),(2,1)}$ is symmetric, because $(x,y)in Simplies (y,x)in S$
$endgroup$
– saulspatz
Oct 20 '18 at 21:47
$begingroup$
You've got the wrong idea about what "symmetric" means. It isn't that $x=y$. For example $S={(1,2),(2,1)}$ is symmetric, because $(x,y)in Simplies (y,x)in S$
$endgroup$
– saulspatz
Oct 20 '18 at 21:47
1
1
$begingroup$
What saulspatz says - but regarding your concrete question: Yes, the empty set is vacuously symmetric
$endgroup$
– Hagen von Eitzen
Oct 20 '18 at 21:49
$begingroup$
What saulspatz says - but regarding your concrete question: Yes, the empty set is vacuously symmetric
$endgroup$
– Hagen von Eitzen
Oct 20 '18 at 21:49
1
1
$begingroup$
If $S subset Btimes B$ then what does "symmetric set of B" mean?
$endgroup$
– fleablood
Oct 20 '18 at 21:58
$begingroup$
If $S subset Btimes B$ then what does "symmetric set of B" mean?
$endgroup$
– fleablood
Oct 20 '18 at 21:58
$begingroup$
Then it should be 4*4= 16., Which is not the same as $2^{10}$,according to greedoid's answer. Am I missing anything?
$endgroup$
– DRPR
Oct 20 '18 at 22:06
$begingroup$
Then it should be 4*4= 16., Which is not the same as $2^{10}$,according to greedoid's answer. Am I missing anything?
$endgroup$
– DRPR
Oct 20 '18 at 22:06
$begingroup$
Are you looking for all symmetric relations on B?: meaning all symmetric relations that are subsets of $B times B$? The set you found constitutes one symmetric relation on $B$. ${(1, 2), (2, 1)}$ is another. ${(3, 4), (4, 3)}$ is yet another symmetric relation on $B$. There are many more.
$endgroup$
– Namaste
Oct 20 '18 at 22:07
$begingroup$
Are you looking for all symmetric relations on B?: meaning all symmetric relations that are subsets of $B times B$? The set you found constitutes one symmetric relation on $B$. ${(1, 2), (2, 1)}$ is another. ${(3, 4), (4, 3)}$ is yet another symmetric relation on $B$. There are many more.
$endgroup$
– Namaste
Oct 20 '18 at 22:07
|
show 1 more comment
2 Answers
2
active
oldest
votes
$begingroup$
Notice there are $16$ elements $(a,b)$.
For every element $(a,b)$ and every Symmetric set $Ssubset Btimes B$ we have two options: either $(a,b) in S$ or .... $(a,b) not in S$. But if $(a,b) in S$ then $(b,a) in S$. And if $(a,b) not in S$ then $(b,a) not in S$.
If we didn't have the condition of Symmetry we could state that there are $2^{16}$ subsets $M subset Btimes B$ by simply noting that for each subset $M$ and each element $(a,b)$ we have two options and as to whether $(a,b)$ is or is not in $M$ and those there are $2^{16}$ possible subsets that can be constructed by simply going through the $16$ elements and either choosing to put it in or not put it in each subset we construct.
For a symmetric set we can only make the choice an one of the elements $(a,b)$. Once we make the choice whether $(a,b)$ is or is not in $S$ then we have no choice but to make the exact same choice for whether $(b,a)$ is or is not in $S$.
So the number of symmetric sets is $2^k$ where $k$ is the number of distinct elements $(a,b)$ that we are allowed to make distinct choices on.
What is $k$? Well, $k < 16$. But ... how do we count of the $(a,b)$s but then omit the $(b,a)$s?
Well.... There are $16$ $(a,b)$. There are $4$ $(a,b; a = b)$ so there are $16-4 = 12$ $(a,b; ane b)$ and there $6=frac {12}2$ $(a,b; a < b)$ and $6$ $(a,b; a > b)$. And there are $6 + 4 = 10$ $(a,b; a le b)$.
For each of the $10$ $(a,b; ale b)$ we have two options as to whether we will allow it to be an element of symmetric $S$. For each of the $6$ $(b, a; b > a)$ the chose as to whether we will allow it to be an element of symmetric $S$ will have already been made when we made a decision for $(a,b)$.
So $k = 10$ and there are $2^{10} = 1024$ symmetric subsets.
(You did not consider such subsets as ${ (1,3), (2,4), (3,3),(3,1), (4,2)}$ or ${(1,2), (2,3), (1,4), (2,1), (3,2),(4,1)}$....)
.....
If we list the 16 elements in order:
$(1,1), color{blue}{(1,2),(1,3),(1,4)}$
$color{red}{(2,1)} ,(2,2), color{blue}{(2,3),(2,4)}$
$color{red}{(3,1),(3,2)} ,(3,3), color{blue}{(3,4)}$
$color{red}{(4,1),(4,2),(4,3)},(4,4)$
The six blue pairs on the top are in one to one corespondence with the six red pairs on the bottom.
In constructing a symmetric set $S$ we can make a choice for every blue or black pair as to whether or not to include that element in $S$. However once we make the decision for a blue pair we must make the exact same decision for the coresponding red pair.
There are $10$ distinct independent pairs the we can choose or not choose to put in $S$ so there are $2^{10} $ such symmetric sets we may construct
answered Oct 20 '18 at 22:31
fleabloodfleablood
1
$endgroup$
add a comment |
$begingroup$
Any symmetric set we can write as $Mcup Ncup N^T$, where $M$ is a subset of $${(1,1),(2,2),...(n,n)}$$ and $N$ is a subset of (uper diagonal if you draw a matrix of $ntimes n$) $${(1,2),(1,3),...(1,n),(2,3),(2,4)...(n-1,n)}$$
Note that $N^T$ is defined by: $(x,y)in N iff (y,x)in N^T$ and is therefore uniqely detrmined by $N$.
So there is $$2^ncdot 2^{n(n-1)over 2}= 2^{n(n+1)over 2}$$ symmetric relations.
answered Oct 20 '18 at 21:51
Maria MazurMaria Mazur
50k1361125
$endgroup$
2
$begingroup$
The set $B$ is defined in the question to be $B = {1,2,3,4}$. You may want to use different notation in your answer to avoid ambiguity.
$endgroup$
– Xander Henderson
Oct 20 '18 at 21:53
2
$begingroup$
You mean you can write it as $M cup N cup P$ where $M$ and $N$ are as you describe and $P$ is obtained from $N$ by replacing each $(m, n) in N$ by $(n, m)$.
$endgroup$
– Rob Arthan
Oct 20 '18 at 21:54
1
$begingroup$
The usage of $N^T$ warrants an explanation.
$endgroup$
– Théophile
Oct 20 '18 at 21:56
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%2f2963804%2ffind-the-symmetric-subsets-of-b-1-2-3-4%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$
Notice there are $16$ elements $(a,b)$.
For every element $(a,b)$ and every Symmetric set $Ssubset Btimes B$ we have two options: either $(a,b) in S$ or .... $(a,b) not in S$. But if $(a,b) in S$ then $(b,a) in S$. And if $(a,b) not in S$ then $(b,a) not in S$.
If we didn't have the condition of Symmetry we could state that there are $2^{16}$ subsets $M subset Btimes B$ by simply noting that for each subset $M$ and each element $(a,b)$ we have two options and as to whether $(a,b)$ is or is not in $M$ and those there are $2^{16}$ possible subsets that can be constructed by simply going through the $16$ elements and either choosing to put it in or not put it in each subset we construct.
For a symmetric set we can only make the choice an one of the elements $(a,b)$. Once we make the choice whether $(a,b)$ is or is not in $S$ then we have no choice but to make the exact same choice for whether $(b,a)$ is or is not in $S$.
So the number of symmetric sets is $2^k$ where $k$ is the number of distinct elements $(a,b)$ that we are allowed to make distinct choices on.
What is $k$? Well, $k < 16$. But ... how do we count of the $(a,b)$s but then omit the $(b,a)$s?
Well.... There are $16$ $(a,b)$. There are $4$ $(a,b; a = b)$ so there are $16-4 = 12$ $(a,b; ane b)$ and there $6=frac {12}2$ $(a,b; a < b)$ and $6$ $(a,b; a > b)$. And there are $6 + 4 = 10$ $(a,b; a le b)$.
For each of the $10$ $(a,b; ale b)$ we have two options as to whether we will allow it to be an element of symmetric $S$. For each of the $6$ $(b, a; b > a)$ the chose as to whether we will allow it to be an element of symmetric $S$ will have already been made when we made a decision for $(a,b)$.
So $k = 10$ and there are $2^{10} = 1024$ symmetric subsets.
(You did not consider such subsets as ${ (1,3), (2,4), (3,3),(3,1), (4,2)}$ or ${(1,2), (2,3), (1,4), (2,1), (3,2),(4,1)}$....)
.....
If we list the 16 elements in order:
$(1,1), color{blue}{(1,2),(1,3),(1,4)}$
$color{red}{(2,1)} ,(2,2), color{blue}{(2,3),(2,4)}$
$color{red}{(3,1),(3,2)} ,(3,3), color{blue}{(3,4)}$
$color{red}{(4,1),(4,2),(4,3)},(4,4)$
The six blue pairs on the top are in one to one corespondence with the six red pairs on the bottom.
In constructing a symmetric set $S$ we can make a choice for every blue or black pair as to whether or not to include that element in $S$. However once we make the decision for a blue pair we must make the exact same decision for the coresponding red pair.
There are $10$ distinct independent pairs the we can choose or not choose to put in $S$ so there are $2^{10} $ such symmetric sets we may construct
answered Oct 20 '18 at 22:31
fleabloodfleablood
1
$endgroup$
add a comment |
$begingroup$
Notice there are $16$ elements $(a,b)$.
For every element $(a,b)$ and every Symmetric set $Ssubset Btimes B$ we have two options: either $(a,b) in S$ or .... $(a,b) not in S$. But if $(a,b) in S$ then $(b,a) in S$. And if $(a,b) not in S$ then $(b,a) not in S$.
If we didn't have the condition of Symmetry we could state that there are $2^{16}$ subsets $M subset Btimes B$ by simply noting that for each subset $M$ and each element $(a,b)$ we have two options and as to whether $(a,b)$ is or is not in $M$ and those there are $2^{16}$ possible subsets that can be constructed by simply going through the $16$ elements and either choosing to put it in or not put it in each subset we construct.
For a symmetric set we can only make the choice an one of the elements $(a,b)$. Once we make the choice whether $(a,b)$ is or is not in $S$ then we have no choice but to make the exact same choice for whether $(b,a)$ is or is not in $S$.
So the number of symmetric sets is $2^k$ where $k$ is the number of distinct elements $(a,b)$ that we are allowed to make distinct choices on.
What is $k$? Well, $k < 16$. But ... how do we count of the $(a,b)$s but then omit the $(b,a)$s?
Well.... There are $16$ $(a,b)$. There are $4$ $(a,b; a = b)$ so there are $16-4 = 12$ $(a,b; ane b)$ and there $6=frac {12}2$ $(a,b; a < b)$ and $6$ $(a,b; a > b)$. And there are $6 + 4 = 10$ $(a,b; a le b)$.
For each of the $10$ $(a,b; ale b)$ we have two options as to whether we will allow it to be an element of symmetric $S$. For each of the $6$ $(b, a; b > a)$ the chose as to whether we will allow it to be an element of symmetric $S$ will have already been made when we made a decision for $(a,b)$.
So $k = 10$ and there are $2^{10} = 1024$ symmetric subsets.
(You did not consider such subsets as ${ (1,3), (2,4), (3,3),(3,1), (4,2)}$ or ${(1,2), (2,3), (1,4), (2,1), (3,2),(4,1)}$....)
.....
If we list the 16 elements in order:
$(1,1), color{blue}{(1,2),(1,3),(1,4)}$
$color{red}{(2,1)} ,(2,2), color{blue}{(2,3),(2,4)}$
$color{red}{(3,1),(3,2)} ,(3,3), color{blue}{(3,4)}$
$color{red}{(4,1),(4,2),(4,3)},(4,4)$
The six blue pairs on the top are in one to one corespondence with the six red pairs on the bottom.
In constructing a symmetric set $S$ we can make a choice for every blue or black pair as to whether or not to include that element in $S$. However once we make the decision for a blue pair we must make the exact same decision for the coresponding red pair.
There are $10$ distinct independent pairs the we can choose or not choose to put in $S$ so there are $2^{10} $ such symmetric sets we may construct
answered Oct 20 '18 at 22:31
fleabloodfleablood
1
$endgroup$
add a comment |
$begingroup$
Notice there are $16$ elements $(a,b)$.
For every element $(a,b)$ and every Symmetric set $Ssubset Btimes B$ we have two options: either $(a,b) in S$ or .... $(a,b) not in S$. But if $(a,b) in S$ then $(b,a) in S$. And if $(a,b) not in S$ then $(b,a) not in S$.
If we didn't have the condition of Symmetry we could state that there are $2^{16}$ subsets $M subset Btimes B$ by simply noting that for each subset $M$ and each element $(a,b)$ we have two options and as to whether $(a,b)$ is or is not in $M$ and those there are $2^{16}$ possible subsets that can be constructed by simply going through the $16$ elements and either choosing to put it in or not put it in each subset we construct.
For a symmetric set we can only make the choice an one of the elements $(a,b)$. Once we make the choice whether $(a,b)$ is or is not in $S$ then we have no choice but to make the exact same choice for whether $(b,a)$ is or is not in $S$.
So the number of symmetric sets is $2^k$ where $k$ is the number of distinct elements $(a,b)$ that we are allowed to make distinct choices on.
What is $k$? Well, $k < 16$. But ... how do we count of the $(a,b)$s but then omit the $(b,a)$s?
Well.... There are $16$ $(a,b)$. There are $4$ $(a,b; a = b)$ so there are $16-4 = 12$ $(a,b; ane b)$ and there $6=frac {12}2$ $(a,b; a < b)$ and $6$ $(a,b; a > b)$. And there are $6 + 4 = 10$ $(a,b; a le b)$.
For each of the $10$ $(a,b; ale b)$ we have two options as to whether we will allow it to be an element of symmetric $S$. For each of the $6$ $(b, a; b > a)$ the chose as to whether we will allow it to be an element of symmetric $S$ will have already been made when we made a decision for $(a,b)$.
So $k = 10$ and there are $2^{10} = 1024$ symmetric subsets.
(You did not consider such subsets as ${ (1,3), (2,4), (3,3),(3,1), (4,2)}$ or ${(1,2), (2,3), (1,4), (2,1), (3,2),(4,1)}$....)
.....
If we list the 16 elements in order:
$(1,1), color{blue}{(1,2),(1,3),(1,4)}$
$color{red}{(2,1)} ,(2,2), color{blue}{(2,3),(2,4)}$
$color{red}{(3,1),(3,2)} ,(3,3), color{blue}{(3,4)}$
$color{red}{(4,1),(4,2),(4,3)},(4,4)$
The six blue pairs on the top are in one to one corespondence with the six red pairs on the bottom.
In constructing a symmetric set $S$ we can make a choice for every blue or black pair as to whether or not to include that element in $S$. However once we make the decision for a blue pair we must make the exact same decision for the coresponding red pair.
There are $10$ distinct independent pairs the we can choose or not choose to put in $S$ so there are $2^{10} $ such symmetric sets we may construct
answered Oct 20 '18 at 22:31
fleabloodfleablood
1
$endgroup$
Notice there are $16$ elements $(a,b)$.
For every element $(a,b)$ and every Symmetric set $Ssubset Btimes B$ we have two options: either $(a,b) in S$ or .... $(a,b) not in S$. But if $(a,b) in S$ then $(b,a) in S$. And if $(a,b) not in S$ then $(b,a) not in S$.
If we didn't have the condition of Symmetry we could state that there are $2^{16}$ subsets $M subset Btimes B$ by simply noting that for each subset $M$ and each element $(a,b)$ we have two options and as to whether $(a,b)$ is or is not in $M$ and those there are $2^{16}$ possible subsets that can be constructed by simply going through the $16$ elements and either choosing to put it in or not put it in each subset we construct.
For a symmetric set we can only make the choice an one of the elements $(a,b)$. Once we make the choice whether $(a,b)$ is or is not in $S$ then we have no choice but to make the exact same choice for whether $(b,a)$ is or is not in $S$.
So the number of symmetric sets is $2^k$ where $k$ is the number of distinct elements $(a,b)$ that we are allowed to make distinct choices on.
What is $k$? Well, $k < 16$. But ... how do we count of the $(a,b)$s but then omit the $(b,a)$s?
Well.... There are $16$ $(a,b)$. There are $4$ $(a,b; a = b)$ so there are $16-4 = 12$ $(a,b; ane b)$ and there $6=frac {12}2$ $(a,b; a < b)$ and $6$ $(a,b; a > b)$. And there are $6 + 4 = 10$ $(a,b; a le b)$.
For each of the $10$ $(a,b; ale b)$ we have two options as to whether we will allow it to be an element of symmetric $S$. For each of the $6$ $(b, a; b > a)$ the chose as to whether we will allow it to be an element of symmetric $S$ will have already been made when we made a decision for $(a,b)$.
So $k = 10$ and there are $2^{10} = 1024$ symmetric subsets.
(You did not consider such subsets as ${ (1,3), (2,4), (3,3),(3,1), (4,2)}$ or ${(1,2), (2,3), (1,4), (2,1), (3,2),(4,1)}$....)
.....
If we list the 16 elements in order:
$(1,1), color{blue}{(1,2),(1,3),(1,4)}$
$color{red}{(2,1)} ,(2,2), color{blue}{(2,3),(2,4)}$
$color{red}{(3,1),(3,2)} ,(3,3), color{blue}{(3,4)}$
$color{red}{(4,1),(4,2),(4,3)},(4,4)$
The six blue pairs on the top are in one to one corespondence with the six red pairs on the bottom.
In constructing a symmetric set $S$ we can make a choice for every blue or black pair as to whether or not to include that element in $S$. However once we make the decision for a blue pair we must make the exact same decision for the coresponding red pair.
There are $10$ distinct independent pairs the we can choose or not choose to put in $S$ so there are $2^{10} $ such symmetric sets we may construct
answered Oct 20 '18 at 22:31
fleabloodfleablood
1
edited Oct 20 '18 at 22:54
answered Oct 20 '18 at 22:31
fleabloodfleablood
1
answered Oct 20 '18 at 22:31
fleabloodfleablood
1
answered Oct 20 '18 at 22:31
fleabloodfleablood
1
1
add a comment |
add a comment |
$begingroup$
Any symmetric set we can write as $Mcup Ncup N^T$, where $M$ is a subset of $${(1,1),(2,2),...(n,n)}$$ and $N$ is a subset of (uper diagonal if you draw a matrix of $ntimes n$) $${(1,2),(1,3),...(1,n),(2,3),(2,4)...(n-1,n)}$$
Note that $N^T$ is defined by: $(x,y)in N iff (y,x)in N^T$ and is therefore uniqely detrmined by $N$.
So there is $$2^ncdot 2^{n(n-1)over 2}= 2^{n(n+1)over 2}$$ symmetric relations.
answered Oct 20 '18 at 21:51
Maria MazurMaria Mazur
50k1361125
$endgroup$
2
$begingroup$
The set $B$ is defined in the question to be $B = {1,2,3,4}$. You may want to use different notation in your answer to avoid ambiguity.
$endgroup$
– Xander Henderson
Oct 20 '18 at 21:53
2
$begingroup$
You mean you can write it as $M cup N cup P$ where $M$ and $N$ are as you describe and $P$ is obtained from $N$ by replacing each $(m, n) in N$ by $(n, m)$.
$endgroup$
– Rob Arthan
Oct 20 '18 at 21:54
1
$begingroup$
The usage of $N^T$ warrants an explanation.
$endgroup$
– Théophile
Oct 20 '18 at 21:56
add a comment |
$begingroup$
Any symmetric set we can write as $Mcup Ncup N^T$, where $M$ is a subset of $${(1,1),(2,2),...(n,n)}$$ and $N$ is a subset of (uper diagonal if you draw a matrix of $ntimes n$) $${(1,2),(1,3),...(1,n),(2,3),(2,4)...(n-1,n)}$$
Note that $N^T$ is defined by: $(x,y)in N iff (y,x)in N^T$ and is therefore uniqely detrmined by $N$.
So there is $$2^ncdot 2^{n(n-1)over 2}= 2^{n(n+1)over 2}$$ symmetric relations.
answered Oct 20 '18 at 21:51
Maria MazurMaria Mazur
50k1361125
$endgroup$
2
$begingroup$
The set $B$ is defined in the question to be $B = {1,2,3,4}$. You may want to use different notation in your answer to avoid ambiguity.
$endgroup$
– Xander Henderson
Oct 20 '18 at 21:53
2
$begingroup$
You mean you can write it as $M cup N cup P$ where $M$ and $N$ are as you describe and $P$ is obtained from $N$ by replacing each $(m, n) in N$ by $(n, m)$.
$endgroup$
– Rob Arthan
Oct 20 '18 at 21:54
1
$begingroup$
The usage of $N^T$ warrants an explanation.
$endgroup$
– Théophile
Oct 20 '18 at 21:56
add a comment |
$begingroup$
Any symmetric set we can write as $Mcup Ncup N^T$, where $M$ is a subset of $${(1,1),(2,2),...(n,n)}$$ and $N$ is a subset of (uper diagonal if you draw a matrix of $ntimes n$) $${(1,2),(1,3),...(1,n),(2,3),(2,4)...(n-1,n)}$$
Note that $N^T$ is defined by: $(x,y)in N iff (y,x)in N^T$ and is therefore uniqely detrmined by $N$.
So there is $$2^ncdot 2^{n(n-1)over 2}= 2^{n(n+1)over 2}$$ symmetric relations.
answered Oct 20 '18 at 21:51
Maria MazurMaria Mazur
50k1361125
$endgroup$
Any symmetric set we can write as $Mcup Ncup N^T$, where $M$ is a subset of $${(1,1),(2,2),...(n,n)}$$ and $N$ is a subset of (uper diagonal if you draw a matrix of $ntimes n$) $${(1,2),(1,3),...(1,n),(2,3),(2,4)...(n-1,n)}$$
Note that $N^T$ is defined by: $(x,y)in N iff (y,x)in N^T$ and is therefore uniqely detrmined by $N$.
So there is $$2^ncdot 2^{n(n-1)over 2}= 2^{n(n+1)over 2}$$ symmetric relations.
answered Oct 20 '18 at 21:51
Maria MazurMaria Mazur
50k1361125
edited Oct 20 '18 at 21:57
answered Oct 20 '18 at 21:51
Maria MazurMaria Mazur
50k1361125
answered Oct 20 '18 at 21:51
Maria MazurMaria Mazur
50k1361125
answered Oct 20 '18 at 21:51
Maria MazurMaria Mazur
50k1361125
50k1361125
2
$begingroup$
The set $B$ is defined in the question to be $B = {1,2,3,4}$. You may want to use different notation in your answer to avoid ambiguity.
$endgroup$
– Xander Henderson
Oct 20 '18 at 21:53
2
$begingroup$
You mean you can write it as $M cup N cup P$ where $M$ and $N$ are as you describe and $P$ is obtained from $N$ by replacing each $(m, n) in N$ by $(n, m)$.
$endgroup$
– Rob Arthan
Oct 20 '18 at 21:54
1
$begingroup$
The usage of $N^T$ warrants an explanation.
$endgroup$
– Théophile
Oct 20 '18 at 21:56
add a comment |
2
$begingroup$
The set $B$ is defined in the question to be $B = {1,2,3,4}$. You may want to use different notation in your answer to avoid ambiguity.
$endgroup$
– Xander Henderson
Oct 20 '18 at 21:53
2
$begingroup$
You mean you can write it as $M cup N cup P$ where $M$ and $N$ are as you describe and $P$ is obtained from $N$ by replacing each $(m, n) in N$ by $(n, m)$.
$endgroup$
– Rob Arthan
Oct 20 '18 at 21:54
1
$begingroup$
The usage of $N^T$ warrants an explanation.
$endgroup$
– Théophile
Oct 20 '18 at 21:56
2
2
$begingroup$
The set $B$ is defined in the question to be $B = {1,2,3,4}$. You may want to use different notation in your answer to avoid ambiguity.
$endgroup$
– Xander Henderson
Oct 20 '18 at 21:53
$begingroup$
The set $B$ is defined in the question to be $B = {1,2,3,4}$. You may want to use different notation in your answer to avoid ambiguity.
$endgroup$
– Xander Henderson
Oct 20 '18 at 21:53
2
2
$begingroup$
You mean you can write it as $M cup N cup P$ where $M$ and $N$ are as you describe and $P$ is obtained from $N$ by replacing each $(m, n) in N$ by $(n, m)$.
$endgroup$
– Rob Arthan
Oct 20 '18 at 21:54
$begingroup$
You mean you can write it as $M cup N cup P$ where $M$ and $N$ are as you describe and $P$ is obtained from $N$ by replacing each $(m, n) in N$ by $(n, m)$.
$endgroup$
– Rob Arthan
Oct 20 '18 at 21:54
1
1
$begingroup$
The usage of $N^T$ warrants an explanation.
$endgroup$
– Théophile
Oct 20 '18 at 21:56
$begingroup$
The usage of $N^T$ warrants an explanation.
$endgroup$
– Théophile
Oct 20 '18 at 21:56
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%2f2963804%2ffind-the-symmetric-subsets-of-b-1-2-3-4%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
4
$begingroup$
You've got the wrong idea about what "symmetric" means. It isn't that $x=y$. For example $S={(1,2),(2,1)}$ is symmetric, because $(x,y)in Simplies (y,x)in S$
$endgroup$
– saulspatz
Oct 20 '18 at 21:47
1
$begingroup$
What saulspatz says - but regarding your concrete question: Yes, the empty set is vacuously symmetric
$endgroup$
– Hagen von Eitzen
Oct 20 '18 at 21:49
1
$begingroup$
If $S subset Btimes B$ then what does "symmetric set of B" mean?
$endgroup$
– fleablood
Oct 20 '18 at 21:58
$begingroup$
Then it should be 4*4= 16., Which is not the same as $2^{10}$,according to greedoid's answer. Am I missing anything?
$endgroup$
– DRPR
Oct 20 '18 at 22:06
$begingroup$
Are you looking for all symmetric relations on B?: meaning all symmetric relations that are subsets of $B times B$? The set you found constitutes one symmetric relation on $B$. ${(1, 2), (2, 1)}$ is another. ${(3, 4), (4, 3)}$ is yet another symmetric relation on $B$. There are many more.
$endgroup$
– Namaste
Oct 20 '18 at 22:07