A Note on the Logarithm of Infinite Cardinals

I thought I had posted something about the logarithm of \aleph_0, which is something I think about at times, but I can’t seem to find it, so I’ll begin from scratch:

Lemma 1. The logarithm of \aleph_0 is not equal to \aleph_0.

Proof. Assume that \aleph_0 = \log(\aleph_0). If we assume that \aleph_1 = |\mathbb{R}| = 2^{\aleph_0}, then it follows that \aleph_1 = 2^{\log(\aleph_0)}, which leads to a contradiction, since 2^{\log(\aleph_0)} = \aleph_0.

Definitions. As a consequence, I’ve defined a new number, \Omega = \log(\aleph_0), that I’ve used in apparently unpublished research to think about the number of bits you’d need to represent a countably infinite system. However, it just dawned on me that you can construct a system that has a number of bits equal to \Omega as follows:

Assume that a system S is comprised of a countable number of rows, each indexed by the natural numbers, starting with 1. Now assume that for each row, you have a number of bits equal to the index of the row. So for example, in row 1, you have 1 bit, which can be in exactly 2^1 states, and in row 2, 2 bits, which can be in exactly 2^2 = 4 states, etc. However, assume S has a tape head, like a UTM, that can move both up and down rows, and left and right, thereby reading or writing to the bits in the row at its current index. So for example, if the head is currently at row 2, it can move left or right, to access the 2 bits that are in that row. Further, assume that if the head moves either up or down, then all of the bits in every row reset to zero. So this means that once the tape head changes rows, all of the information in the entire system is effectively deleted.

The number of states that S can occupy is at least \aleph_0, since it can represent every natural number. However, S is distinct from a countably infinite binary string, since changing the row of the tape head causes the entire system to reset, which implies that only a finite number of bits, all within a single row, can ever be used in combination with one another. The number of bits in S is therefore unbounded, but not equal to \aleph_0, because they cannot be used in combination with one another, outside of a single row.

Lemma  2. The number of states of S cannot be greater than \aleph_0.

Proof. We can assign finite, mutually exclusive subsets of \mathbb{N} to each row i of S with a cardinality of at least 2^i (e.g., use mutually exclusive subsets of powers of primes). Therefore, the number of states of S cannot be greater than the number of elements in \mathbb{N}, which is equal to \aleph_0.

Corollary  3. The number of states of S is equal to \aleph_0.

Proof. Every natural number corresponds to at least one state of S, which implies that the number of states of S is at least \aleph_0. However, Lemma 2 implies that the number of states of S cannot be greater than \aleph_0, which implies that they are equal.

Assumption. The number of bits in a system is equal to the logarithm of the number of states of the system.

This is a standard assumption for finite systems, since it implies that a system with N states is equivalent to \log(N) bits. In this case, it implies that S is equivalent to \Omega = \log(\aleph_0) bits, since S has exactly \aleph_0 states, just like the set of natural numbers itself.

Lemma 4. \Omega + c = \Omega, for all c \in \mathbb{R}.

Proof. Assume \Omega + c = X. It follows that 2^{\Omega + c} = 2^{\Omega} 2^{c} = \aleph_0 2^c = \aleph_0, which implies X = \Omega.

Corollary 5. \Omega \notin \mathbb{N}.

Proof. This follows immediately from Lemma 4, since there is no such natural number.

Note that \Omega - 1 = \Omega, which in turn implies that we can remove any single row from S, without reducing the number of bits in S, which is clearly the case.

Corollary  6. \Omega < \aleph_0.

Proof. We can assign finite, mutually exclusive subsets of \mathbb{N} to each row i of S with a cardinality of at least i (e.g., use mutually exclusive subsets of powers of primes). Therefore, the number of bits in S cannot be greater than the number of elements in \mathbb{N}, which is equal to \aleph_0. However, Lemma 1 implies that \Omega \neq \aleph_0, and therefore, \Omega < \aleph_0.

Corollary  7. \Omega > n, for all n \in \mathbb{N}.

Proof. For any given n \in \mathbb{N}, we can always find a row i of S such that i > n. Therefore, the number of bits in S is greater than n, for all n \in \mathbb{N}.

Corollary  8. There is no set A \subseteq \mathbb{N} with a cardinality of \Omega.

Proof. Assume such a set A exists. Because \Omega > n, for all n \in \mathbb{N}, |A| cannot be finite. Because |A| < |\mathbb{N}|, A cannot be countable. All subsets of \mathbb{N} are comprised of either a finite, or countable number of elements, which completes the proof.

So to summarize, the number of bits in S is sufficient to represent all natural numbers, and the number of states of S is equal to the cardinality of the natural numbers. If we assume as a general matter, that the number of bits in a system is equal to the logarithm of the number of states of the system, then the number of bits in S is \Omega = \log(\aleph_0).

Corollary  9. There is no number of bits X < \Omega, such that X > n, for all n \in \mathbb{N}.

Proof. Assume that such a number exists, and that for some system \bar{S}, the number of states of \bar{S} is 2^X. If 2^X = \aleph_0, then X = \Omega, which leads to a contradiction, so it must be the case that 2^X \neq \aleph_0. Because X < \Omega, the number of states of \bar{S} must be less than the number of states of S, and so 2^X < \aleph_0. This implies that we can assign each state of \bar{S} a unique natural number, which in turn implies the existence of a set of natural numbers A, such that |A| > n, for all n \in \mathbb{N}, and |A| < \aleph_0. Since the existence of \bar{S} implies the existence of A, which leads to a contradiction, \bar{S} does not exist.

Corollary  10. There is no set A such that |A| = \Omega.

Proof. Assume such a set A exists. Since \Omega < \aleph_0, we can assign each element of A a unique natural number, which will in the aggregate generate a set B \subset \mathbb{N}. The existence of B contradicts Corollary 8, which completes the proof.

This work implies that \Omega is the smallest non-finite number, and that it does not correspond to the cardinality of any set.

This in turn implies an elegant theory of number itself:

Begin with a system S_0, that is always in the same state s_0, and assume that the number of states of S_0 is 1, and that the number of bits in S_0 is 0 = \log(1). Now assume the existence of S_1, that is always in the same state s_1, and that this state is distinct from s_0. Further, assume the existence of some system \bar{S} that can be in either s_0 or s_1, and assume that the number of states of \bar{S} is 2, and that the number of bits in \bar{S} is 1 = \log(2). If we allow for unbounded instances of \bar{S} to exist in conjunction with one another, then basic counting principles imply the existence of all natural numbers, since a collection of systems, each equivalent to \bar{S}, is in turn equivalent to some binary string.

Note that in this view, the number 0 always has units of bits, and is never some number of states, just like \Omega must always have units of bits, since it does not correspond to the cardinality of any set, or number of states. It suggests the notion that some numbers must necessarily cary particular units, because they can only be derived from one class of mathematical object, that necessarily implies those units. For example, in this view, 0 must always carry units of bits, and can never cary units of states. In contrast, 1 can be either a number of bits, or a number of states.

Interestingly, Shannon’s equation implies that the logarithm of the reciprocal of a probability, \log(\frac{1}{p}) has units of bits. The work above implies that the logarithm of some number of states, \log(N) also has units of bits. Together, this implies that a probability has units of the reciprocal of some number of states, p = \frac{1}{N}. This is perfectly consistent with a frequentist view of a probability, which would be expressed as some portion of some number of states. Again, all of this work suggests the possibility that numbers have intrinsic units, apart from any physical measurement.

Advertisement

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s