We prove several trichotomy results for ideals of compact sets. Typically, we show that a “sufficiently rich” universally Baire ideal is either Π30-hard. or Σ30-hard. or else a σ-ideal.

If one wants to compute with infinite objects like real numbers or data streams, continuity is a necessary requirement: better and better (finite) approximations of the input are transformed into better and better (finite) approximations of the output. In case the objects are constructively generated, they can be represented by a finite description of the generating procedure. By effectively transforming such descriptions for the generation of the input (respectively, their codes) into (the code of) a description for the generation of the output another type of computable operation is obtained. Such operations are also called effective. The relationship of both classes of operations has always been a question of great interest.

In this paper the setting is extended to the case of multifunctions. Various ways of coding (indexing) sets are discussed and their relationship is investigated. Moreover, effective versions of several continuity notions for multifunctions are introduced. For each of these notions an indexing system for sets is exhibited so that the multifunctions that are effective with respect to this indexing system are exactly the multifunction which are effectively continuous with respect to the continuity notion under consideration. Mostly, in addition to being effective the multifunctions need also possess certain witnessing functions. Important special cases are discussed where such witnessing functions always exist.

We prove that for a finitely generated infinite nilpotent group G with structure (G, ·, …), the connected component G*0 of a sufficiently saturated extension G* of G exists and equals

We construct an expansion of ℤ by a predicate (ℤ, +, P) such that the type-connected component is strictly smaller than ℤ*0. We generalize this to finitely generated virtually solvable groups. As a corollary of our construction we obtain an optimality result for the van der Waerden theorem for finite partitions of groups.

We define a class of finite state automata acting on transfinite sequences, and use these automata to prove that no singular cardinal can be defined by a monadic second order formula over the ordinals.

A λ-theory T is a consistent set of equations between λ-terms closed under derivability. The degree of T is the degree of the set of Gödel numbers of its elements. is the λ-theory axiomatized by the set {M = N∣ M, N unsolvable}. A λ-theory is sensible iff T ⊃ ; for a motivation see [6] and [4].

In §1 it is proved that the theory is Σ20-complete. We present Wadsworth's proof that its unique maximal consistent extension * (= Th(D∞)) is Π20-complete. In §2 it is proved that η (= λη-calculus + ) is not closed under the ω-rule (see [1]). In §3 arguments are given to conjecture that is Π11-complete. This is done by representing recursive sets of sequence numbers as λ-terms and by connecting wellfoundedness of trees with provability in ω. In §4 an infinite set of equations independent over η will be constructed. From this it follows that there are 2ℵ0 sensible theories T such that and 2ℵ0 sensible hard models of arbitrarily high degrees. In §5 some nonprovability results needed in §§1 and 2 are established. For this purpose one uses the theory η extended with a reduction relation for which the Church–Rosser theorem holds. The concept of Gross reduction is used in order to show that certain terms have no common reduct.

Evidence is given that implication (and its special case, negation) carry the logical strength of a system of formal logic. This is done by proving normalization and cut elimination for a system based on combinatory logic or λ-calculus with logical constants for and, or, all, and exists, but with none for either implication or negation. The proof is strictly finitary, showing that this system is very weak. The results can be extended to a “classical” version of the system. They can also be extended to a system with a restricted set of rules for implication: the result is a system of intuitionistic higher-order BCK logic with unrestricted comprehension and without restriction on the rules for disjunction elimination and existential elimination. The result does not extend to the classical version of the BCK logic.

In Chapter X of The Structure of appearance the concept of linear array is given in terms of a two-place predicate “M” for matching. Also given in terms of “M” is the two-place predicate “B” for besideness. It is unnecessary to discuss here the formal definitions, since Goodman has proved that they are adequate to describe our presystematic ideas of linear array and besideness. Thus, we shall be concerned with a finite collection of elements with an assigned order satisfying:

This order is not uniquely defined by the relation M; either of the two end points may be taken as the ‘first.’ We shall represent the order in diagrams by the convention that x is to the left of y if x < y. For x ≠ y, we shall define S(x, y), the distance between x and y, as one more than the number of elements strictly between them, in the order <; also, S(x, x) = 0. Thus S(x, y) = 1 if and only if x is beside y. The order is connected with the reflexive and symmetric matching relation M by the conditions

