This is a completely informal presentation of the ideas behind the diagonal lemma. One really can't see this important result from too many different angles. This one aims at getting the main idea across. (For the cognoscenti, it is in the spirit of Quine's treatment in terms of "appended to its own quotation".).

We’ve now proved our key version of the First Theorem, Theorem 42. If T is the right kind of ω-consistent theory including enough arithmetic, then there will be an arithmetic sentence GT such that T ￿ GT and T ￿ ¬GT. Moreover, GT is constructed so that it is true if and only if unprovable-in T (so it is true). Now recall that, for a p.r. axiomatized theory T , Prf T(m, n) is the relation which holds just if m (...) is the super g.n. of a sequence of wffs that is a T proof of a sentence with g.n. n. This relation is p.r. decidable (see §25.4). Assuming T extends Q, it can capture any p.r. decidable relation, including Prf T (§22). So we can define.. (shrink)

A cornerstone of modern mathematical logic is the diagonal lemma of Gödel and Carnap. It is used in e.g. the classical proofs of the theorems of Gödel, Rosser and Tarski. From its first explication in 1934, just essentially one proof has appeared for the diagonal lemma in the literature; a proof that is so tricky and hard to relate that many authors have tried to avoid the lemma altogether. As a result, some so called (...) class='Hi'>diagonal-free proofs have been given for the above mentioned fundamental theorems of logic. In this paper, we provide new proofs for the semantic formulation of the diagonal lemma, and for a weak version of the syntactic formulation of it. (shrink)

We prove the equivalence of the semantic version of Tarski’s theorem on the undefinability of truth with the semantic version of the diagonal lemma and also show the equivalence of a syntactic version of Tarski’s undefinability theorem with a weak syntactic diagonal lemma. We outline two seemingly diagonal-free proofs for these theorems from the literature and show that the syntactic version of Tarski’s theorem can deliver Gödel–Rosser’s incompleteness theorem.

We prove that the statement “there is aksuch that for everyfthere is ak-bounded diagonally nonrecursive function relative tof” does not imply weak König’s lemma over${\rm{RC}}{{\rm{A}}_0} + {\rm{B\Sigma }}_2^0$. This answers a question posed by Simpson. A recursion-theoretic consequence is that the classic fact that everyk-bounded diagonally nonrecursive function computes a 2-bounded diagonally nonrecursive function may fail in the absence of${\rm{I\Sigma }}_2^0$.

A function is diagonally non-computable if it diagonalizes against the universal partial computable function. D.n.c. functions play a central role in algorithmic randomness and reverse mathematics. Flood and Towsner asked for which functions h, the principle stating the existence of an h-bounded d.n.c. function implies Ramsey-type weak König’s lemma. In this paper, we prove that for every computable order h, there exists an ω\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\omega}$$\end{document} -model of h-DNR which is not a (...) not model of the Ramsey-type graph coloring principle for two colors and therefore not a model of RWKL. The proof combines bushy tree forcing and a technique introduced by Lerman, Solomon and Towsner to transform a computable non-reducibility into a separation over ω\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\omega}$$\end{document} -models. (shrink)

The exponential rise in transgender self-identification invites consideration of what constitutes an ethical response to transgender individuals’ claims about how best to promote their well-being. In this paper, we argue that ‘accepting’ a claim to medical transitioning in order to promote well-being would be in the person’s best interests iff at the point of request the individual is correct in their self-diagnosis as transgender (i.e., the distress felt to reside in the body does not result from another psychological and/or societal (...) problem) such that the medical interventions they are seeking will help them to realise their preferences. If we cannot assume this—and we suggest that we have reasonable grounds to question an unqualified acceptance in some cases—then ‘acceptance’ potentially works against best interests. We propose a distinction between ‘acceptance’ and respectful, in-depth exploration of an individual’s claims about what promotes their well-being. We discuss the ethical relevance of the unconscious mind to considerations of autonomy and consent in working with transgender individuals. An inquisitive stance, we suggest, supports autonomous choice about how to realise an embodied form that sustains well-being by allowing the individual to consider both conscious and unconscious factors shaping wishes and values, hence choices. (shrink)

