Countable bits


by dodo
Tags: bits, countable
dodo
dodo is offline
#1
Apr27-08, 09:11 AM
P: 688
Hello, I have a curiosity.

With a finite number of bits, say 5, you can represent 2^5 items. If B = {00001, 00010, 00100, 01000, 10000} is the set of these 5 bits, you can combine them to represent the power set of B, with cardinality 2^5.

With a countably infinite number of bits, you could represent a countable set like the naturals, using only one bit per natural, as in {...00001, ...00010, ...00100, ...01000, ...}; it would appear that by combining bits you could represent the power set of the previous, with cardinality aleph_1.

Thus it would look like, to represent the naturals with bit combinations, you'd need an infinite, yet less than countable, number of bits, such that its power set is countable. Where is the way out of this paradox?
Phys.Org News Partner Mathematics news on Phys.org
Math modeling handbook now available
Hyperbolic homogeneous polynomials, oh my!
Researchers help Boston Marathon organizers plan for 2014 race
HallsofIvy
HallsofIvy is offline
#2
Apr27-08, 09:45 AM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 38,904
Take a close look at the definition of "countable". There is NO set that is "infinite yet less than countable". Saying that you need only a subset of a countable set does not mean you need a set that is "infinite but less than countable". Any subset of a countable set is either finite or countable.
dodo
dodo is offline
#3
Apr27-08, 09:53 AM
P: 688
The part I don't understand, is why the sets {...00001, ...00010, ...00100, ...01000, ...} and {...00000, ...00001, ...00010, ...00011, ...00100, ...00101, ...00110, ...00111, ..01000, ...} have the same cardinality, being one (apparently) the power set of the other.

HallsofIvy
HallsofIvy is offline
#4
Apr27-08, 10:09 AM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 38,904

Countable bits


Oh, I see what you are saying. The two sets do NOT have the same cardinality.
it would appear that by combining bits you could represent the power set of the previous
It may appear that way but it is not true.
dodo
dodo is offline
#5
Apr27-08, 10:30 AM
P: 688
Quote Quote by HallsofIvy View Post
Oh, I see what you are saying. The two sets do NOT have the same cardinality.
Are you saying that {...00001, ...00010, ...00100, ...01000, ...} has cardinality aleph_0, and {...00000, ...00001, ...00010, ...00011, ...00100, ...00101, ...00110, ...00111, ..01000, ...} has cardinality aleph_1?

Because that brings back my original question: if a countable number of bits represent a set of cardinality aleph_1, how many bits you need to represent a countable set?
HallsofIvy
HallsofIvy is offline
#6
Apr27-08, 12:41 PM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 38,904
Quote Quote by Dodo View Post
Are you saying that {...00001, ...00010, ...00100, ...01000, ...} has cardinality aleph_0, and {...00000, ...00001, ...00010, ...00011, ...00100, ...00101, ...00110, ...00111, ..01000, ...} has cardinality aleph_1?
No, I said just the opposite: that a countable number of bits does not represent the power set.

Because that brings back my original question: if a countable number of bits represent a set of cardinality aleph_1, how many bits you need to represent a countable set?
dodo
dodo is offline
#7
Apr27-08, 02:16 PM
P: 688
I still can't make sense of this, so let me try a different approach: I will write down numbered statements, and you can tell me which might be true and which is outright false.

On the premises,

Let S = {...00001, ...00010, ...00100, ...01000, ...} be the set of all elements with infinite countable (aleph_0) bits each, and where, on each element, only one of its bits is 1, the rest are 0.

Let P = (...00000, ...00001, ...00010, ...00011, ...00100, ...00101, ...} be the set of all possible combinations of infinite countable bits. The bit size of each element is as in the set S. But this time we place no restriction on the bit values, 0 or 1.

Which of the following are true and which are false?
(It is acceptable to say "sounds reasonable" instead of plain "true", to avoid loading you with a formal proof of the statements. Of if you prefer, say "I don't find any immediate reason to label it as false". :)

1) In the set S, it is possible to establish a bijection between bit positions and set elements. Namely, f(1) = ...00001, f(2) = ...00010, f(3) = ...00100, f(4) = ...01000, ...
2) The cardinality of S is aleph_0.
3) It is possible to establish a bijection between P and the power set of S. Namely, f(A) = a1 or a2 or a3 or ..., where "or" it the namesake bitwise operation, a1,a2,a3,... belong to A, and A belongs to the power set of S. f( { } ), the image of the empty set, is defined as ...00000.
4) The cardinality of P is not the same as the cardinality of S.
5) The cardinality of P is aleph_1.
CRGreathouse
CRGreathouse is offline
#8
Apr27-08, 07:13 PM
Sci Advisor
HW Helper
P: 3,680
Quote Quote by Dodo View Post
The part I don't understand, is why the sets {...00001, ...00010, ...00100, ...01000, ...} and {...00000, ...00001, ...00010, ...00011, ...00100, ...00101, ...00110, ...00111, ..01000, ...} have the same cardinality, being one (apparently) the power set of the other.
The first set is isomorphic to the natural numbers and has cardinality aleph-0. The second set is isomorphic to the real numbers and has cardinality 2^aleph-0.
CRGreathouse
CRGreathouse is offline
#9
Apr27-08, 07:16 PM
Sci Advisor
HW Helper
P: 3,680
Quote Quote by Dodo View Post
Let S = {...00001, ...00010, ...00100, ...01000, ...} be the set of all elements with infinite countable (aleph_0) bits each, and where, on each element, only one of its bits is 1, the rest are 0.

