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.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.
https://hdl.handle.net/11365/1082657