Notini et al 1 offer a timely addition in the wake of a significant increase in young people identifying as transgender and gender diverse. The authors focus specifically on the case of 18-year-old Phoenix’s request for ongoing puberty suppression to affirm a non-binary gender identity. A central issue raised by Phoenix’s predicament, and that I suggest we can extend to ethical consideration of requests for other types of medical intervention by binary and non-binary TGD individuals, is whether we should ‘affirm’ (...) the claims made by TGD young people about what promotes their well-being. As a clinician working with TGD young people who have undergone a range of medical interventions to align their bodies with their gender identity, my starting presumption is that it is important to respect what people think will help them: there are some TGD young people for whom, all things considered, medical interventions to affirm gender identity promote their well-being. Well-being has become an important conceptual currency in ethical debates and lies at the core of the authors’ analysis of Phoenix’s case. While the authors do not ground their argument in favour of OPS in a specific theory of well-being, welfarist considerations 2 appear to underpin …. (shrink)

Notini _et al_ 1 offer a timely addition in the wake of a significant increase in young people identifying as transgender and gender diverse. The authors focus specifically on the case of 18-year-old Phoenix’s request for ongoing puberty suppression to affirm a non-binary gender identity. A central issue raised by Phoenix’s predicament, and that I suggest we can extend to ethical consideration of requests for other types of medical intervention by binary and non-binary TGD individuals, is whether we should ‘affirm’ (...) the claims made by TGD young people about what promotes their well-being. As a clinician working with TGD young people who have undergone a range of medical interventions to align their bodies with their gender identity, my starting presumption is that it is important to respect what people think will help them: there are some TGD... (shrink)

_Alessandra Lemma - Winner of the Levy-Goldfarb Award for Child Psychoanalysis!_ The contemporary relevance of psychoanalysis is being increasingly questioned; _Off the Couch_ challenges this view, demonstrating that psychoanalytic thinking and its applications are both innovative and relevant, in particular to the management and treatment of more disturbed and difficult to engage patient groups. Chapters address: clinical applications in diverse settings across the age range the relevance of psychoanalytic thinking to the practice of CBT, psychosomatics and general psychiatry the (...) contribution of psychoanalytic thinking to mental health policy and the politics of conflict and mediation. This book suggests that psychoanalysis has a vital position within the public health sector and discusses how it can be better utilised in the treatment of a range of mental health problems. It also highlights the role of empirical research in providing a robust evidence base. _Off the Couch_ will be essential reading for those practicing in the field of mental health and will also be useful for anyone involved in the development of mental health and public policies. It will ensure that practitioners and supervisors have a clear insight into how psychoanalysis can be applied in general healthcare. (shrink)

Central to the liar paradox is the phenomenon of 'self-reference'. The paradox typically begins with a sentence like: -/- (L): (L) is not true -/- Historically, doubts about the intelligibility of self-reference have been quite common. In some sense, though, these doubts were answered by Kurt Gödel's famous 'diagonal lemma'. This paper surveys some of the methods by which self-reference can be achieved, focusing first on purely syntactic methods before turning attention to the 'arithmetized' methods introduced by Gödel. (...) It's primary lesson is that we need to be more careful than we usually have been about self-reference. (shrink)

Solovay's 1976 completeness result for modal provability logic employs the recursion theorem in its proof. It is shown that the uses of the recursion theorem can in this proof replaced by the diagonalization lemma for arithmetic and that, in effect, the proof neatly fits the framework of another, enriched, system of modal logic so that any arithmetical system for which this logic is sound is strong enough to carry out the proof, in particular $\text{I}\Delta _{0}+\text{EXP}$ . The method is (...) adapted to obtain a similar completeness result for the Rosser logic. (shrink)

