SUPPLEMENT Smullyan, Raymond M
Theory of Formal Systems. (AM-47),
03/2016, Letnik:
47
Book Chapter
In this supplement we first give a very trief introductory sketch of the structure of those systems (call “theories” by Tarski) whose logical basis includes at least the first order predicate ...calculus. We then discuss the applications of Chapters III, IV, V to these systems. Some of these applications are veil known; others are new.
We have organized this material so that the various sections can be read immediately following those chapters which they presuppose; we indicate in advance just what is needed for each section. The reader familiar with the definition of “theory” can skip § 1.
Sections §1
FORMAL MATHEMATICAL SYSTEMS Smullyan, Raymond M
Theory of Formal Systems. (AM-47),
03/2016, Letnik:
47
Book Chapter
In this chapter, we are interested in first giving a precise definition of a “formal” or “finitary” mathematical system, and then in establishing an important theorem, based on the works of Church ...and Post, concerning an interesting limitation of our possible knowledge of such systems. This theorem, which we can only state quite crudely at this stage, is essentially to the effect that there exists no decision procedure for formalized mathematics. Stated otherwise, there exists no “mechanical” method which will decide which sentences are provable in which mathematical systems. We shall subsequently use this theorem to prove and extend some
We consider the sequence w1, w2, ..., w1... of all r.e. sets arranged as in the Post enumeration (cf. #A, Chapter IV). A number set α is called productive iff there is a recursive function φ(x) such ...that for every r.e. subset w1of α, φ(1) ε α-w1; such a function φ(x) is called a productive function for α. Post calls a set a creative iff α is r.e. and α is productive. Thus α is creative iff α is r.e. and there exists a recursive function φ(x) such that for every number 1 for which w1is disjoint
In this chapter we lay the groundwork for the remainder of this study. The results of #A are needed for Chapter III; Section #B is needed for Chapter IV. The results of #C, though not actually needed ...for our further development of recursive function theory, are of some independent interest and are useful in certain metamathematical applications.
(a) Common Representability. Let (E1) and (E2) be 2 elementary formal systems over a common alphabet K. We shall call them Independent iff they contain no common predicates. By (E1) U (E2) we mean the E.F.S. over K whose axioms are those of
RECURSIVE FUNCTION THEORY Smullyan, Raymond M
Theory of Formal Systems. (AM-47),
03/2016, Letnik:
47
Book Chapter
In this chapter we present a connected development of recursive function theory from the viewpoint of elementary formal systems. Sections #A and #B are completely independent. The results of #A are ...fundamental for all of Chapter V. The reader desirous of quickly seeing the applications of Chapter III to mathematical logic (as developed in the supplement) might wish to read #B before #A.
In Chapter II we showed that certain operations (e.g., union, intersection, existential quantification, finite quantification, explicit transformations) preserve recursive enumerability. One of the principal aims of this sections is to define what it means for an operation
This article is written for both the general mathematican and the specialist in mathematical logic. No prior knowledge of matemathematics, recursion theory or combinatory logic is presupposed, ...although this paper deals with quite general abstractions of standard results in those three areas. Our purpose is to show how some apparently diverse results in these areas can be derived from a common construction. In Section 1 we consider five classical fixed point arguments (or rather, generalizations of them) which we present as problems that the reader might enjoy trying to solve. Solutions are given at the end of the section. In Section 2 we show how all these solutions can be obtained as special cases of a single fixed point theorem. In Section 3 we consider another generalization of the five fixed point results of Section 1 and show that this is of the same strength as that of Section 2. In Section 4 we show some curious strengthenings of results of Section 3 which we believe to be of some interest on their own accounts.
Some new double analogues of induction and transfinite recursion are given which yields a relatively simple proof of a result of Robert Cowen, 2 which in turn is a strengthening of an earlier result ...of Smullyan 1, which in turn gives a unified approach to Zorn's Lemma, the transfinite recursion theorem and certain results about ordinal numbers.
Uniform Self-Reference Smullyan, Raymond M.
Studia logica,
12/1985, Letnik:
44, Številka:
4
Journal Article
Recenzirano
Self-referential sentences have played a key role in Tarski's proof 9 of the non-definibility of arithmetic truth within arithmetic and Gödel's proof 2 of the incompleteness of Peano Arithmetic. In ...this article we consider some new methods of achieving self-reference in a uniform manner.
FIXED POINTS AND SELF-REFERENCE Smullyan, Raymond M.
International Journal of Mathematics and Mathematical Sciences,
1984, Letnik:
1984, Številka:
2
Journal Article
Recenzirano
Odprti dostop
It is shown how Gödel′s famous diagonal argument and a generalization of the recursion theorem are derivable from a common construation. The abstract fixed point theorem of this article is ...independent of both metamathematics and recursion theory and is perfectly comprehensible to the non‐specialist.
PDF
