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)

In this short work, Cantor's famous 'diagonal' proof of the non-recursivity of the class of real numbers is stated and discussed.

Cantor’s proof that the reals are uncountable forms a central pillar in the edifices of higher order recursion theory and set theory. It also has important applications in model theory, and in the foundations of topology and analysis. Due partly to these factors, and to the simplicity and elegance of the proof, it has come to be accepted as part of the ABC’s of mathematics. But even if as an Archimedean point it supports tomes of mathematical theory, (...) there is a question that demands clarification: What, exactly, does Cantor’s proof show? One of few places where this question is addressed is Appendix II of Wittgenstein’s Remarks on the Foundations of Mathematics. This essay is devoted to clarifying Wittgenstein’s remarks in that section. (shrink)

Cantor's diagonal proof is sig­nificant both because the central method of proof used in it has been subsequently applied in a number of other proofs, and because it is considered to confirm the existence of infinite sets whose size fun­ damentally and by an order of magnitude exceeds the size of the "classical" infinite set represented by all natural numbers, while their size can theoretically exceed every conceivable limit. Although Can­tor's proof is generally accepted by the (...) scientific community, some experts are somewhat reserved about it. The aim of this paper is to present Cantor's proof in an accessible way, while pointing out its (hidden) assumptions and possible problematic points, and pointing out that some of its underlying assumptions are not indisputable mathematical truths, but rather postulated propositions that may or may not be accepted. (shrink)

We trace self-reference phenomena to the possibility of naming functions by names that belong to the domain over which the functions are defined. A naming system is a structure of the form ,{ }), where D is a non-empty set; for every a∈ D, which is a name of a k-ary function, {a}: Dk → D is the function named by a, and type is the type of a, which tells us if a is a name and, if it is, (...) the arity of the named function. Under quite general conditions we get a fixed point theorem, whose special cases include the fixed point theorem underlying Gödel's proof, Kleene's recursion theorem and many other theorems of this nature, including the solution to simultaneous fixed point equations. Partial functions are accommodated by including “undefined” values; we investigate different systems arising out of different ways of dealing with them. Many-sorted naming systems are suggested as a natural approach to general computatability with many data types over arbitrary structures. The first part of the paper is a historical reconstruction of the way Gödel probably derived his proof from Cantor's diagonalization, through the semantic version of Richard. The incompleteness proof–including the fixed point construction–result from a natural line of thought, thereby dispelling the appearance of a “magic trick”. The analysis goes on to show how Kleene's recursion theorem is obtained along the same lines. (shrink)

In the paper, a detailed analysis of some new logical aspects of Cantor’s diagonal proof of the uncountability of continuum is presented. For the first time, strict formal, axiomatic, and algorithmic definitions of the notions of potential and actual infinities are presented. It is shown that the actualization of infinite sets and sequences used in Cantor’s proof is a necessary, but hidden, condition of the proof. The explication of the necessary condition and its factual (...) usage within the framework of Cantor’s proof makes, Cantor’s proof invalid. It’s shown that traditional Cantor’s proof has a second necessary, but hidden as well, condition which is teleological by its nature, i.e., is not mathematical. The explication of the second necessary condition makes Cantor’s statement on the uncountability of continuum unprovable from the point of view of classical logic.One of the most dramatic facts in history of science is connected just with the notion of actual infinity and consists in the following. On the one hand, Aristotle, Berkeley, Locke, Descartes, Spinoza, Gauss, Kant, Cauchy, Kronecker, Hermite, Poincaré, Bair, Borel, Brouwer, Quine, Wittgenstein, Weyl, Luzin, and a lot of other outstanding creators of classical logic and classical mathematics, during millenniums, stated categorically and insistently warned about that the actual infinity is a self-contradictory notion and its usage in mathematics is inadmissible (e.g., according to Poincare, “There is no actual infinity. - Cantorians forgot that and fell into contradictions. Later generations will regard Mengenlehre (set theory) as a disease from which one has recovered”). On the other hand, a lot of outstanding scientists of the XX c.c., such as Hilbert, Church, Turing, Gödel, etc., and modern axiomatic set theory as a whole ignored this (intuitive though) opinion of genii and accepted Cantor’s “transfinite paradise”, based on the actual infinity. In the paper some logical, philosophical, and psychological aspects of this historical “favorable opposition” are analyzed, and the fact that the scientific intuition of genii has won the historical battle against the mytho-’logic’ of Cantor’s transfinite ‘paradise’ is explained and logically justified. (shrink)

