This short article presents an algorithm for bracket abstraction [1] which avoids a combinatorial explosion in the size of the resulting expression when applied repeatedly for abstraction in a series of variables. It differs from a previous solution [2] in introducing only a finite number of additional combinators and in not requiring that all the variables to be abstracted be treated together in a single operation.

All structures to be considered here have universe ω, and all languages come equipped with Gödel numberings. If is a structure, then D(), the open diagram of , can be thought of as a subset of ω, and it makes sense to talk about the Turing degree deg(D()). This depends on the presentation as well as the isomorphism type of .

For example, consider the ordering = (ω, <). For any B ⊆ ω, it is possible to code B in a copy of as follows: Let π be the permutation of ω such that for each n ∈ ω, π leaves 2n and 2n + 1 fixed if n ∈ B and switches 2n with 2n + 1 if n ∉ B. Let be the copy of such that ≃π. Then n ∈ B iff the sentence 2n < 2n + 1 is in D(). In §4, this idea will be used to show that for any structure that is not completely trivial, {deg(D()): ≃ } is closed upwards.

It would be satisfying to have a way of assigning Turing degrees to structures such that the degree assigned to a given structure measured the recursion-theoretic complexity of the isomorphism type and was independent of the presentation. Jockusch suggested the following.

In the last few decades many formal systems of fuzzy logics have been developed. Since the main differences between fuzzy and classical logics lie at the propositional level, the fuzzy predicate logics have developed more slowly (compared to the propositional ones). In this text we aim to promote interest in fuzzy predicate logics by contributing to the model theory of fuzzy predicate logics. First, we generalize the completeness theorem, then we use it to get results on conservative extensions of theories and on witnessed models.

In this paper we introduce canonical extensions of partially ordered sets and monotone maps and a corresponding discrete duality. We then use these to give a uniform treatment of completeness of relational semantics for various substructural logics with implication as the residual(s) of fusion.

We consider small-weight Cutting Planes (CP*) proofs; that is, Cutting Planes (CP) proofs with coefficients up to Poly(n). We use the well known lower bounds for monotone complexity to prove an exponential lower bound for the length of CP* proofs, for a family of tautologies based on the clique function. Because Resolution is a special case of small-weight CP, our method also gives a new and simpler exponential lower bound for Resolution.

We also prove the following two theorems: (1) Tree-like CP* proofs cannot polynomially simulate non-tree-like CP* proofs. (2) Tree-like CP* proofs and Bounded-depth-Frege proofs cannot polynomially simulate each other.

Our proofs also work for some generalizations of the CP* proof system. In particular, they work for CP* with a deduction rule, and also for any proof system that allows any formula with small communication complexity, and any set of sound rules of inference.

The eventual purpose of this paper is to provide certain specific representations of ordinals and develop their basic properties as needed for the proofs of the results announced in [3]. Since the choice of these representations is really intelligible only if the general principles involved are made explicit, we devote the first half of this paper (§§1 and 2) to such questions. The entire treatment is self-contained.

Classical logic is not adequate to face the essential vagueness of human reasoning, which is approximate rather than precise in nature. The logical treatment of the concepts of vagueness and approximation is of increasing importance in artificial intelligence and related research. Consequently, many logicians have proposed different systems of many-valued logic as a formalization of approximate reasoning (see, for example, Goguen [G], Gerla and Tortora [GT], Novak [No], Pavelka [P], and Takeuti and Titani [TT]). As far as we know, all the proposals are obtained by extending the range of truth values of propositions. In these logical systems reasoning is still exact and to make a conclusion the antecedent clause of its rule must match its premise exactly. In addition. Wang [W] pointed out: “If we compare calculation with proving,... Procedures of calculation... can be made so by fairly well-developed methods of approximation; whereas... we do not have a clear conception of approximate methods in theorem proving.... The concept of approximate proofs, though undeniably of another kind than approximations in numerical calculations, is not incapable of more exact formulation in terms of, say, sketches of and gradual improvements toward a correct proof” (see pp, 224–225). As far as the author is aware, however, no attempts have been made to give a conception of approximate methods in theorem proving.

