Alonzo Church's mathematical work on computability and undecidability is well-known indeed, and we seem to have an excellent understanding of the context in which it arose. The approach Church took to the underlying conceptual issues, by contrast, is less well understood. Why, for example, was "Church's Thesis" put forward publicly only in April 1935, when it had been formulated already in February/March 1934? Why did Church choose to formulate it then in terms of Gödel's general recursiveness, not his own λ (...) -definability as he had done in 1934? A number of letters were exchanged between Church and Paul Bernays during the period from December 1934 to August 1937; they throw light on critical developments in Princeton during that period and reveal novel aspects of Church's distinctive contribution to the analysis of the informal notion of effective calculability. In particular, they allow me to give informed, though still tentative answers to the questions I raised; the character of my answers is reflected by an alternative title for this paper, Why Church needed Gödel's recursiveness for his Thesis. In Section 5, I contrast Church's analysis with that of Alan Turing and explore, in the very last section, an analogy with Dedekind's investigation of continuity. (shrink)

We show that there is a model of ZF in which the Borel hierarchy on the reals has length ω2. This implies that ω1 has countable cofinality, so the axiom of choice fails very badly in our model. A similar argument produces models of ZF in which the Borel hierarchy has exactly λ + 1 levels for any given limit ordinal λ less than ω2. We also show that assuming a large cardinal hypothesis there are models of ZF in which (...) the Borel hierarchy is arbitrarily long. (shrink)

In papers published between 1930 and 1935. Zermelo outlines a foundational program, with infinitary logic at its heart, that is intended to (1) secure axiomatic set theory as a foundation for arithmetic and analysis and (2) show that all mathematical propositions are decidable. Zermelo's theory of systems of infinitely long propositions may be termed "Cantorian" in that a logical distinction between open and closed domains plays a signal role. Well-foundedness and strong inaccessibility are used to systematically integrate highly transfinite concepts (...) of demonstrability and existence. Zermelo incompleteness is then the analogue of the Problem of Proper Classes, and the resolution of these two anomalies is similarly analogous. (shrink)