Siguiente: Propiedades Un nivel arriba: Kolmogorov Anterior: Kolmogorov

Conjuntos ralos

Sea A un conjunto. Definamos

$$A^{\leq n}=\{x\in A\vert \vert x\vert\leq n\}.$$

A es ralo si

$$\lim_{n\rightarrow\infty}\frac{1}{n}\mbox{\rm card}(A^{\leq n})=0.$$

Lema 1: Si A es un conjunto recursivo y ralo entonces para cada constante c se tiene que sólo para un número finito de elementos x se cumple

$$K(x)\geq \vert x\vert-c.$$

Lema 2: Sea A es un conjunto recursivo enumerable y $\epsilon>0$. Si

$$\lim_{n\rightarrow\infty}\frac{1}{n^{-(1+\epsilon)2^n}}\mbox{\rm card}(A^{\leq n})=0$$

entonces para cada constante c se tiene que sólo para un número finito de elementos x se cumple

$$K(x)\geq \vert x\vert-c.$$

Lema 3: Sea A es un conjunto recursivo enumerable. Si

$$\mbox{\rm card}(A^{\leq n})\leq p(n)$$

donde p(X) es un polinomio, entonces para cada constante c se tiene que sólo para un número finito de elementos x se cumple

$$K(x)\geq \frac{\vert x\vert}{c}.$$