The purpose of this paper is. unlike all the previous proposals, to develop a propositional calculus, a predicate calculus in which the truth values of propositions are still true or false exactly and in which the reasoning may be approximate and allow the antecedent clause of a rule to match its premise only approximately. In a forthcoming paper we shall establish set theory, based on the logic introduced here, in which there are ∣L∣ binary predicates ∈λ, λ ∈ L such that R(∈, ∈λ) = λ where ∈ stands for ∈1 and 1 is the greatest element in L, and x ∈λy is interpreted as that x belongs to y in the degree of λ, and relate it to intuitionistic fuzzy set theory of Takeuti and Titani [TT] and intuitionistic modal set theory of Lano [L]. In another forthcoming paper we shall introduce the resolution principle under approximate match and illustrate its applications in production systems of artificial intelligence.

The importance of the logical ‘generalized quantifiers’ (Mostowski [1957]) for the semantics of natural language was brought out clearly in Barwise & Cooper [1981]. Basically, the idea is that a quantifier phrase QA (such as “all women”, “most children”, “no men”) refers to a set of sets of individuals, viz. those B for which (QA)B holds. Thus, e.g., given a fixed model with universe E,

where ⟦A⟧ is the set of individuals forming the extension of the predicate “A” in the model. This point of view permits an elegant and uniform semantic treatment of the subject-predicate form that pervades natural language.

Such denotations of quantifier phrases exhibit familiar mathematical structures. Thus, for instance, all A produces filters, and no A produces ideals. The denotation of most A is neither; but it is still monotone, in the sense of being closed under supersets. Mere closure under subsets occurs too; witness a quantifier phrase like few A. These mathematical structures are at present being used in organizing linguistic observations and formulating hypotheses about them. In addition to the already mentioned paper of Barwise & Cooper, an interesting example is Zwarts [1981], containing applications to the phenomena of “negative polarity” and “conjunction reduction”. In the course of the latter investigation, several methodological issues of a wider logical interest arose, and these have inspired the present paper.

In order to present these issues, let us shift the above perspective, placing the emphasis on quantifier expressions per se (“all”, “most”, “no”, “some”, etcetera), viewed as denoting relations Q between sets of individuals.

Martin [12] has shown that the determinacy of analytic games is a consequence of the existence of sharps. Our main result is the converse of this:

Theorem. If analytic games are determined, then x2 exists for all reals x.

This theorem answers question 80 of Friedman [5]. We actually obtain a somewhat sharper result; see Theorem 4.1. Martin had previously deduced the existence of sharps from 3 − Π11-determinacy (where α − Π11 is the αth level of the difference hierarchy based on − Π11 see [1]). Martin has also shown that the existence of sharps implies < ω2 − Π11-determinacy.

Our method also produces the following:

Theorem. If all analytic, non-Borel sets of reals are Borel isomorphic, then x* exists for all reals x.

The converse to this theorem had been previously proven by Steel [7], [18].

We owe a debt of gratitude to Ramez Sami and John Steel, some of whose ideas form basic components in the proofs of our results.

For the various notation, definitions and theorems which we will assume throughout this paper, the reader should consult [3, §§5, 17], [8], [13] and [14, Chapter 16].

Throughout this paper we will concern ourselves only with methods for obtaining 0# (rather than x# for all reals x). By relativizing our arguments to each real x, one can produce x2.

A denumerable structure is said to be recursive iff its universe is a recursive subset of the natural numbers and its relations and operations are recursive. For example, the standard model of number theory is recursive. A structure is said to be recursively presentable iff it is isomorphic to a recursive structure. For example, a Boolean algebra generated by ℵ0 free generators is easily seen to be recursively presentable. (For basic facts concerning Boolean algebras, the reader is referred to R. Sikorski [9] and A. Tarski and A. Mostowski [10].)

