Self-referencing languages revisited

Abstract

Paradoxes, particularly Tarski's liar paradox, represent an ongoing challenge that have long attracted special interest. There have been numerous attempts to give either a formal or a more realistic resolution to this area based on natural logical intuition or common sense. The present semantic analysis of the problem components concludes that the traditional language of logic fails to detect Tarski's paradox, since the formalised version of the liar sentence does not represent a correct de¯nition. Neither the formal language, nor the logical system is de¯cient in this respect. Only natural language statements cannot be interpreted adequately by traditional language of logic.

Introduction

Paradoxes play a remarkable role in philosophy and logic. Several have been resolved, eliminated or brought to rest by appropriate theories (e.g.: Cretan paradox: Epimenides the Cretan says \All Cretans are liars", or the key statement of Nihilism: \there is no truth"), while others attract perpetual and changeless interest. Time and again new researches they challenge, and consistently elude resolution.

One of the most impressive paradoxes is analysed in this paper, speci¯cally Tarski's liar paradox associated with the de¯nition of logical truth. Much e®ort has been made since Tarski's theory of meta languages to obtain a semantically more acceptable explanation. For a thorough, complete and even historical analysis of this matter the reader can be referred to Feferman [2], although, there are many other papers continuously re-examining this point [1, 4, 5, 3].

Self-referencing languages surely imply a fundamental dilemma within philosophical logic. However, this property also demands particular interest from the Arti¯cial Intelligence community. Clearly, a potential attribute of representation languages is bene¯cial in reasoning systems of any kind, no matter whether it is for a human or robot. Natural languages are essentially rich in introspective statements concerning feelings, remarks, opinions, knowledge or other contentrelated features. Assertions of this kind apply a large variety of linguistic devices such as indirect quotations or modalities which are also occasionally loaded by self-reference. Therefore, an adequate representation of self-reference is crucial not only theoretically or philosophically, but also from a practical, functional point of view.

The problem occurs not at the level of natural languages, but that of the formalisation process. Formalisation of some natural language sentences can be inadequate even if it is possible. The latter alternative can obviously be ignored, since it would impugn the possibility of natural human understanding, without which there is no meaningful communication, formal or otherwise. The justi¯cation and resolution of the former option is the objective of this paper.

The foremost exact phrasing and modelling of the informal liar sentences was originated by Tarski and subsequently by numerous alternatives by Kripke, Gilmore, Feferman, Perlis, Kerber and others. It will be shown that the initial formal rephrasing of the liar sentence does not satisfy the natural requirement of being a valid de¯nition.

The paper presents an attempt to answer this problem, which is based on a di®erent logical language, determined by one of the authors, which has been proven to have a better expressive power. 2

Traditional formalising self-reference

The problem itself cannot even be identi¯ed without any formal representation. The ¯rst realization relating a Cretan type of sentence is accomplished by Tarski. 2.1

Tarski's paradox

Roots of Tarski's paradox are summarised here from [2]. Let x; ::: range over the statements of the language of a logical system, which are assumed to be closed under the usual propositional operators denoted by », &, _, ¾, ´. Each statement x of the language has a name, i.e. there is an associated closed term pxq of the language. Then the following axiom is accepted for a predicate t(pxq), which is interpreted as expressing that x is true: for each statement x of the language.

For the derivation of a contradiction in this system the liar sentence is taken: t(pxq) ´ x ( 2 ) is not true.

l :´ » t(plq) ( 1 ) ( 2 ) ( 3 ) formalised mostly as

By de¯nition ( 1 ) and transitivity of biconditional we obtain t(plq) ´ » t(plq), immediately implying inconsistency of the system. 2.2

The solution routes

There has been considerable work on theories eliminating these paradoxes. Numerous, seemingly di®erent escape routes have been determined the common idea of which is to discard problematic sentences: 1. either by altering the syntax so that undesirable statements could be excluded from the language, 2. or by revising critical axioms semantically so that antinomic formulae could be evaluated exceptionally (e.g. as meaningless ones).

Because of limited space, individual instances of the above categories are not discussed here. The former is followed by Tarski and Kerber [3], while the latter is preferred by Feferman [2] and Perlis [4, 5]. 3

An examination of formal liar sentences

As was shown previously, naive truth theory is considered to be demolished by paradoxes of self-reference, inspiring to create alternative theories avoiding these antinomies. The following approach tries to review the representation technique of the liar sentence challenging naive truth theory. 3.1

Liar sentence translated by biconditional

Many authors discussing the liar paradox represent sentence ( 2 ) as was shown in section 2.1, e.g. [2, 4]. Obviously,

