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.

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)

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. (shrink)

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)

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)

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 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)

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.

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.

(No abstract is available for this citation).

Plato’s Theaetetus sets the problem of the definition of science; moreover, what there is in question is the problem of the definition in general. Defining means measuring, referring to definite parameters what is initially indefinite. But it is not a case that the dialogue opens with the discussion about the commensurable and incommensurable numbers: the search for what is common to all sciences is the search for their common measure, for the term to which various elements are or can be (...) commensurated. The apories Plato is showing in refuting the Protagorean thesis appear clearly as an objection against the absolute commensurability of all things: each sense is a parameter of a determinate sensible object and then results as quite incommensurable with another sense; a present sensation is incommensurable with a non present one, either past or future; all these facts question the possibility of the definition, for they reduce the knowledge, and the reality, to a set of atomic and quite unrelated elements. In the same way, the other definitions of science are rejected because of their incompleteness. But the negative conclusion of the Theaetetus regarding the definition of science must be assumed in a positive way: every operation of defining constantly presents an excess which belongs to the incommensurability and leaves every definition in a state of incompleteness. Through a comparison with the problem of the commensurable and incommensurable numbers, what is eventually shown is that the Being itself, as a mean between subject and predicate in the proposition, constitutes the diagonal element of every process of definition, irreducible to the elements that come into play. Being is, literally said, the incommensurable. (shrink)

Gödel’s first incompleteness theorem is sometimes said to refute mechanism about the mind. §1 contains a discussion of mechanism. We look into its origins, motivations and commitments, both in general and with regard to the human mind, and ask about the place of modern computers and modern cognitive science within the general mechanistic paradigm. In §2 we give a sharp formulation of a mechanistic thesis about the mind in terms of the mathematical notion of computability. We present the argument from (...) Gödel’s theorem against mechanism in terms of this formulation and raise two objections, one of which is known but is here given a more precise formulation, and the other is new and based on the discussion in §1. (shrink)

Motivated by the goal of constructing a model in which there are no κ-Aronszajn trees for any regular $k>\aleph_1$, we produce a model with many singular cardinals where both the singular cardinals hypothesis and weak square fail.

Myofascial Pain Syndrome is somatic pain due to muscular tension associated with muscular-skeletal imbalance. The pain and discomfort of the patient is not simply due to some isolated tension, but in the dynamic relationships between related structures. As the body adjusts to reestablish balance and symmetry, the tension and pain in one area “diagonalizes,” creating a tense correlate along a diagonal axis. This diagonalization of tension exacerbates and perpetuates the initial condition of pain and dysfunction. The purpose of this (...) paper is to argue that there are moral and social analogues to MFPS with their own forms of diagonalized asymmetry. Following the Aristotelian model of virtue and vice, whereby moral traits and dispositions become vice as a result of a loss of balance in conduct, and George Herbert Mead’s social psychology, which describes the self in terms of dynamic interrelation and co-operation of multiple sub-selves, I maintain that otherwise positive strengths in personal character, when overemphasized or exaggerated, can be juxtaposed to analogous weaknesses in related areas of personal health and conduct. I will argue that the descriptive analogy of MFPS has a corollary set of prescriptions for restoring balance in a moral subject. (shrink)

The relation between least and diagonal fixed points is a well known and completely studied question for a large class of partially ordered models of the lambda calculus and combinatory logic. Here we consider this question in the context of algebraic recursion theory, whose close connection with combinatory logic recently become apparent. We find a comparatively simple and rather weak general condition which suffices to prove the equality of least fixed points with canonical (corresponding to those produced by the Curry (...) combinator in lambda calculus) diagonal fixed points in a class of partially ordered algebras which covers both combinatory spaces of Skordev and operative spaces of Ivanov. Especially, this yields an essential improvement of the axiomatization of recursion theory via combinatory spaces. (shrink)

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.