A Turing Machine (TM) is an abstract, synchronous, deterministic computer with a finite number of internal states. It operates on the set of infinite words, or tapes, over some finite alphabet, scanning exactly one symbol of the tape at a time. (Only a 2-symbol alphabet, consisting of “0” and “|”, will be considered here, and the scanned symbol of a tape will be distinguished by an underscore.) depending upon its internal state and the symbol under scan, it can perform one or more of the following operations: replace the scanned symbol with a new symbol, focus its attention on an adjacent square, and transfer control to a new state.

The proposition that a decreasing sequence of ordinals necessarily terminates has been given a new, and perhaps unexpected, importance by the rôle which it plays in Gentzen's proof of the freedom from contradiction of the “reine Zahlentheorie.” Gödel's construction of non-demonstrable propositions and the establishment of the impossibility of a proof of freedom from contradiction, within the framework of a certain type of formal system, showed that a proof of freedom from contradiction could be found only by transcending the axioms and proof processes of that formal system. Gentzen's proof succeeds by utilising transfinite induction to prove that certain sequences of reduction processes, enumerated by ordinals less than ε (the first ordinal to satisfy ε = ὡ) are finite. Were it possible to prove the restricted ordinal theorem, that a descending sequence of ordinals, less than ε, is finite, in Gentzen's “reine Zahlentheorie,” then it would be possible to determine a contradiction in that number system. In his paper, Gentzen proves the theorem of transfinite induction, which he requires, by an intuitive argument. There is also a method of reducing transfinite induction, for ordinals less than ε, to a number-theoretic principle given by Hilbert and Bernays, and a similar method by Ackermann. None of these proofs of transfinite induction is finitist.

The “implicational paradoxes” are treated by most contemporary logicians somewhat as follows:

“The two-valued prepositional calculus sanctions as valid many of the obvious and satisfactory inferences which we recognize intuitively as valid, such as

(A→.B→C)→.A→B→.A→C,2

and

A→B→.B→C→.A→C;

it consequently suggests itself as a candidate for a formal analysis of implication.

H. Scholz [11] defined the spectrum of a formula φ of first-order logic with equality to be the set of all natural numbers n for which φ has a model of cardinality n. He then asked for a characterization of spectra. Only partial progress has been made. Computational aspects of this problem have been worked on by Gunter Asser [1], A. Mostowski [9], and J. H. Bennett [2]. It is known that spectra include the Grzegorczyk class and are properly included in . However, no progress has been made toward establishing whether spectra properly include , or whether spectra are closed under complementation.

A possible connection with automata theory arises from the fact that contains just those sets which are accepted by deterministic linear-bounded Turing machines (Ritchie [10]). Another resemblance lies in the fact that the same two problems (closure under complement, and proper inclusion of ) have remained open for the class of context sensitive languages for several years.

In this paper we show that these similarities are not accidental—that spectra and context sensitive languages are closely related, and that their open questions are merely special cases of a family of open questions which relate to the difference (if any) between deterministic and nondeterministic time or space bounded Turing machines.

In particular we show that spectra are just those sets which are acceptable by nondeterministic Turing machines in time 2cx, where c is constant and x is the length of the input. Combining this result with results of Bennett [2], Ritchie [10], Kuroda [7], and Cook [3], we obtain the “hierarchy” of classes of sets shown in Figure 1. It is of interest to note that in all of these cases the amount of unrestricted read/write memory appears to be too small to allow diagonalization within the larger classes.

In previous papers we developed two functional calculi of first order based on strict implication which we called S2 and S4. In the present paper, these systems will be extended to include a functional calculus of second order with the purpose of introducing the relation of identity of individuals.

Primitive symbols. ̂ {the abstraction operator, the blank space to be replaced by an appropriate variable}.