l ´ » t(plq) is not a literal translation of ( 2 ), thus many authors disagree with this formula.

Another reason against the use of the biconditional here is that according to ¯rst-order logic the next logical consequence holds: ( 4 ) ( 5 ) ( 6 ) Interpreting this for ( 1 ) yields

(p ´ q) `a » (p ´ » q) x ´ t(pxq) ` » (x ´ » t(pxq)) that makes the de¯ning scheme of the liar sentence false immediately. In other words this translation of the liar sentence cannot cause any paradox relative to truth de¯nition.

According to the accepted reasoning this step concludes the commonly known paradox.

Nevertheless, the above deduction su®ers from the same defects that in the previous section. It is easy to show by the truth de¯nition ( 1 ) together with Leibniz's rule, (a = b) ¾ (F (a) ¾ F (b)), that

(pxq = pyq) ¾ (x ´ y) from which by the substitution » t(pxq)=y and applying the contraposition rule » (x ´ » t(pxq)) ¾ » (pxq = p » t(pxq)q) is reached. Then from this latter and ( 6 ) t(plq) ´ l ´ » t(plq) ( 7 ) ( 8 ) (9) (10) (11) 3.2

Liar sentence translated by equation

The previous, ( 4 ), interpretation of the liar sentence ( 2 ) is rather controversial. Another common representation of ( 2 ) is the following:

plq = p » t(plq)q The only di®erence between ( 7 ) and ( 4 ) is that the biconditional is replaced by an equation. This change makes the translation of ( 2 ) clearer, although one may still have doubts concerning it, as the consequences remain the same.

At this point contradiction can be deduced, if plq is substituted into ( 1 ), then Leibniz's rule and transitivity of biconditional is applied:

» (pxq = p » t(pxq)q) can be deduced, that contradicts to the assumption ( 7 ).

Now it is shown that even the modi¯ed representation of the liar sentence, ( 7 ), cannot cause paradox relative to the truth de¯nition ( 1 ), as the scheme pxq = p » t(pxq)q is also evaluated false.

Essentially, this means that translations of ( 2 ), i.e. ( 4 ) and ( 7 ) hitherto discussed, are unsound as de¯nitions, and thus fail to represent ( 2 ) adequately. 4

Finding a way out

Section 3 has shown that the root problem with liar type self-referencing is at an earlier level than was expected. The formula scheme working as the de¯nition of a liar sentence is unravelled as a false scheme. This fact seems to weaken the commonly known formal proofs of liar paradox, hence an apparent question probing the grounds of this inde¯nite phenomenon arises. On the other hand, this antinomy is still present in natural languages [8]. Thus, it cannot be due to a defect in natural language. There is no choice but to assume that the representation itself is invalid.

The question remains open whether a logical type of representation which is able to render this content adequately can exist. The rest of this paper argues that an isomorphic representation is necessary for this purpose, as described in the next section.

Representing a liar by iCTRL

The previous sections have shown that traditional language of logic has di±culties in representing self-referential sentences in their natural form. The imperfect ¯delity of translation may be a su±cient cause of improper interpretation of the case. Thus, changing the logical representation language may e®ect a more adequate model of the phenomenon. We present an alternative and novel manner of representing the matter relying on intensional conformal text representation language (iCTRL) initiated by one of the authors [6, 7]. It is a knowledge representation tool closer to natural languages, preserving not only truth as traditional logical language does, but it also models natural grammatical relations. Accordingly, it seems to be suitable for a better formalisation of self-reference, at the same time it allows veri¯cation of soundness of the preceding issues.

There is only limited space here to give a detailed formal introduction to iCTRL, so the reader is referred to [6, 7]. Although, a rather reduced sublanguage of iCTRL is su±cient for the whole description, the reader should be made familiar with some new notation. We focus immediately on truth de¯nition. The previously discussed de¯nition ( 1 ) can be now written as t x; h®ix: ´ ® (12) where ® represents any arbitrary proposition, h®ix the name of this proposition, ®, while t x stands for the truth predicate, and t x; h®ix: expresses the statement that ® is a true statement.

This latter expression deserves more attention. The predicate symbol t x itself appears to be the same as in classical logic, but its application to the corresponding name symbol di®ers from the way as it is commonly treated: t(h®i), since name symbols are treated now as singular predicate symbols, i.e. they must have an argument. Finally \," and \." are punctuation symbols, the former links the predicate of the formula with its subject, providing they share a common variable symbol, the latter closes the formula. Evaluation of the actual sentence t x; h®ix: simply answers the expectations: it is true if and only if the extension of h®ix is completely included in the extension of t x.

