Title of article :
Diagonal arguments and fixed points
Author/Authors :
Karimi ، A. - Tarbiat Modares University , Salehi ، S. - University of Tabriz
Abstract :
A universal schema for diagonalization was popularized by N.S. Yanofsky (2003), based on a pioneering work of F.W. Lawvere (1969), in which the existence of a (diagonolized-out and contradictory) object implies the existence of a fixed-point for a certain function. It was shown that many self-referential paradoxes and diagonally proved theorems can fit in that schema. Here, we fit more theorems in the universal schema of diagonalization, such as Euclid s proof for the infinitude of the primes and new proofs of G.~Boolos (1997) for Cantor s theorem on the non-equinumerosity of a set with its powerset. Then, in Linear Temporal Logic, we show the non-existence of a fixed-point in this logic whose proof resembles the argument of Yablo s paradox (1985, 1993). Thus, Yablo s paradox turns for the first time into a genuine mathematico-logical theorem in the framework of Linear Temporal Logic. Again the diagonal schema of the paper is used in this proof; and it is also shown that G.~Priest s inclosure schema (1997) can fit in our universal diagonal/fixed-point schema. We also show the existence of dominating (Ackermann-like) functions (which dominate a given countable set of functions, such as primitive recursive functions) in the schema.
Keywords :
Diagonal argument , self , reference , fixed , points , Yablo s paradox , (linear) temporal logic
Journal title :
Bulletin of the Iranian Mathematical Society
Journal title :
Bulletin of the Iranian Mathematical Society