We study the complexity of the topological isomorphism relation for various classes of closed subgroups of the group of permutations of the natural numbers. We use the setting of Borel reducibility between equivalence relations on Borel spaces. For profinite, locally compact, and Roelcke precompact groups, we show that the complexity is the same as the one of countable graph isomorphism. For oligomorphic groups, we merely establish this as an upper bound.

In the present paper we prove that the poset of all extensions of the logic defined by a class of matrices whose sets of distinguished values are equationally definable by their algebra reducts is the retract, under a Galois connection, of the poset of all subprevarieties of the prevariety generated by the class of the algebra reducts of the matrices involved. We apply this general result to the problem of finding and studying all extensions of the logic of paradox (viz., the implication-free fragment of any non-classical normal extension of the relevance-mingle logic). In order to solve this problem, we first study the structure of prevarieties of Kleene lattices. Then, we show that the poset of extensions of the logic of paradox forms a four-element chain, all the extensions being finitely many-valued and finitely-axiomatizable logics. There are just two proper consistent extensions of the logic of paradox. The first is the classical logic that is relatively axiomatized by the Modus ponens rule for the material implication. The second extension, being intermediate between the logic of paradox and the classical logic, is the one relatively axiomatized by the Ex Contradictione Quodlibet rule.

Some of the theorems contained in the interesting and incisive paper [*] (D. J. Shoesmith and T. J. Smiley, Deducibility and many-valuedness, this Journal, vol. 36 (1970), pp. 610–622) are strongly connected with some earlier results, especially those presented in the paper of Łoś and Suszko [2]. The lack of appropriate bibliographical references in [*] shows that some results which have been obtained relatively long ago are, unfortunately, not so widely known as one might expect. The main task of this short note is to inform briefly on a few results and problems related to those examined in [*].

This paper points out an error of Parigot's proof of strong normalization of second order classical natural deduction by the CPS-translation, discusses erasing-continuation of the CPS-translation, and corrects that proof by using the notion of augmentations.

Using a dictionary translating a variety of classical and modern covering properties into combinatorial properties of continuous images, we get a simple way to understand the interrelations between these properties in ZFC and in the realm of the trichotomy axiom for upward closed families of sets of natural numbers. While it is now known that the answer to the Hurewicz 1927 problem is positive, it is shown here that semifilter trichotomy implies a negative answer to a slightly stronger form of this problem.

Ordinary equational logic is a connective-free fragment of first-order logic which is concerned with total functions under the relation of ordinary equality. In [AN] (see also [AN1]) and in [Cr] it has been extended in two equivalent ways into a near-equational system of logic for partial functions. The extension given in [Cr] deals with partial functions under two relationships: a relationship of existence-dependent existence and one of existence-dependent Kleene equality. For the language that involves both relationships a set of rules was given that is complete. Those rules in the set that involve only existence-dependent existence turned out to be complete for the sublanguage that involves this relationship only. In the present paper we give a set of rules that is complete for the other sublanguage, namely the language of partial functions under existence-dependent Kleene equality.

This language lacks a certain, often needed, power of expressing existence and fails, in particular, to be an extension of the language that underlies ordinary equational logic. That it possesses a fairly simple complete set of rules is therefore perhaps more of theoretical than of practical interest. The present paper is thus intended to serve as a supplement to [Cr] and, less directly, to [AN]. The subject is further rounded out, and some contrast is provided, by [Rob]. The systems of logic treated there are based on the weaker language in which partial functions are considered under the more basic relation of Kleene equality.

We study some generalized notions of cohesiveness which arise naturally in connection with effective versions of Ramsey's Theorem. An infinite set A of natural numbers is n-cohesive (respectively, n-r-cohesive) if A is almost homogeneous for every computably enumerable (respectively, computable) 2-coloring of the n-element sets of natural numbers. (Thus the 1-cohesive and 1-r-cohesive sets coincide with the cohesive and r-cohesive sets, respectively.) We consider the degrees of unsolvability and arithmetical definability levels of n-cohesive and n-r-cohesive sets. For example, we show that for all n ≥ 2, there exists a n-cohesive set. We improve this result for n = 2 by showing that there is a 2-cohesive set. We show that the n-cohesive and n-r-cohesive degrees together form a linear, non-collapsing hierarchy of degrees for n ≥ 2. In addition, for n ≥ 2 we characterize the jumps of n-cohesive degrees as exactly the degrees ≥ 0(n+1) and also characterize the jumps of the n-r-cohesive degrees.