The main aims of this paper are firstly to present new and simpler postulate sets for certain well-known systems of modal logic, and secondly, in the light of these results, to suggest some new or newly formulated calculi, capable of interpretation as systems of epistemic or deontic modalities. The symbolism throughout is that of [9] (see especially Part III, Chapter I). In what follows, by a Lewis modal system is meant a system which (i) contains the full classical propositional calculus, (ii) is contained in the Lewis system S5, (iii) admits of the substitutability of tautologous equivalents, (iv) possesses as theses the four formulae:

We shall also say that a system Σ1 is stricter than a system Σ2, if both are Lewis modal systems and Σ1 is contained in Σ2 but Σ2 is not contained in Σ1; and we shall call Σ1absolutely strict, if it possesses an infinity of irreducible modalities. Thus, the five systems of Lewis in [5], S1, S2, S3, S4, and S5, are all Lewis modal systems by this definition; they are in an order of decreasing strictness from S1 to S5; and S1 and S2 alone are absolutely strict.

In recent years much effort has gone into the study of languages which strengthen the classical first-order predicate calculus in various ways. This effort has been motivated by the desire to find a language which is

(I) strong enough to express interesting properties not expressible by the classical language, but

(II) still simple enough to yield interesting general results. Languages investigated include second-order logic, weak second-order logic, ω-logic, languages with generalized quantifiers, and infinitary logic.

Recursive model theory is supposed to be the study of the effectiveness of constructions and theorems in model theory. This often involves getting “effective” versions of various classical model-theoretic notions. The traditional way of doing this is to restrict attention to recursive models, and recursive isomorphisms between them, etc. Thus for example the following definition appears in the literature (in [3] and [1]).

Definition. Given a recursive model A and an n Є ω, a subset R ⊆ An is called intrinsically r.e. provided that for every recursive model B ≈ A, the isomorphic image in B of R is an r.e. subset of Bn.

It is clear that if R is definable by a (recursive, infinitary) Σ10 formula (with finitely many parameters from A), then R is intrinsically r.e. It seems natural for the converse to be true. Indeed, provided that (A, R) is sufficiently “regular” in a sense made precise in a theorem of Ash and Nerode (see [3]), the converse is true. However, if we drop the (rather strong) regularity conditions, there exist “pathological” examples of intrinsically r.e. relations which are not definable by a Σ10 formula (see [7]).

In this paper, we suggest a rather different approach to studying the effectiveness of model theory, an approach we have dubbed “effective model theory”. The basic idea is to allow arbitrary nonrecursive models, but to require all notions to be relativized to the complexity of the models involved. (Much the same notion has been used in [2] under the name “relatively recursive model theory”.) Thus for example we have the following effective model theory version of the property of being intrinsically r.e.

In [1] Quine has presented a method for finding the simplest disjunctive normal forms of truth functions. Like the tabular methods of [2] and [3], Quine's method requires expansion of a formula into developed normal form as a preliminary step. This aspect of his method to a certain extent defeats one of the purposes of a mechanical method, which is to secure simplest forms in complicated cases (perhaps by using a digital computer) [4]. In the present paper we develop a method for both disjunctive and conjunctive normal truth functions which is in some respects similar to Quine's but which does not involve prior expansion of a formula into developed normal form. Familiarity with [1] is presupposed.

We use the notations and conventions of [1] with the following exceptions and additions. ‘Φ’ names any formula, ‘Ψ’ any conjunction of literals, and ‘χ’ any disjunction of literals. Any disjunction of conjunctions of literals is a disjunctive normal formula and is designated by ‘ψ’; any conjunction of disjunctions of literals is a conjunctive normal formula and is designated by ‘X’. Note that we do not make use of Quine's notion of fundamental formulas. A formula Ψ occurring in a disjunctive normal formula ψ, provided it is a disjunct of ψ, is a clause; similarly for χ. We use ‘≠” for logical equivalence of formulas and ‘=’ for identity of formulas to within the order of literals in clauses and the order of clauses in normal formulas.