In this paper we will discuss the active part played by certain diagonal arguments in the genesis of computability theory. 1 In some cases it is enough to assume the enumerability of Y while in others the effective enumerability is a substantial demand. These enigmatical words by Kleene were our point of departure: When Church proposed this thesis, I sat down to disprove it by diagonalizing out of the class of the λ–definable functions. But, quickly realizing that the diagonalization cannot (...) be done effectively, I became overnight a supporter of the thesis. (1981, p. 59) The title of our paper alludes to this very work, a task on which Kleene claims to have set out after hearing such a remarkable statement from Church, who was his teacher at the time. There are quite a few points made in this extract that may be surprising. First, it talks about a proof by diagonalization in order to test—in fact to try to falsify—a hypothesis that is not strictly formal. Second, it states that such a proof or diagonal construction fails. Third, it seems to use the failure as a support for the thesis. Finally, the episode we have just described took place at a time, autumn 1933, in which many of the results that characterize Computability Theory had not yet materialized. The aim of this paper is to show that Church and Kleene discovered a way to block a very particular instance of a diagonal construction: one that is closely related to the content of Church's thesis. We will start by analysing the logical structure of a diagonal construction. Then we will introduce the historical context in order to analyse the reasons that might have led Kleene to think that the failure of this very specific diagonal proof could support the thesis. This is a joint paper. We have both attempted to add a small piece to an amazing historical jigsaw puzzle at a juncture we feel to be appropiate. In the paper by Manzano 1997 the aforementioned words by Kleene were quoted, and since then several logicians, Enrique Alonso first and foremost, have questioned her on this issue. Here we both submit our reply. (1999, pp. 249--273). (shrink)

In a recent paper, Montagna proved the undecidability of the first-order theory of diagonalisable algebras. This result is here refined — the set of finitely refutable sentences is shown effectively inseparable from the set of theorems. The proof is quite simple.

Milne [2005] argued that a sentence saying of itself that it does not have a truthmaker is true but does not have a truthmaker. López de Sa and Zardini [2006] worried that, by parity of reasoning, one should conclude that a sentence saying of itself that it is not both true and short is true but not short. Recently, Milne [2013] and Gołosz [2015] have replied to López de Sa and Zardini’s worry, arguing in different ways that the worry is (...) illfounded. In this paper, I’ll address these replies and argue that they fail to dispel López de Sa and Zardini’s worry, bringing out in the process some broader points concerning the use of self-referential sentences in arguments in philosophy of logic. (shrink)

The role of the environment in producing the correct classical limit in the Bohm interpretation of quantum mechanics is investigated, in the context of a model of quantum Brownian motion. One of the effects of the interaction is to produce a rapid approximate diagonalisation of the reduced density matrix in the position representation. This effect is, by itself, insufficient to produce generically quasi-classical behaviour of the Bohmian trajectory. However, it is shown that, if the system particle is initially in (...) an approximate energy eigenstate, then there is a tendency for the Bohmian trajectory to become approximately classical on a longer time-scale. The relationship between this phenomenon and the behaviour of the Wigner function post-decoherence is discussed. (shrink)

This paper examines the paradox of revisability. This paradox was proposed by Jerrold Katz as a problem for Quinean naturalised epistemology. Katz employs diagonalisation to demonstrate what he takes to be an inconsistency in the constitutive principles of Quine's epistemology. Specifically, the problem seems to rest with the principle of universal revisability which states that no statement is immune to revision. In this paper it is argued that although there is something odd about employing universal revisability to revise itself, (...) there is nothing paradoxical about this. At least, there is no paradox along the lines suggested by Katz. (shrink)

This manuscript explores the orthogonality constraints on configurations and orbitals subject to the property that states are mutually orthogonal. The orthogonality constraints lead to properties that affect the description of chemical systems. When states are described as linear combinations of configurations, the coefficient matrix diagonalises S−1H. Therefore, single-configuration states are only possible in one-electron systems: non-orthogonal configurations yield single-configuration states only if S−1H is diagonal, but this would violate the orthonormalisation constraint. Further, the coefficient matrix is not constrained to be (...) square. Similarly, the orbitals used to construct configurations may also be orthogonal or non-orthogonal; orbitals are only required to be mutually orthogonal at the one-electron limit. Orthogonal orbitals are generally preferred due to their mathematical and conceptual simplicity, leading to fictitious unoccupied orbitals. Since the Fock operator is orthogonality agnostic, non-orthogonal orbitals can be generated by solving the Fock equation independently for each electron; the virtual orbitals produced by this conception are true excitation orbitals as they are eigensolutions of the Fock operator. Additionally, we show that the number of molecular orbitals generated is not restricted to the number of atomic orbitals employed in the computation. This manuscript explores the mathematical relationships that need to be satisfied under the various orthogonality regimes. We also present mathematical relationships that provide results that are independent of the orthogonality approximation within a particular computational method. (shrink)

Derrida's key concepts or pseudo-concepts of différance, the trace, and the undecidable suggest analogies to some of the most significant results of formal, symbolic logic and metalogic. As early as 1970, Derrida himself pointed out an analogy between his use of ‘undecidable’ and Gödel's incompleteness theorems, which demonstrate the existence, in any sufficiently complex and consistent system, of propositions which cannot be proven or disproven (i.e., decided) within that system itself. More recently, Graham Priest has interpreted différance as an instance (...) of the general metalogical procedure of diagonalisation. In this essay, I consider the extent to which Derrida's key terms and the essential operations of deconstruction can be formalised. I argue that, if formalisation is indeed the technique of writing par excellence, then the formalisation of deconstructive concepts tends to show how the auto-deconstruction of total systems arises from the problematic possibility of writing itself. For instance, since diagonalisation permits the ‘arithmetisation of syntax’ whereby a formal system is able to formulate claims about its own logico-grammatical properties, we can understand its potential to inscribe the undecidable within the systematicity of language as simply one instance of the potential of writing, in figuring itself, to render inscrutable the trace of its own origin. (shrink)

