Theorema Posner–Robinson

Theorema Posner–Robinson est theorema theoriae facultatis calculandi de gradibus Turing.

 Expositio 
Theorema. Sit  copia numerorum naturalium, quae calculari non potest. (Id est .) Tum est copia  ut
.

 Demonstratio 
Sit . Volumus facere series , quorum:
  est copia finita rerum sicut , in qua , .  est functio ab  in , ut  si et tantum si ,
  est copia finita rerum ,
in qua serie, si :
 (a) Cuique  et , ,
 (b)  et ,
 (c) Cuique , .
ita ut, si , tum . Sit . Si habemus , sic agamus ut  faciamus:
 Sit  formula numero . Si nancisci possumus copiam  quae (a) satisfaciat, ut cuique , , tum sit  et .
 Sin nancisci non possumus , tum sciamus cuique copiae  quae (a) satisfaciat esse  ut . Sit igitur collectio  ut:

Sed scilicet , ergo . Lemma habemus:
Lemma. (de conis vitandis) Sit collectio non vacua  ut , in quo  (vide pagina de hierarchia arithmetica). Sit . Tum est  ut .
Ergo, sit , tum est  ut , id est, . Igitur sit  et .
Nunc tota serie facta habemus  ut . Ergo , quod erat demonstrandum.

 Significatio 
Hoc theorema naturam omnium copiarum quae calculari non possunt patefacit. Si  est copia quae calculari non potest, tum nancisci possumus copia , ut differentia inter  et  sit .

Categoria:Theoremata mathematica
Categoria:Logica