The paper discusses a relatively underexamined element of Wittgenstein’s philosophy of mathematics associated with his critique of set theory. I outline Wittgenstein’s objections to the theories of Dedekind and Cantor, including the confounding of extension and intension, the faulty definition of the infinite set as infinite extension and the critique of Cantor’s diagonal proof. One of Wittgenstein’s major objections to set theory was that the concept of the size of infinite sets, which Cantor expressed by means of (...) symbols אₒ and c, had no application, i.e. that there was no grammatical technique that could show how such expressions were to be used. Notions of set theory are, so to speak, exterior – they find themselves outdoors, outside of what we usually do. They form a discourse that takes us beyond the horizon of everydayness and commonality. They are like an engine idling of the language of mathematics. (shrink)

Cantor's 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 Cantor's 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.

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)

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)

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

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)

With respect to the metaphysics of infinity, the tendency of standard debates is to either endorse or to deny the reality of ‘the infinite’. But how should we understand the notion of ‘reality’ employed in stating these options? Wittgenstein’s critical strategy shows that the notion is grounded in a confusion: talk of infinity naturally takes hold of one’s imagination due to the sway of verbal pictures and analogies suggested by our words. This is the source of various philosophical pictures that (...) in turn give rise to the standard metaphysical debates: that the mathematics of infinity corresponds to a special realm of infinite objects, that the infinite is profoundly huge or vast, or that the ability to think about infinity reveals mysterious powers in human beings. First, I explain Wittgenstein’s general strategy for undermining philosophical pictures of ‘the infinite’ – as he describes it in Zettel; and then show how that critical strategy is applied to Cantor’s diagonalization proof in Remarks on the Foundations of Mathematics II. (shrink)

In this paper, I elaborate the difference between the concept of infinity and the idea of infinity through Cantor's diagonalization proof to illuminate a passage in Kant's Critique of Judgment. Taking Lyotard's analysis of aesthetic judgments as the basis for my own project, I focus on the idea of a collapse of temporality required for objective cognition and its concomitant preclusion of cognitive subjectivity. Finally, after borrowing language from Hegel's Phenomenology of Spirit, I show that even though there is (...) not a cognitive subject in judgments of the sublime, there is nevertheless a subjectivity that consciousness is tasked with, even if it never fulfills this task when it is confronted with a mathematically sublime object, and it is an subjectivity that would transcend time in order to know the object in-itself. (shrink)

This book clearly explains what an infinite number is, how infinite numbers differ from finite numbers, and how infinite numbers differ from one another. The concept of recursivity is concisely but thoroughly covered, as are the concepts of cardinal and ordinal number. All of Cantor's key proofs are clearly stated, including his epoch-making diagonal proof, whereby he proved that that there are more reals than rationals and, more generally, that there are infinitely large, non-recursive classes. In the final (...) section, Kurt Gödel's celebrated Incompleteness Theorem is shown to be equivalent with a number of the various different theorems proved in this short but profound work. (shrink)

In this paper Richard’s Paradox and the Proof of Cantor’s Theorem are compared. It is argued that there is no conclusive reason to treat them differently such as to call the one a Paradox and the other a Proof.