In diesem Beitrag werden die Bedingungen f ̈ur die Entscheidbarkeit eines lo-gischen Systems untersucht, indem Theorien der Unentscheidbarkeit, inner-halb der formalen Logik und der rekursiven Funktionen, analysiert werden.Eine notwendige und implizite Voraussetzung f ̈ur den Beweis des Fixpunkt-theorems (Diagonalisierungslemma) ist die Annahme der Abgeschlossenheitaller Formeln unter einerVariablen-Komposition, d.h., der Verkn ̈upfung vonVariablen in den Signaturen von Formeln. Eine Variablen-Kompositionvon Formeln ist in einer Pr ̈adikatenlogik repr ̈asentierbar, wenn der Satz∀ψ∀k(⊢ψ(k)↔∃y(ψ∧y≡k))hergeleitet werden kann, etwa durch einegeeignete semantische Definition der Quantoren. Als weitere (...) Bedingung wirdim Beitrag herausgearbeitet, dass bei dem Beweis eine Interpretation zugrun-deliegen muss, aus der sich die Existenz einer in diesem Text definiertenvari-ablen Signatur in einer Unbestimmtenmit einerkonstanten Interpretationher-leiten l ̈asst.Es wird ein Rekursionssatz f ̈ur Formeln in Analogie zum Rekursionssatz vonKleene (1943, S. 52-53) bewiesen, der das Diagonalisierungslemma als Spezial-fall abdeckt. Die hier gew ̈ahlte Notation und Beweisf ̈uhrung soll die Bedin-gungen f ̈ur seine Beweisbarkeit deutlich machen. Es wird zudem bewiesen,dass die Annahmen der Repr ̈asentierbarkeit einer Variablen-Kompositionund der mittels einer variablen Signatur in einer Unbestimmten darstellbarenkonstanten Interpretation aus der Behauptung des Rekursionssatzes folgen,also ̈aquivalent sind zur Existenz von Fixpunkten∀ψ∃φ(⊢φ↔ψ(⌜φ⌝)).Mit diesen Resultaten kann begr ̈undet werden, warum in einem pr ̈adikativenlogischen System die Negation des Diagonalisierungslemmas bewiesen wer-den kann, in dem diese Pr ̈amissen nicht gelten aber dennoch die expliziteVoraussetzung des Diagonalisierungslemmas erf ̈ullt ist. D.h. eine Spracheder pr ̈adikativen Logik ist m ̈achtig genug, alle berechenbaren Funktionen zurepr ̈asentieren, so wie Solte 2020 es als unerwartetes Ergebnis aufgezeigt hat.Als Ausblick auf ein derartiges logisches System wird eine entscheidbareStruktur berechenbarer Funktionen skizziert.Das bedeutet, in dieserStruktur kann eine pr ̈adikative Logik interpretiert werden, in der es keineunentscheidbaren S ̈atze gibt. (shrink)

We prove that any 1-closed (see def 1.1) model of the Π 2 consequences of PA satisfies ¬Cons PA which gives a proof of the second Godel incompleteness theorem without the use of the Godel diagonal lemma. We prove a few other theorems by the same method.

It is well known that, in Peano arithmetic, there exists a formula Theor (x) which numerates the set of theorems. By Gödel's and Löb's results, we have that Theor (˹p˺) ≡ p implies p is a theorem ∼Theor (˹p˺) ≡ p implies p is provably equivalent to Theor (˹0 = 1˺). Therefore, the considered "equations" admit, up to provable equivalence, only one solution. In this paper we prove (Corollary 1) that, in general, if P (x) is an arbitrary formula built (...) from Theor (x), then the fixed-point of P (x) (which exists by the diagonalization lemma) is unique up to provable equivalence. This result is settled referring to the concept of diagonalizable algebra (see Introduction). (shrink)

Within the technical frame supplied by the algebraic variety of diagonalizable algebras, defined by R. Magari in [2], we prove the following: Let T be any first-order theory with a predicate Pr satisfying the canonical derivability conditions, including Löb's property. Then any formula in T built up from the propositional variables $q,p_{1},...,p_{n}$ , using logical connectives and the predicate Pr, has the same "fixed-points" relative to q (that is, formulas $\psi (p_{1},...,p_{n})$ for which for all $p_{1},...,p_{n}\vdash _{T}\phi (\psi (p_{1},...,p_{n}),p_{1},...,p_{n})\leftrightarrow \psi (...) (p_{1},...,p_{n})$ ) of a formula $\phi ^{\ast}$ of the same kind, obtained from φ in an effective way. Moreover, such $\phi ^{\ast}$ is provably equivalent to the formula obtained from φ substituting with $\phi ^{\ast}$ itself all the occurrences of q which are under Pr. In the particular case where q is always under Pr in φ, $\phi ^{\ast}$ is the unique (up to provable equivalence) "fixed-point" of φ. Since this result is proved only assuming Pr to be canonical, it can be deduced that Löb's property is, in a sense, equivalent to Gödel's diagonalization lemma. All the results are proved more generally in the intuitionistic case. (shrink)

We prove Yablo’s paradox without the diagonal lemma or the recursion theorem. Only a disquotation schema and axioms for a serial and transitive ordering are used in the proof. The consequences for the discussion on whether Yablo’s paradox is circular or involves self-reference are evaluated.

