Skip to main content
MathOverflow

Return to Question

Notice removed Draw attention by CommunityBot
Bounty Ended with Carlo Beenakker's answer chosen by CommunityBot
Notice added Draw attention by Jori
Bounty Started worth 100 reputation by Jori
added 7 characters in body
Source Link
Jori
Jori
  • 189
  • 8

We know that Kolmogorov Cmplexity (KC) has connections to mathematical logic since it can be used to prove the Gödel incompleteness results (Chaitin's Theorem and Kritchman-Raz). Are there any other striking application of Kolmogorov complexity to mathematical logic (outside KC itself of course)?

Relatively simple examples like the ones I mentioned are preferred, but more complicated illustrations are also very welcome!

(This is cross posted from MSE, because I wasn't getting any useful replies there)

We know that Kolmogorov Cmplexity (KC) has connections to mathematical logic since it can be used to prove the Gödel incompleteness results (Chaitin's Theorem and Kritchman-Raz). Are there any other striking application of Kolmogorov complexity to mathematical logic (outside KC itself of course)?

Relatively simple examples like the ones I mentioned are preferred, but more complicated illustrations are also very welcome!

(This is cross posted from MSE, because I wasn't getting any replies there)

We know that Kolmogorov Cmplexity (KC) has connections to mathematical logic since it can be used to prove the Gödel incompleteness results (Chaitin's Theorem and Kritchman-Raz). Are there any other striking application of Kolmogorov complexity to mathematical logic (outside KC itself of course)?

Relatively simple examples like the ones I mentioned are preferred, but more complicated illustrations are also very welcome!

(This is cross posted from MSE, because I wasn't getting any useful replies there)

Source Link
Jori
Jori
  • 189
  • 8

The connections between Kolmogorov complexity and mathematical logic

We know that Kolmogorov Cmplexity (KC) has connections to mathematical logic since it can be used to prove the Gödel incompleteness results (Chaitin's Theorem and Kritchman-Raz). Are there any other striking application of Kolmogorov complexity to mathematical logic (outside KC itself of course)?

Relatively simple examples like the ones I mentioned are preferred, but more complicated illustrations are also very welcome!

(This is cross posted from MSE, because I wasn't getting any replies there)