Exploring a Paradox: Representing Countable Sets with Bits

[dodo]

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?

 

[HallsofIvy]

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]

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]

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]

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]

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]

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]

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]

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 $2^{\aleph_0}=\beth_1$, but this is not known in general to equal $\aleph_1$.

 

[dodo]

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]

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.
$$\aleph_0\le\kappa\le\aleph_1$$ is such that $\kappa=\aleph_0$ or $\kappa=\aleph_1$ for all $\kappa$. In that sense the aleph number is the successor: no cardinal is 'between' $\alpeh_0$ and $\aleph_1$ just like no natural number is 'between' 1 and 2.

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

(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, $\mathcal{c}=\beth_1$.

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 $2^S=\aleph_0$.

 

[dodo]

I think you mean this: there is no set S for which $2^S=\aleph_0$.

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]

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: $\aleph_0$. How many bits for the reals? $\aleph_0$. How many bits for the functions $f:\mathbb{R}\to\mathbb{R}$? $2^{\aleph_0}$.

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