On effectively computable realizations of choice functions
type: Item
instance of: scholarly article
title: On effectively computable realizations of choice functions
zbMATH Open document ID: 0587.03035
DOI: 10.1016/0165-4896(85)90038-1
author: Alain A. Lewis
published in: Mathematical Social Sciences
publication date: 1985-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 03D45
Mathematics Subject Classification ID: 91B06
Mathematics Subject Classification ID: 03D20
Mathematics Subject Classification ID: 03D10
Mathematics Subject Classification ID: 03C57
zbMATH DE Number: 3941527
zbMATH Keywords: Turing machines
zbMATH Keywords: recursive realizability
zbMATH Keywords: recursive unsolvability
zbMATH Keywords: Kleene-Mostowski arithmetic hierarchy
zbMATH Keywords: recursively presented models
zbMATH Keywords: recursive metric space
zbMATH Keywords: recursive space of alternatives
zbMATH Keywords: recursively rational choice function
zbMATH Keywords: Church's thesis
zbMATH Keywords: demand correspondences
MaRDI profile type: Publication
full work available at URL: 0165-4896(85)90038-1
OpenAlex ID: W1514705400
cites work: The metalogic of economic predictions, calculations and propositions
cites work: Q5570933
cites work: Social choice and individual values
cites work: Social Decision Functions and the Veto
cites work: Realization of Choice Functions
cites work: Hilbert's Tenth Problem is Unsolvable
cites work: Q5588318
cites work: The complexity of economic decision rules
cites work: Q5817866
cites work: Q3048535
cites work: Complexity of games and bounded rationality
cites work: Q3231295
cites work: A topological analog to the Rice-Shapiro index theorem
cites work: Q5330638
cites work: The axiom of choice
cites work: \(\lambda\)-definability and recursiveness
cites work: Q5812175
cites work: Q5528627
cites work: Q3214888
cites work: Q5733134
cites work: On some games which are relevant to the theory of recursively enumerable sets
cites work: Some Generic Properties of Aggregate Excess Demand and an Application
cites work: The generation of a social welfare function under ordinal preferences
cites work: Transversal theory. An account of some aspects of combinatorial mathematics
cites work: Recursive metric spaces
cites work: Q5518362
cites work: The Existence of Choice Functions
cites work: Some Stone spaces and recursion theory
cites work: The upper semi-lattice of degrees of recursive unsolvability
cites work: Recursive Functions and Hierarchies
cites work: Q3245637
cites work: Recursive Real Numbers
cites work: Q4403954
cites work: Classes of Predictably Computable Functions
cites work: Q5573961
cites work: Degrees of Computability
cites work: Q3677761
cites work: Utility theory based on rational probabilities
cites work: Q5537599
cites work: Q3251780
cites work: Q3216650
cites work: Recursively enumerable sets and degrees
cites work: Q5553288
cites work: On Computable Numbers, with an Application to the Entscheidungsproblem
description: scientific article; zbMATH DE number 3941527