On effectively computable realizations of choice functions (Q1072545)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On effectively computable realizations of choice functions
scientific article

    Statements

    On effectively computable realizations of choice functions (English)
    0 references
    0 references
    1985
    0 references
    If \({\mathcal M}({\mathbb{R}}^ n)\) is a recursive metric space in the sense of Moschovakis, let \(<{\mathcal R}({\mathcal X}),{\mathbb{F}}_{{\mathcal R}}>\) be a recursive space of alternatives derived from \({\mathcal M}({\mathbb{R}}^ n)\) where \({\mathcal R}({\mathcal X})\) is the recursive representation of a compact, convex subset of \({\mathbb{R}}^ n_+\), and where \({\mathbb{F}}_{{\mathcal R}}\) is the class of recursive subsets of \({\mathcal R}({\mathcal X})\), Let \(\phi:{\mathbb{F}}_{{\mathcal R}}\to {\mathcal P}({\mathcal R}({\mathcal X}))\) be a choice function on \(<{\mathcal R}({\mathcal X}),{\mathbb{F}}_{{\mathcal R}}>\) such that for some binary relation \(\gtrsim:{\mathcal R}({\mathcal X})^ 2\to \{0,1\}\) and a potentially partial recursive function \(f:{\mathcal R}({\mathcal X})\to {\mathbb{N}}:\) (i) \(\forall \alpha,\beta \in {\mathcal R}({\mathcal X})[\alpha \gtrsim \beta \to f(\alpha)\geq f(\beta)]\) and (ii) \(\forall A\in {\mathbb{F}}_{{\mathcal R}}[\phi (A)=\{\alpha: \forall \beta \in A\) \((f(\alpha)\geq f(\beta))\}]\), and call \(\phi\) recursively rational. The main theorem of this paper proves that no non-trivial recursively rational choice function \(\phi\), on a recursive space of alternatives \(<{\mathcal R}({\mathcal X}),{\mathbb{F}}_{{\mathcal R}}>\), can be recursively realized within Church's thesis. This result has as a consequence that non-trivial demand correspondences on recursive spaces of alternatives \(<{\mathcal R}({\mathcal X}),{\mathbb{F}}_{{\mathcal R}}>\) in the neo-classical sense, are not recursively realizable within Church's thesis.
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    Turing machines
    0 references
    recursive realizability
    0 references
    recursive unsolvability
    0 references
    Kleene-Mostowski arithmetic hierarchy
    0 references
    recursively presented models
    0 references
    recursive metric space
    0 references
    recursive space of alternatives
    0 references
    recursively rational choice function
    0 references
    Church's thesis
    0 references
    demand correspondences
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references