We characterize the structure of computably categorical trees of finite height, and prove that our criterion is both necessary and sufficient. Intuitively, the characterization is easiest to express in terms of isomorphisms of (possibly infinite) trees, but in fact it is equivalent to a -condition. We show that all trees which are not computably categorical have computable dimension ω. Finally, we prove that for every n ≥ 1 in ω, there exists a computable tree of finite height which is Σ30-categorical but not Δn3-categorical

In this third and last paper on inner models we consider some of the inherent limitations of the method of using inner models of the type defined in 1.2 for the proof of consistency results for the particular system of set theory under consideration. Roughly speaking this limitation may be described by saying that practically no further consistency results can be obtained by the construction of models satisfying the conditions of theorem 1.5, i.e., conditions 1.31, 1.32, 1.33, 1.51, viz.:

This applies in particular to the ‘complete models’ defined in 1.4. Before going on to a precise statement of these limitations we shall consider now the theorem on which they depend. This is concerned with a particular type of complete model examples of which we call “proper complete models”; they are those complete models which are essentially interior to the universe, those whose classes are sets of the universe constituting a class thereof, i.e., those for which the following proposition is true:

The main theorem of this paper is that the statement that there are no models of this kind can be expressed formally in the same way as the axioms A, B, C and furthermore it can be proved that if the axiom system A, B, C is consistent then so is the system consisting of axioms A, B, C, plus this new hypothesis that there exist no proper complete models. When combined with the axiom ‘V = L’ introduced by Gödel in (1) this new hypothesis yields a system in which any normal complete model which exists has for its universal class V, the universal class of the original system.

In this paper we show that any countable upper semilattice with zero can be embedded as an initial segment of the degrees of unsolvability. This provides a characterization of the order types of the countable initial segments of the degrees since any such initial segment is trivially an initial segment of a countable upper semilattice. Let a segment S of the degrees be a set of degrees such that, if a, b Є S and a < c < b, then c Є S. One may readily observe that our result also characterizes the order types of all countable segments of the degrees of unsolvability.

We derive a Mal'cev condition for congruence meet-semidistributivity and then use it to prove two theorems. Theorem A: if a variety in a finite language is congruence meet-semidistributive and residually less than some finite cardinal, then it is finitely based. Theorem B: there is an algorithm which, given m < ω and a finite algebra in a finite language, determines whether the variety generated by the algebra is congruence meet-semidistributive and residually less than m.

We prove that the problem of determining the minimum propositional proof length is NP-hard to approximate within a factor of . These results are very robust in that they hold for almost all natural proof systems, including: Frege systems, extended Frege systems, resolution. Horn resolution, the polynomial calculus, the sequent calculus, the cut-free sequent calculus, as well as the polynomial calculus. Our hardness of approximation results usually apply to proof length measured either by number of symbols or by number of inferences, for tree-like or dag-like proofs. We introduce the Monotone Minimum (Circuit) Satisfying Assignment problem and reduce it to the problems of approximation of the length of proofs.

This work results from an attempt to give the vague notion of relevance a concrete semantical interpretation. The idea is that propositions may be divided into different “domains of relevance”. Each “domain” has its own “T” and “F” values, and propositions “belonging” to one domain can never entail propositions “belonging” to another, unconnected one.

The semantics we have developed were found to correspond to an already known system, which we call here RMI⥲. Its axioms are the implication-negation axioms of the system RM ([1, Chapter 5]). However, as Meyer has shown, RM is not a conservative extension of RMI⥲, since RMI⥲ has the sharing-of-variables property ([5], and [1, pp. 148–149[), which the implication-negation fragment of RM has not.

RMI⥲ has four advantages in comparison to its more famous sister R⥲ (the pure intentional fragment of the system R; see [1]):

a) It has a very natural (from a relevance point of view) many-valued semantics, the simple form of which we describe here.

b) RMI⥲, ⊢ A1 → [A2 → (… → (An → A) …)] iff there is a proof of A from the set {A1, …, An} that actually uses all the members of this set. In R⥲, this holds only if we talk about “sequences” instead of “sets”. This is somewhat less intuitive (see [1, pp. 394–395]).

c) RMI⥲ is a maximal “natural” relevance logic, in the sense that every proper extension of it limits the number of “domains of relevance” (§III).

We consider the problem of finding and classifying representations in algebraic logic. This is approached by letting two players build a representation using a game. Homogeneous and universal representations are characterized according to the outcome of certain games. The Lyndon conditions defining representable relation algebras (for the finite case) and a similar schema for cylindric algebras are derived. Finte relation algebras with homogeneous representations are characterized by first order formulas. Equivalence games are defined, and are used to establish whether an algebra is ω-categorical. We have a simple proof that the perfect extension of a representable relation algebra is completely representable.