The purpose of this note is to present a strong form of the liar paradox. It is strong because the logical resources needed to generate the paradox are weak, in each of two senses. First, few expressive resources required: conjunction, negation, and identity. In particular, this form of the liar does not need to make any use of the conditional. Second, few inferential resources are required. These are: (i) conjunction introduction; (ii) substitution of identicals; and (iii) the inference: From ¬(p (...) ∧ p), infer ¬ p. It is, interestingly enough, also essential to the argument that the ‘strong’ form of the diagonal lemma be used: the one that delivers a term λ such that we can prove: λ = ¬ T(⌈λ⌉); rather than just a sentence Λ for which we can prove: Λ ≡ ¬T(⌈Λ⌉). The truth-theoretic principles used to generate the paradox are these: ¬(S ∧ T(⌈¬S⌉); and ¬(¬S ∧ ¬T(⌈¬S⌉). These are classically equivalent to the two directions of the T-scheme, but they are intuitively weaker. The lesson I would like to draw is: There can be no consistent solution to the Liar paradox that does not involve abandoning truth-theoretic principles that should be every bit as dear to our hearts as the T-scheme. So we shall have to learn to live with the Liar, one way or another. (shrink)

Predicates are term-to-sentence devices, and operators are sentence-to-sentence devices. What Kaplan and Montague's Paradox of the Knower demonstrates is that necessity and other modalities cannot be treated as predicates, consistent with arithmetic; they must be treated as operators instead. Such is the current wisdom.A number of previous pieces have challenged such a view by showing that a predicative treatment of modalities neednot raise the Paradox of the Knower. This paper attempts to challenge the current wisdom in another way as well: (...) to show that mere appeal to modal operators in the sense of sentence-to-sentence devices is insufficient toescape the Paradox of the Knower. A family of systems is outlined in which closed formulae can encode other formulae and in which the diagonal lemma and Paradox of the Knower are thereby demonstrable for operators in this sense. (shrink)

Solovay's 1976 completeness result for modal provability logic employs the recursion theorem in its proof. It is shown that the uses of the recursion theorem can in this proof be replaced by the diagonalization lemma for arithmetic and that, in effect, the proof neatly fits the framework of another, enriched, system of modal logic (the so-called Rosser logic of Gauspari-Solovay, 1979) so that any arithmetical system for which this logic is sound is strong enough to carry out the proof, (...) in particular I0+EXP. The method is adapted to obtain a similar completeness result for the Rosser logic. (shrink)

We present a semantic proof of Löb's theorem for theories T containing ZF. Without using the diagonalization lemma, we construct a sentence AUT T, which says intuitively that the predicate autological with respect to T (i.e. applying to itself in every model of T) is itself autological with respect to T. In effect, the sentence AUT T states I follow semantically from T. Then we show that this sentence indeed follows from T and therefore is true.

We give some information about new proofs of the incompleteness theorems, found in 1990s. Some of them do not require the diagonal lemma as a method of construction of an independent statement.

A ground-motive for this study of some historical and metaphysical implications of the diagonal lemmas of Cantor and Gödel is Cantor's insightful remark to Dedekind in 1899 that the Inbegriff alles Denkbaren (aggregate of everything thinkable) might, like some class-theoretic entities, be inkonsistent. In the essay's opening sections, I trace some recent antecedents of Cantor's observation in logical writings of Bolzano and Dedekind (more remote counterparts of his language appear in the First Critique), then attempt to relativize the notion (...) of Inkonsistenz to self-sufficient theories T which interpret themselves. In effect, I argue that Gödel's diagonal lemma suggests a sense in which metatheoretic notions of proof, well-foundeness and satisfaction are object-theoretically inkonsistent. With respect to Cantor's Inbegriff, for example, the lemma yields that any object-theoretic reconstruction of thinkability generates an antidiagonal sentence , which one can paraphrase asSelf-referential application of the assertion that. (shrink)

A suprise may occur if we use a similar strategy to the Liar's paradox to mathematically formalize "This sentence does not contain the symbol X".

We give new proofs of both incompleteness theorems. We do not use the diagonalization lemma, but work with some quickly growing functions instead.

We transform the proof of the second incompleteness theorem given in [3] to a proof-theoretic version, avoiding the use of the arithmetized completeness theorem. We give also new proofs of old results: The Arithmetical Hierarchy Theorem and Tarski's Theorem on undefinability of truth; the proofs in which the construction of a sentence by means of diagonalization lemma is not needed.

The paper studies two formal schemes related to -completeness.LetS be a suitable formal theory containing primitive recursive arithmetic and letT be a formal extension ofS. Denoted by (a), (b) and (c), respectively, are the following three propositions (where (x) is a formula with the only free variable x): (a) (for anyn) ( T (n)), (b) T x Pr T (–(x)–) and (c) T x(x) (the notational conventions are those of Smoryski [3]). The aim of this paper is to examine the (...) meaning of the schemes which result from the formalizations, over the base theoryS, of the implications (b) (c) and (a) (b), where ranges over all formulae. The analysis yields two results overS : 1. the schema corresponding to (b) (c) is equivalent to ¬Cons T and 2. the schema corresponding to (a) (b) is not consistent with 1-CON T. The former result follows from a simple adaptation of the -incompleteness proof; the second is new and is based on a particular application of the diagonalization lemma. (shrink)

Quantum physics exhibits various non-classical and paradoxical features. Among them are non-locality and contextuality (e.g. Bell’s theorem or the Einstein-Podolsky-Rosen paradox). Since they are expected to constitute a key resource in quantum computation, several approaches have been proposed to provide high-level expressions for them. In one of these approaches, Abramsky and others use the mathematics of algebraic topology and characterize non-locality and contextuality as the same type of phenomena as M. C. Escher’s impossible figures. This article expands this topological insight (...) and demonstrates that logical paradoxes arising from circular references (of the sort formalized by Gödel’s fixed-point or diagonalization lemma) share the same topological structure as the quantum paradoxes, by reformatting the topological model of contextuality into a semantics of logical paradoxes. This topological semantics indeed provides a unifying perspective from which previous approaches of philosophers and logicians to logical paradoxes can be understood as diverse ways of fine-tuning topologies to model paradoxes. (shrink)

Set theory, it has been contended, developed from its beginnings through a progression ofmathematicalmoves, despite being intertwined with pronounced metaphysical attitudes and exaggerated foundational claims that have been held on its behalf. In this paper, the seminal results of set theory are woven together in terms of a unifying mathematical motif, one whose transmutations serve to illuminate the historical development of the subject. The motif is foreshadowed in Cantor's diagonal proof, and emerges in the interstices of the inclusion vs. (...) membership distinction, a distinction only clarified at the turn of this century, remarkable though this may seem. Russell runs with this distinction, but is quickly caught on the horns of his well-known paradox, an early expression of our motif. The motif becomes fully manifest through the study of functionsof the power set of a set into the set in the fundamental work of Zermelo on set theory. His first proof in 1904 of his Well-Ordering Theoremis a central articulation containing much of what would become familiar in the subsequent development of set theory. Afterwards, the motif is cast by Kuratowski as a fixed point theorem, one subsequently abstracted to partial orders by Bourbaki in connection with Zorn's Lemma. Migrating beyond set theory, that generalization becomes cited as the strongest of fixed point theorems useful in computer science.Section 1 describes the emergence of our guiding motif as a line of development from Cantor's diagonal proof to Russell's Paradox, fueled by the clarification of the inclusion vs. membership distinction. Section 2 engages the motif as fully participating in Zermelo's work on the Well-Ordering Theorem and as newly informing on Cantor's basic result that there is no bijection. Then Section 3 describes in connection with Zorn's Lemma the transformation of the motif into an abstract fixed point theorem, one accorded significance in computer science. (shrink)

Our account of the problem of the classical limit of quantum mechanics involves two elements. The first one is self-induced decoherence, conceived as a process that depends on the own dynamics of a closed quantum system governed by a Hamiltonian with continuous spectrum; the study of decoherence is addressed by means of a formalism used to give meaning to the van Hove states with diagonal singularities. The second element is macroscopicity represented by the limit $\hbar \rightarrow 0$ : when (...) the macroscopic limit is applied to the Wigner transformation of the diagonal state resulting from decoherence, the description of the quantum system becomes equivalent to the description of an ensemble of classical trajectories on phase space weighted by their corresponding probabilities. (shrink)

We examine the reverse mathematical strength of a variation of Hindman’s Theorem (HT) constructed by essentially combining HT with the Thin Set Theorem to obtain a principle that we call thin-HT. This principle states that every coloring c:N→N has an infinite set S⊆N whose finite sums are thin for c, meaning that there is an i with c(s)≠i for all nonempty sums s of finitely many distinct elements of S. We show that there is a computable instance of thin-HT such (...) that every solution computes ∅′, as is the case with HT, as shown by Blass, Hirst, and Simpson (1987). In analyzing this proof, we deduce that thin-HT implies ACA0 over RCA0+IΣ20. On the other hand, using Rumyantsev and Shen’s computable version of the Lovász Local Lemma, we show that there is a computable instance of the restriction of thin-HT to sums of exactly 2 elements such that any solution has diagonally noncomputable degree relative to ∅′. Hence there is a computable instance of this restriction of thin-HT with no Σ20 solution. (shrink)

We consider structures of the form, where Φ and Ψ are non-empty sets and is a relation whose domain is Ψ. In particular, by using a special kind of a diagonal argument, we prove that if Φ is a denumerable recursive set, Ψ is a denumerable r.e. set, and R is an r.e. relation, then there exists an infinite family of infinite recursive subsets of Φ which are not R -images of elements of Ψ. The proof is a very (...) elementary one, without any reference even to e.g. the -theorem. Some consequences of the main result are also discussed. (shrink)

A diagonal version of the strong reflection principle is introduced, along with fragments of this principle associated with arbitrary forcing classes. The relationships between the resulting principles and related principles, such as the corresponding forcing axioms and the corresponding fragments of the strong reflection principle, are analyzed, and consequences are presented. Some of these consequences are “exact” versions of diagonal stationary reflection principles of sets of ordinals. We also separate some of these diagonal strong reflection principles from (...) related axioms. (shrink)

The diagonal method is often used to show that Turing machines cannot solve their own halting problem. There have been several recent attempts to show that this method also exposes either contradiction or arbitrariness in other theoretical models of computation which claim to be able to solve the halting problem for Turing machines. We show that such arguments are flawed—a contradiction only occurs if a type of machine can compute its own diagonal function. We then demonstrate why such (...) a situation does not occur for the methods of hypercomputation under attack, and why it is unlikely to occur for any other serious methods. Introduction Issues with specific hypermachines Conclusions for hypercomputation. (shrink)

A German translation with 2017 postscript of Floyd, Juliet. 2012. "Wittgenstein's Diagonal Argument: A Variation on Cantor and Turing." In Epistemology versus Ontology, Logic, Epistemology: Essays in Honor of Per Martin-Löf, edited by P. Dybjer, S. Lindström, E. Palmgren and G. Sundholm, 25-44. Dordrecht: Springer Science+Business Media. An analysis of philosophical aspects of Turing's diagonal argument in his (136) "On computable numbers, with an application to the Entscheidungsproblem" in relation to Wittgenstein's writings on Turing and Cantor.

Stalnaker’s ‘Assertion’ (1978 [1999]) offers a classic account of diagonalization as an approach to the meaning of a declarative sentence in context. Here I explore the relationship between diagonalization and some puzzles in Mahtani’s book The Objects of Credence. Diagonalization can influence how we think about both credence and desirability, so it influences both components of a standard expected utility equation. In that vein, I touch on two of Mahtani’s case-studies, chance and the finite version of the Two Envelope Paradox.

A. N. Turing’s 1936 concept of computability, computing machines, and computable binary digital sequences, is subject to Turing’s Cardinality Paradox. The paradox conjoins two opposed but comparably powerful lines of argument, supporting the propositions that the cardinality of dedicated Turing machines outputting all and only the computable binary digital sequences can only be denumerable, and yet must also be nondenumerable. Turing’s objections to a similar kind of diagonalization are answered, and the implications of the paradox for the concept of a (...) Turing machine, computability, computable sequences, and Turing’s effort to prove the unsolvability of the Entscheidungsproblem, are explained in light of the paradox. A solution to Turing’s Cardinality Paradox is proposed, positing a higher geometrical dimensionality of machine symbol-editing information processing and storage media than is available to canonical Turing machine tapes. The suggestion is to add volume to Turing’s discrete two-dimensional machine tape squares, considering them instead as similarly ideally connected massive three-dimensional machine information cells. Three-dimensional computing machine symbol-editing information processing cells, as opposed to Turing’s two-dimensional machine tape squares, can take advantage of a denumerably infinite potential for parallel digital sequence computing, by which to accommodate denumerably infinitely many computable diagonalizations. A three-dimensional model of machine information storage and processing cells is recommended on independent grounds as better representing the biological realities of digital information processing isomorphisms in the three-dimensional neural networks of living computers. (shrink)

Reliabilism about epistemic justification - the thesis that what makes a belief epistemically justified is that it was produced by a reliable process of belief-formation - must face two problems. First, what has been called "the new evil demon problem", which arises from the idea that the beliefs of victims of an evil demon are as justified as our own beliefs, although they are not - the objector claims - reliably produced. And second, the problem of diagnosing why skepticism is (...) so appealing despite being false. I present a special version of reliabilism, "indexical reliabilism", based on two-dimensional semantics, and show how it can solve both problems. (shrink)

Lexicalized theories of syntax often assume that verb-structure regularities are mediated by lemmas, which abstract over variation in verb tense and aspect. German syntax seems to challenge this assumption, because verb position depends on tense and aspect. To examine how German speakers link these elements, a structural priming study was performed which varied syntactic structure, verb position, and verb overlap.structural priming was found, both within and across verb position, but priming was larger when the verb position was the same between (...) prime and target. Priming was boosted by verb overlap, but there was no interaction with verb position. The results can be explained by a lemma model where tense and aspect are linked to structural choices in German. Since the architecture of this lemma model is not consistent with results from English, a connectionist model was developed which could explain the cross-linguistic variation in the production system. Together, these findings support the view that language learning plays an important role in determining the nature of structural priming in different languages. (shrink)

Frank Jackson and David Chalmers have suggested that the diagonal intensions defined by their two-dimensional framework can play the two key roles of Fregean senses: they provide a priori accessible extension conditions for a representation and they provide the identity conditions for meanings and thought contents. In this paper, I clarify the nature of the psychological abilities that are needed to underwrite the first role. I then argue that these psychological abilities are not sufficiently stable or cognitively salient to (...) individuate meanings or thought contents. (shrink)

We work with weakly precomplete equivalence relations introduced by Badaev. The weak precompleteness is a natural notion inspired by various fixed point theorems in computability theory. Let E be an equivalence relation on the set of natural numbers $$\omega $$, having at least two classes. A total function f is a diagonal function for E if for every x, the numbers x and f(x) are not E-equivalent. It is known that in the case of c.e. relations E, the weak (...) precompleteness of E is equivalent to the lack of computable diagonal functions for E. Here we prove that this result fails already for $$\Delta ^0_2$$ equivalence relations, starting with the $$\Pi ^{-1}_2$$ level. We focus on the Turing degrees of possible diagonal functions. We prove that for any noncomputable c.e. degree $${\textbf{d}}$$, there exists a weakly precomplete c.e. equivalence E admitting a $${\textbf{d}}$$ -computable diagonal function. We observe that a Turing degree $${\textbf{d}}$$ can compute a diagonal function for every $$\Delta ^0_2$$ equivalence relation E if and only if $${\textbf{d}}$$ computes $${\textbf{0}}'$$. On the other hand, every PA degree can compute a diagonal function for an arbitrary c.e. equivalence E. In addition, if $${\textbf{d}}$$ computes diagonal functions for all c.e. E, then $${\textbf{d}}$$ must be a DNC degree. (shrink)

We introduce three families of diagonal reflection principles for matrices of stationary sets of ordinals. We analyze both their relationships among themselves and their relationships with other known principles of simultaneous stationary reflection, the strong reflection principle, and the existence of square sequences.

We investigate diagonal actions of Polish groups and the related intersection operator on closed subgroups of the acting group. The Borelness of the diagonal orbit equivalence relation is characterized and is shown to be connected with the Borelness of the intersection operator. We also consider relatively tame Polish groups and give a characterization of them in the class of countable products of countable abelian groups. Finally an example of a logic action is considered and its complexity in the (...) Borel reducbility hierarchy determined. (shrink)

The effects of the forcing axioms \, \ and \ on the failure of weak threaded square principles of the form \\) are analyzed. To this end, a diagonal reflection principle, \, and it implies the failure of \\) if \. It is also shown that this result is sharp. It is noted that \/\ imply the failure of \\), for every regular \, and that this result is sharp as well.

This book presents a systematic, unified treatment of fixed points as they occur in Godels incompleteness proofs, recursion theory, combinatory logic, semantics, and metamathematics. Packed with instructive problems and solutions, the book offers an excellent introduction to the subject and highlights recent research.