It is a trivial fact that if we have a square table filled with numbers, we can always form a column which is not yet contained in the table. Despite its apparent triviality, this fact underlies the foundations of most of the path-breaking results of logic in the second half of the nineteenth and the first half of the twentieth century. We explain how this fact can be used to show that there are more sequences of natural numbers than there (...) are natural numbers, that there are more real numbers than natural numbers and that every set has more subsets than elements (all results due to Cantor); we indicate how this fact can be seen as underlying the celebrated Russell paradox; and we show how it can be employed to expose the most fundamental result of mathematical logic of the twentieth century, Gödel's incompleteness theorem. Finally, we show how this fact yields the unsolvability of the halting problem for Turing machines. (shrink)

bk. 1. Tools for dialectic -- bk. 2. Historical-philosophical background materials -- bk. 3. Groundworks for dialectical logic.

These remarks take up the reflexive problematics of Being and Nothingness and related texts from a metalogical perspective. A mutually illuminating translation is posited between, on the one hand, Sartre’s theory of pure reflection, the linchpin of the works of Sartre’s early period and the site of their greatest difficulties, and, on the other hand, the quasi-formalism of diagonalization, the engine of the classical theorems of Cantor, Gödel, Tarski, Turing, etc. Surprisingly, the dialectic of mathematical logic from its inception (...) through the discovery of the diagonal theorems can be recognized as a particularly clear instance of the drama of reflection according to Sartre, especially in the positing and overcoming of its proper value-ideal, viz. the synthesis of consistency and completeness. Conversely, this translation solves a number of systematic problems about pure reflection’s relations to accessory reflection, phenomenological reflection, pre-reflective self-consciousness, conversion, and value. Negative foundations, the metaphysical position emerging from this translation between existential philosophy and metalogic, concurs by different paths with Badiou’s Being and Event in rejecting both ontotheological foundationalisms and constructivist antifoundationalisms. (shrink)

We present a survey of some results and problems concerning constructions which require a diagonalization of length continuum to be carried out, particularly constructions of almost disjoint families of various sorts. We emphasize the role of cardinal invariants of the continuum and their combinatorial characterizations in such constructions.

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$.

Environmental rights are diagonal if they are held by individuals or groups against the governments of states other than their own. The potential importance of such rights is obvious: governments' actions often affect the environment beyond their jurisdiction, and those who live in and rely upon the environment affected would like to be able to exercise rights against the governments causing them harm. Although international law has not adopted a comprehensive, uniform approach to such rights, human rights law and international (...) environmental law have begun to develop some possible bases for diagonal environmental rights. Human rights law operates primarily along a vertical axis, setting out individuals' rights against their governments and the corresponding duties owed by the governments, but it may also be diagonal, giving rise to duties on the part of states that extend beyond their own territory. The scope and extent of diagonal human rights are often controversial, and environmental rights face additional difficulties, because the environmental protection required by human rights is clarifying only gradually, on a case-by-case basis. To the extent that human rights require such protection when aligned vertically, it would be logical to conclude that they require the same degree of protection whenever they may be aligned diagonally. Human rights law provides few precedents to support that conclusion, however. Compared to human rights law, international environmental law (IEL) provides a clearer and more specific set of duties with respect to environmental protection. Moreover, most IEL is extraterritorial, in that it requires states to regulate actions within their control that could harm the environment beyond their territory. The problem with grounding diagonal environmental rights in IEL is that, in contrast to human rights law, most IEL operates along a horizontal axis: its duties are owed by states to other states, not to private actors. If the challenge for human rights law is to extend rights from the vertical axis to the diagonal, the challenge for IEL is to derive diagonal rights from horizontal ones. (shrink)

Speakers assert in order to communicate information. It is natural, therefore, to hold that the content of an assertion is whatever information it communicates to its audience. In cases involving uncertainty about the semantic values of context-sensitive lexical items, moreover, it is natural to hold that the information an assertion communicates to its audience is whatever information audience members are in a position to recover from it by assuming that the proposition it semantically determines is true. This sort of picture (...) corresponds to an influential and widely endorsed theory of assertoric content: diagonalism. I begin by arguing that, despite its intuitive appeal, diagonalism should be rejected because it conflicts with our intuitive judgments about the circumstances in which the contents of speakers’ assertions would be true or false. I then show that the failure of diagonalism requires us to either abandon a familiar way of thinking about information and rational assertion or hold that the content of an assertion is not always the information it communicates. I suggest that we choose the latter horn of this dilemma — assertoric content is better characterized in terms of the commitments speakers undertake than in terms of the information they communicate. (shrink)