The prevalent interpretation of Gödel’s Second Theorem states that a sufficiently adequate and consistent theory does not prove its consistency. It is however not entirely clear how to justify this informal reading, as the formulation of the underlying mathematical theorem depends on several arbitrary formalisation choices. In this paper I examine the theorem’s dependency regarding Gödel numberings. I introducedeviantnumberings, yielding provability predicates satisfying Löb’s conditions, which result in provable consistency sentences. According to the main result of this paper however, these (...) “counterexamples” do not refute the theorem’s prevalent interpretation, since once a natural class ofadmissiblenumberings is singled out, invariance is maintained. (shrink)

Lucas and Penrose have contended that, by displaying how any characterisation of arithmetical proof programmable into a machine allows of diagonalisation, generating a humanly recognisable proof which eludes that characterisation, Gödel's incompleteness theorem rules out any purely mechanical model of the human intellect. The main criticisms of this argument have been that the proof generated by diagonalisation (i) will not be humanly recognisable unless humans can grasp the specification of the object-system (Benacerraf); and (ii) counts as a proof (...) only on the (unproven) hypothesis that the object system is consistent (Putnam). The present paper argues that criticism (ii) may be met head-on by an intuitionistic proponent of the anti-mechanist argument; and that criticism (i) is simply mistaken. However the paper concludes by questioning the sufficiency of the situation for an interesting anti-mechanist conclusion. (shrink)

We claim that a recent article of P. Cotogno ([2003]) in this journal is based on an incorrect argument concerning the non-computability of diagonal functions. The point is that whilst diagonal functions are not computable by any function of the class over which they diagonalise, there is no ?logical incomputability? in their being computed over a wider class. Hence this ?logical incomputability? regrettably cannot be used in his argument that no hypercomputation can compute the Halting problem. This seems to lead (...) him into a further error in his analysis of the supposed conventional status of the infinite time Turing machines of Hamkins and Lewis ([2000]). Theorem 1 refutes this directly. The diagonalisation misunderstanding Infinite computation Conclusion. (shrink)

Lucas and Penrose have contended that, by displaying how any characterisation of arithmetical proof programmable into a machine allows of diagonalisation, generating a humanly recognisable proof which eludes that characterisation, Gödel's incompleteness theorem rules out any purely mechanical model of the human intellect. The main criticisms of this argument have been that the proof generated by diagonalisation will not be humanly recognisable unless humans can grasp the specification of the object-system ; and counts as a proof only on (...) the hypothesis that the object system is consistent. The present paper argues that criticism may be met head-on by an intuitionistic proponent of the anti-mechanist argument; and that criticism is simply mistaken. However the paper concludes by questioning the sufficiency of the situation for an interesting anti-mechanist conclusion. (shrink)

A probabilistic propositional logic, endowed with a constructor for asserting compatibility of diagonalisable and bounded observables, is presented and illustrated for reasoning about the random results of projective measurements made on a given quantum state. Simultaneous measurements are assumed to imply that the underlying observables are compatible. A sound and weakly complete axiomatisation is provided relying on the decidable first-order theory of real closed ordered fields. The proposed logic is proved to be a conservative extension of classical propositional logic.

What are the objects of knowledge, belief, probability, apriority or analyticity? For at least some of these properties, it seems plausible that the objects are sentences, or sentence-like entities. However, results from mathematical logic indicate that sentential properties are subject to severe formal limitations. After surveying these results, I argue that they are more problematic than often assumed, that they can be avoided by taking the objects of the relevant property to be coarse-grained (“sets of worlds”) propositions, and that all (...) this has little to do with the choice between operators and predicates. (shrink)

On montre que, avec la notion traditionnelle et grammaticale du prédicat comme ce qui reste de la phrase après l’enlèvement du sujet, le paradoxe de Russell, ou d’autres comparables comme le paradoxe de Grelling et le paradoxe de la prédication, ne posent aucun problème. L’interdit formel standard sur la substitution des prédicats impliquant des variables libres dans des schémas où ces variables deviendraient liées, suffit pour prévenir le développement des paradoxes standard. On discute ensuite des réarrangements requis dans les fondations (...) de la Théorie des ensembles pour intégrer cette idée, et on explique les conséquences pour les questions étroitement liées de la Diagonalisation et du Théorème de Cantor. (shrink)

On montre que, avec la notion traditionnelle et grammaticale du prédicat comme ce qui reste de la phrase après l’enlèvement du sujet, le paradoxe de Russell, ou d’autres comparables comme le paradoxe de Grelling et le paradoxe de la prédication, ne posent aucun problème. L’interdit formel standard sur la substitution des prédicats impliquant des variables libres dans des schémas où ces variables deviendraient liées, suffit pour prévenir le développement des paradoxes standard. On discute ensuite des réarrangements requis dans les fondations (...) de la Théorie des ensembles pour intégrer cette idée, et on explique les conséquences pour les questions étroitement liées de la Diagonalisation et du Théorème de Cantor. (shrink)