Is the cardinality of an infinite set correlated with the amount of information needed to specify any one element?

Question

I was thinking about the fact that some infinities are 'bigger' than others. For example, the cardinality of the reals is literally bigger than the cardinality of the rationals. One cannot match them one-to-one. Georg Cantor proved this several times.

But if I look at the infinities and the items they contain, I noticed a pattern. Aleph-0 is the infinity of the rational numbers. Any rational number is either terminating or repeating. To store any given rational finite number, one would need a finite amount of information. No matter how precise, the precision would be finite, and thus could be representable in a finite amount of information (bits, digits, etc).

But then if I look at the power set of Aleph-0 which is has the cardinality of the reals, to specify any given element from any other requires infinite information. An infinite number of bits is required to name any given irrational number. However, the amount of information needed to name any one element of an uncountable set is infinite, but countable. Each digit of pi corresponds to a natural number.

So if I extend this, to, say, the power set of the set of the real numbers, would that mean, to specify any given element, I would need an uncountable amount of information? There would be no digits in order that could possibly name any given element in the set, even given an infinite number of them?

In summary, is my assumption correct that for any one of the infinity infinite sets of differing sizes, to single out any one element, would require an amount of information equal to the previous smaller infinity?

Answer 1

Taking bits as our unit of information: given a cardinality $I$, the cardinality of the number of distinct objects that can be specified with $I$ bits of information is precisely $2^I$. So if the set to be encoded has cardinality $J$, then we must have at least as much information as the smallest cardinal $I$ such that $2^I \ge J$. Whether this is the cardinal preceding $J$ depends very much on what model of set theory one works in.

(The case of finite information to specify the countably infinite set $\Bbb Q$ seems to violate this, but "finite" isn't the same as "finite and of bounded size".)

Answer 2

An infinite number of bits is required to name any given irrational number.

This is not the case: an irrational algebraic (real) number, for example, can be finitely specified. I guess you're thinking of the non-computable, maybe even non-arithmetical/analytical numbers here

However, the amount of information needed to name any one element of an uncountable set is infinite, but countable.

Also doesn't seem right: the finite cardinals are elements of all uncountable cardinals, by definition, and it certainly should only take a finite amount of information to specify any finite cardinal

That said, there is a certain interesting kind of 'measure of complexity/information' in set theory, the ordinal rank, that's not at all about specifying individual elements, but rather saying when is "the sooner this set can occour/appear" in terms of all its elements, considered collectively, and it's notably not correlated with size, as, for example, $rank(2^{\omega}) = \omega + 1 \lt rank(\omega + \omega) = \omega + \omega$