[FOM] inconsistency of P

[David Diamondstone]

> So far as I know, the concept of the "Kolmogorov
> complexity of a theory", as opposed to the Kolmogorov
> complexity of a number, is undefined. Certainly it
> does not occur in Chaitin's theorem or the Kritchman-Raz 
> proof.

You can talk about the Kolmogorov complexity of anything that can be coded with a number, including any finitely axiomatizable theory (code the axioms with a number) or any computably axiomatizable theory (code the machine enumerating the axioms with a number).

The point is that Chaitin's proof of the incompleteness theorem reaches a contradiction when the number l is such that the machine which searches through PA proofs for a proof that K(n)>l is actually shorter than l bits. The program of this machine needs to contain a description of PA in order to generate PA proofs, so the number l depends on the theory. If you replaced PA with a different theory, the number l would change, and would always be larger than the Kolmogorov complexity of the theory itself, up to some constant independent of the theory.