In this paper, I try to accomplish two goals. The first is to provide a general characterization of a method of proofs called — in mathematics — the diagonal argument. The second is to establish that analogical thinking plays an important role also in mathematical creativity. Namely, mathematical research make use of analogies regarding general strategies of proof. Some of mathematicians, for example George Polya, argued that deductions is impotent without analogy. What I want to show is that there exists (...) a direct line leading from Cantor’s diagonal argument to constructions that underlies of the proofs of several important theorems of the mathematical logic (in particular, Church’s theorem concerning the undecidability of formal arithmetic, Gödel’s theorem concerning the incopleteness of formal arithmetic, Tarski’s theorem concerning truth, and Turing’s theorem concerning the Halting Problem), and that the line could be described as an analogical mapping. In other words, Cantor’s diagonal argument and the proofs of the limitative theorems are structurally the same. Hence they can be represented as instances (or special cases) of the same general scheme. (shrink)

Putnam construed the aim of Carnap’s program of inductive logic as the specification of a “universal learning machine,” and presented a diagonal proof against the very possibility of such a thing. Yet the ideas of Solomonoff and Levin lead to a mathematical foundation of precisely those aspects of Carnap’s program that Putnam took issue with, and in particular, resurrect the notion of a universal mechanical rule for induction. In this paper, I take up the question whether the Solomonoff–Levin proposal is (...) successful in this respect. I expose the general strategy to evade Putnam’s argument, leading to a broader discussion of the outer limits of mechanized induction. I argue that this strategy ultimately still succumbs to diagonalization, reinforcing Putnam’s impossibility claim. (shrink)

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)

Computationalism is the claim that all possible thoughts are computations, i.e. executions of algorithms. The aim of the paper is to show that if intentionality is semantically clear, in a way defined in the paper, then computationalism must be false. Using a convenient version of the phenomenological relation of intentionality and a diagonalization device inspired by Thomson's theorem of 1962, we show there exists a thought that canno be a computation.

In recent years, free speech debates have featured unusually prominently in public debate in Australia. At the same time, significant restrictions on freedom of speech have been enacted in the context of counterterrorism legislation, asylum-seeker policy, and anti-protest laws. This article critically analyses these policy developments through the lens of a capabilities approach-informed analysis of the importance of free speech. This engenders an understanding of the constitutive role of speech in individuals’ lives, and through that its vital role in democratic (...) deliberation and legitimation. I will argue that many of the restrictions placed on free speech in Australia in recent years place democratic processes of deliberation and legitimation at risk. (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 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)

Diagonalization is a proof technique that formal learning theorists use to show that inductive problems are unsolvable. The technique intuitively requires the construction of the mathematical equivalent of a "Cartesian demon" that fools the scientist no matter how he proceeds. A natural question that arises is whether diagonalization is complete. That is, given an arbitrary unsolvable inductive problem, does an invincible demon exist? The answer to that question turns out to depend upon what axioms of set theory we (...) adopt. The two main results of the paper show that if we assume ZermeloFraenkel set theory plus AC and CH, there exist undetermined inductive games. The existence of such games entails that diagonalization is incomplete. On the other hand, if we assume the Axiom of Determinacy, or even a weaker axiom known as Wadge Determinacy, then diagonalization is complete. In order to prove the results, inductive inquiry is viewed as an infinitary game played between the scientist and nature. Such games have been studied extensively by descriptive set theorists. Analogues to the results above are mentioned, in which both the scientist and the demon are restricted to computable strategies. The results exhibit a surprising connection between inductive methodology and the foundations of set theory. (shrink)