In this paper we investigate some recursion-theoretic properties of the positive numerations induced by certain remarkable formulas of any theory T as strong as Peano Arithmetic: in particular we prove that any Sigma_n-truth predicate (in an appropriate sense) induces a precomplete positive numeration and that the formulas which preserve the provable equivalence induce u-m-v equivalence relations (and there exist formulas which induce u-m-c but not precomplete numerations). By means of theory of numerations, a classical result due to Putnam and Smullyan (1960) and redemonstrated by Smorynski (1978) is generalized.

Sorbi, A. (1983). Numerazioni positive, r.e. classi e formule. BOLLETTINO DELL'UNIONE MATEMATICA ITALIANA. A, 1-B(6), 403-411.

Numerazioni positive, r.e. classi e formule

Sorbi Andrea
1983-01-01

Abstract

In this paper we investigate some recursion-theoretic properties of the positive numerations induced by certain remarkable formulas of any theory T as strong as Peano Arithmetic: in particular we prove that any Sigma_n-truth predicate (in an appropriate sense) induces a precomplete positive numeration and that the formulas which preserve the provable equivalence induce u-m-v equivalence relations (and there exist formulas which induce u-m-c but not precomplete numerations). By means of theory of numerations, a classical result due to Putnam and Smullyan (1960) and redemonstrated by Smorynski (1978) is generalized.
1983
Sorbi, A. (1983). Numerazioni positive, r.e. classi e formule. BOLLETTINO DELL'UNIONE MATEMATICA ITALIANA. A, 1-B(6), 403-411.
File in questo prodotto:
File Dimensione Formato  
numerazioni-positive.pdf

non disponibili

Descrizione: Articolo
Tipologia: PDF editoriale
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 2.91 MB
Formato Adobe PDF
2.91 MB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11365/1082968