In this paper we discuss the following contributions to recursion theory made by John Myhill: two sets are recursively isomorphic iff they are one-one equivalent; two sets are recursively isomorphic iff they are recursively equivalent and their complements are also recursively equivalent; every two creative sets are recursively isomorphic; the recursive analogue of the Cantor–Bernstein theorem; the notion of a combinatorial function and its use in the theory of recursive equivalence types.

As to the misconceptions: In the first place, the existence of "undecidable propositions" or "unsolvable problems" has only remote connections with the failure of excluded middle. More precisely, from the fact that a certain problem is unsolvable, one cannot infer that the affirmative and negative answers to that problem are both incorrect. Both Gödel's and Church's theorems were originally proved for systems with the excluded middle, i.e. for systems in which 'p or not p' is provable for every proposition 'p'; (...) though in the light of Gödel's theorem there are propositions 'p' such that neither 'p' nor 'not p' is provable in those systems. Careful distinction should be made between the following locutions. (shrink)

Information can be public among a group. Whether or not information is public matters, for example, for accounts of interdependent rational choice, of communication, and of joint intention. A standard analysis of public information identifies it with (some variant of) common belief. The latter notion is stipulatively defined as an infinite conjunction: for p to be commonly believed is for it to believed by all members of a group, for all members to believe that all members believe it, and so (...) forth. This analysis is often presupposed without much argument in philosophy. Theoretical entrenchment or intuitions about cases might give some traction on the question, but give little insight about why the identification holds, if it does. The strategy of this paper is to characterize a practical-normative role for information being public, and show that the only things that play that role are (variants of) common belief as stipulatively characterized. In more detail: a functional role for “taking a proposition for granted” in non-isolated decision making is characterized. I then present some minimal conditions under which such an attitude is correctly held. The key assumption links this attitude to beliefs about what is public. From minimal a priori principles, we can argue that a proposition being public among a group entails common commitment to believe among that group. Later sections explore partial converses to this result, the factivity of publicity and publicity from the perspective of outsiders to the group, and objections to the aprioricity of the result deriving from a posteriori existential presuppositions. (shrink)