An important open problem from algebraic logic is addressed by devising another two-player game, and using it to derive equational axiomatisations for the classes of all representable relation algebras and representable cylindric algebras.

Other instances of this approach are looked at, and include the step by step method.

The notion of a “partition relation”, as it has been studied in the context of set theory for the past several years, was inspired by the following theorem of F. P. Ramsey [14]:

Theorem 0.1. Let n be a positive integer and let {A, B} be a partition of those subsets of the nonnegative integers containing exactly n elements. Then there exists an infinite subset x of the nonnegative integers all of whose n-element subsets are contained in only one of A or B. (Any such set x is said to be “homogeneous” for the partition.)

We have come to believe that propositional modal logic (with the usual relational semantics) must be understood as a rather strong fragment of classical second-order predicate logic. (The interpretation of propositional modal logic in second-order predicate logic is well known; see e.g. [2, §1].) “Strong” refers of course to the expressive power of the languages, not to the deductive power of formal systems. By “rather strong” we mean sufficiently strong that theorems about first-order logic which fail for second-order logic usually fail even for propositional modal logic. Some evidence for this belief is contained in [2] and [3]. In the former is exhibited a finitely axiomatized consistent tense logic having no relational models, and the latter presents a finitely axiomatized modal logic between T and S4, such that □p → □2p is valid in all relational models of the logic but is not a thesis of the logic. The result of [2] is strong evidence that bimodal logic is essentially second-order, but that of [3] does not eliminate the possibility that unimodal logic only appears to be incomplete because we have not adopted sufficiently powerful rules of inference. In the present paper we present stronger evidence of the essentially second-order nature of unimodal logic.

We present a formal theory of propositions and combinator terms, and in this theory we give an interpretation of Martin-Löf's type theory. The construction of the interpretation is inspired by the semantics for type theory, but it can also be viewed as a formalized realizability interpretation.

We consider structural completeness in modal logics. The main result is the necessary and sufficient condition for modal logics over K4 to be hereditarily structurally complete: a modal logic λ is hereditarily structurally complete iff λ is not included in any logic from the list of twenty special tabular logics. Hence there are exactly twenty maximal structurally incomplete modal logics above K4 and they are all tabular.

In 1984. Danecki proved that satisfiability in IPDL, i.e., Propositional Dynamic Logic (PDL) extended with an intersection operator on programs, is decidabie in deterministic double exponential time. Since then, the exact complexity of IPDL has remained an open problem: the best known lower bound was the ExpTime one stemming from plain PDL until, in 2004. the first author established ExpSpace-hardness. In this paper, we finally close the gap and prove that IPDL is hard for 2-ExpTime. thus 2-ExpTime-complete. We then sharpen our lower bound, showing that it even applies to IPDL without the test operator interpreted on tree structures.

The basic setting of nonstandard analysis consists of a set-theoretical structure together with a map * from into another structure * of the same sort. The function * is taken to be an elementary embedding (in an appropriate sense) and is generally assumed to make * into an enlargement of [13]. The structures and * may be type-hierarchies as in [11] and [13] or they may be cumulative structures with ω levels as in [14]. The assumption that * is an enlargement of has been found to be the weakest hypothesis which allows for the familiar applications of nonstandard analysis in calculus, elementary topology, etc. Indeed, practice has shown that a smooth and useful theory can be achieved only by assuming also that * has some stronger properties such as the saturation properties first introduced in nonstandard analysis by Luxemburg [11].

This paper concerns an entirely new family of properties, stronger than the saturation properties. For each cardinal number κ, * satisfies the κ-isomorphism property (as an enlargement of ) if the following condition holds:

For each first order language L with fewer than κ nonlogical symbols, if and are elementarily equivalent structures for L whose domains, relations and functions are all internal (relative to * and ), then and are isomorphic.

The main purpose of this note is to prove (theorem 11, § 5) that, in any interpretation of the formalisation of Aristotelian syllogistic given by Łukasiewicz [4], it is always possible to associate with each element a a non-null sub-class φ(a) of some ‘universal’ class V in such a way that ‘Aab’ (all a are b), ‘Iab’ (some a are b) are equivalent respectively to ‘φ(a) is contained in φ(b)’, ‘φ(a) has a non-null intersection with φ(b)’. Similarly (theorem 6, §4) we show that in Wedberg's system [14] with primitives ‘Aab’, ‘a’ (not a), it is possible to find a mapping a → φ(a) as above such that ‘Aab’ is equivalent to ‘φ(a) is contained in φ(b)’ and φ(a‘ is equal to φ(a)’, the complement of φ(a) with respect to V. Thus, if we make the preliminary step of identifying elements a, b such that Aab and Aba both hold (i.e. taking equivalence classes with respect to the relation Aab & Aba), we are left with essentially only one kind of interpretation for these systems, namely the ‘normal’ interpretation by classes. Slupecki [11], [12] has proved that Łukasiewicz's system is a complete and decidable theory of the relations of inclusion and intersection of non-null classes, and Wedberg [14] has proved that his system is a complete and decidable theory of the relation of inclusion and the operation of complementation for nonnull, non-universal classes. Using the above-mentioned embedding theorem, we are able to obtain (theorems 9, 6, §§ 5, 4) very simple proofs of these results.

