Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
Stefan Geschke explained what to do in order to construct a model in which there is no scale. The recursion theory part still remains open. –  Yuval Filmus Jul 21 '10 at 22:26
add comment

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
In Frankiewicz and Zbierski's notation, you're showing that b < d, where b is the cardinality of the minimal unbounded set, and d the cardinality of the minimal cofinal set. That implies the non-existence of a scale. I wonder what Hechler forcing is for (and what is it), if this problem can be solved using simple Cohen forcing? –  Yuval Filmus Jul 20 '10 at 14:16
    
Yes, indeed, I am constructing a model where $b<d$ for the partial order of codes. While the Cohen forcing adds a code that is incomparable to the codes in the ground model, Hechler forcing adds a function $f:\mathbb N\to\mathbb N$ that dominates all functions in the ground model. I didn't check any details, but I think there is an analog to Hechler forcing for codes. This would allow to construct models where $2^{\aleph_0}$ is big, but there is a scale of length $\omega_1$. (Iteration of Hechler forcing resp. its analog of length $\omega_1$ over a model with the desired $2^{\aleph_0}$.) –  Stefan Geschke Jul 20 '10 at 15:18
    
Hechler introduced his forcing to prove a far more general result than the consistency of b < d. He showed how to get any reasonable prescribed partial ordering in the ground model to be isomorphic to a cofinal subset of $\omega^\omega$ in a forcing extension. (Here $\omega^\omega$ means the set of functions from natural numbers to natural numbers, and the ordering is eventual domination.) "Reasonable" means that every countable subset of the prescribed ordering must have an upper bound. –  Andreas Blass Jul 20 '10 at 15:22
    
You can also iterate Hechler forcing of length $\kappa$, $\kappa\geq 2^{\aleph_0}$ and obtain a model with a scale of length $\kappa$. In general, Hechler forcing can be used to embed partial orders cofinally into the partial order of functions from $\mathbb N$ to $\mathbb N$ with eventual dominance. You obviously need some assumptions on your partial order, such as every countable subset is bounded, to get a cofinal embedding. Anyhow. This way you can use Hechler forcing to get models without scales. But as pointed out, if you only want "no scales", Cohen forcing is enough. –  Stefan Geschke Jul 20 '10 at 15:23
    
Oh. Hi Andreas. Apparently you posted your comment about Hechler forcing while I was typing my second part. –  Stefan Geschke Jul 20 '10 at 16:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.