We try to count the number of countable models M of T with a fixed set Q = Φ(M) of realizations of a type Φ. Also, for stable T, we define an ordinal rank measuring multiplicity of types, with additivity properties similar to those of U-rank.

Let Z2, Z3, and Z4 denote 2nd, 3rd, and 4th order arithmetic, respectively. We let Harrington’s Principle, HP, denote the statement that there is a real x such that every x-admissible ordinal is a cardinal in L. The known proofs of Harrington’s theorem “$Det\left( {{\rm{\Sigma }}_1^1} \right)$ implies 0♯ exists” are done in two steps: first show that $Det\left( {{\rm{\Sigma }}_1^1} \right)$ implies HP, and then show that HP implies 0♯ exists. The first step is provable in Z2. In this paper we show that Z2 + HP is equiconsistent with ZFC and that Z3 + HP is equiconsistent with ZFC + there exists a remarkable cardinal. As a corollary, Z3 + HP does not imply 0♯ exists, whereas Z4 + HP does. We also study strengthenings of Harrington’s Principle over 2nd and 3rd order arithmetic.

Let G be a Polish topological group, let X be a Polish space, let J: G × X → X be a Borel-measurable action of G on X, and let A ⊂ X be a Borel set which is invariant with respect to J, i.e., a Borel set of orbits. The following statement, or various equivalent versions of it, is known as the Topological Vaught's Conjecture.

We say that A contains perfectly many orbits if there is a perfect set P ⊂ A such that no two elements of P are in the same orbit. (Assuming ¬CH, A contains perfectly many orbits iff it contains 2ℵ0 orbits.) The Topological Vaught's Conjecture implies the usual, model theoretic, Vaught's Conjecture for Lω1ω, since the isomorphism classes are the orbits of an action of the group of permutations of ω; we give details in §0. The “Borel” assumption cannot be weakened for either A or J.

Given a Borel-measurable Polish action (G,X,J) and an invariant Borel set B ⊂ X, we say that B is a minimal counterexample if (G,X,J,B) is a counterexample to the Topological Vaught's Conjecture and for every invariant Borel C ⊂ B, either C or B\C contains only countably many orbits. This paper is concerned with counterexamples to the Topological Vaught's Conjecture (of course, there may not be any), and in particular, with minimal counterexamples. First, there is a theorem on the existence of minimal counterexamples. This theorem was known for the model theoretic case (it is due to Harnik and Makkai), and is here generalized to arbitrary Borel-measurable Polish actions. Second, we study the properties of minimal counterexamples. We give two different necessary and sufficient conditions for a counterexample to be minimal, as well as some consequences of minimality. Some of these results are proved assuming determinacy axioms.This second part seems to be new even in the model theoretic case.

We give a new elementary proof of the comparison theorem relating and ; the proof does not use Skolem theories.

By the same method we prove:

a) , for suitable classes of sentences;

b) proves the consistency of , for finite k, and hence is stronger than .

a) and b) answer a question of Feferman and Sieg.

It is shown to be consistent that the reals are covered by ℵ1, meagre sets yet there is a Baire class 1 function which cannot be covered by fewer than ℵ2, continuous functions. A new cardinal invariant is introduced which corresponds to the least number of continuous functions required to cover a given function. This is characterized combinatorially. A forcing notion similar to, but not equivalent to, superperfect forcing is introduced.

Let be the restriction of usual order relation to integers which are primes or squares of primes, and let ⊥ denote the coprimeness predicate. The elementary theory of is undecidable. Now denote by <π the restriction of order to primary numbers. All arithmetical relations restricted to primary numbers are definable in the structure (ℕ; ⊥, <π). Furthermore, the structures (ℕ; ∣, <π) (ℕ; =, ×, <π) and (ℕ; =, +, ×) are interdefinable.

The Uniformly Reflexive Structure was introduced by E. G. Wagner who showed that the theory of such structures generalized much of recursive function theory. In this paper Uniformly Reflexive Structures are constructed as factor algebras of free nonassociative algebras. Wagner's question about the existence of a model with no computable splinter (“successor set”) is answered in the affirmative by the construction of a model whose only computable sets are the finite sets and their complements. Finally, for each countable Boolean algebra R of subsets of a countable set which contains the finite subsets, a model is constructed with R as its family of computable sets.

