Theorema Posner–Robinson

E Vicipaedia
Jump to navigation Jump to search

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

Expositio[recensere | fontem recensere]

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

Demonstratio[recensere | fontem recensere]

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:

  1. Sit formula numero . Si nancisci possumus copiam quae (a) satisfaciat, ut cuique , , tum sit et .
  2. 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[recensere | fontem recensere]

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 .