Register to reply 
Countable bits 
Share this thread: 
#1
Apr2708, 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? 


#2
Apr2708, 09:45 AM

Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,568

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.



#3
Apr2708, 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.



#4
Apr2708, 10:09 AM

Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,568

Countable bits
Oh, I see what you are saying. The two sets do NOT have the same cardinality.



#5
Apr2708, 10:30 AM

P: 688

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? 


#6
Apr2708, 12:41 PM

Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,568




#7
Apr2708, 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. 


#8
Apr2708, 07:13 PM

Sci Advisor
HW Helper
P: 3,684




#9
Apr2708, 07:16 PM

Sci Advisor
HW Helper
P: 3,684

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]. 


#10
Apr2808, 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. 


#11
Apr2808, 08:00 AM

Sci Advisor
HW Helper
P: 3,684

[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]. 


#12
Apr2808, 11:20 AM

P: 688




#13
Apr2808, 12:46 PM

Sci Advisor
HW Helper
P: 3,684

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 ebits overtake biobits?  Computing & Technology  11  
Bits and Bytes  Computing & Technology  2 