The diagonal argument has been not only the spring for a new season of paradoxes, but also a powerful tool for the most relevant logic and metamathematical discoveries of our century. These discoveries enlighten the role of logic and arithmetic in the syntactic paradigm. At the beginning of the report we have outlined the underlying idea of 'science' as a 'chain', or maybe better as a 'tree', of systems, connected as semantic/syntax pairs, reaching from one side the empirical sciences of the nature and from the other side natural language and/or logic and set theory and/or informal arithmetic, according to different epistemological approaches.
In this section we try to check the claim that a crucial role had to be played by logic or arithmetic. Now, we give only a short synthesis of the most relevant results to shed some light to the connections between the above paradoxes and those sets of concepts we analysed in the first two reports as the core of the Aristotelian foundation. This section assumes some knowledge about logic and metamathematics, but in the 6-th section the most relevant aspects are more simply stated. However, the interested reader can find a more complete technical analysis in Kleene (KLEENE 1971), and a more detailed historical setting in Kneale and Kneale (KNEALE 1962).
The core of the first Goedel incompleteness theorem can be set in Cantor's ''coding'' of infinite sets and diagonal argument, applied to formalised arithmetic. Namely, we can ''code'' finite strings of symbols from a finite alphabet as natural numbers. Hence, logical and arithmetic expressions and finite sequences of them (that is, ''proofs'' and ''derivations''), although infinite they are, can be ''enumerated''. More, we can easily define this ''coding'' so that it and its inverse ''decoding'' can be arithmetically (uniquely) ''computed''. At this point, Goedel introduces the idea that the properties about these coded sequences of formal expressions can be expressed in a formal language rich enough to express axiomatised (for example, by Peano's axioms) arithmetic.
In the original proof, we can employ this ''coding'' to produce a proposition asserting its own unprovability, something like ''This proposition can not be proved''. It recalls the ''liar'' sentence. But it is not paradoxical, for truth and provability are not necessarily coincident. The coincidence of this two concepts characterises the ''completeness'' of the employed formal system. Indeed, it is easy to prove that ''provability'' entails ''truth'', but the vice versa can be questioned. Hence, if the above proposition is false, it is provable and then true, and this is absurd, if the system is consistent. If it is true, it is also unprovable, but this is not absurd. Then, we have found a proposition true and neither provable nor disprovable, and therefore the system is not complete. We underline that this 'technical' usage of the term 'complete' is homogeneous to the general characterization given at the beginning of this report.
A crucial point of the theorem is the representability of a formal theory, with its terms, formulas and proofs as well, in terms of integers and the representability of meta-linguistic propositions as propositions about integers. The original proof of this theorem was relative to a definite, although very general and acceptable, formal system. However, this condition can be removed. It is possible to give a generalised form, due to Church, which translates the problem in terms of general recursivity of the predicate Prov(f,x,y)) : ''f is the coding of a formula in the variable x, and y the coding of its proof''. The recursivity of ''Prov'' means that there is a preassigned procedure or set of equations, by which, for any given triple of numbers f,x and y, it is possible to decide whether y is the coding number of the proof of the formula p(x), where p is the decoding of f, or not. Obviously, a formula is a theorem if and only if there exists a proof of it. We can thus write Theor(f,x) <=> (Ey) Prov(f,x,y).
In fig.4, we sketch the reasoning-line of the Goedel theorem, in the generalised form due to Church, as proposed by Kleene (KLEENE 1971), in the framework of the ''syntactic paradigm''. Here and in the following, <S> is the Goedel number of the expression S, ''n'' is the expression whose Goedel number is n. In addition, S is the formal representation of the metamathematical S, |- denotes the ''derivability'' relation, (y) and (Ey) are the quantifiers. In the 'informal' arithmetic we quote in the figure Kleene's metamathematical ''enumeration theorem'', by which (Ey)Prov(n,x,y) enumerates, instancing n with all natural numbers, all the predicates of the form (Et)S(x,t), for any general recursive S. In this and in the following figures the horizontal lines depict the ''correct representation'' between informal (left) and formal (right) entities. These graphical schemes aim to elucidate the 'topology' of the antinomical argument. The vertical lines represent the 'answering' actions (provability, truth, validity, etc.). In fig.4 the left vertical arrow represents the employment of the predicate calculus, for example to rewrite (y)not as not(Ey). The syntax system is not fully explicitally drawn. The metamathematical system is displayed at the right of the figure. As common after Plato, negatives are isomorphic in the syntax/semantics pairs. In this proof, for hypothesis, let A(n) ''correctly represent'' the informal (y)not(Prov(n,n,y)), i.e. the ''non-provability'' relation for 'diagonal' elements. Let RA(x,Y) be the metamathematical predicate ''Y is a proof of A(x)'', and let RA(x,y) be the formal number-theoretic predicate associated to RA(x,Y). Then, obviously (Et)RA(x,t) represents the ''provability of A(x)'', and in the same time, being the 'provability' a recursive relation, we can apply the ''enumeration theorem'' to (Et)RA(x,t). Let f be the relative enumerating number. Let now consider A(f). In these hypotheses |-A(f) implies not(|-A(f)), following clockwise fig.4, from the right round-corner square. Then, if the hypothesis of correct representation is right, (y)not(Prov(f,f,y)) is true, but its representing formula A(f) is unprovable, and the system is then incomplete. Otherwise, supposing the formal system both correct and complete, the ''non-provability'' relation is not representable, and the formal system ''provability'' relation undecidable. This is often reported as the ''undecidability'' or ''essential undecidability'' of Peano's arithmetic.
Hence, for no formal consistent system ''provability'' and ''truth'' can coincide, if the system allows the arithmetical coding of its propositions. The ideas of ''formal system'' and ''proof'' are very general: here we need a list of axioms and some principles of deduction which can be somehow coded in an effectively calculable predicate. Beyond this idea of proof, we must suppose only that we can interpret the universal quantifier as a sort of infinite disjunction.
The second Goedel's incompleteness theorem employs the same coding technique to express the ''consistency'' of the formal system in the same system, by coding it with the expression ''the formula '0 not equal 0' cannot be proved''. The theorem demonstrates that if the system is consistent, this expression, and hence the ''consistency'', cannot be proved. Also in this case, some limitations to specific features of the formal system can be removed generalising the provability relation, requiring only its representation by a recursively denumerable formula (MOSTOWSKI 1966).
The comparative 'anatomy' of these antinomical arguments will be developed in the sixth section. Now, we want to make some remarks concerning the role of arithmetic in the 'language' and 'reality' worlds, and the related role of logic. A crucial role had to be played by the supposedly semantic concept of 'truth'. In Goedel's theorems, however, the usage of the truth concept is substantially syntactic, strongly linked to the condition of consistency, by which it entered the argumentation as a tool for asserting some proposition. In the discussion of these theorems often the truth concept assumes a more set-theoretic character, sometimes defined (following Tarski) semantic, as though numbers had a sort of Platonic own existence. We underline that the lack of this Platonic faith has no influence on Goedel's proof, for the 'truth' of the 'pathological' formula has nothing to do with some 'real' arithmetic property, but is only a side-effect of the contradiction and third-excluded principles and the functional commutativity of the diagram. Is it possible to give to the truth a further, more 'semantical', characterization? Defined the least attributions that such characterization needs to satisfy, the answer is 'no': in any theory any chance of syntactical representation of the relative truth is ruled out. In fact, a fundamental result of Tarski's theory is that the 'truth' predicate for a theory, consistent and including number theory, cannot be expressed in the same theory.
It is noteworthy the centrality that arithmetic and recursion theory gain in modern logic, leaving more and more difficulties for the classic 'logicist' approach. Most of all the ''recursion theory'' and the ''theory of algorithms'' allow us to get rid of the reference to specific 'intuitive' logical axioms and inference rules:
...with this concept (recursiveness or Turing's computability) one has for the first time succeeded in giving an absolute definition of an interesting epistemological notion, i.e. one not depending on the formalism chosen. In all other cases treated previously, such as demonstrability and definability, one has been able to define them only relative to a given language, and for each individual language it is clear that the one thus obtained is not the one looked for. For the concept of computability, however, although it is a special kind of demonstrability or decidability, the situation is different. By a kind of miracle it is not necessary to distinguish orders, and the diagonal procedure does not lead outside the defined notion. (GOEDEL 1968)
The 'miracle' is connected to the simple fact that arithmetic has always been the secret core of the signs world: this fact will be clear also in other metamathematical results, as the Loewenheim-Skolem theorem, that we will refer in the following, and accounts for the disappearing in the recursivity reformulation of any dependence on specific formal languages. In addition, if we remember that the crucial difference between intuitionists and formalists was in that the grounding a-priori was respectively arithmetic and signs-manipulation, we can say that Goedel coding employment in metamathematics displays the substantial unity of a (not enough considered) basic signs-philosophy in the XX century mathematics. The general definition of ''computable'' function necessarily entails an existential quantification on an infinite set and then is not finitistic, for, to prove it, we had to verify an actually infinite set of propositions. In fact, if we had a strictly finitistic definition, we could enumerate all computable functions, and recursively define by the diagonal argument a 'pathologic' function, which in the same time had to be and not to be in the enumeration. If we want to get finitistic definitions without running into the diagonal argument, we have to limit ourselves to ''partially computable'' functions. Here, the paradox cannot appear, for here in the 'pathologic' element the 'pathologic' function can be undefined and thus be non-contradictory. This generalised result stresses the purely syntactic nature of metamathematics.
Computable functions (total and partial) ... can be accepted as a basis of a nominalistic mathematics, ... rejects such abstract notions as sets, functions, etc. and admits only those objects which can be named. ...In the theory of computability ...it is sufficient to know how to manipulate the expressions. We can thus say that the theory of computability is purely syntactic. ... The interpretation of a language is defined by means of set-theoretic concepts, which gives rise to the close relations between semantics and the set-theoretical, infinitistic philosophy of mathematics; whereas the theory of computability leans towards a more finitistic nominalistic philosophy.((MOSTOWSKI 1952),41-42)
To examine more closely above Mostowski's words, we need to mention the Loewenheim-Skolen theorem, which asserts that a formula satisfiable in some infinite domain is also satisfiable in the domain of the natural numbers. This result is paradoxical if we consider that in the axiomatic set theory we can prove the existence of a non-denumerably infinite set of sets. If the theory is consistent, this result is satisfiable in the existing models of the theory and, by the Loewenheim-Skolem, also in the domain of natural numbers, which are only a denumerable set. The way out from this paradox can be found in two observations. The first is that in the theory we can define sets only by the predicates of the theory and hence we can define only denumerably many subsets of a given set, and these can be matched in a denumerable set. The second is that the enumeration of a given set is a particular set (of pairs), which could be not definable in the theory, and hence this given set in the theory had to be non-denumerable, although denumerable outside the theory. However,
...the ''paradox'' still confronts us with the following alternative. Either we must maintain that the concepts of an arbitrary subset of a given set, and of a denumerable set, are a priori concepts which elude characterisation by any finite or enumerably infinite system of elementary axioms; or else...we must accept the set-theoretic concepts, in particular that of non-enumerability, as being relative, so that a set which is non-denumerable in a given axiomatization may become denumerable in another, and no absolute non-enumerability exists. This relativization of set theory was proposed by Skolem.((KLEENE 1971), 427)
If we consider also that natural numbers can not be characterised by any finite or effectively numerable infinite set of axioms ((KLEENE 1971), 427-428), and hence, according to the most diffuse interpretation, arithmetic admits more non-isomorphic models, the first Goedel theorem can be read as expressing that the 'paradoxical' proposition could be true of the natural numbers, but false under one of the other interpretations satisfying Peano's axioms. So, both Goedel's and Loewenheim-Skolem's theorems face us with a sharp alternative: - either to accept that crucial concepts, as truth of a proposition, subset of a set, non-enumerability of a set, cannot be formalised (by any finite or enumerably infinite set of axioms). - or to accept that crucial theories, as arithmetic and set theory, when anyhow formalised, admit non-isomorphic models, in which some negative counterpart of crucial concepts, as enumerability or provability, can have different (although uniquely determined in a standard model) truth values. And this, whichever system of axioms present or future be used. That is, these fundamental semantic and infinitistic concepts either cannot be syntactically expressed or cannot be syntactically distinguished from their non-standard finitistic and purely syntactic 'clones'.
On the other side, according to Goedel's and Tarski's theorems, we assert the impossibility in formal systems of proving or expressing something, which on the contrary requires a stronger system to be proved or expressed. The argument can be reproduced, giving infinite hierarchies of systems. Being infinite, these hierarchies of systems substantially limit in a given system the formal expressivity of crucial concepts, as the provability of consistency and the definability of truth, relative to the same system. These two versions (proving the consistency/expressing the truth) seem to represent the same fact from two complementary point of view. Considering their connection and distinguishing them as syntactic (connecting satisfaction of a property for a set of integers with the provability of the representing predicate applied to this set of integers) and semantical (defining truth as a relation stronger than provability) ways to the translation of the vague idea of truth in a given formal system (S), Mostowski wrote:
...the semantical proof is not formalizable in (S) itself. As a corollary we obtain the important theorem that the notion of 'truth' for the system is not definable within (S). The syntactical proof is on the contrary formalizable within (S) and studying carefully this fact we can recognise with Goedel that the consistency of (S) is not provable by means formalizable within (S).((MOSTOWSKI 1952),12)
In conclusion, these results upset almost the whole implicit role of logic and arithmetic in the ''syntactic paradigm'', most of all in his evolution along Leibniz', Cantor's and Hilbert's philosophies. The incompleteness results reveal that the extension of the idea of ''logic'' beyond the first order predicate calculus is untenable, for there Leibniz' reducibility of truth to demonstration is impossible for any possible set of axioms and rules. In addition, the generalisation of Goedel's theorems, substituting the idea of computation to the idea of proof, reveals that logical proofs, in their most general meaning, are no more than particular cases of computation. The same distinction between axioms and rules of inference appear vague, and also the ''deduction tree'' of a formula mirrors the ''derivation tree'' of an equation. Finally, although complete, first order calculus is undecidable. Hence, also the first order logic does not seem to have to play the role that two thousand years of philosophy supposed. Thus logic does not seem to play that special 'syntactic' role in formalising human reason, as a bridge between language and reality, that has been claimed for more than two thousand years.
The 'semantic' rationale for the existence of a privileged special formal calculus named 'logic' could also be grounded in its Tarskian semantics. However, it can be called 'semantics' only in a very ''platonic'' approach, for the codomain of the interpretation is another piece of syntax, i.e. set theory. Moreover, such semantical role (for example, to prove consistency by the existence of models or to define the truth) has been substituted in metamathematics by syntactic techniques (for consistency, the existence of unprovable propositions) or is embedded in paradoxes (for truth, the 'liar'). In general, there is no reason to ascribe to the idea of set some sort of 'primitivity', and also this kind of 'semantics' does not seem to be something more than the 'successor' relation in the 'chain' of formal systems, linked as in fig.3. From many points of view, arithmetic seems, by recursion theory, to be intitled to play the role of the root of the syntactical paradigm, and the very core of the syntactical weltanschauung. But only in a very special way, for its non-finite formalizability sets in the same time arithmetic out of the chain of systems connecting the natural science with reality, from one side, and human reason, from the other one.
The discussion about the structure knowledge had to receive in a purely syntactic approach, in which it is reduced to the idea of representation, is postponed to the fourth report. We could hope that at the first extreme of this 'chain' there could consistently be the real world substantially described by physics. We shall see however in the following that the paradoxical nature of formal thinking will mark its presence also there. And at the opposite extreme of the 'chain' we could hope to find something expressing human reason, probably something very close to the natural language. Could it be, when considering the ancient connection between logic, language and reason, logic or some other formal language (mentalese, language of thoughts)? We have to underline, in the last twenty years, the increasing diffusion of non-standard logic systems to represent human knowledge and natural language. New 'logics' continuously have been proposed to deal with many aspects of reason and language, and many of them show little resemblance with predicate calculus. Not many people advocate today the real possibility of grounding natural language in logic. And few people could endorse the claim of such a grounding in other formal languages.
While leaving these themes to the fourth report, we can suspect that, not only the logic, but the whole hierarchy of formal languages which had to accomplish our science does not seem to have a credible connection neither with natural language nor with the real world. Worse, in this hierarchy of syntactically formalised theories, whenever they had to reduce truth to provability, as necessary for the very idea of formal knowledge, there would be no room for the most important intuitively syntactic theories, namely arithmetic and set theory. And we have to recall how 'poor' were the least conditions for our syntactic formalizations: - the finite alphabet of signs, containing the simplest arithmetic and logical symbols, - few elementary arithmetic operations, - derivation rules reduced substantially to the substitution rule of equals in equals. Also the Aristotelian continuous infinite cannot be captured in any formal system, and the diagonal argument undermines any recursive system. The very idea of cardinality is external to the first order calculus, so that it can be extended with axioms characterising the cardinality of the models for any finite integer and for N , but Loewenheim-Skolem's theorem blocks the formal characterizability of non-denumerable infinities: simply there are not enough formal objects to deal with such infinities, and this cannot be avoid without leaving the very idea of symbolic system. Indeed, in first order logic the coincidence between truth and provability is, according to the proof of Goedel's completeness theorem(KLEENE 1971), also coincident with the validity in the natural numbers domain. The very existence of infinite sets has to be postulated by a specific axiom. So, logic has nothing to say about the number of elements in the universe, and nevertheless it becomes inconsistent in empty domains, for it is always possible to derive (Ex) F(x) from (x) F(x) and this, in an empty domain, is absurd. Thus: which kind of connection could there be between being and sign?