A fundamental notion in a large part of mathematics is the notion of equicardinality. The language with Härtig quantifier is, roughly speaking, a first-order language in which the notion of equicardinality is expressible. Thus this language, denoted by LI, is in some sense very natural and has in consequence special interest. Properties of LI are studied in many papers. In [BF, Chapter VI] there is a short survey of some known results about LI. We feel that a more extensive exposition of these results is needed.

The aim of this paper is to give an overview of the present knowledge about the language LI and list a selection of open problems concerning it.

After the Introduction (§1), in §§2 and 3 we give the fundamental results about LI. In §4 the known model-theoretic properties are discussed. The next section is devoted to properties of mathematical theories in LI. In §6 the spectra of sentences of LI are discussed, and §7 is devoted to properties of LI which depend on set-theoretic assumptions. The paper finishes with a list of open problem and an extensive bibliography. The bibliography contains not only papers we refer to but also all papers known to us containing results about the language with Härtig quantifier.

Contents. §1. Introduction. §2. Preliminaries. §3. Basic results. §4. Model-theoretic properties of LI. §5. Decidability of theories with I. §6. Spectra of LI-sentences. §7. Independence results. §8. What is not yet known about LI. Bibliography.

It is well-known that every involution in a logical or mathematical system gives rise to a theory of duality; for example, negation in the sentential calculus and predicate calculus, complementation in the calculus of classes, complementation and conversion in the calculus of relations, etc. The purpose of this note is to call attention to the fact that every involution in a logical or mathematical system gives rise to a theory of quaternality and that the square of quaternality, of which the classical squares of opposition are special cases, provides a diagrammatic representation for much of the theory of quaternality. For the sake of definiteness we expose the theory of quaternality in the context of the lower predicate calculus.

Let ϕ and ψ be formulas of the lower predicate calculus. The constants {T and F} {∧ and ∨} {→ and ⇷} {← and ⇸}{↔ and ⇹} {↑ and ↓} {∧ (all) and ∨ (some)} are dual. The constant ~ is self-dual. The negational of ϕ, denoted ϕN, is the formula obtained from ϕ by interchanging negated and unnegated variables (that is, sentence variables and predicate variables) and by interchanging dual constants. The contradual of ϕ, denoted ϕC, is the formula obtained from ϕ by interchanging negated and unnegated variables. The dual of ϕ, denoted ϕD, is the formula obtained from ϕ by interchanging dual constants. The four formulas ϕ, ϕN, ϕC, ϕD, are quaternals of each other.

It is consistent that for many cardinals λ there is a family of at least λ+ unbounded subsets of λ which have uniformization properties. In particular if it is consistent that a supercompact cardinal exists, then it is consistent that ℵω has such a family. We have applications to point set topology, Whitehead groups and reconstructing separable abelian p-groups from their socles.

We present two finitely axiomatized modal propositional logics, one between T and S4 and the other an extension of S4, which are incomplete with respect to the neighbourhood or Scott-Montague semantics.

Throughout this paper we are referring to logics which contain all the classical connectives and only one modal connective □ (unary), no propositional constants, all classical tautologies, and which are closed under the rules of modus ponens (MP), substitution, and the rule RE (from A ↔ B infer αA ↔ □B). Such logics are called classical by Segerberg [6]. Classical logics which contain the formula □p ∧ □q → □(p ∧ q) (denoted by K) and its “converse,” □{p ∧ q)→ □p ∧ □q (denoted by R) are called regular; regular logics which are closed under the rule of necessitation, RN (from A infer □A), are called normal. The logics that we are particularly concerned with are all normal, although some of our results will be true for all regular or all classical logics. It is well known that K and R and closure under RN imply closure under RE and also that normal logics are also those logics closed under RN and containing □{p → q) → {□p → □q).

We analyse here the monadic theory of the rational order, the monadic theory of the real line with quantification over “small” subsets and models of these theories. We prove that the results are in some sense the best possible.