Is the set of all sets of bit strings countably infinite, finite, or uncountable?
$begingroup$
I’m not sure how to interpret “the set of all sets of bit strings.” Does this mean I could have some set like this:
Further, if this is the case, could I say that I can order the elements from smallest set to largest set, where each element itself is already ordered from least amount of bits to greatest, and say the overall set is countably infinite?
elementary-set-theory
asked Nov 30 '18 at 21:56
darylnakdarylnak
167111
$endgroup$
add a comment |
$begingroup$
I’m not sure how to interpret “the set of all sets of bit strings.” Does this mean I could have some set like this:
Further, if this is the case, could I say that I can order the elements from smallest set to largest set, where each element itself is already ordered from least amount of bits to greatest, and say the overall set is countably infinite?
elementary-set-theory
asked Nov 30 '18 at 21:56
darylnakdarylnak
167111
$endgroup$
$begingroup$
No, you can't . If you accept infinite bit strings there are already uncountably many of them.
$endgroup$
– Ross Millikan
Nov 30 '18 at 22:07
1
$begingroup$
A heuristic you can use to determine whether a set is countable is that it is countable if each of its elements has a finite description. (I wrote a blog post about this a couple of weeks ago.) A set of bit strings may be infinite, so it's reasonable to expect that the set of all sets of bit strings is uncountable. (But then, of course, you have to prove it—see the answers below for help with that!)
$endgroup$
– Clive Newstead
Nov 30 '18 at 22:59
$begingroup$
Your interpretation of what "set of sets of" means is right. But they're not countable—see below for why.
$endgroup$
– timtfj
Nov 30 '18 at 23:10
add a comment |
$begingroup$
I’m not sure how to interpret “the set of all sets of bit strings.” Does this mean I could have some set like this:
Further, if this is the case, could I say that I can order the elements from smallest set to largest set, where each element itself is already ordered from least amount of bits to greatest, and say the overall set is countably infinite?
elementary-set-theory
asked Nov 30 '18 at 21:56
darylnakdarylnak
167111
$endgroup$
I’m not sure how to interpret “the set of all sets of bit strings.” Does this mean I could have some set like this:
Further, if this is the case, could I say that I can order the elements from smallest set to largest set, where each element itself is already ordered from least amount of bits to greatest, and say the overall set is countably infinite?
elementary-set-theory
elementary-set-theory
asked Nov 30 '18 at 21:56
darylnakdarylnak
167111
asked Nov 30 '18 at 21:56
darylnakdarylnak
167111
edited Nov 30 '18 at 22:11
darylnak
asked Nov 30 '18 at 21:56
darylnakdarylnak
167111
asked Nov 30 '18 at 21:56
darylnakdarylnak
167111
asked Nov 30 '18 at 21:56
darylnakdarylnak
167111
167111
$begingroup$
No, you can't . If you accept infinite bit strings there are already uncountably many of them.
$endgroup$
– Ross Millikan
Nov 30 '18 at 22:07
1
$begingroup$
A heuristic you can use to determine whether a set is countable is that it is countable if each of its elements has a finite description. (I wrote a blog post about this a couple of weeks ago.) A set of bit strings may be infinite, so it's reasonable to expect that the set of all sets of bit strings is uncountable. (But then, of course, you have to prove it—see the answers below for help with that!)
$endgroup$
– Clive Newstead
Nov 30 '18 at 22:59
$begingroup$
Your interpretation of what "set of sets of" means is right. But they're not countable—see below for why.
$endgroup$
– timtfj
Nov 30 '18 at 23:10
add a comment |
$begingroup$
No, you can't . If you accept infinite bit strings there are already uncountably many of them.
$endgroup$
– Ross Millikan
Nov 30 '18 at 22:07
1
$begingroup$
A heuristic you can use to determine whether a set is countable is that it is countable if each of its elements has a finite description. (I wrote a blog post about this a couple of weeks ago.) A set of bit strings may be infinite, so it's reasonable to expect that the set of all sets of bit strings is uncountable. (But then, of course, you have to prove it—see the answers below for help with that!)
$endgroup$
– Clive Newstead
Nov 30 '18 at 22:59
$begingroup$
Your interpretation of what "set of sets of" means is right. But they're not countable—see below for why.
$endgroup$
– timtfj
Nov 30 '18 at 23:10
$begingroup$
No, you can't . If you accept infinite bit strings there are already uncountably many of them.
$endgroup$
– Ross Millikan
Nov 30 '18 at 22:07
$begingroup$
No, you can't . If you accept infinite bit strings there are already uncountably many of them.
$endgroup$
– Ross Millikan
Nov 30 '18 at 22:07
1
1
$begingroup$
A heuristic you can use to determine whether a set is countable is that it is countable if each of its elements has a finite description. (I wrote a blog post about this a couple of weeks ago.) A set of bit strings may be infinite, so it's reasonable to expect that the set of all sets of bit strings is uncountable. (But then, of course, you have to prove it—see the answers below for help with that!)
$endgroup$
– Clive Newstead
Nov 30 '18 at 22:59
$begingroup$
A heuristic you can use to determine whether a set is countable is that it is countable if each of its elements has a finite description. (I wrote a blog post about this a couple of weeks ago.) A set of bit strings may be infinite, so it's reasonable to expect that the set of all sets of bit strings is uncountable. (But then, of course, you have to prove it—see the answers below for help with that!)
$endgroup$
– Clive Newstead
Nov 30 '18 at 22:59
$begingroup$
Your interpretation of what "set of sets of" means is right. But they're not countable—see below for why.
$endgroup$
– timtfj
Nov 30 '18 at 23:10
$begingroup$
Your interpretation of what "set of sets of" means is right. But they're not countable—see below for why.
$endgroup$
– timtfj
Nov 30 '18 at 23:10
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
How many strings?
(i) If you're only allowing finite strings, then each one is simply an integer expressed in binary, and the set of strings is countably infinite.
(ii) If you're allowing infinite strings, then pairing every real number in $(0,1)$ with its binary representation tells you that they're uncountably infinite since there are uncountably many real numbers in $(0,1)$ and each can be represented by a string.
How many sets of strings?
If there are only countably-infinitely many strings, then for each set of strings you can construct an infinitely long binary number which contains 1 or 0 as its $n$th bit depending on whether the $n$th string is included. By the argument in (ii), there are uncountably many such numbers. Each is paired with one of the sets of strings, so there are uncountably many sets of strings.
If the strings themselves are uncountable then the sets of strings are too, since for each string there is a set containing just that string and you've got to at least have all those sets.
So either way, there are uncountably many sets of strings.
Note: The full argument would need refining a bit, because the integers actually have multiple representations (just add some zeros at the start) and so do some real numbers (similar to $0.49999. . . = 0.5 = 0.50000. . .$ in decimal).
answered Nov 30 '18 at 22:44
timtfjtimtfj
2,298420
$endgroup$
add a comment |
$begingroup$
You have to decide whether bit strings are all of finite length or include countably infinite ones. In the first case there are $aleph_0$ of them, in the second case there are $2^{aleph_0}$ of them. You should have proved this already. If $S$ is the set of bit strings, you are being asked $|P(P(S))|$. Each power set operation corresponds to raising $2$ to the power of the size of the set.
answered Nov 30 '18 at 22:06
Ross MillikanRoss Millikan
296k23198371
$endgroup$
$begingroup$
I don't think he has to decide that in order to know whether there are countably many sets—since there are uncountably many anyway.
$endgroup$
– timtfj
Nov 30 '18 at 23:15
$begingroup$
@timtfj: It is uncountable, but a different uncountable infinity if you start with infinite length strings. You are correct that if it is multiple choice, uncountable is easy to come to.
$endgroup$
– Ross Millikan
Dec 1 '18 at 1:09
$begingroup$
Sure. I just meant that it's not strictly necessary to know which cardinality it is, since it has to be an uncountable one. I was being pedantic about whether "have to" is strictly true.
$endgroup$
– timtfj
Dec 1 '18 at 1:23
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%2f3020694%2fis-the-set-of-all-sets-of-bit-strings-countably-infinite-finite-or-uncountable%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$
How many strings?
(i) If you're only allowing finite strings, then each one is simply an integer expressed in binary, and the set of strings is countably infinite.
(ii) If you're allowing infinite strings, then pairing every real number in $(0,1)$ with its binary representation tells you that they're uncountably infinite since there are uncountably many real numbers in $(0,1)$ and each can be represented by a string.
How many sets of strings?
If there are only countably-infinitely many strings, then for each set of strings you can construct an infinitely long binary number which contains 1 or 0 as its $n$th bit depending on whether the $n$th string is included. By the argument in (ii), there are uncountably many such numbers. Each is paired with one of the sets of strings, so there are uncountably many sets of strings.
If the strings themselves are uncountable then the sets of strings are too, since for each string there is a set containing just that string and you've got to at least have all those sets.
So either way, there are uncountably many sets of strings.
Note: The full argument would need refining a bit, because the integers actually have multiple representations (just add some zeros at the start) and so do some real numbers (similar to $0.49999. . . = 0.5 = 0.50000. . .$ in decimal).
answered Nov 30 '18 at 22:44
timtfjtimtfj
2,298420
$endgroup$
add a comment |
$begingroup$
How many strings?
(i) If you're only allowing finite strings, then each one is simply an integer expressed in binary, and the set of strings is countably infinite.
(ii) If you're allowing infinite strings, then pairing every real number in $(0,1)$ with its binary representation tells you that they're uncountably infinite since there are uncountably many real numbers in $(0,1)$ and each can be represented by a string.
How many sets of strings?
If there are only countably-infinitely many strings, then for each set of strings you can construct an infinitely long binary number which contains 1 or 0 as its $n$th bit depending on whether the $n$th string is included. By the argument in (ii), there are uncountably many such numbers. Each is paired with one of the sets of strings, so there are uncountably many sets of strings.
If the strings themselves are uncountable then the sets of strings are too, since for each string there is a set containing just that string and you've got to at least have all those sets.
So either way, there are uncountably many sets of strings.
Note: The full argument would need refining a bit, because the integers actually have multiple representations (just add some zeros at the start) and so do some real numbers (similar to $0.49999. . . = 0.5 = 0.50000. . .$ in decimal).
answered Nov 30 '18 at 22:44
timtfjtimtfj
2,298420
$endgroup$
add a comment |
$begingroup$
How many strings?
(i) If you're only allowing finite strings, then each one is simply an integer expressed in binary, and the set of strings is countably infinite.
(ii) If you're allowing infinite strings, then pairing every real number in $(0,1)$ with its binary representation tells you that they're uncountably infinite since there are uncountably many real numbers in $(0,1)$ and each can be represented by a string.
How many sets of strings?
If there are only countably-infinitely many strings, then for each set of strings you can construct an infinitely long binary number which contains 1 or 0 as its $n$th bit depending on whether the $n$th string is included. By the argument in (ii), there are uncountably many such numbers. Each is paired with one of the sets of strings, so there are uncountably many sets of strings.
If the strings themselves are uncountable then the sets of strings are too, since for each string there is a set containing just that string and you've got to at least have all those sets.
So either way, there are uncountably many sets of strings.
Note: The full argument would need refining a bit, because the integers actually have multiple representations (just add some zeros at the start) and so do some real numbers (similar to $0.49999. . . = 0.5 = 0.50000. . .$ in decimal).
answered Nov 30 '18 at 22:44
timtfjtimtfj
2,298420
$endgroup$
How many strings?
(i) If you're only allowing finite strings, then each one is simply an integer expressed in binary, and the set of strings is countably infinite.
(ii) If you're allowing infinite strings, then pairing every real number in $(0,1)$ with its binary representation tells you that they're uncountably infinite since there are uncountably many real numbers in $(0,1)$ and each can be represented by a string.
How many sets of strings?
If there are only countably-infinitely many strings, then for each set of strings you can construct an infinitely long binary number which contains 1 or 0 as its $n$th bit depending on whether the $n$th string is included. By the argument in (ii), there are uncountably many such numbers. Each is paired with one of the sets of strings, so there are uncountably many sets of strings.
If the strings themselves are uncountable then the sets of strings are too, since for each string there is a set containing just that string and you've got to at least have all those sets.
So either way, there are uncountably many sets of strings.
Note: The full argument would need refining a bit, because the integers actually have multiple representations (just add some zeros at the start) and so do some real numbers (similar to $0.49999. . . = 0.5 = 0.50000. . .$ in decimal).
answered Nov 30 '18 at 22:44
timtfjtimtfj
2,298420
edited Nov 30 '18 at 23:38
answered Nov 30 '18 at 22:44
timtfjtimtfj
2,298420
answered Nov 30 '18 at 22:44
timtfjtimtfj
2,298420
answered Nov 30 '18 at 22:44
timtfjtimtfj
2,298420
2,298420
add a comment |
add a comment |
$begingroup$
You have to decide whether bit strings are all of finite length or include countably infinite ones. In the first case there are $aleph_0$ of them, in the second case there are $2^{aleph_0}$ of them. You should have proved this already. If $S$ is the set of bit strings, you are being asked $|P(P(S))|$. Each power set operation corresponds to raising $2$ to the power of the size of the set.
answered Nov 30 '18 at 22:06
Ross MillikanRoss Millikan
296k23198371
$endgroup$
$begingroup$
I don't think he has to decide that in order to know whether there are countably many sets—since there are uncountably many anyway.
$endgroup$
– timtfj
Nov 30 '18 at 23:15
$begingroup$
@timtfj: It is uncountable, but a different uncountable infinity if you start with infinite length strings. You are correct that if it is multiple choice, uncountable is easy to come to.
$endgroup$
– Ross Millikan
Dec 1 '18 at 1:09
$begingroup$
Sure. I just meant that it's not strictly necessary to know which cardinality it is, since it has to be an uncountable one. I was being pedantic about whether "have to" is strictly true.
$endgroup$
– timtfj
Dec 1 '18 at 1:23
add a comment |
$begingroup$
You have to decide whether bit strings are all of finite length or include countably infinite ones. In the first case there are $aleph_0$ of them, in the second case there are $2^{aleph_0}$ of them. You should have proved this already. If $S$ is the set of bit strings, you are being asked $|P(P(S))|$. Each power set operation corresponds to raising $2$ to the power of the size of the set.
answered Nov 30 '18 at 22:06
Ross MillikanRoss Millikan
296k23198371
$endgroup$
$begingroup$
I don't think he has to decide that in order to know whether there are countably many sets—since there are uncountably many anyway.
$endgroup$
– timtfj
Nov 30 '18 at 23:15
$begingroup$
@timtfj: It is uncountable, but a different uncountable infinity if you start with infinite length strings. You are correct that if it is multiple choice, uncountable is easy to come to.
$endgroup$
– Ross Millikan
Dec 1 '18 at 1:09
$begingroup$
Sure. I just meant that it's not strictly necessary to know which cardinality it is, since it has to be an uncountable one. I was being pedantic about whether "have to" is strictly true.
$endgroup$
– timtfj
Dec 1 '18 at 1:23
add a comment |
$begingroup$
You have to decide whether bit strings are all of finite length or include countably infinite ones. In the first case there are $aleph_0$ of them, in the second case there are $2^{aleph_0}$ of them. You should have proved this already. If $S$ is the set of bit strings, you are being asked $|P(P(S))|$. Each power set operation corresponds to raising $2$ to the power of the size of the set.
answered Nov 30 '18 at 22:06
Ross MillikanRoss Millikan
296k23198371
$endgroup$
You have to decide whether bit strings are all of finite length or include countably infinite ones. In the first case there are $aleph_0$ of them, in the second case there are $2^{aleph_0}$ of them. You should have proved this already. If $S$ is the set of bit strings, you are being asked $|P(P(S))|$. Each power set operation corresponds to raising $2$ to the power of the size of the set.
answered Nov 30 '18 at 22:06
Ross MillikanRoss Millikan
296k23198371
answered Nov 30 '18 at 22:06
Ross MillikanRoss Millikan
296k23198371
answered Nov 30 '18 at 22:06
Ross MillikanRoss Millikan
296k23198371
answered Nov 30 '18 at 22:06
Ross MillikanRoss Millikan
296k23198371
296k23198371
$begingroup$
I don't think he has to decide that in order to know whether there are countably many sets—since there are uncountably many anyway.
$endgroup$
– timtfj
Nov 30 '18 at 23:15
$begingroup$
@timtfj: It is uncountable, but a different uncountable infinity if you start with infinite length strings. You are correct that if it is multiple choice, uncountable is easy to come to.
$endgroup$
– Ross Millikan
Dec 1 '18 at 1:09
$begingroup$
Sure. I just meant that it's not strictly necessary to know which cardinality it is, since it has to be an uncountable one. I was being pedantic about whether "have to" is strictly true.
$endgroup$
– timtfj
Dec 1 '18 at 1:23
add a comment |
$begingroup$
I don't think he has to decide that in order to know whether there are countably many sets—since there are uncountably many anyway.
$endgroup$
– timtfj
Nov 30 '18 at 23:15
$begingroup$
@timtfj: It is uncountable, but a different uncountable infinity if you start with infinite length strings. You are correct that if it is multiple choice, uncountable is easy to come to.
$endgroup$
– Ross Millikan
Dec 1 '18 at 1:09
$begingroup$
Sure. I just meant that it's not strictly necessary to know which cardinality it is, since it has to be an uncountable one. I was being pedantic about whether "have to" is strictly true.
$endgroup$
– timtfj
Dec 1 '18 at 1:23
$begingroup$
I don't think he has to decide that in order to know whether there are countably many sets—since there are uncountably many anyway.
$endgroup$
– timtfj
Nov 30 '18 at 23:15
$begingroup$
I don't think he has to decide that in order to know whether there are countably many sets—since there are uncountably many anyway.
$endgroup$
– timtfj
Nov 30 '18 at 23:15
$begingroup$
@timtfj: It is uncountable, but a different uncountable infinity if you start with infinite length strings. You are correct that if it is multiple choice, uncountable is easy to come to.
$endgroup$
– Ross Millikan
Dec 1 '18 at 1:09
$begingroup$
@timtfj: It is uncountable, but a different uncountable infinity if you start with infinite length strings. You are correct that if it is multiple choice, uncountable is easy to come to.
$endgroup$
– Ross Millikan
Dec 1 '18 at 1:09
$begingroup$
Sure. I just meant that it's not strictly necessary to know which cardinality it is, since it has to be an uncountable one. I was being pedantic about whether "have to" is strictly true.
$endgroup$
– timtfj
Dec 1 '18 at 1:23
$begingroup$
Sure. I just meant that it's not strictly necessary to know which cardinality it is, since it has to be an uncountable one. I was being pedantic about whether "have to" is strictly true.
$endgroup$
– timtfj
Dec 1 '18 at 1:23
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%2f3020694%2fis-the-set-of-all-sets-of-bit-strings-countably-infinite-finite-or-uncountable%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$
No, you can't . If you accept infinite bit strings there are already uncountably many of them.
$endgroup$
– Ross Millikan
Nov 30 '18 at 22:07
1
$begingroup$
A heuristic you can use to determine whether a set is countable is that it is countable if each of its elements has a finite description. (I wrote a blog post about this a couple of weeks ago.) A set of bit strings may be infinite, so it's reasonable to expect that the set of all sets of bit strings is uncountable. (But then, of course, you have to prove it—see the answers below for help with that!)
$endgroup$
– Clive Newstead
Nov 30 '18 at 22:59
$begingroup$
Your interpretation of what "set of sets of" means is right. But they're not countable—see below for why.
$endgroup$
– timtfj
Nov 30 '18 at 23:10