Let P = (...00000, ...00001, ...00010, ...00011, ...00100, ...00101, ...} be the set of all possible combinations of infinite countable bits. The bit size of each element is as in the set S. But this time we place no restriction on the bit values, 0 or 1.

Which of the following are true and which are false?
(It is acceptable to say "sounds reasonable" instead of plain "true", to avoid loading you with a formal proof of the statements. Of if you prefer, say "I don't find any immediate reason to label it as false". :)

1) In the set S, it is possible to establish a bijection between bit positions and set elements. Namely, f(1) = ...00001, f(2) = ...00010, f(3) = ...00100, f(4) = ...01000, ...
2) The cardinality of S is aleph_0.
3) It is possible to establish a bijection between P and the power set of S. Namely, f(A) = a1 or a2 or a3 or ..., where "or" it the namesake bitwise operation, a1,a2,a3,... belong to A, and A belongs to the power set of S. f( { } ), the image of the empty set, is defined as ...00000.
4) The cardinality of P is not the same as the cardinality of S.
5) The cardinality of P is aleph_1.
1. True
2. True
3. True
4. True
5. True, assuming the continuum hypothesis. The cardinality is [itex]2^{\aleph_0}=\beth_1[/itex], but this is not known in general to equal [itex]\aleph_1[/itex].
dodo
dodo is offline
#10
Apr28-08, 02:42 AM
P: 688
Hey, thanks for your answers. Your answer to 5) goes beyond me, but it's ok, more reading material.

The purpose of these questions, and the spirit of the original post, was the following: on finite sets, you can quantify the "information content" of the set (as in "number of bits needed to represent/transfer the elements on the set, assuming a uniform distribution model").

If you attempt to extend the concept to infinite sets, you can attempt an answer for infinite sets with cardinality bigger than countable (as post #7 attempts to illustrate), but you get in trouble with countable sets (how many bits you need to represent them? - a finite number of bits is too small, a infinite countable number of bits is too big). It is this lapse which I found disturbing.
CRGreathouse
CRGreathouse is offline
#11
Apr28-08, 08:00 AM
Sci Advisor
HW Helper
P: 3,680
Quote Quote by Dodo View Post
Hey, thanks for your answers. Your answer to 5) goes beyond me, but it's ok, more reading material.
I guess you don't really understand what the aleph numbers are.
[tex]\aleph_0\le\kappa\le\aleph_1[/tex] is such that [itex]\kappa=\aleph_0[/itex] or [itex]\kappa=\aleph_1[/itex] for all [itex]\kappa[/itex]. In that sense the aleph number is the successor: no cardinal is 'between' [itex]\alpeh_0[/itex] and [itex]\aleph_1[/itex] just like no natural number is 'between' 1 and 2.

Beth numbers are [tex]\beth_0=\aleph_0,\;\beth_{n+1}=2^{\beth_n}[/tex]. The real numbers have cardinality [itex]\beth_1[/itex].

Quote Quote by Dodo View Post
(as in "number of bits needed to represent/transfer the elements on the set, assuming a uniform distribution model")
Uniform distribution on a countably infinite bitstring gives you the cardinality of the reals, [itex]\mathcal{c}=\beth_1[/itex].

Quote Quote by Dodo View Post
If you attempt to extend the concept to infinite sets, you can attempt an answer for infinite sets with cardinality bigger than countable (as post #7 attempts to illustrate), but you get in trouble with countable sets (how many bits you need to represent them? - a finite number of bits is too small, a infinite countable number of bits is too big). It is this lapse which I found disturbing.
I think you mean this: there is no set S for which [itex]2^S=\aleph_0[/itex].
dodo
dodo is offline
#12
Apr28-08, 11:20 AM
P: 688
Quote Quote by CRGreathouse View Post
I think you mean this: there is no set S for which [itex]2^S=\aleph_0[/itex].
I chose to rephrase it in more dramatic terms: the question "how many bits you need to represent the naturals" has no answer. Annoying.
CRGreathouse
CRGreathouse is offline
#13
Apr28-08, 12:46 PM
Sci Advisor
HW Helper
P: 3,680
Quote Quote by Dodo View Post
I chose to rephrase it in more dramatic terms: the question "how many bits you need to represent the naturals" has no answer. Annoying.
No, because that's answerable: [itex]\aleph_0[/itex]. How many bits for the reals? [itex]\aleph_0[/itex]. How many bits for the functions [itex]f:\mathbb{R}\to\mathbb{R}[/itex]? [itex]2^{\aleph_0}[/itex].

Edit: in my post above, I meant to write "the cardinality of the reals, [tex]\mathfrak{c}=2^{\aleph_0}[/tex].".


Register to reply

Related Discussions
A metric space having a countable dense subset has a countable base. Calculus & Beyond Homework 2
Countable But Not Second Countable Topological Space General Math 3
Bored to Bits General Discussion 19
When will e-bits overtake bio-bits? Computing & Technology 11
Bits and Bytes Computing & Technology 2