Numbers. Natural numbers -- Integers -- Real numbers -- Irrational and transcendental numbers -- Funny numbers. Zero -- e : the unnatural natural number -- [Phi] : the golden ratio -- i : the imaginary number -- Writing numbers. Roman numerals -- Egyptian fractions -- Continued fractions -- Logic. Mr. Spock is not logical -- Proofs, truth, and trees : oh my! -- Programming with logic -- Temporal reasoning -- Sets. Cantor's diagonalization : infinity isn't just infinity -- Axiomatic set (...) theory : keep the good, dump the bad -- Models : using sets as the LEGOs of the math world -- Transfinite numbers : counting and ordering infinite sets -- Group theory : finding symmetries with sets -- Mechanical math. Finite state machines : simplicity goes far -- The turing machine -- Pathology and the heart of computing -- Calculus : no, not that calculus- [lambda] calculus -- Numbers, booleans, and recursion -- Types, types, types : modeling [lambda] calculus -- The halting problem. (shrink)

Cantor’s proof that the powerset of the set of all natural numbers is uncountable yields a version of Richard’s paradox when restricted to the full definable universe, that is, to the universe containing all objects that can be defined not just in one formal language but by means of the full expressive power of natural language: this universe seems to be countable on one account and uncountable on another. We argue that the claim that definitional contexts impose restrictions (...) on the scope of quantifiers reveals a natural way out. (shrink)

Georg Cantor's absolute infinity, the paradoxical Burali-Forti class Ω of all ordinals, is a monstrous non-entity for which being called a "class" is an undeserved dignity. This must be the ultimate vexation for mathematical philosophers who hold on to some residual sense of realism in set theory. By careful use of Ω, we can rescue Georg Cantor's 1899 "proof" sketch of the Well-Ordering Theorem––being generous, considering his declining health. We take the contrapositive of Cantor's suggestion and add Zermelo's choice (...) function. This results in a concise and uncomplicated proof of the Well-Ordering Theorem. (shrink)

A mahāvidyā inference is used for establishing another inference. Its Reason is normally an omnipresent property. Its Target is defined in terms of a general feature that is satisfied by different properties in different cases. It assumes that there is no case that has the absence of its Target. The main defect of a mahāvidyā inference μ is a counterbalancing inference that can be formed by a little modification of μ. The discovery of its counterbalancing inference can invalidate such an (...) inference. This paper will argue that Cantor’s diagonal argument too shares some features of the mahāvidyā inference. A diagonal argument has a counterbalanced statement. Its main defect is its counterbalancing inference. Apart from presenting an epistemological perspective that explains the disquiet over Cantor’s proof, this paper would show that both the mahāvidyā and diagonal argument formally contain their own invalidators. (shrink)

Cantor’s proof that the reals is uncountable forms a central pillar in the edifices of higher order recursion theory and set theory. It also has important applications in model theory, and in the foundations of topology and analysis. Due partly to these factors, and to the simplicity and elegance of the proof, it has come to be accepted as part of the ABC’s of mathematics. But even if it supports tomes of mathematical theory, there is a question (...) that demands clarification: What does Cantor’s proof show? One of few places where this question is addressed is Appendix II of Wittgenstein’s Remarks on the Foundations of Mathematics. This essay is devoted to clarifying Wittgenstein’s key interpretive remarks. (shrink)

This work is, in large part, a series of refutations; it is also the author's Ph.D. thesis. First to be refuted is Russell's vicious circle principle as a general remedy for the solution of the paradoxes. The author rejects the classification of paradoxes into syntactic and semantic, since in his view there are no purely syntactic paradoxes. The distinction in logic between the uninterpreted syntactical aspect of a system and the system when given a determinate interpretation is held to be (...) untenable. Tarski's distinction between object-language and meta-language and his concept of semantically closed language are considered irrelevant for the solution of the Liar paradox. The author claims that the usual versions of the Liar paradox have the same structure as the Barber paradox, viz., [S ↔ ~S]. The author solves the Liar paradox by pointing out that it does not have a proper reference. Cantor's diagonal argument for the indenumerability [[sic]] of the real numbers is labeled as unsatisfactory. Since the diagonal number is dependent upon the real numbers in the constructed list, the author claims that this makes the diagonal number to be of a different nature and status than the real numbers in the list; thus we have what the author calls the dependence fallacy. The author also refuses to accept Cantor's nested interval proof of the indenumerability [[sic]] of the real numbers. Within the proof, two infinite sequences are constructed, each of which converges to a limit. Because the proof does not give a "definite rule of convergence," the author is not satisfied that the infinite sequences converge. Also rejected is Cantor's theorem. Other paradoxes analyzed are the Berry, Richard, heterological, "Richardian", Russell, Cantor, and Burali-Forti paradoxes.--T. G. N. (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)

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)

