A revolution in logic? (English) Zbl 0891.03001

Hintikka, Jaakko; Sandu, Gabriel

Nord. J. Philos. Log. 1, No. 2, 169-183 (1996).

The title of the paper refers to Independence Friendly (IF) first-order logic and understandings of its relationship with “ordinary” logics. For an underlying fuller exposition the authors refer to J. Hintikka [The principles of mathematics revisited (1996; Zbl 0869.03003)].
IF first-order logic allows a more general (in)dependence between quantifiers in a linear quantifier prefix string than what can be represented with a (one-type) parentheses-indication of quantifier scopes, as in received first-order logic. The authors use a slash notation to indicate quantifier independence. For example, \((\forall x)(\exists y/\forall x) S[x,y]\) means the same thing as \((\exists y)(\forall x) S[x,y]\). But in the “Henkin quantifier”, \((\forall x)(\forall z)(\exists y/\forall z)(\exists u/\forall x) S[x,y,z,u]\), the slash is necessary. Without it, the independence needs, for example, a parallel quantifier prefix. The same slash notation is also applied to propositional connectives. IF first-order logic is essentially the result of adding the slash to the conceptual arsenal of the received first-order logic.
In contrast to its predecessors, IF first-order logic is semantically incomplete: the class of valid IF first-order logic formulas is not recursively enumerable. The set of inconsistent formulas (assuming an extension, because the natural negation in IF first-order logic is not a classical contradictory negation but a strong dual negation) is recursively enumerable.
The authors consider IF first-order logic as a basic first-order quantification logic and look at its semantical incompleteness as the most profoundly revolutionary feature of the new logic. For the discussion, they distinguish between two further kinds of completeness. (a) descriptive completeness: the possible models of an axiom system (description) include all and only intended models; (b) deductive completeness: in an axiom system one can logically prove \(S\) or \(\neg S\) for each sentence \(S\) in the language in question. By way of example, Gödel’s incompleteness theorem establishes deductive incompleteness of elementary arithmetic. This deductive incompleteness implies descriptive incompleteness (nonaxiomatizability) of elementary arithmetic only if the underlying logic is semantically complete – which is the case in Gödel’s incompleteness proof. Hence, the authors argue, the semantical incompleteness of IF first-order logic opens up a possibility that we might be able to formulate descriptively complete axiom systems [utilizing from the outside a logic that is powerful beyond axiomatization] for various nontrivial mathematical theories already on the first-order level without violating Gödel’s incompleteness theorem. By comparison, the authors point out that it is well known that descriptively complete but deductively incomplete axiomatizations of practically all mathematical theories can be formulated in higher-order logic. Comparing, in this respect, IF first-order logic with higher-order logic, the authors argue that the first-order alternative stays clear of some difficulties that arise in the second (concerning the existence of sets or other higher-type entities). [In the reviewer’s opinion there is a price in communicability that has to be payed for keeping the strength of IF logic down on first-order level, whereby for example autonomous “definitions” of truth are admitted. Since tertium non datur does not hold in IF first order logic, there will be truth-value gaps revealing that it is not the whole truth that is “defined”.]
The authors go further and even suggest a change in the generally accepted terminology in saying “that IF first-order logic is ‘formally complete’ but not ‘computable’. To put the same point in different terms, the inevitable incompleteness that is found in logic and in the foundations of mathematics is not a symptom of any intrinsic limitation to what can be done by means of logic or mathematics. It is a limitation to what can be done by means of computers.” [The reviewer would rather understand the last two sentences in saying that the limitations do not refer to logics and mathematics, or to logical and mathematical activities, but to what can be sharply communicated about mathematical and logical results and findings. And we must not forget that this is how we have obtained knowledge of noncomputability, nonformalizability, etc., although our ways of ordering them in degrees (of noncomputability etc.) may be open to contextual choices.]
The friendliness of IF first-order logic to (in)dependencies is further discussed in terms of context-dependencies in arguments against the principle of compositionality, sometimes formulated as an assertion of semantical context-independence. IF first-order logic violates the principle [as do logics in language with descriptions and interpretations as a systemic whole].
The reviewer has found the unconventional ideas of the paper most stimulating, in particular in providing examples relevant for the tension between describability and interpretability (varying one at price of the other) in a general holistic conception of language.

Reviewer: L.Löfgren (Lund)

MSC:

03A05	Philosophical and critical aspects of logic and foundations
03-03	History of mathematical logic and foundations
01A55	History of mathematics in the 19th century

Keywords:

Independence Friendly first-order logic; quantifier independence; semantical incompleteness; descriptive completeness; deductive completeness; context-dependencies; compositionality; describability; interpretability

Citations:

Zbl 0869.03003