Notation

Much but not all of the notation used here is similar or identical to the one used in the standard textbook on Kolmogorov complexity by Li and Vitányi [30].

Since sentences over any finite alphabet are encodable as bitstrings, without loss of generality we focus on the binary alphabet $B=\{0,1\}$. $lambda$ denotes the empty string, $B^*$ the set of finite sequences over $B$, $B^{infty}$ the set of infinite sequences over $B$, $B^{sharp} = B^* cup B^{infty}$. $x,y,z,z^1,z^2$ stand for strings in $B^{sharp}$. If $x in B^*$ then $xy$ is the concatenation of $x$ and $y$ (e.g., if $x=10000$ and $y=1111$ then $xy = 100001111$). Let us order $B^{sharp}$ lexicographically: if $x$ precedes $y$ alphabetically (like in the example above) then we write $x prec y$ or $y succ x$; if $x$ may also equal $y$ then we write $x preceq y$ or $y succeq x$ (e.g., $lambda prec 001 prec 010 prec 1 prec 1111...$). The context will make clear where we also identify $x in B^*$ with a unique nonnegative integer $1x$ (e.g., string 0100 is represented by integer 10100 in the dyadic system or $20=1*2^4+0*2^3+1*2^2+0*2^1+0*2^0$ in the decimal system). Indices $i,j,m,m_0,m_1,n,n_0,t,t_0$ range over the positive integers, constants $c,c_0,c_1$ over the positive reals, $f,g$ denote functions mapping integers to integers, $log$ the logarithm with basis 2, $lg(r) = max_k \{integer k: 2^k leq r \}$ for real $r>0$. For $x in B^* backslash \{ lambda \}$, $0.x$ stands for the real number with dyadic expansion $x$ (note that $0.x0111....=0.x1=0.x10=0.x100...$ for $x in B^*$, although $x0111....neq x1 neq x10 neq x100...$). For $x in B^*$, $l(x)$ denotes the number of bits in $x$, where $l(x)= infty$ for $x in B^{infty}$; $l(lambda) = 0$. $x_{n}$ is the prefix of $x$ consisting of the first $n$ bits, if $l(x) geq n$, and $x$ otherwise ( $x_0 := lambda$). For those $x in B^*$ that contain at least one 0-bit, $x'$ denotes the lexicographically smallest $y succ x$ satisfying $l(y) leq l(x)$ ($x'$ is undefined for $x$ of the form $111ldots 1$). We write $f(n)=O(g(n))$ if there exists $c,n_0$ such that $f(n) leq cg(n)$ for all $n > n_0$.

For notational simplicity we will use the $sum$ sign also to indicate summation over uncountably many strings in $B^{sharp}$, rather than using traditional measure notation and $int$ signs. The reader should not feel uncomfortable with this notational liberty -- density-like nonzero sums over uncountably many bitstrings, each with individual measure zero, will not play any critical role in the proofs.