This dissertation provides a careful reading of the later Wittgenstein’s philosophy of mathematics centered around three major themes: reality, determination, and infinity. The reading offered gives pride of place to Wittgenstein’s therapeutic conception of philosophy. This conception views questions often taken as fundamental in the philosophy of mathematics with suspicion and attempts to diagnose the confusions which lead to them. In the first essay, I explain Wittgenstein’s approach to perennial issues regarding the alleged reality to which mathematical truths or propositions (...) correspond. Wittgenstein diagnoses exotic pictures of mathematical reality as stemming from misleading analogies formed across empirical and mathematical propositions. The second essay explains Wittgenstein’s treatment of perplexity regarding the ability of a mathematical rule to determine its applications in advance. This too is found to depend on a misleading analogy, in this case across behavioral and mathematical senses of ‘determine’. The third and final essay discusses Wittgenstein’s general critical approach to “the infinite”. Philosophical perplexity about infinity is shown to depend on the verbal imagery regularly associated with proofs and their power to take hold of one’s imagination. Wittgenstein dampens the imaginative excesses often associated with “the infinite” by offering a sober redescription of Cantor’s famous method of diagonalization. (shrink)

The present note was prompted by Weber’s approach to proving Cantor’s theorem, i.e., the claim that the cardinality of the power set of a set is always greater than that of the set itself. While I do not contest that his proof succeeds, my point is that he neglects the possibility that by similar methods it can be shown also that no non-empty set satisfies Cantor’s theorem. In this paper unrestricted abstraction based on a cut free Gentzen (...) type sequential calculus will be employed to prove both results. In view of the connection between Priest’s three-valued logic of paradox and cut free Gentzen calculi this, a fortiori, has an impact on any paraconsistent set theory built on Priest’s logic of paradox. (shrink)

This chapter presents a response to Chapter 1. The arguments put forward in that chapter attempted to drive us from the paradise created by Cantor’s theory of infinite number. The principal complaint is that Cantor’s proof that the subsets of a set are more numerous than its elements fails to yield an adequate diagnosis of Russell’s paradox. This chapter argues that Cantor’s proof was never meant to be a diagnosis of Russell’s paradox. Further, it argues (...) that Cantor’s theory is fine as it is. (shrink)

In this article, as implied by the title, I intend to argue for the unattainability of Cantor’s Absolute at least in terms of the proof-theoretical means of set-theory and of the theory of large cardinals. For this reason a significant part of the article is a critical review of the progress of set-theory and of mathematical foundations toward resolving problems which to the one or the other degree are associated with the concept of infinity especially the one beyond (...) that of the natural intuition of natural numbers. Naturally the review includes the foundation and development of the theory of large cardinals, especially after Cohen’s revolutionary introduction of the forcing method, insofar as it paved the way toward a transcendence of the delimitative character of Gödel’s constructible universe L and further toward ever stronger infinity assumptions. Given that Cantor in his theory of transfinite numbers defined the mathematical absolute in ontological rather than concrete mathematical terms, I proceed in the last section to a philosophical discussion with certain prompts from phenomenology regarding the transposability of the formal conception of the infinite to the level of subjective constitution and argue in these terms on the infeasibility of acceding to an ‘absolute’ infinite cardinality. Of course the argumentation is strongly based on a view of the set-theoretical universe V of von Neumann’s cumulative hierarchy as a formal representative of the essential traits one would seek from a model of Cantor’s Absolute. It is also based on the conclusions reached from the whole discussion within the context of formal-theoretical structures as such. (shrink)

