Diagonalization in Formal Mathematics

verfasst von: Paulo Guilherme Santos

Verlag: Springer Fachmedien Wiesbaden

Buchreihe : BestMasters

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

In this book, Paulo Guilherme Santos studies diagonalization in formal mathematics from logical aspects to everyday mathematics. He starts with a study of the diagonalization lemma and its relation to the strong diagonalization lemma. After that, Yablo’s paradox is examined, and a self-referential interpretation is given. From that, a general structure of diagonalization with paradoxes is presented. Finally, the author studies a general theory of diagonalization with the help of examples from mathematics.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Preliminaries

Abstract

As the main subject of the current thesis is Mathematical Logic, we will assume that the main definitions and results of Logic are known (the definition of formula, the connectives, first-order theories, etc); for more information in introductory notions of Logic see: [Sho18], [Bar93], [Rau06], and [EFT96]. We will also assume the main definitions and results of Category Theory, a domain where we will use the right-to-left notation (in the rest we will use the usual function notation): af will denote, in the context of categories, the composition of f with a (see [Lan13] for more informations).

Paulo Guilherme Santos

Chapter 2. Introduction

Abstract

In the context of Mathematics, diagonalization is a very broad term that is linked to several phenomena that vanish from paradoxes to fixed point theorems. Nevertheless, although diagonalization is used to refer to a great variety of phenomena, there is a transversal idea to the use of the term: given a relation R(x₀, . . . ,x_n), it is used to refer to the possibility of R(a, . . . ,a) being the case for a given element a. It is now immediate how fixed point theorems are a case of diagonalization: given a function f , to say that f has a fixed point is equivalent to say that the relation R(x,y) defined by f (x) = y is diagonalisable (has a fixed point).

Paulo Guilherme Santos

Chapter 3. Two uses of the Diagonalization Lemma

Abstract

In this chapter, we will use the Diagonalization Lemma for two purposes: to present natural properties related to self-reference that are not decidable, and to argue that one cannot prove the Strong Diagonalization Lemma using the Diagonalization Lemma, i.e., that diagonalization of term is substantially different from diagonalization of formulas.

Paulo Guilherme Santos

Chapter 4. Yablo’s Paradox and Self-Reference

Abstract

Yablo in [Yab93] presented a paradox that, according to him, should not depend on self-reference.

Paulo Guilherme Santos

Chapter 5. Smullyan’s Theorem, Löb’s Theorem, and a General Approach to Paradoxes

Abstract

In this chapter, we are going to present a result by Smullyan that is behind several important diagonalization phenomena, and we are going to present a general approach to several paradoxes. The main ideas of this chapter are based on a paper by the author: [SK17].

Paulo Guilherme Santos

Chapter 6. General Theory of Diagonalization

Abstract

In this chapter we will present a general theory of diagonalization. We will move towards the goal of the next chapter: the study of Mathematical examples.

Paulo Guilherme Santos

Chapter 7. Mathematical Examples

Abstract

In this chapter we will study several examples of diagonalization from Mathematics and we will show that all of them are a particular case of the reasoning of the GDT.

Paulo Guilherme Santos

Chapter 8. Conclusions and Future Work

Abstract

The main objective of the present work was to study diagonalization in a formal system with a view towards a general theory of diagonalization that can be applied to everyday Mathematics. We started to study in detail the Diagonalization Lemma in Chapter 3, then we moved to argue that Yablo’s Paradox is self-referential in Chapter 4. After that, in Chapter 5, we presented a common origin of several paradoxes and Löb’s Theorem; furthermore, we presented a general approach to paradoxes.

Paulo Guilherme Santos

Backmatter

Titel: Diagonalization in Formal Mathematics
verfasst von: Paulo Guilherme Santos
Verlag: Springer Fachmedien Wiesbaden
Electronic ISBN: 978-3-658-29111-2
Print ISBN: 978-3-658-29110-5
DOI: https://doi.org/10.1007/978-3-658-29111-2