Before trying to represent self-reference, the ordinary case should be presented brie°y. Regularly, subjects, like h®ix, and corresponding predicates, such as t x, share the same variable symbol, because they are referring to the same group of individuals. However, an exterior subject, mentioned earlier or later in a text, cannot be referred to in this way, only by a compound reference variable term. E.g. y : x can provide that compound term redirecting its left side variable parameter to its right side one that refers to that subject expression sharing the same variable parameter name. Let the pair of sentences John walks. He whistles. be considered. The corresponding pair of formulae in this context is walk x; J ohn x: whistle y : x: A referred subject can naturally be eliminated by inserting it as it is referred to: walk x; J ohn x: whistle y; J ohn y:3 3 As a matter of fact, subject reference needs a bit more complex notation, which was simpli¯ed here to reduce unacquainted formalism to the minimum.

After these preliminary notes the iCTRL formula which exactly formalises the liar sentence ( 2 ) is Now the sentence itself plays the role of the subject of the predicate t x, the variable parameter of which x is redirected to the referred subject by t x : y.

Considering (12), it does not appear signi¯cantly di®er from the earlier version of truth de¯nition. Nevertheless, the liar sentence representative (13) is quite dissimilar to the classical formulae, ( 4 ) and ( 7 ), respectively. According to the construction, it is a literal translation of ( 2 ). It does not comprise any extraneous constituents such as biconditional or equation, which are also auxiliary tools in the corresponding classical formulae.

Contradiction results from a substitution of h» t x : yiy: into truth de¯nition (12), that is » t x; h®ix: ´ » ® generating: h» t x : yiy: (13) » h» t x : yiy: (14) Accomplishment of this substitution appears to be strange, because the liar sentence predicate » t x : y inside, wrapped into the subject part of the sentence, is to be matched by the left side of (12), » t x; h®ix:

The other pair of contradictory statements, similar to (14) and (13), correspondingly causes a paradox. If negation of liar » h» t x : yiy:, is substituted into (12) that is » (» t x; h®ix): ´ ®, that similarly yields h» t x : yiy:, then that is a contradiction.

In conclusion, the liar sentence has been proven plainly to be antinomic showing that inconsistency based on this kind of argumentation is clearly achieved. Traditional attempts to explain this make the impression that natural language and formal language of logic have drifted apart. However, this is not the case for iCTRL. 6

Closing Remarks

The source of Tarski's semantical paradox has been revised in this paper concluding with the recognition that a liar sentence, which is traditionally applied to generate an explicit antinomy with the classical truth de¯nition, fails to give an e®ective argument against the related conventional extension of ¯rst-order logic. This conclusion can be deduced in each formalisation instance of the classical language of logic originating from the fact that the liar sentence de¯nition fails to de¯ne the liar sentence itself. iCTRL modelling enabling a formal syntactic ¯delity of translation from natural languages, can prove this paradox case exactly. The approach presented here has shown an adequate representation of self-reference that may stimulate further development with respect to representation techniques of introspection. The core idea of this paper emerged during a colloquium with Prof. Weissmahr. The authors would like to express their indebtedness to him for his invaluable help and encouragement without which this work could never have come to fruition.

The authors would like to thank the anonymous reviewers for their help that made this paper more concise and distinct.

References

1. Gilmore , P. C. : The consistency of partial set theory without extensionality , Proc. of Symposia in Pure Mathematics , 13 /II ( 1974 ) 147 { 153 .

2. Feferman , S. : Toward useful type-free theories . I., J of Symbolic Logic , 49 /1 ( 1984 ) 75 { 111 .

3. Kerber , M: On Knowledge, Strings and Paradoxes , Proceedings of JELIA , Springer Verlag, 1998 .

4. Perlis , D. : Languages with self-reference I: foundations , Arti¯cial Intelligence , 25 ( 1985 ) 301 { 322 .

5. Perlis , D. : Meta in Logic, in Maes, P.; Nardi , D. eds.: Meta-level architectures and re°ection , Elsevier Science B.V. , 1988 , 37 { 49 .

6. R¶edey G.: Conformal Text Representation , Engineering Applications of AI , 6 ( 1993 ) 65 { 71 .

7. R¶edey G.: iCTRL: Intensional Conformal Text Representation Language , Arti¯cial Intelligence , 109 /1- 2 ( 1999 ) 33 { 70 .

8. Sainsbury , R.M. : Paradoxes, second edition, Cambridge University Press, 1995 .