We show that for every countable recursively saturated model M of Peano arithmetic and every subset A⊆M, there exists a full satisfaction class SA⊆M2 such that A is definable in (M,SA) without parameters. It follows that in every such model, there exists a full satisfaction class which makes every element definable, and thus the expanded model is minimal and rigid. On the other hand, as observed by Roman Kossak, for every full satisfaction class S there are two elements which have (...) the same arithmetical type, but exactly one of them is in S. In particular, the automorphism group of a model expanded with a satisfaction class is never equal to the automorphism group of the original model. The analogue of the first result proved here for full satisfaction classes was obtained also by Roman Kossak for partial inductive satisfaction classes. However, the proof relied on the induction scheme in a crucial way, so recapturing the result in the setting of full satisfaction classes requires quite different arguments. (shrink)

We investigate two constants cT and rT, introduced by Chaitin and Raatikainen respectively, defined for each recursively axiomatizable consistent theory T and universal Turing machine used to determine Kolmogorov complexity. Raatikainen argued that cT does not represent the complexity of T and found that for two theories S and T, one can always find a universal Turing machine such that equation image. We prove the following are equivalent: equation image for some universal Turing machine, equation image for some universal Turing (...) machine, and T proves some Π1-sentence which S cannnot prove. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim. (shrink)