We investigate how to characterize total set-theoretic functionals in game theoretic models, and prove that well-founded winning strategies give a proper subclass of them, exactly consisting in Tait-definable functionals. Within the framework of generalized Novikoff-Coquand games with transfinite plays, total functionals (of finite type) are exactly definable by winning strategies, possibly of transfinite height. We exhibit two computable total type 3 functionals (of interest in program extraction from classical proofs) such that no well-founded strategy may define them.
Total functionals and well-founded strategies
BERARDI, Stefano;DE' LIGUORO, Ugo
1999-01-01
Abstract
We investigate how to characterize total set-theoretic functionals in game theoretic models, and prove that well-founded winning strategies give a proper subclass of them, exactly consisting in Tait-definable functionals. Within the framework of generalized Novikoff-Coquand games with transfinite plays, total functionals (of finite type) are exactly definable by winning strategies, possibly of transfinite height. We exhibit two computable total type 3 functionals (of interest in program extraction from classical proofs) such that no well-founded strategy may define them.File in questo prodotto:
File | Dimensione | Formato | |
---|---|---|---|
1999 Berardi dL - Total Functionals and Well-Founded Strategies.pdf
Accesso riservato
Descrizione: Articolo principale
Tipo di file:
PDF EDITORIALE
Dimensione
313.43 kB
Formato
Adobe PDF
|
313.43 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.