What Gödel referred to as “outer” consistency is contrasted with the “inner” consistency of arithmetic from a constructivist point of view. In the settheoretic setting of Peano arithmetic, the diagonal procedure leads out of the realm of natural numbers. It is shown that Hilbert’s programme of arithmetization points rather to an “internalisation” of consistency. The programme was continued by Herbrand, Gödel and Tarski. Tarski’s method of quantifier elimination and Gödel’s Dialectica interpretation are part and parcel of Hilbert’s finitist ideal (...) which is achieved by going back to Kronecker’s programme of a general arithmetic of forms or homogeneous polynomials. The paper can be seen as a historical complement to our result on “The Internal Consistency of Arithmetic with Infinite Descent” . An internal consistency proof for arithmetic means that transfinite induction is not needed and that arithmetic can be shown to be consistent within the bounds of arithmetic, that is with the help of Fermat’s infinite descent and Kronecker’s general or polynomial arithmetic, thus returning into arithmetic without the detour of Cantor’s transfinite arithmetic of ideal elements. (shrink)

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)

We construct a novel proof of Cantor's theorem in set theory.

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.

(No abstract is available for this citation).

In these articles, I describe Cantor’s power-class theorem, as well as a number of logical and philosophical paradoxes that stem from it, many of which were discovered or considered (implicitly or explicitly) in Bertrand Russell’s work. These include Russell’s paradox of the class of all classes not members of themselves, as well as others involving properties, propositions, descriptive senses, class-intensions, and equivalence classes of coextensional properties. Part I focuses on Cantor’s theorem, its proof, how it can be (...) used to manufacture paradoxes, Frege’s diagnosis of the core difficulty, and several broad categories of strategies for offering solutions to these paradoxes. (shrink)

This paper offers an evaluation of Wittgenstein's critique of Cantorian set theory, illustrating his broader philosophical stance on mathematics. By emphasizing the constructed nature of mathematical theories, Wittgenstein encourages a reflective approach to mathematics that acknowledges human agency in its development. His engagement with Cantorian set theory provides valuable insights into the philosophical and practical dimensions of mathematics, urging a reconsideration of its foundations and the nature of mathematical proofs. This perspective aligns closely with the philosophy of mathematical practice, which (...) emphasizes the human side of mathematics by its focus on mathematical practice. (shrink)

The paper claims that the strategy adopted in the proof of Cantor’s theorem is problematic. Using the strategy, an unacceptable situation is built. The paper also makes the suggestion that the proof of Cantor’s theorem is possible due to lack of an apparatus to represent emptiness at a certain level in the ontology of set-theory.

The paper continues my earlier Chat with OpenAI’s ChatGPT with a Focused LLM Experiment (FLEX). The idea is to conduct Large Language Model (LLM) based explorations of certain areas or concepts. The approach is based on crafting initial guiding prompts and then follow up with user prompts based on the LLMs’ responses. The goals include improving understanding of LLM capabilities and their limitations culminating in optimized prompts. The specific subjects explored as research subject matter include a) diagonalization techniques as practiced (...) by Cantor, Turing, Gödel, and the advances, such as the Forcing techniques introduced by Paul Cohen and later investigators, b) Knowledge Hierarchies & Mapping Exercises, c) Discussions of IJ Good’s Speculations Concerning the First Ultraintelligent Machine, AGI, and Super- intelligence. Results suggest variability between major models like ChatGPT-4, Llama-3, Cohere, Sonnet and Opus. Results also point to strong dependence on users’ preexisting knowledge and skill bases. The paper should be viewed as ’raw data’ rather than a polished authoritative reference. (shrink)

The model theoretic `back and forth' construction of isomorphisms and automorphisms is based on the proof by Cantor that the theory of dense linear orderings without endpoints is ℵ 0 -categorical. However, Cantor's method is slightly different and for many other structures it yields an injection which is not surjective. The purpose here is to examine Cantor's method (here called `going forth') and to determine when it works and when it fails. Partial answers to this question are found, extending (...) those earlier given by Cameron. We also give fuller characterisations of when forth suffices for model theoretic classes such as structures containing Jordan sets for the automorphism group, and ℵ 0 -categorical ω-stable structures. The work is based on the author's Ph.D. thesis. (shrink)

