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)
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)
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)
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.
Reliabilism about epistemic justification – thethesis that what makes a belief epistemicallyjustified is that it was produced by a reliableprocess of belief-formation – must face twoproblems. First, what has been called ``the newevil demon problem'', which arises from the ideathat the beliefs of victims of an evil demonare as justified as our own beliefs, althoughthey are not – the objector claims – reliablyproduced. And second, the problem of diagnosingwhy skepticism is so appealing despite beingfalse. I present a special version ofreliabilism, (...) ``indexical reliabilism'', based ontwo-dimensional semantics, and show how it cansolve both problems. (shrink)
This book is about one of the most baffling of all paradoxes--the famous Liar paradox. Suppose we say: "We are lying now." Then if we are lying, we are telling the truth; and if we are telling the truth we are lying. This paradox is more than an intriguing puzzle, since it involves the concept of truth. Thus any coherent theory of truth must deal with the Liar. Keith Simmons discusses the solutions proposed by medieval philosophers and offers his own (...) solutions and in the process assesses other contemporary attempts to solve the paradox. Unlike such attempts, Simmons' "singularity" solution does not abandon classical semantics and does not appeal to the kind of hierarchical view found in Barwise's and Etchemendy's The Liar. Moreover, Simmons' solution resolves the vexing problem of semantic universality--the problem of whether there are semantic concepts beyond the expressive reach of a natural language such as English. (shrink)
In a recent article (‘The Continuum: Russell’s Moment of Candour’), Christopher Ormell argues against the traditional mathematical view that the real numbers form an uncountably infinite set. He rejects the conclusion of Cantor’s diagonal argument for the higher, non-denumerable infinity of the real numbers. He does so on the basis that the classical conception of a real number is mys- terious, ineffable, and epistemically suspect. Instead, he urges that mathematics should admit only ‘well-defined’ real numbers as proper objects of (...) study. In practice, this means excluding as inadmissible all those real numbers whose decimal expansions cannot be calculated in as much detail as one would like by some rule. We argue against Ormell that the classical realist account of the continuum has explanatory power in mathematics and should be accepted, much in the same way that "dark matter" is posited by physicists to explain observations in cosmology. In effect, the indefinable real numbers are like the "dark matter" of real analysis. (shrink)
We first consider the entailment logic MC, based on meaning containment, which contains neither the Law of Excluded Middle (LEM) nor the Disjunctive Syllogism (DS). We then argue that the DS may be assumed at least on a similar basis as the assumption of the LEM, which is then justified over a finite domain or for a recursive property over an infinite domain. In the latter case, use is made of Mathematical Induction. We then show that an instance of the (...) LEM is intrumental in the proof of Cantor's Theorem, and we then argue that this is based on a more general form than can be reasonably justified. We briefly consider the impact of our approach on arithmetic and naive set theory, and compare it with intuitionist mathematics and briefly with recursive mathematics. Our "Four Basic Logical Issues" paper would provide useful background, the current paper being an application of the some of the ideas in it. (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)
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)
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)
We consider structures of the form (Φ, Ψ, R ), 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)
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 iscomplete. That is, given an arbitrary unsolvable inductive problem, does an invincible demon exist?The answer to that question tunas out to depend upon what axioms of set theory we adopt. The two main (...) results of the paper show that if we assume Zermelo-Fraenkel 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. (shrink)
We answer a question of Just, Miller, Scheepers and Szeptycki whether certain diagonalization properties for sequences of open covers are provably closed under taking finite or countable unions.
The Gödelian symphony -- Foundations and paradoxes -- This sentence is false -- The liar and Gödel -- Language and metalanguage -- The axiomatic method or how to get the non-obvious out of the obvious -- Peano's axioms -- And the unsatisfied logicists, Frege and Russell -- Bits of set theory -- The abstraction principle -- Bytes of set theory -- Properties, relations, functions, that is, sets again -- Calculating, computing, enumerating, that is, the notion of algorithm -- Taking numbers (...) as sets of sets -- It's raining paradoxes -- Cantor's diagonal argument -- Self-reference and paradoxes -- Hilbert -- Strings of symbols -- In mathematics there is no ignorabimus -- Gödel on stage -- Our first encounter with the incompleteness theorem -- And some provisos -- Gödelization, or say it with numbers! -- TNT -- The arithmetical axioms of tnt and the standard model N -- The fundamental property of formal systems -- The Gödel numbering -- And the arithmetization of syntax -- Bits of recursive arithmetic -- Making algorithms precise -- Bits of recursion theory -- Church's thesis -- The recursiveness of predicates, sets, properties, and relations -- And how it is represented in typographical number theory -- Introspection and representation -- The representability of properties, relations, and functions -- And the Gödelian loop -- I am not provable -- Proof pairs -- The property of being a theorem of TNI (is not recursive!) -- Arithmetizing substitution -- How can a TNT sentence refer to itself? -- Fixed point -- Consistency and omega-consistency -- Proving G1 -- Rosser's proof -- The unprovability of consistency and the immediate consequences of G1 and -- G2 -- Technical interlude -- Immediate consequences of G1 and G2 -- Undecidable1 and undecidable 2 -- Essential incompleteness, or the syndicate of mathematicians -- Robinson arithmetic -- How general are Gödel's results? -- Bits of turing machine -- G1 and G2 in general -- Unexpected fish in the formal net -- Supernatural numbers -- The culpability of the induction scheme -- Bits of truth (not too much of it, though) -- The world after Gödel -- Bourgeois mathematicians! : the postmodern interpretations -- What is postmodernism? -- From Gödel to Lenin -- Is biblical proof decidable? -- Speaking of the totality -- Bourgeois teachers! -- (un)interesting bifurcations -- A footnote to Plato -- Explorers in the realm of numbers -- The essence of a life -- The philosophical prejudices of our times -- From Gödel to Tarski -- Human, too human -- Mathematical faith -- I'm not crazy! -- Qualified doubts -- From gentzen to the dialectica interpretation -- Mathematicians are people of faith -- Mind versus computer : Gödel and artificial intelligence -- Is mind (just) a program? -- Seeing the truth and going outside the system -- The basic mistake -- In the haze of the transfinite -- Know thyself : Socrates and the inexhaustibility of mathematics -- Gödel versus wittgenstein and the paraconsistent interpretation -- When geniuses meet -- The implausible Wittgenstein -- There is no metamathematics -- Proof and prose -- The single argument -- But how can arithmetic be inconsistent? -- The costs and benefits of making Wittgenstein plausible. (shrink)
The authors investigated the ontological argument computationally. The premises and conclusion of the argument are represented in the syntax understood by the automated reasoning engine PROVER9. Using the logic of definite descriptions, the authors developed a valid representation of the argument that required three non-logical premises. PROVER9, however, discovered a simpler valid argument for God's existence from a single non-logical premise. Reducing the argument to one non-logical premise brings the investigation of the soundness of the argument into better focus. Also, (...) the simpler representation of the argument brings out clearly how the ontological argument constitutes an early example of a ?diagonal argument? and, moreover, one used to establish a positive conclusion rather than a paradox. (shrink)
In this paper I put forward a representationalist theory of conscious experience based on Robert Stalnaker's version of two-dimensional modal semantics. According to this theory the phenomenal character of an experience correlates with a content equivalent to what Stalnaker calls the diagonal proposition. I show that the theory is closely related both to functionalist theories of consciousness and to higher-order representational theories. It is also more compatible with an anti-Cartesian view of the mind than standard representationalist theories.
Kirsten Besheer has recently considered Descartes’ doubting appropriately in the context of his physiological theories in the spirit of recent important re-appraisals of his natural philosophy. However, Besheer does not address the notorious indubitability and its source that Descartes claims to have discovered. David Cunning has remarked that Descartes’ insistence on the indubitability of his existence presents “an intractable problem of interpretation” in the light of passages that suggest his existence is “just as dubitable as anything else”. However, although the (...) cogito argument is widely thought to be central to the force of Descartes’ indubitability, for his part, Cunning does not consider its relevance and force. Accordingly, this article is concerned with the cogito argument and the question central to Hintikka’s seminal contribution, described by Cottingham as “Perhaps the most debated question,” namely, whether or not the cogito can be construed as a logical inference. Clearly, an inferential account has the potential to explain the certainty of Descartes’ conclusion that he exists. Recently, Sarkar offers what he characterizes as “novel and fairly conclusive reasons why the cogito cannot be construed as an argument,” asserting “the discovery of the cogito can only be an intuition not a deduction.” Obviously, it would greatly support the opposing inferential construal if a remotely plausible logical argument could be proposed. Toward this end, I defend the virtues of my ‘Diagonal’ account of Descartes’ cogito Above all, I show how my analysis meets the requirement that any satisfactory solution to the problem of the cogito would reconcile Descartes’ claim that the cogito is a certain inference with his claim that it is an intuitive kind of knowledge. Through a critical discussion of analyses such as that of Gallois , I show that it is possible to provide a textually faithful analysis that permits seeing the cogito as both inference and intuition because it may be seen as an exercise in the mathematical method of Analysis. Above all, as Feldman requires, I show that the Diagonal account is not only textually elegant, but permits crediting Descartes with a worthy insight, thereby resolving the tension between what Howell has termed the Humean and Cartesian problems, namely, the elusiveness and the certainty of the self. (shrink)
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)
We will define three kinds of identity: the Bourbaki identity, the logical identity and the diagonal identity (in short B-, l-, d-identity respectively) and study the connections between them. A whole picture of these relations is given at the end of the paper.
Kirsten Besheer has recently considered Descartes’ doubting appropriately in the context of his physiological theories in the spirit of recent important re-appraisals of his natural philosophy. However, Besheer does not address the notorious indubitability and its source that Descartes claims to have discovered. David Cunning has remarked that Descartes’ insistence on the indubitability of his existence presents “an intractable problem of interpretation” in the light of passages that suggest his existence is “just as dubitable as anything else”. However, although the (...) cogito argument is widely thought to be central to the force of Descartes’ indubitability, for his part, Cunning does not consider its relevance and force. Accordingly, this article is concerned with the cogito argument and the question central to Hintikka’s seminal contribution, described by Cottingham as “Perhaps the most debated question,” namely, whether or not the cogito can be construed as a logical inference. Clearly, an inferential account has the potential to explain the certainty of Descartes’ conclusion that he exists. Recently, Sarkar offers what he characterizes as “novel and fairly conclusive reasons why the cogito cannot be construed as an argument,” asserting “the discovery of the cogito can only be an intuition not a deduction.” Obviously, it would greatly support the opposing inferential construal if a remotely plausible logical argument could be proposed. Toward this end, I defend the virtues of my ‘Diagonal’ account of Descartes’ cogito Above all, I show how my analysis meets the requirement that any satisfactory solution to the problem of the cogito would reconcile Descartes’ claim that the cogito is a certain inference with his claim that it is an intuitive kind of knowledge. Through a critical discussion of analyses such as that of Gallois , I show that it is possible to provide a textually faithful analysis that permits seeing the cogito as both inference and intuition because it may be seen as an exercise in the mathematical method of Analysis. Above all, as Feldman requires, I show that the Diagonal account is not only textually elegant, but permits crediting Descartes with a worthy insight, thereby resolving the tension between what Howell has termed the Humean and Cartesian problems, namely, the elusiveness and the certainty of the self. (shrink)
This work represents an attempt to stake out the landscape for dynamicism based on a radical dismissal of the information-processing paradigm that dominates the philosophy of cognitive science. In Section 2, after setting up the basic toolkit of a theory of minimal representationalism, I introduce the central tenets of dynamic systems theory (DST) by discussing recent research in the dynamics of embodiment (Thelen et al. [2001]) in the perseverative-reaching literature. A recent proposal on the dynamics of representation—the dynamic field approach (...) (Spencer and Schöner [2003])—according to which the alleged representational gap between DST and representational theories of cognition needs to be bridged in order to explain higher-order cognitive activity will then be reviewed. In Section 3, I shall argue that Spencer and Schöner's attempt to bridge the representational gap may jeopardize the whole (antirepresentationalist) spirit of the DST project. In order to show why, I shall introduce the key concepts of reliability of environment and primagenesis, and argue that DST can account for de-coupled, offline cognitive activity with no need of positing representational resources. Conclusions and directions for future research will follow. Introduction 1.1 Minimal representationalism The dynamic field approach 2.1 Dynamic systems theory and the continuity hypothesis 2.2 The dynamic field approach: Bridging the representational gap? Towards a general theory of antirepresentationalism 3.1 Diagonal systems and microstimulated dissociations 3.2 Reliability of environment and primagenesis 3.3 Towards a general theory of antirepresentationalism Conclusion CiteULike Connotea Del.icio.us What's this? (shrink)
The compulsion of proofs is an ancient idea, which plays an important role in Plato’s dialogues. The reader perhaps recalls Socrates’ question to the slave boy in the Meno: “If the side of a square A is 2 feet, and the corresponding area is 4, how long is the side of a square whose area is double, i.e. 8?”. The slave answers: “Obviously, Socrates, it will be twice the length” (cf. Me 82-85). A straightforward analogy: if the area is double, (...) the side is double. Nevertheless, the answer is wrong. Socrates wants to lead the slave to the right conclusion. The boy should reach the truth through steps that are all “his own”, performed with full conviction. To this aim, Socrates addresses a series of short pressing questions to the slave boy. Simple questions provoke equally simple replies, though the boy is sometimes puzzled and surprised by the answers he feels compelled to give. In the first part of the exchange the boy is gradually forced to admit that a square B with double side (i.e. side of length 4) has an area which is not double, but four times as big, i. e. 16. In the second part the boy hazards the guess that the square with double area has a side of length 3, since 3 is between 2 and 4. But Socrates easily drives him to acknowledging that if the side is 3, the area of the resulting square C is 9, not 8. The boy can only exclaim: “By Zeus, Socrates, I do not know!”. In the third part, at Socrates’ prompting, the diagonal of the original square A is drawn within the second fourfold square B. Responding to Socrates’ questions, the boy is led to conclude that the square D whose side is the diagonal of A is precisely the required square: its area is 8. (shrink)
Robert Stalnaker contrasts two interpretations, semantic and metasemantic, of the two-dimensionalist framework. On the semantic interpretation, the primary intension or diagonal proposition associated with an utterance is a semantic value that the utterance has in virtue of the actual linguistic meaning of the corresponding sentence, and that primary intension is both what a competent speaker grasps and what determines different secondary intensions or horizontal propositions relative to different possible worlds considered as actual. The metasemantic interpretation reverses the order of (...) explanation: an utterance has the primary intension it has because it yields the secondary intensions it yields relative to different possible worlds considered as actual. In these possible worlds, the semantic facts can be different: the metasemantic interpretation is metasemantic in the sense that the secondary intensions are determined relative to possible worlds considered as actual given the meanings the expressions have there. Stalnaker holds a causal picture of the reference of names, according to which names have no meaning over and above their unique referent, and therefore maintains that the semantic interpretation is not an option. He thus endorses the metasemantic interpretation, while insisting that this interpretation does not, contrary to what he originally thought, yield any account of a priori truth and knowledge. My double aim in this paper is to show (i) that the metasemantic interpretation, as sketched by Stalnaker, is not compatible with one natural understanding of the causal picture of reference, on which names are rigid because they have their original bearers essentially , and (ii) that a third kind of interpretation of the framework is available, the metasyntactic interpretation, which grants that names have their bearers essentially and yields some account of a priori knowledge. (shrink)
The article deals with Cantor’s argument for the non-denumerability of reals somewhat in the spirit of Lakatos’ logic of mathematical discovery. At the outset Cantor’s proof is compared with some other famous proofs such as Dedekind’s recursion theorem, showing that rather than usual proofs they are resolutions to do things differently. Based on this I argue that there are “ontologically” safer ways of developing the diagonal argument into a full-fledged theory of continuum, concluding eventually that famous semantic paradoxes based (...) on diagonal construction are caused by superficial understanding of what a name is. (shrink)
Inspired by two-dimensional modal logic, some have sought to provide analyses of the notion of the contingent a priori which identify the a priori with truths which have a necessary diagonal. I argue that these analyses fail insofar as they miss the crucial epistemic aspect of the a priori. Augmenting these analyses with specifically epistemic accounts might be possible, but the interest would then reside in these epistemic accounts of the a priori and not in the formal models.
odel’s incompleteness results apply to formal theories for which syntactic constructs can be given names, in the same language, so that some basic syntactic operations are representable in the theory. It is now customary to derive these results from the fixed point theorem (also known as the reflection theorem), which asserts the existence of sentences that “speak about themselves”. Let T be the theory and, for each wff φ, let pφq be the term that serves as its name. Then the (...) theorem says that, for any wff α(v) (with one free variable), there exists a sentence β for which: T ` β ↔ α(pβq) β is sometimes called the fixed point of α(v). All that is needed for the fixed point theorem is.. (shrink)
Is it still possible to add a new column? Still of course, it can be form example 0, 0, 0; or 1, 1, 1. Now suppose that the table is very large. Can we still do the same? Well it seems that still the answer must be positive, though now it need not be so easy to find a new column. Here is an easy method: make the first number of the new column different from that in the first row (...) of the first column of the original table, make the second number in the second column different from that in the second row of the second column, etc. Hence the number in the n th row of the new column is different from that in the n th row of the n th column; and hence the new column is different from each column of the original table. (shrink)
Cantors diagonal argument provides an indirect proof that there is no one-one function from the power set of a set A into A. This paper provides a somewhat more constructive proof of Cantors theorem, showing how, given a function f from the power set of A into A, one can explicitly define a counterexample to the thesis that f is one-one.
Following F. William Lawvere, we show that many self-referential paradoxes, incompleteness theorems and fixed point theorems fall out of the same simple scheme. We demonstrate these similarities by showing how this simple scheme encompasses the semantic paradoxes, and how they arise as diagonal arguments and fixed point theorems in logic, computability theory, complexity theory and formal language theory.
It would be an understatement to say that Russell was interested in Cantorian diagonal paradoxes. His discovery of the various versions of Russell’s paradox—the classes version, the predicates version, the propositional functions version—had a lasting effect on his views in philosophical logic. Similar Cantorian paradoxes regarding propositions—such as that discussed in §500 of The Principles of Mathematics—were surely among the reasons Russell eventually abandoned his ontology of propositions.1 However, Russell’s reasons for abandoning what he called “denoting concepts”, and his (...) rejection of similar “semantic dualisms” such as Frege’s theory of sense and reference—at least in “On Denoting”—made no explicit mention of any Cantorian paradox. My aim in this paper is to argue that such paradoxes do pose a problem for certain theories such as Frege’s, and early Russell’s, about how definite descriptions are meaningful. My first aim is simply to lay out the problem I have in mind. Next, I shall turn to arguing that the theories of descriptions endorsed by Frege and by Russell prior to “On Denoting” are susceptible to the problem. Finally, I explore what responses a.. (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)
Tarski’s Indefinability Theorem can be generalized so that it applies to many-valued languages. We introduce a notion of strong semantic self-representation applicable to any (sufficiently rich) interpreted many-valued language L. A sufficiently rich interpreted many-valued language L is SSSR just in case it has a function symbol n(x) such that, for any f Sent(L), the denotation of the term n(“f”) in L is precisely ||f||L, the semantic value of f in L. By a simple diagonal construction (finding a sentence (...) l such that l is equivalent to n(“l”) T), it is shown that no such language strongly represents itself semantically. Hence, no such language can be its own metalanguage. (shrink)
I was interested to read Greg Pritchard’s articles ‘Civilised Lands’ in past issues of your magazine. In general, I think he gave a good overview of places of interest and tips for an overseas visitor on a climbing holiday to Australia. He failed, however, to warn visitors of the Australian pastime of sandbagging (which, I might add, Mr. Pritchard is a deft exponent of himself). I don’t know what state sandbagging has reached in your country but in Australia it has (...) become a refined art form. It is for this reason that I feel compelled to write this article, so as to warn otherwise unsuspecting English climbers of the possible pitfalls (or perhaps ground-falls would be more appropriate here) they may face on an Australian holiday. Firstly, an outline of what sandbagging is. The basic aim of the game is for the bagger to get an unsuspecting victim (also known as a baggee or sometimes a bunny) to do a climb (which, in the context of the game, is known as “the bag”) which they (the baggee) will not enjoy for one or a combination of three basic reasons. The first is that the climb may be positively dangerous, either loose and/or unprotected. Secondly, the climb may be much harder than either the grade or appearances indicate. Thirdly, the climb may be simply repulsive; for example, it might look like a nice diagonal layback flake and yet turn out to be a smooth flared overhanging off-width. The baggee, naturally enough, has a really miserable time and of course this gives the bagger great delight—in perfect accord with Toadie’s Law of the Conservation of Happiness (“happiness can be neither created nor destroyed”). Now, different baggers operate with different emphasis on each of the three basic bagging criteria, and have as their goal different levels of baggee misery. For example, there are those extremists, operating largely on criterion one, who are not completely happy unless they have witnessed a ground-fall from a reasonable height, in which case, if you are the baggee, your Australian holiday may consist of a few weeks in traction in Natimuk Bush Nursing Hospital.. (shrink)
Understanding a conversation sometimes requires us to keep track of what has been said about the objects under discussion. This fact presents a problem for a familiar account of content, the Russellian theory as advanced by Scott Soames and Nathan Salmon. Here I sketch an account of keeping track of objects in conversation, on which it involves presupposing unexpressed identity statements about the objects under discussion. The account is an application of a Stalnaker-style possible worlds account of assertion content, that (...) treats these unexpressed identities as part of an evolving set of presuppositions. Finally, I propose a two-dimensionalist extension of the basic Stalnakerian account to deal with the sort of case in which utterances are best understood as conveying the diagonal proposition of a two-dimensional propositional concept. These are discourses in which some of all parties to the conversation are confused about exactly which object is being discussed, even though they do keep track of what has been said about it. (shrink)
The creation-of-matter hypothesis of the Bondi-Gold-Hoyle steady-state cosmology requires that in an infinite time to which the first transfinite number may be assigned the number of atoms of matter produced would be equal to the cardinal number of the set of mathematical points in the continuum. The existence of a set of finite atoms with that cardinal number is physically unacceptable. The argument for the production of a non-denumerable set of atoms, in infinite time, is given in terms of a (...) model which is shown to be isomorphic with the original Cantor "diagonal" proof for the existence of a non-denumerable infinity. An alternative model which meets the requirements of the steady-state theory is presented; in this model, the number of atoms is explicitly no greater than countably infinite, and remains countably infinite as long as the past time of the universe is restricted to the unlimited set of finite unit-time intervals. If the origin of the steady-state universe is taken as being within that infinite set, expressed by the negative natural numbers, the contradiction of an atom at every mathematical point does not arise. The contradiction does arise if the origin is not within the set of finite numbers, and accordingly there is a restriction as to which concept of infinite past may properly be maintained in the steady-state theory. (shrink)
In Zwicker (1987) the hypergame paradox is introduced and studied. In this paper we continue this investigation, comparing the hypergame argument with the diagonal one, in order to find a proof schema. In particular, in Theorems 9 and 10 we discuss the complexity of the set of founded elements in a recursively enumerable relation on the set N of natural numbers, in the framework of reduction between relations. We also find an application in the theory of diagonalizable algebras and (...) construct an undecidable formula. (shrink)
Imagine a very fi ne grid or graph on which dots are placed at various coordinates so that, as a consequence, this or that shape materializes there. Depending on the coordinates of the dots, different shapes will appear, and for every shape there will be a pattern in the coordinates that guarantees its appearance. Take, for example, the diagonal line that slopes rightward and upward at an angle of 45 degrees from the origin. This line is bound to make (...) an appearance so long as the coordinates satisfy the condition or pattern that as they move away from the origin, (0,0), the coordinates are progressively larger pairs of equal numbers: (1,1), (3,3), and so on. In the world of such dots and shapes, it is going to be in principle possible, for any array of dots that realizes a relevant shape, to derive the presence of the shape from the numerical coordinates of the dots. More particularly, it is going to be possible to derive that shape without reliance on anything other than, fi rst, the empirical fact that the given array of coordinates instantiates this or that pattern; and second, the a priori knowable fact that the pattern guarantees the presence of the shape in question. The nature of the shapes on any grid—if indeed there are any relevant shapes present—is going to be a priori derivable from the positions of the dots; it is going to be possible in principle to derive the one from the other. The simplest and most appealing version of physicalism parallels this sort of doctrine about dots and shapes (Pettit 1994, 1995). It holds that just as the positions of the dots determine the nature of the shapes a priori, so the way the natural world is physically organized a priori determines the way it presents itself in psychological and other terms. The way things are physically confi gured entails the presence of psychological and other realities, and it does this without reliance on anything other than what a.. (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.
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)
In just proportional exchange, under Aristotle's theory of reciprocal justice, superior sharers in a community materially assist the weaker, and receive honour as a reward. Aristotle's economic thought is represented with a system of 18 formulae. Explained are: (1) What Aristotle means when he says that it is impossible for two sharers or their erga to be commensurable; (2) The extent to which the variables in Aristotle's proportions can be quantified. (3) What diagonal pairing ( ?ατ δ? ??τ?o? σ (...) ??????) is; (4) How need makes sharers and their erga ?sufficiently' commensurable; and (5) Aristotle's theory of what is just in exchange. (shrink)
Summary The incommensurability of scientific theories is not the only famous incommensurability issue in the history of western philosophy. The commensurability of all magnitudes (things) by means of ratios of integers (arithmetical ratios) wasthe thesis of Pythagoreanism. The diagonal and side of a square, however, are not commensurable, thus the Pythagorean thesis is refuted. Most philosophers ancient and contemporary would agree that Pythagoreanism was refuted by the counter-example and the concommitant argument or proof. The incommensurabilists were victorious. The present (...) paper examines the prospects of the contemporary thesis of the incommensurability of scientific theories in the light of the history of the Pythagorean thesis. What factors were responsible for the rather clear-cut victory of theincommensurability side? How were they able to carry through a refutation? How likely is it that the contemporary dispute over the commensurability of scientific theories will be resolved in such a sharp manner? The paper concludes that it is not at all likely. (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)
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)
Given an ideal $I$ , let $\mathbb{P}_{I}$ denote the forcing with $I$ -positive sets. We consider models of forcing axioms $MA(\Gamma)$ which also have a normal ideal $I$ with completeness $\omega_{2}$ such that $\mathbb{P}_{I}\in \Gamma$ . Using a bit more than a superhuge cardinal, we produce a model of PFA (proper forcing axiom) which has many ideals on $\omega_{2}$ whose associated forcings are proper; a similar phenomenon is also observed in the standard model of $MA^{+\omega_{1}}(\sigma\mbox{-closed})$ obtained from a supercompact cardinal. (...) Our model of PFA also exhibits weaker versions of ideal properties, which were shown by Foreman and Magidor to be inconsistent with PFA. Along the way, we also show (1) the diagonal reflection principle for internally club sets ( $\mathit{DRP}(IC_{\omega_{1}})$ ) introduced by the author in earlier work is equivalent to a natural weakening of “there is an ideal $I$ such that $\mathbb{P}_{I}$ is proper”; and (2) for many natural classes $\Gamma$ of posets, $MA^{+\omega_{1}}(\Gamma)$ is equivalent to an apparently stronger version which we call $MA^{+\operatorname{Diag}}(\Gamma)$. (shrink)
This essay is about mathematics as a written or literate language. Through historical and anthropological observations drawn from the history of Greek mathematics and the oral tradition preceding the rise of literacy in Greece, as well as considerations on the nature of alphabetic writing, it is argued that three essential linguistic features of mathematical discourse are jointly possible only through written, alphabetic language. The essay concludes with a discussion of how both alphabetic principles and issues related to literacy faced by (...) the Greeks in the axiomatization of geometry play a central role in some specific metamathematical theories. Drawing extensively on the work of ArpSd Szatx5, Eric Havelock, and Albert Lord, the implications developed between Szab6's history of Greek mathematics and Havelock and Lord's theories of writing and oral traditions (Homer's in particular) are the author's own, as are the applications to modern logic. (shrink)
We propose a technical reformulation of the measurement problem of quantum mechanics, which is based on the postulate that the final state of a measurement is classical; this accords with experimental practice as well as with Bohr's views. Unlike the usual formulation (in which the post-measurement state is a a unit vector in Hilbert space, such as a wave-function), our version actually admits a purely technical solution within the confines of conventional quantum theory (as opposed to solutions that either modify (...) this theory, or introduce unusual and controversial interpretative rules and/or ontologies). To that effect, we recall a remarkable phenomenon in the theory of Schroedinger operators (discovered in 1981 by Jona-Lasinio, Martinelli, and Scoppola), according to which the ground state of a symmetric double-well Hamiltonian (which is paradigmatically of Schroedinger's Cat type) becomes exponentially sensitive to tiny perturbations of the potential as h -> 0. We show that this instability emerges also from the textbook WKB approximation, extend it to time-dependent perturbations, and study the dynamical transition from the ground state of the double well to the perturbed ground state (in which the cat is typically either dead or alive, depending on the details of the perturbation). Numerical simulations show that, in an individual experiment, certain (especially adiabatically rising) perturbations may (quite literally) cause the collapse of the wavefunction in the classical limit. Thus we combine the technical and conceptual virtues of dynamical collapse models a la GRW (which do solve the measurement problem) with those of decoherence (in that our perturbations come from the environment) without sharing their drawbacks: although single measurement outcomes are obtained (instead of merely diagonal reduced density matrices), no modification of quantum mechanics is needed. (shrink)
With each projective geometry we can associate a Lyndon algebra. Such an algebra always satisfies Tarski's axioms for relation algebras and Lyndon algebras thus form an interesting connection between the fields of projective geometry and algebraic logic. In this paper we prove that if G is a class of projective geometries which contains an infinite projective geometry of dimension at least three, then the class L(G) of Lyndon algebras associated with projective geometries in G has an undecidable equational theory. In (...) our proof we develop and use a connection between projective geometries and diagonal-free cylindric algebras. (shrink)
Turing’s famous 1936 paper “On computable numbers, with an application to the Entscheidungsproblem” defines a computable real number and uses Cantor’s diagonal argument to exhibit an uncomputable real. Roughly speaking, a computable real is one that one can calculate digit by digit, that there is an algorithm for approximating as closely as one may wish. All the reals one normally encounters in analysis are computable, like π, √2 and e. But they are much scarcer than the uncomputable reals because, (...) as Turing points out, the computable reals are countable, whilst the uncomputable reals have the power of the continuum. Furthermore, any countable set of reals has measure zero, so the computable reals have measure zero. In other words, if one picks a real at random in the unit interval with uniform probability distribution, the probability of obtaining an uncomputable real is unity. One may obtain a computable real, but that is in- finitely improbable. But how about individual examples of uncomputable reals? We will show two: H and the halting probability Ω, both contained in the unit interval. Their construction was anticipated in.. (shrink)
La lógica borrosa se ha definido como un sistema preciso de razonamiento, deducción y computación en el que los objetos del discurso se encuentran asociados a información que, por lo general, consideramos imprecisa, incompleta, incierta, poco fiable, parcialmente verdadera o parcialmente posible.
In a first section, we discuss Quine’s claim according to which identity is a logical notion. We point out that Quine mixes up various types of identities: trivial (or diagonal) identity, Leibniz identity, etc.; and this leads him to commit several mistakes. In a second section, we review Quine’s criticisms to various philosophers (Wittgenstein, Whitehead, Leibniz, etc.), who according to him made confusion between names and objects in defining identity. We show that in fact only Korzybski can be accused (...) of such confusion. In a third section, we analyze the relation between identity and entity. We notice that for Quine a river is the result of the identification of river stages, but that he admits it as an entity by opposition to squareness, which according to him is a result of an identification process of higher abstraction. (shrink)
S. Ulam asked about the number of nonisomorphic projective algebras with k generators. This paper answers his question for projective algebras of finite dimension at least three and shows that there are the maximum possible number, continuum many, of nonisomorphic one-generated structures of finite dimension n, where n is at least three, of the following kinds: projective set algebras, projective algebras, diagonal-free cylindric set algebras, diagonal-free cylindric algebras, cylindric set algebras, and cylindric algebras. The results of this paper (...) extend earlier results to the collection of cylindric set algebras and provide a uniform proof for all the results. Extensions of these results for dimension two are discussed where some modifications on the hypotheses are needed. Furthermore for α |geq 2, the number of isomorphism classes of regular locally finite cylindric set algebras of dimension α of the following two kinds are computed: ones of power κ for infinite $\kappa \geq|\alpha|$ , and ones with a single generator. (shrink)
The paper is meant as a survey of issues in computational complexity from the standpoint of its relevance to social research. Moreover, the threads are hinted at that lead to computer science from mathematical logic and from philosophical questions about the limits and the power both of mathematics and the human mind. Especially, the paper addresses Turing's idea of oracle, considering its impact on computational (i.e., relying on simulations) economy, sociology etc. Oracle is meant as a device capable of finding (...) the values of uncomputable functions. Such an idealized entity is exemplified by the human mind's procedure of recognizing the truth of the Gödelian sentence, of identifying uncomputable numbers through Turing's diagonal procedure, etc. Since such procedures are strictly defined and are as reliable as any calculations, they are worth to be called computation as well. From the computation in the strict sense, that defined as purely algorithmic (mechanical) process, one distinguishes them with the term "hipercomputation". Now the following questions arise. - Are there undecidable problems (ie. not decidable with appropriate algorithms) in social research as are (according to what is reported esp. By S. Wolfram) in natural sciences? The answer in the negative would impose limitations on computer simulations (as entirely relying on algorithms). - If there are, then we have the next question: can such problems be addressed with hipercomputational procedures? - How such hipercomputational procedures would be related to analog computation (coextensive, everlappiing, etc.)? Another set of issues is stated in terms of tractability of decidable problems, that is, the efficiency of algorithms needed for solutions. As inefficient are regarded those which require more resources (time, memory, etc.) than is available in a foreseeable future. In this context, one discusses methods of such an efficient organizing computational processes to overcome the scarcity of resources; thus parallel, distributive, interactive, etc. computing are used as remedies. The paper claims, hinting at F.Hayek's ideas, that in some social systems (e.g., stock exchange, and free market in general) such an efficient organization of their computational activities spontaneously evolves. And this is the main source of its advantages over the central economic planning (as defended by O. Lange). This noticing (in terms of complexity theory) of analogy between Hayek's point and the current discussion of efficiency of algorithms is what may count as an original contribution of the present paper. (shrink)
Here's the article which was a 1964 Stanford AI Memo. After the original memo, several people offered different proofs of the theorem including Shmuel Winograd, Marvin Minsky and Dimitri Stefanyuk - none published, to my knowledge. Winograd claimed that his proof was non-creative, because it didn't use an extraneous idea like the colors of the squares. This set off a contest to see who could produce the most non-creative proof. Minsky's idea was to start with the diagonal next to (...) an excluded corner ssquare, note that 2 dominoes had to project from it to the diagonal with three squares, and from there 1 domino to the four square diagonal, etc. Coming from the other end also leaves only six of the eight squares in the long diagonal covered. Minsky's proof gets high points for non-creativity, because it is specific to the 8 by 8 board. (Using the colors it is easy to show that a Minsky style proof will work for any even sized board.). (shrink)
We propose a technical reformulation of the measurement problem of quantum mechanics, which is based on the postulate that the final state of a measurement is classical; this accords with experimental practice as well as with Bohr’s views. Unlike the usual formulation (in which the post-measurement state is a unit vector in Hilbert space), our version actually opens the possibility of admitting a purely technical solution within the confines of conventional quantum theory (as opposed to solutions that either modify this (...) theory, or introduce unusual and controversial interpretative rules and/or ontologies).To that effect, we recall a remarkable phenomenon in the theory of Schrödinger operators (discovered in 1981 by Jona-Lasinio, Martinelli, and Scoppola), according to which the ground state of a symmetric double-well Hamiltonian (which is paradigmatically of Schrödinger’s Cat type) becomes exponentially sensitive to tiny perturbations of the potential as ħ→0. We show that this instability emerges also from the textbook wkb approximation, extend it to time-dependent perturbations, and study the dynamical transition from the ground state of the double well to the perturbed ground state (in which the cat is typically either dead or alive, depending on the details of the perturbation).Numerical simulations show that adiabatically arising perturbations may (quite literally) cause the collapse of the wave-function in the classical limit. Thus, at least in the context of a simple mathematical model, we combine the technical and conceptual virtues of decoherence (which fails to solve the measurement problem but launches the key idea that perturbations may come from the environment) with those of dynamical collapse models à la grw (which do solve the measurement problem but are ad hoc), without sharing their drawbacks: single measurement outcomes are obtained (instead of merely diagonal reduced density matrices), and no modification of quantum mechanics is needed. (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.
We prove that every rectangularly dense diagonal-free cylindric algebra is representable. As a corollary, we give finite, sound and complete axiomatizations for the finite-variable fragments of first order logic without equality and for multi-dimensional modal S5-logic.
I here investigate the sense in which diagonalization allows one to construct sentences that are self-referential. Truly self-referential sentences cannot be constructed in the standard language of arithmetic: There is a simple theory of truth that is intuitively inconsistent but is consistent with Peano arithmetic, as standardly formulated. True self-reference is possible only if we expand the language to include function-symbols for all primitive recursive functions. This language is therefore the natural setting for investigations of self-reference.
This short sketch of Gödel’s incompleteness proof shows how it arises naturally from Cantor’s diagonalization method [1891]. It renders Gödel’s proof and its relation to the semantic paradoxes transparent. Some historical details, which are often ignored, are pointed out. We also make some observations on circularity and draw brief comparisons with natural language. The sketch does not include the messy details of the arithmetization of the language, but the motives for it are made obvious. We suggest this as a more (...) efficient way to teach the topic than what is found in the standard textbooks. For the sake of self–containment Cantor’s original diagonalization is included. A broader and more technical perspective on diagonalization is given in [Gaifman 2005]. In [1891] Cantor presented a new type of argument that shows that the set of all binary sequences (sequences of the form a0, a1,…,an,…, where each ai is either 0 or 1) is not denumerable ─ that is, cannot be arranged in a sequence, where the index ranges over the natural numbers. Let A0, A2,…An, … be a sequence of binary sequences. Say An = an,0, an,1, …, an,i, … . Define a new sequence A* = b0, b1,…,bn,… , by putting. (shrink)
This short sketch of Gödel’s incompleteness proof shows how it arises naturally from Cantor’s diagonalization method [1891]. It renders the proof of the so–called fixed point theorem transparent. We also point out various historical details and make some observations on circularity and some comparisons with natural language. The sketch does not include the messy details of the arithmetization of the language, but the motive for arithmetization and what it should accomplish are made obvious. We suggest this as a way to (...) teach the incompleteness results to students that have had a basic course in logic, which is more efficient than the standard textbooks. For the sake of self–containment Cantor’s original diagonalization is included. A broader and more technical perspective on diagonalization is given in [Gaifman 2005]. Motivated partly by didactic considerations, the present paper presents things somewhat differently. It also includes various points concerning natural language and circularity that appear only here. (shrink)
Hypercomputation—the hypothesis that Turing-incomputable objects can be computed through infinitary means—is ineffective, as the unsolvability of the halting problem for Turing machines depends just on the absence of a definite value for some paradoxical construction; nature and quantity of computing resources are immaterial. The assumption that the halting problem is solved by oracles of higher Turing degree amounts just to postulation; infinite-time oracles are not actually solving paradoxes, but simply assigning them conventional values. Special values for non-terminating processes are likewise (...) irrelevant, since diagonalization can cover any amount of value assignments. This should not be construed as a restriction of computing power: Turing’s uncomputability is not a ‘barrier’ to be broken, but simply an effect of the expressive power of consistent programming systems. (shrink)
We investigate what happens when ‘truth’ is replaced with ‘provability’ in Yablo’s paradox. By diagonalization, appropriate sequences of sentences can be constructed. Such sequences contain no sentence decided by the background consistent and sufficiently strong arithmetical theory. If the provability predicate satisfies the derivability conditions, each such sentence is provably equivalent to the consistency statement and to the Gödel sentence. Thus each two such sentences are provably equivalent to each other. The same holds for the arithmetization of the existential Yablo (...) paradox. We also look at a formulation which employs Rosser’s provability predicate. (shrink)
Few people have thought so hard about the nature of the quantum theory as has Jeff Bub,· and so it seems appropriate to offer in his honor some reflections on that theory. My topic is an old one, the consistency of our microscopic theories with our macroscopic theories, my example, the Aspect experiments (Aspect et al., 1981, 1982, 1982a; Clauser and Shimony, l978;_Duncan and Kleinpoppen, 199,8) is familiar, and my sirnplrcation of it is borrowed. All that is new here is (...) a kind of diagonalization: an argument that the fundamental principles found to be violated by the quantum theory must be assumed to be true of the experimental apparatus used in the experiments.. (shrink)
Full proofs of the Gödel incompleteness theorems are highly intricate affairs. Much of the intricacy lies in the details of setting up and checking the properties of a coding system representing the syntax of an object language (typically, that of arithmetic) within that same language. These details are seldom illuminating and tend to obscure the core of the argument. For this reason a number of efforts have been made to present the essentials of the proofs of Gödel’s theorems without getting (...) mired in syntactic or computational details. One of the most important of these efforts was made by Löb [8] in connection with his analysis of sentences asserting their own provability. Löb formulated three conditions (now known as the Hilbert-Bernays-Löb derivability conditions), on the provability predicate in a formal system which are jointly sufficient to yield the Gödel’s second incompleteness theorem for it. A key role in Löb’s analysis is played by (a special case of) what later became known as the diagonalization or fixed point property of formal systems, a property which had already, in essence, been exploited by Gödel in his original proofs of the incompleteness theorems. The fixed point property plays a central role in Lawvere’s [7] category-theoretic account of incompleteness phenomena (see also [10]). Incompleteness theorems have also been subjected to intensive investigation within the framework of modal logic (see, e.g.[4], [5]). In this formulation the modal operator takes up the role previously played by the provability predicate, and the derivability conditions on the latter are translated into algebraic conditions (the so-called GL, i.e., Gödel–Löb, conditions) on the former. My purpose here is to present a framework for incompleteness phenomena, fully compatible with intuitionistic or constructive principles, in which the idea of a coding system is retained, only in a 2 simple, but very general form, a form wholly free of syntactical notions. As codes we shall take the elements of an arbitrary given nonempty set, possibly, but not necessarily, the set of natural numbers.. (shrink)
It is argued that Yablo’s Paradox is not strictly paradoxical, but rather ‘ω-paradoxical’. Under a natural formalization, the list of Yablo sentences may be constructed using a diagonalization argument and can be shown to be ω-inconsistent, but nonetheless consistent. The derivation of an inconsistency requires a uniform fixed-point construction. Moreover, the truth-theoretic disquotational principle required is also uniform, rather than the local disquotational T-scheme. The theory with the local disquotation T-scheme applied to individual sentences from the Yablo list is also (...) consistent. (shrink)
The place of the subjective -- Everything that is of a whole constitutes an obstacle to it insofar as it is included in it -- Action, manor of the subject -- The real is the impasse of formalization : formalization is the locus of the passing-into-force of the real -- Hegel : "the activity of force is essentially activity reacting against itself" -- Subjective and objective -- The subject under the signifiers of the exception -- Of force as disappearance, whose (...) effect is the whole from which it has disappeared -- Deduction of the splitting -- A la nue accablante tu? -- Any subject is a forced exception, which comes in second place -- Jewelry for the sacred of any subtraction of existence -- Lack and destruction -- The new one forbids the new one and presupposes it -- On the side of the true -- There are no class relations -- Every subject crosses a lack of being and a destruction -- The subjects antecedence to itself -- Torsion -- Theory of the subject according to Sophocles, theory of the subject according to Eeschylus -- Of the strands of the knot, knowing only the color -- A materialist reversal of materialism -- The Black sheep of materialism -- The indissoluble salt of truth -- Answering to the sphinx demands from the subject not to have to answer or the sphinx -- Algebra and topology -- Neigborhoods -- Consistency, second name of the real after the cause -- So little ontology -- Subjectivization and subjective process -- The topological opposite of the knot is not the cut-dispersion but the destruction-recomposition -- Subjectivizing anticipation, retroaction of the subjective process -- Hurry! hurry! word of the living! -- The inexistent -- Logic of the excess -- Topics of ethics -- Where? -- The subjective twist : and -- Diagonals of the imaginary -- Schema -- Ethics as the dissipation of the paradoxes of partisanship -- Classical detour -- Love what you will never believe twice. (shrink)
Arithmetical self-reference through diagonalization is compared with self-recognition in a mirror, in a series of diagrams that show the structure and main stages of construction of self-referential sentences. A Gödel code is compared with a mirror, Gödel numbers with mirror images, numerical reference to arithmetical formulas with using a mirror to see things indirectly, self-reference with looking at one’s own image, and arithmetical provability of self-reference with recognition of the mirror image. The comparison turns arithmetical self-reference into an idealized model (...) of self-recognition and the conception(s) of self based on that capacity. (shrink)
There is a familiar derivation of G¨ odel’s Theorem from the proof by diagonalization of the unsolvability of the Halting Problem. That proof, though, still involves a kind of self-referential trick, as we in effect construct a sentence that says ‘the algorithm searching for a proof of me doesn’t halt’. It is worth showing, then, that some core results in the theory of partial recursive functions directly entail G¨ odel’s First Incompleteness Theorem without any further self-referential trick.
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)
One of the most familiar uses of the Russell paradox, or, at least, of the idea underlying it, is in proving Cantor's theorem that the cardinality of any set is strictly less than that of its power set. The other method of proving Cantor's theorem ââ¬â employed by Cantor himself in showing that the set of real numbers is uncountable ââ¬â is that of diagonalization. Typically, diagonalization arguments are used to show that function spaces are "large" in a suitable sense. (...) Classically, these two methods are equivalent. But constructively they are not: while the argument for Russell's paradox is perfectly constructive, (i.e., employs intuitionistically acceptable principles of logic) the method of diagonalization fails to be so. I describe the ways in which these two methods.. (shrink)
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)
There are many classical connections between the proof-theoretic strength of systems of arithmetic and the provable totality of recursive functions. In this paper we study the provability strength of the totality of recursive functions by investigating the degree structure induced by the relative provability order of recursive algorithms. We prove several results about this proof-theoretic degree structure using recursion-theoretic techniques such as diagonalization and the Recursion Theorem.
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.
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)
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 investigate the effect of a variant of Matet forcing on ultrafilters in the ground model and give a characterization of those P-points that survive such forcing, answering a question left open by Blass [4]. We investigate the question of when this variant of Matet forcing can be used to diagonalize small filters without destroying P-points in the ground model. We also deal with the question of generic existence of stable ordered-union ultrafilters.
In a perfect world, physicians and drug producers would have only one goal: to advance the health of their patients. Unfortunately, ours is not a perfect world. While every physician’s prime responsibility—by oath and by law—is to the patient, every pharmaceutical producer’s first and foremost obligation, by design, is to shareholders and employees. Their ultimate objectives are diagonally diverse. This situation calls for a code of ethics to govern the marketing and prescription of pharmaceuticals. This paper attempts to identifythe business (...) practices prevailing in the Indian pharmaceutical industry, in order to provide a basis for constructing an appropriate code of ethics. The research is based on surveys or in-depth interviews of physicians, patients, retail pharmacists, and drug manufacturers. (shrink)
