Please enable JavaScript.
Coggle requires JavaScript to display documents.
Calcolabilità e Logica (Incompletezza (Teoremi di incompletezza (:recycle:…
Calcolabilità e Logica
Incompletezza
- La funzione godeliana
- Definizione di SF godeliano
-
Teoremi limitativi:
- :recycle: Tarski
- :recycle: Church
- :recycle: Godel 1
- :recycle: Rosser
- Predicato standard di derivabilità
- :recycle: :recycle: Loeb
- :recycle: :recycle: Godel 2
-
-
Incompletezza
-
-
-
-
Codifica di sequenze
- monus, rem, Prime
- Succprimes
- px
- Def. (z)k, lth(z)
Definizione di Delta-0 e Sigma-1, Sigma
:recycle: D => |-f oppure |- non-f
In PA sigma <-> sigma-1
-
Rappresentabilità
:recycle: rapp. T => rapp. F
Es. sigma(x,y)
-
-
:recycle: PR sono rappresentabili
[induzione]
- Le formule sono tutte Sigma
-
-
Definizioni
- funzione come termine
- predicato come formula
- funzione come formula
Codifica del linguaggio di PA:
- sintassi
- Term, Seq, Form, Sub, Der, Cancel, Prov sono PR
- Teor è RP
-
Definizione di Sigma-correttezza
- PA è Sigma-corretta
- Ogni T Sigma-corretta è consistente
-
-
-
Definizioni:
- SF completo
- SF è RE
- SF decidibile
- SF assiomatizzabile
-
Teoremi di incompletezza
-
-
:recycle: Esistono teorie contenenti PA assiomatizzabili, consistenti, ma non Sigma-corrette
-
-
-
-
-
-