By applying a notion of reducibility suggested by DiPaola and Heller to the domains of a recursion category previously introduced by ourselves, we get many-one reducibility between PI-2(0) sets of the arithmetical hierarchy of sets of functions by means of general recursive operators. We give a characterization of the complete domains in this reducibility. We also introduce an upper semilattice B to which this reducibility gives rise in a standard way. Several facts about B are proved: we characterize the finite ideals of B; the first order theory of B is shown to be undecidable.

Sorbi, A. (1991). Comparing Pi^0_2 of the Baire space by means of general recursive operators. FUNDAMENTA MATHEMATICAE, 138(1), 1-12 [10.4064/fm-138-1-1-12].

Comparing Pi^0_2 of the Baire space by means of general recursive operators

Sorbi Andrea
1991-01-01

Abstract

By applying a notion of reducibility suggested by DiPaola and Heller to the domains of a recursion category previously introduced by ourselves, we get many-one reducibility between PI-2(0) sets of the arithmetical hierarchy of sets of functions by means of general recursive operators. We give a characterization of the complete domains in this reducibility. We also introduce an upper semilattice B to which this reducibility gives rise in a standard way. Several facts about B are proved: we characterize the finite ideals of B; the first order theory of B is shown to be undecidable.
1991
Sorbi, A. (1991). Comparing Pi^0_2 of the Baire space by means of general recursive operators. FUNDAMENTA MATHEMATICAE, 138(1), 1-12 [10.4064/fm-138-1-1-12].
File in questo prodotto:
File Dimensione Formato  
comparing.pdf

non disponibili

Descrizione: Articolo
Tipologia: PDF editoriale
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 1.11 MB
Formato Adobe PDF
1.11 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/1082657