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
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
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