(2) Bx, y ⊃ Mx, y,

(3) Mx, y▪x ≤; u ≤ ν ≤ y▪ ⊃ ▪Mu, ν.

Condition (3) is what Goodman calls the weak mapping rule. All arrays considered here must satisfy (3). To avoid trivial cases, we shall assume that not all elements match. There is a strong mapping rule,

(4) Mx, y▪ ∼Mu, ν▪ ▪ ▪S(x, y) < S(u, ν),

which it is desirable, but not necessary, for arrays to satisfy. An array which does satisfy (4) is called regular.

The concept of elementary epimorphism is introduced. Inverse systems of such maps are considered, and a dual of the elementary chain lemma is found (Cor. 4.2). The same is done for pure epimorphisms (Cor. 4.3 and 4.4). Finally, this is applied to certain inverse limits of flat modules (Thm. 6.4) and certain inverse limits of absolutely pure modules (Cor. 6.3).

This paper studies the expressive power that an extra first order quantifier adds to a fragment of monadic second order logic, extending the toolkit of Janin and Marcinkowski [JM01].

We introduce an operation existsn (S) on properties S that says “there are n components having S”. We use this operation to show that under natural strictness conditions, adding a first order quantifier word u to the beginning of a prefix class V increases the expressive power monotonically in u. As a corollary, if the first order quantifiers are not already absorbed in V, then both the quantifier alternation hierarchy and the existential quantifier hierarchy in the positive first order closure of V are strict.

We generalize and simplify methods from Marcinkowski [Mar99] to uncover limitations of the expressive power of an additional first order quantifier, and show that for a wide class of properties S, S cannot belong to the positive first order closure of a monadic prefix class W unless it already belongs to W.

We introduce another operation alt(S) on properties which has the same relationship with the Circuit Value Problem as reach(S) (defined in [JM01]) has with the Directed Reachability Problem. We use alt(S) to show that Πn ⊈ FO(Σn), Σn ⊈ FO(∆n). and ∆n+1 ⊈ FOB(Σn), solving some open problems raised in [Mat98].

Symmetic combinatory logic with the symmetric analogue of a combinatorially complete base (in the form of symmetric λ-calculus) is known to lack the Church-Rosser property. We prove a much stronger theorem that no symmetric combinatory logic that contains at least two proper symmetric combinatory has the Church-Rosser property. Although the statement of the result looks similar to an earlier one concerning dual combinatory logic, the proof is different because symmetric combinators may form redexes in both left and right associated terms. Perhaps surprisingly, we are also able to show that certain symmetric combinatory logics that include just one particular constant are not confluent. This result (beyond other differences) clearly sets apart symmetric combinatory logic from dual combinatory logic, since all dual combinatory systems with a single combinator or a single dual combinator are Church-Rosser. Lastly, we prove that a symmetric combinatory logic that contains the fixed point and the one-place identity combinator has the Church-Rosser property.

Let Pr be Presburger's arithmetic, i.e., the complete theory of the structure (ω, +). Lipshitz and Nadel showed in [4] that a countable model of Pr is recursively saturated iff it can be expanded to a model of Peano arithmetic, PA. As a starting point for an introductory discussion, let us mention one more fact about countable recursively saturated models of Pr. If is such a model then the following is readily seen (as explained also in §1):

Any two countable recursively saturated elementary endextensions of are isomorphic.

If we drop “countable” from the assumption of this statement, we can still say that the two models are ∞ω-equivalent. Must they be isomorphic if both have cardinality ℵ1? Certainly not, since one of the models can be ω 1-like while the other is not. Once we realized this much, let us concentrate on ω 1-like structures. We prove in §3:

Theorem. Any countable recursively saturated model of Pr has isomorphism types of ω 1-like recursively saturated elementary endextensions. Only one of these is the isomorphism type of a structure that can be expanded to a model of PA.

The key technical result is proven in §2. It says that an as above has precisely two countable recursively saturated elementary endextensions which are nonisomorphic over .