G. Genzten’s 1938 proof of the consistency of pure arithmetic was hailed as a success for finitism and constructivism, but his proof requires induction along ordinal notations in Cantor normal form up to the first epsilon number, ε0. This left the task of giving a finitisically acceptable proof of the well-ordering of those ordinal notations, without which Gentzen’s proof could hardly be seen as a success for finitism. In his seminal book Proof Theory G. Takeuti (...) provides such a proof. After a brief philosophical introduction, we provide a reconstruction of Takeuti’s proof including corrections, comments, re-organization and notational adjustments for the sake of clarity. The result is a much longer, but much more tractable proof of the well-ordering of ordinal notations in Cantor normal form less than ε0, that nevertheless follows Takeuti’s strategy closely. We end with some more general comments about that proof strategy and the notion of accessibility more generally. (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)

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)

In a recent article, 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)

If one of Gentzen’s consistency proofs for pure number theory could be shown to be finitistically acceptable, an important part of Hilbert’s program would be vindicated. This paper focuses on whether the transfinite induction on ordinal notations needed for Gentzen’s second proof can be finitistically justified. In particular, the focus is on Takeuti’s purportedly finitistically acceptable proof of the well ordering of ordinal notations in Cantor normal form.The paper begins with a historically informed discussion of finitism and its (...) limits, before introducing Gentzen and Takeuti’s respective proofs. The rest of the paper is dedicated to investigating the finitistic acceptability of Takeuti’s proof, including a small but important fix to that proof. That discussion strongly suggests that there is a philosophically interesting finitist standpoint that Takeuti’s proof, and therefore Gentzen’s proof, conforms to. (shrink)

If one of Gentzen’s consistency proofs for pure number theory could be shown to be finitistically acceptable, an important part of Hilbert’s program would be vindicated. This paper focuses on whether the transfinite induction on ordinal notations needed for Gentzen’s second proof can be finitistically justified. In particular, the focus is on Takeuti’s purportedly finitistically acceptable proof of the well ordering of ordinal notations in Cantor normal form.The paper begins with a historically informed discussion of finitism and its (...) limits, before introducing Gentzen and Takeuti’s respective proofs. The rest of the paper is dedicated to investigating the finitistic acceptability of Takeuti’s proof, including a small but important fix to that proof. That discussion strongly suggests that there is a philosophically interesting finitist standpoint that Takeuti’s proof, and therefore Gentzen’s proof, conforms to. (shrink)

If it could be shown that one of Gentzen's consistency proofs for pure number theory could be shown to be finitistically acceptable, an important part of Hilbert's program would be vindicated. This paper focuses on whether the transfinite induction on ordinal notations needed for Gentzen's second proof can be finitistically justified. In particular, the focus is on Takeuti's purportedly finitistically acceptable proof of the well-ordering of ordinal notations in Cantor normal form. The paper begins with a historically informed (...) discussion of finitism and its limits, before introducing Gentzen and Takeuti's respective proofs. The rest of the paper is dedicated to investigating the finitistic acceptability of Takeuti's proof, including a small but important fix to that proof. That discussion strongly suggests that there is a philosophically interesting finitist standpoint that Takeuti's proof, and therefore Gentzen's proof, conforms to. (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)

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

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

By formalizing Berry's paradox, Vopěnka, Chaitin, Boolos and others proved the incompleteness theorems without using the diagonal argument. In this paper, we shall examine these proofs closely and show their relationships. Firstly, we shall show that we can use the diagonal argument for proofs of the incompleteness theorems based on Berry's paradox. Then, we shall show that an extension of Boolos' proof can be considered as a special case of Chaitin's proof by defining a suitable Kolmogorov (...) complexity. We shall show also that Vopěnka's proof can be reformulated in arithmetic by using the arithmetized completeness theorem. (shrink)