This paper continues the exposition of a demonstrably consistent foundation for mathematics begun in An extension of basic logic (hereafter referred to as EBL) and in The Heine-Borel theorem in extended basic logic (hereafter referred to as HB). Still earlier papers related to these are A basic logic (referred to as BL) and Representations of calculi (referred to as RC). The main conventions and results of all the above papers will be presupposed in what follows. The numbering of sections and paragraphs will be a continuation of that of EBL and HB.

Given a finitely generated group Γ we study the space Isom(Γ, ) of all actions of Γ by isometries of the rational Urysohn metric space , where Isom (Γ, ) is equipped with the topology it inherits seen as a closed subset of Isom . When Γ is the free group on n generators this space is just Isom , but is in general significantly more complicated. We prove that when Γ is finitely generated Abelian there is a generic point in Isom(Γ, ), i.e., there is a comeagre set of mutually conjugate isometric actions of Γ on .

We study classes of ultrafilters on ω defined by a natural property of the Loeb measure in the Nonstandard Universe corresponding to the ultrafilter. This class, the Property M ultrafilters, is shown to contain all ultrafilters built up by taking iterated products over collections of pairwise nonisomorphic selective ultrafilters. Results on Property M ultrafilters are applied to the construction of extensions of probability measures, and to the study of measurable reductions between ultrafilters.

We establish cut-free left-handed Gentzenizations for a range of major relevant logics from B through to R, all with distribution. B is the basic system of the Routley-Meyer semantics (see [15], pp. 287–300) and R is the logic of relevant implication (see [1], p. 341). Previously, the contractionless logics DW, TW, EW, RW and RWK were Gentzenized in [3], [4] and [5], and also the distributionless logics LBQ, LDWQ, LTWQo, LEWQot, LRWQ, LRWKQ and LRQ in [6] and [7]. This paper provides Gentzenizations for the logics DJ, TJ, T and R, with various levels of contraction, and for the contractionless logic B, which could not be included in [4] using the technique developed there. We also include the Gentzenization of TW in order to compare it with that in [4]. The Gentzenizations that we obtain here for DW and RW are inferior to those already obtained in [4], but they are included for reference when constructing other systems. The logics EW and E present a difficulty for our method and are omitted. For background to the Gentzenization of relevant logics, see [6], and for motivation behind the logics involved, see [6], [1] and [15]. Because of the number of properties that are brought to bear in obtaining these systems, we prefer to consider Gentzenizations for particular logics rather than for arbitrary bunches of axioms.

We formulate and prove (in ZFC) a strong coloring theorem which holds at successors of singular cardinals, and use it to answer several questions concerning Shelah's principle Pr1 (μ+, μ+, μ+, cf (μ)) for singular μ.

In analogy to the definition of the halting problem K, an r.e. set A is called a diagonal iff there is a computable numbering ψ of the class of all partial recursive functions such that A = {i ∈ ω: ψi(i)↓} (in that case we say that A is the diagonal of ψ). This notion has been introduced in [10]. It captures all r.e. sets that can be constructed by diagonalization.

It was shown that any nonrecursive r.e. T-degree contains a diagonal, that for any diagonal A there is an r.e. nonrecursive nondiagonal B ≤TA, and that there are r.e. degrees a such that any r.e. set from a is a diagonal.

In §2 of the present paper we show that the property “A is a diagonal” is elementary lattice theoretic (e.l.t.). This result complements and generalizes previous results of Harrington and Lachlan, respectively. Harrington (see [16, XV. 1]) proved that the property of being the diagonal of some Gödelnumbering (i.e., of being creative) is e.l.t., and Lachlan [12] proved that the property of being a simple diagonal (i.e., of being simple and not hh-simple [10]) is e.l.t.

In §§3 and 4 we study the position of diagonals and nondiagonals inside the lattice of r.e. sets. We concentrate on an important class of nondiagonals, generalizing the maximal and hemimaximal sets: the -maximal sets. Using the results from [6] we are able to classify the -maximal sets that can be obtained as halfs of splittings of hh-simple sets.