Изменения
→Применение
}}
Заметим, что во всех множествах пар все <tex>n</tex> ограничены какой-то константой, следовательно существует огромное число истинных, но недоказуемых утверждений вида <tex>KS(x) \geqslant n</tex>
===Доказательство бесконечности простых чисел===
{{Утверждение
|statement= Простых чисел бесконечно много.
|proof=
Предположим, что простых чисел конечное число. Тогда любое число <tex>n = {p_1}^{\alpha_1}{p_2}^{\alpha_2}\dots{p_k}^{\alpha_k}</tex>, где <tex>k</tex> {{---}} это некоторая константа. Возьмём <tex>n</tex> наибольшей колмогоровской сложности. Тогда <tex>KS(n) \geqslant log_2 n</tex>, но также <tex>KS(n) \leqslant k log_2 log_2 n + c</tex>, т.к. <tex>\alpha_i \leqslant log_2 n</tex>. Но это неравенство не будет выполняться на достаточно больших <tex>n</tex>, противоречие.
}}
== Источники ==
