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.
Foreword Raymond Smullyan
The Mathematics of Various Entertaining Subjects,
12/2015
Book Chapter
Recreational mathematics can provide a most pleasant introduction to deep results in mathematics and logic to the general public. For example, take the field known aspropositional logic, which deals ...with the way simple propositions are combined to form more complex propositions, using the connectivesnot, and, or(where “or” should be taken in the sense of “at least one,”)if-then, andif and only if. I have found that a most useful way of approaching this subject is by the logic oflyingandtruth-telling, which people can relate to quite easily. And so let us turn to a
Chameleonic Languages Smullyan, Raymond M.
Synthese (Dordrecht),
08/1984, Letnik:
60, Številka:
2
Journal Article
Recenzirano
Chameleonic (indexical) constructions in natural & arithmetic langs are analyzed within informal & formal frameworks, & indexical & nonindexical (normal) sentences are described. The problems of ...reference, cross-reference, & simultaneous self-reference are addressed & a chameleonic formula representing a set in which a chameleonic sentence is chameleonically true is arithmetically presented. 6 References. Z. Dubiel
Analytic natural deduction Smullyan, Raymond M.
The Journal of symbolic logic,
06/1965, Letnik:
30, Številka:
2
Journal Article
Recenzirano
We consider some natural deduction systems for quantification theory whose only quantificational rules involve elimination of quantifiers. By imposing certain restrictions on the rules, we obtain a ...system which we term
Analytic Natural Deduction
; it has the property that the only formulas used in the proof of a given formula
X
are either subformulas of
X
, or negations of subformulas of
X
. By imposing further restrictions, we obtain a canonical procedure which is bound to terminate, if the formula being tested is valid. The procedure (ultimately in the spirit of Herbrand 1) can be thought of as a partial linearization of the method of semantical tableaux 2, 3. A further linearization leads to a variant of Gentzen's system which we shall study in a sequel.
The completeness theorem for semantical tableaux rests essentially on König's lemma on infinite graphs 4. Our completeness theorem for natural deduction uses as a counterpart to König's lemma, a lemma on infinite “nest structures”, as they are to be defined. These structures can be looked at as the underlying combinatorial basis of a wide variety of natural deduction systems.
In § 1 we study these nest structures in complete abstraction from quantification theory; the results of this section are of a purely combinatorial nature. The applications to quantification theory are given in § 2.
On Post's canonical systems Smullyan, Raymond M.
The Journal of symbolic logic,
03/1962, Letnik:
27, Številka:
1
Journal Article
Recenzirano
We assume familiarity with the canonical languages of Post (cf. 1, 2).
A set
S
of strings is said to be
representable
in a canonical system (
F
) if there is a string
π
such that for every string
X, ...X ∈ S
if and only if
πX
is provable in (
F
).
Suppose that
K
is a finite alphabet containing at least 2 symbols, and that
W
is a set of strings in (the symbols of)
K
. If
W
is representable in some canonical system, is it necessarily representable in a canonical system which uses only the symbols of
K
? We answer this question affirmatively. Thus, e.g., it is possible to construct a 2-sign universal system over its own alphabet.
2
This paper treats of semantical systems
S
of sufficient strength so that for any set
W
definable in
S
(in a sense which will be made precise), there must exist a sentence
X
which is true in
S
if and ...only if it is an element of
W
. We call such an
X
a
Tarski
sentence for
W
. It is the sentence which (in a purely extensional sense) says of itself that it is in
W
. If
W
is the set of all expressions not provable in some syntactical system
C
, then
X
is the Gödel sentence which is true (in
S
) if and only if it is not provable (in
C
). We provide a novel method for the construction of these sentences, which yields sentences particularly simple in structure. The method is applicable to a variety of systems, including a form of elementary arithmetic, and some systems of protosyntax self applied. In application to the former, we obtain an extremely simple and direct proof of a theorem, which is essentially Tarski's theorem that the truth set of elementary arithmetic is not arithmetically definable.
The crux of our method is in the use of a certain function, the ‘norm’ function, which replaces the classical use of the
diagonal
function. To give a heuristic idea of the norm function, let us define the norm of an expression E (of informal English) as E followed by its own quotation.
PDF
