The connection between Kolmogorov complexity and mathematical logic

I'm glad I found this question, here are two of my favorite relatively simple, yet lengthy, examples. The Kolmogorov complexity will be denoted $C(x)$.

---

Theorem: There are infinitely many primes.

Proof: Suppose there isn't. The there are $k$ primes $p_{1},p_{2},...,p{k}$ for $k in mathbb{N}$. Therefore, we can take any $m in mathbb{N}$ and write it as a product of these $k$ primes: $$m = p^{e_{1}}_{1}...p^{e_{k}}_{k}.$$ Now, let $m$ be Kolmogorov random and have length $n$. We can describe $m$ by $e_{1},e_{2},...,e_{k}$. We claim that this gives a short description of $m$. First, $e_{i} le $ log$m$, thus $|e_{i}| le$ log$cdot$log$m$. Hence $|langle e_{1},...,e_{k}rangle| le 2k$log$cdot$ log$m$. Therefore, as $m le 2^{n+1}$, $|langle e_{1},...,e_{k} rangle| le 2k$log$(n+1)$, so $C(m) le 2k$log$(n+1)+c$ (for $c in mathbb{N}$). For large enough $n$, this contradicts $C(m) ge$, which follows from the fact that $m$ is random. $blacksquare$

---

One could say that the proof above is more complex than the original one. However, the following result is pretty close to the real “prime number theorem” and, in my opinion, is definitely easier.

Let $p_{m}$ be the largest prime that divides $m$. The we can describe $m$ by specifying $p_{i}$ and $frac{m}{p_{i}}$; and actually all we need is $i$ and $frac{m}{p_{i}}$ since we can compute $p_{i}$ given $i$. for $m$ random, we have the following: $C(m) le C(<i, frac{m}{p_{i}}>) le 2$log$|i|+|i|+|frac{m}{p_{i}}|$, so log$m le 2$log$cdot$log$i+$log$i+$log$m -$log$p_{i}$. Cancelling gives us log$p_{i} le$ log$i+2$log$cdot$log$i$ which in turn gives $p_{i} le i$$($log$i$$)^{2}$.

The classical theorem is that the $i$-th prime is below $i$ log $i$, so the above is pretty close. Interestingly, most strings are “close” to being random.

---

EDIT: Since I have realized, according to the comment on this answer, that these examples are outside mathematical logic. To make up for this, I provide the following link. This is a great .pdf that explores the usage of Kolmogorov complexity on logical operators and related formulae. Also, it gives some pretty neat diagrams of these ideas! I will keep the examples above to, hopefully, provide a good outside mathematical logic learning experience.