When do cofinal chains of universal codings of the integers exist?

2010-07-19T02:23:32Z

Universal codings of integers

A (binary) coding of the integers is a prefix-free code of the natural numbers, whose codewords are non-decreasing in size. A coding is universal if it is short enough (log n + o(log n)), but that's not important.

Some examples:

The unary coding 0, 10, 110, ...; code length is n
Code first the length of the number in unary, then the number itself in binary; code length is about 2log n
Code first the length of the number using the previous coding, then the number itself in binary; code length is about log n + 2log log n
...
Diagonalize the construction to get code length of log n + log log n + ... + 2log^* n
Continue this way through the constructible ordinals

The diagonalized code, known as the $\omega$-code, is due to Peter Elias.

A partial ordering of codes

The sequence of codes above are progressively better, in the following sense:

A coding a is better than a coding b if |b(n)| - |a(n)| tends to infinity.

There are some natural questions to ask:

Is there a best code?
If not, is there an optimal sequence of codes?

As it turns out, not only is there no best code, but given any sequence of codes, we can always find a code which is better than all of them; the proof from one of Hausdorff's papers (Untersuchungen über Ordnungtypen V from 1907) can be adapted to our setting.

Scales

The best thing that can be hoped for is a chain of codes which is cofinal for the poset of codes, i.e. a set of mutually comparable codings, such that for each arbitrary coding, our scale contains a superior one (such a beast Hausdorff called a Pantachie).

The problem of scales is well-known, and it is easy to show the existence of a scale given CH (following Hausdorff's steps). In other settings (and possibly this one), existence already follows from MA. However, most of the literature deals with somewhat different posets, and it is not clear that their results apply in this case.

Here are some pointers:

Hausdorff Gaps and Limits by Frankiewicz and Zbierski, which deals with the ordering f > g if f(n) > g(n) infinitely often.
Gaps in $\omega^\omega$ by Marion Scheepers, which deals with the ordering f > g if f(n) - g(n) tends to infinity.

In their settings, Hechler forcing can be used to produce worlds in which there is no scale.

Is the existence of scale (in the context of monotone codings of integers) independent of set theory?

Codings and series

Some easy reductions connect our problem with problems involving convergent series and divergent series satisfying some extra conditions, which stem from our monotonicity requirements; the key is Kraft's inequality, stating that a code with codeword lengths w_i exists iff the sum $\sum 2^{-w_i}$ converges.

The reductions are most easily stated if we extend our posets with some equivalence relation. We then say that two posets are interlacing if there are two order-preserving mappings (between the two posets in both directions) which are pseudo-inverses, i.e. their composition sends a point to an equivalent one. Given two interlacing posets, one has a scale iff the other one has a scale.

The following posets are interlacing:

Arbitrary (non-monotone) codes, with a < b if b is better than a, and a ~ b if |a(n)-b(n)| is bounded.
Convergent positive series, with a < b if b(n) = o(a(n)), and a ~ b if a(n) = O(b(n)) and b(n) = O(a(n)).
Divergent positive series (reverse definition of <).

Monotonicity complicates the picture (the corresponding series are no longer arbitrary) but seems necessary, since one can give a non-monotone code with the property that no monotone code is better than it.

Effective and efficient codings

The motivation behind the question is the actual usage of universal codings by computer engineers. New, impractical methods of codings are suggested all the time, but no one seems to have tackled the fundamental question.

This prompts us to ask similar questions for effective (computable) codings.

Can classical recursion theory hierarchies be adapted to the setting of codes?

It would be nice to get an analog of the fast-growing hierarchy, for example.

We could further wonder what happens if we ask our coding procedure to be efficient, for example linear-time computable.

Answer by Stefan Geschke for When do cofinal chains of universal codings of the integers exist?

2010-07-20T12:06:59Z

I believe I can answer your first question. But the answer involves forcing, which I cannot explain here (see Kunen's Set Theory. An introduction to independence proofs). Assuming CH, there is a scale of codes. Why? Enumerates all codes as $(c_\alpha)_{\alpha<\omega_1}$. Construct a sequence $(a_\alpha)_{\alpha<\omega_1}$ such that for each $\alpha$, the code $a_\alpha$ is better than $c_\alpha$ and all $a_{\beta}$, $\beta<\alpha$. This is possible since for every countable set of codes there is one code that is better than all of them, if I understand you correctly.
Now $(a_\alpha)_{\alpha<\omega_1}$ is a scale of codes.

For the other consistency result, namely ZFC is consistent with the non-existence of scales, consider the partial order of finite initial segments of monotone prefix-free codes, where a finite initial segment $c$ is stronger than $d$ ($c\leq d$) if $c$ extends $d$.
This partial order is countable and every element has two extensions that don't have a common extension. This implies that the partial order is forcing equivalent to the so called Cohen forcing.

Whenever $c$ is a finite initial segment of a code, $n$ is a natural number and $a$ is a code, then $c$ can be extended to a finite initial segment $d$ of a code such that for some $m>n$, $d$ already contains the code word of $m$ and this code word for $m$ is longer than the code word for $m$ that $a$ has.
Similarly, $c$ can be extended to a finite $d$ that for some $m>n$ has a shorter code word for $m$ than $a$ has.

This shows that forcing with this partial order adds a code that is incomparable with all codes in the ground model.

Now we start from a model of set theory that satisfies CH and force over it with a finite support product of $\aleph_2$ copies of the countable partial order defined above. This forcing adds a family $(c_\alpha)_{\alpha<\omega_2}$ generic codes. (CH fails in this generic extension). I claim that no subfamily of size $\aleph_1$ of this family of codes has an upper bound.

Why? Let $A\subseteq\omega_2$ be of size $\aleph_1$. By the properties of Cohen forcing (c.c.c. in particular) we may assume, after enlarging $A$ if necessary, that $A$ is already in the ground model. Now, whenever $a$ is a code in the generic extension, then $a$ has a name that only depends on countably many of the $c_\alpha$'s.
Take $\beta\in A$ outside this countable set of indices. Then, by the argument above, $c_\beta$ and $a$ are incomparable as codes (this is because $c_\beta$ is generic over a model containing $a$) and hence $a$ is not an upper bound of the $c_\alpha$, $\alpha\in A$.

A similar argument shows that in the model of set theory that we have constructed (which is in fact Cohen's original model that refutes CH) no set of codes of size $<\aleph_2$ is cofinal. (Why? If $C$ is a set of $\aleph_1$ codes, then there still is some $\alpha<\omega_2$ such that $c_\alpha$ is generic over a model that contains $C$ and now no element of $C$ is an upper bound for $c_\alpha$.)

We now have a model of set theory in which there is an unbounded set of codes of size $\aleph_1$ but no cofinal set of size $<\aleph_2$. This implies that there is no scale.

I hope it is possible to get something out of this answer. I am fully aware that I am using forcing jargon here, but to really give a complete proof would take a lot of space and time. I would guess that the code problem can actually be reduced to some partial order which has been studied in the literature.