A relational structure is called weakly atomic-compact if and only if every set Σ of atomic formulas (taken from the first-order language of the similarity type of augmented by a possibly uncountable set of additional variables as “unknowns”) is satisfiable in whenever every finite subset of Σ is so satisfiable. This notion (as well as some related ones which will be mentioned in §4) was introduced by J. Mycielski as a generalization to model theory of I. Kaplansky's notion of an algebraically compact Abelian group (cf. [5], [7], [1], [8]).

Computability theory is used to evaluate the complexity of classifying various kinds of Lebesgue spaces and associated isometric isomorphism problems.

We generalize Specker's theorem on typical ambiguity, that NF and TST + Ambiguity have the same stratified consequences, to the subschemes Amb(Γ) of ambiguity restricted to classes of sentences Γ with certain natural closure conditions.

Let ω be the nonnegative integers. G. E. Sacks once asked whether there exists an infinite X ⊆ ω such that, for all Y ⊆ X, ω1Yω1 where ω1 is the first nonrecursive ordinal. In this note we negatively answer this question by giving a simple proof that for every infinite set X ⊆ ω there exists Y ⊆ X such that the first recursively inaccessible ordinal. This is accomplished by proving that Hα is hyper-arithmetic in Y whereHα is the αth hyperjump of the empty set ∅, defined in a suitable sense for all ordinals

Background information and undefined notation can be found in Rogers [11]. In particular, we write A ≤hB(A ≤T B) if A is hyperarithmetical (recursive) in B, and A ≡hB if A ≤hB and B ≤hA. We will say that a set A is hyperarithmetically (recursively) encodable if, for every infinite set X ⊆ ω, there exists Y ⊆ X such that A ≤hY (A ≤TY). For any set A (hyperdegree a) let A′ (a′) denote the hyperjump of A (a). Let 0 denote the hyperdegree of ∅. A function f majorizes a function g if f(n) ≥ g(n) for every n. E1 is the representing (type-2) functional of

introduced by Tugué [13] (also Kleene [6]). Let be the smallest ordinal which is not the order type of any well-ordering recursive in E1. Information on can be found in Richter [9] and [10].

For several old problems in combinatorial set theory A. Hajnal and the present author [2] showed that on collapsing a sufficiently Mahlo cardinal to ω 1 by the Lévy-collapse one gets a model where these problems are solved in the “counter-example” direction. The authors of [2] have speculated that the theorems of that paper should hold in L, and this, in fact, was shown for some of the results by Todorčević and Velleman [7,8]. The observation that collapsing a large cardinal to ω 1 may give rise to L-like constructions is not new. As it was shown long ago by Silver and Rowbottom, there is a Kurepa-tree if a strongly inaccessible cardinal is Lévy-collapsed to ω 1. In [5] it is proved that even Silver's W holds in that model. Here we show that even a quagmire exists there, but not necessarily a morass. To be more exact, we show that if κ < λ are the first two strongly inaccessible cardinals, first λ is Lévy-collapsed to κ +, and then κ is Lévy-collapsed to then there is no ω 1-morass with built-in diamond in the resulting model (GCH is assumed). If λ is Mahlo, there is not even a morass.

Our notations are standard. For excellent survey papers on morass-like principles and their uses in combinatorial set theory see [4,5,6].

We presuppose the terminology of [1], and we give a negative answer to the following problem ([1], p. 19): Does every essentially undecidable axiomatizable theory have an essentially undecidable finitely axiomatizable subtheory?

We use the following theorem of Kleene ([2], p. 311). There exist two recursively enumerable sets α and β such that (1) α and β are disjoint (2) there is no recursive set η for which α ⊂ η, β ⊂ η′. By the definition of recursive enumerability, there are recursive predicates Φ and Ψ for which

We now specify a theory T which will afford a counter-example to the given problem of Tarski. The only non-logical constants of T are two binary predicates P and Q, one unary operation symbol S, and one individual constant 0. As in ([1], p. 52) we define

The only non-logical axioms of T are the formulae P(Δm, Δn) for all pairs of integers m, n satisfying Δ(m, n); the formulae Q(Δm, Δn) for all pairs of integers m, n satisfying Ψ(m, n); and the formula

T is consistent, since it has a model. It remains to show that (1) every consistent extension of T is undecidable (2) if T1 is a finitely axiomatizable subtheory of T, there exists a consistent and decidable extension of T1 which has the same constants as T1.

In this paper, we remark on some properties of equality that tend to be neglected and use them to give a proof of an extension of Lyndon's interpolation theorem. Let LK be a first order classical predicate calculus and LK= a first order classical predicate calculus with equality. We assume that LK and LK= have the propositional constant Τ (truth). For each formula F in LK=, let Rel+ (F), Rel− (F), Rel(F), and Fun(F) be the set of all the predicate symbols which occur in F positively, the set of all the predicate symbols which occur in F negatively, the set of all the predicate symbols which occur in F, and the set of all the function symbols which occur in F.

Theorem A (Lyndon [5]). Suppose that A and B are sentences in LK such that A ⊃ B is provable in LK. Then there is a sentence C in LK such that:

(i) A ⊃ C and C ⊃ B are provable in LK;

(ii) and

(iii) .

The sentence C which satisfies (i), (ii), (iii) in Theorem A is said to be an interpolant for A ⊃ B in Theorem A. Note that condition (iii) is not included in the original form of Lyndon's interpolation theorem (cf. [5]), but we can easily add this condition. Also, there is some obscurity in the original formulation with regard to the equality symbol. For example, Lyndon writes: “The theorem takes the same form whether or not we admit a predicate denoting identity, with suitable axioms, to the predicate calculus” [5, p. 129].

We build on an existing a term-sequent logic for the λ-calculus. We formulate a general sequent system that fully integrates αβη-reductions between untyped λ-terms into first order logic.

We prove a cut-elimination result and then offer an application of cut-elimination by giving a notion of uniform proof for λ-terms. We suggest how this allows us to view the calculus of untyped αβ-reductions as a logic programming language (as well as a functional programming language, as it is traditionally seen).

We consider the question “Is every nonzero generic degree a density-1-bounding generic degree?” By previous results [8] either resolution of this question would answer an open question concerning the structure of the generic degrees: A positive result would prove that there are no minimal generic degrees, and a negative result would prove that there exist minimal pairs in the generic degrees.

We consider several techniques for showing that the answer might be positive, and use those techniques to prove that a wide class of assumptions is sufficient to prove density-1-bounding.

We also consider a historic difficulty in constructing a potential counterexample: By previous results [7] any generic degree that is not density-1-bounding must be quasiminimal, so in particular, any construction of a non-density-1-bounding generic degree must use a method that is able to construct a quasiminimal generic degree. However, all previously known examples of quasiminimal sets are also density-1, and so trivially density-1-bounding. We provide several examples of non-density-1 sets that are quasiminimal.

Using cofinite and mod-finite reducibility, we extend our results to the uniform coarse degrees, and to the nonuniform generic degrees. We define all of the above terms, and we provide independent motivation for the study of each of them.

Combined with a concurrently written paper of Hirschfeldt, Jockusch, Kuyper, and Schupp [4], this paper provides a characterization of the level of randomness required to ensure quasiminimality in the uniform and nonuniform coarse and generic degrees.

By operations on models we show how to relate completeness with respect to permissive-nominal models to completeness with respect to nominal models with finite support. Models with finite support are a special case of permissive-nominal models, so the construction hinges on generating from an instance of the latter, some instance of the former in which sufficiently many inequalities are preserved between elements. We do this using an infinite generalisation of nominal atoms-abstraction.

The results are of interest in their own right, but also, we factor the mathematics so as to maximise the chances that it could be used off-the-shelf for other nominal reasoning systems too. Models with infinite support can be easier to work with, so it is useful to have a semi-automatic theorem to transfer results from classes of infinitely-supported nominal models to the more restricted class of models with finite support.

In conclusion, we consider different permissive-nominal syntaxes and nominal models and discuss how they relate to the results proved here.

We explore a general method based on trees of elementary submodels in order to present highly simplified proofs to numerous results in infinite combinatorics. While countable elementary submodels have been employed in such settings already, we significantly broaden this framework by developing the corresponding technique for countably closed models of size continuum. The applications range from various theorems on paradoxical decompositions of the plane, to coloring sparse set systems, results on graph chromatic number and constructions from point-set topology. Our main purpose is to demonstrate the ease and wide applicability of this method in a form accessible to anyone with a basic background in set theory and logic.

We study Σ1(ω1)-definable sets (i.e., sets that are equal to the collection of all sets satisfying a certain Σ1-formula with parameter ω1 ) in the presence of large cardinals. Our results show that the existence of a Woodin cardinal and a measurable cardinal above it imply that no well-ordering of the reals is Σ1(ω1)-definable, the set of all stationary subsets of ω1 is not Σ1(ω1)-definable and the complement of every Σ1(ω1)-definable Bernstein subset of ${}_{}^{{\omega _1}}\omega _1^{}$ is not Σ1(ω1)-definable. In contrast, we show that the existence of a Woodin cardinal is compatible with the existence of a Σ1(ω1)-definable well-ordering of H(ω2) and the existence of a Δ1(ω1)-definable Bernstein subset of ${}_{}^{{\omega _1}}\omega _1^{}$. We also show that, if there are infinitely many Woodin cardinals and a measurable cardinal above them, then there is no Σ1(ω1)-definable uniformization of the club filter on ω1. Moreover, we prove a perfect set theorem for Σ1(ω1)-definable subsets of ${}_{}^{{\omega _1}}\omega _1^{}$, assuming that there is a measurable cardinal and the nonstationary ideal on ω1 is saturated. The proofs of these results use iterated generic ultrapowers and Woodin’s ℙmax-forcing. Finally, we also prove variants of some of these results for Σ1(κ)-definable subsets of κκ, in the case where κ itself has certain large cardinal properties.

In this paper we investigate the connections between categoricity and ranks. We use stability theory to prove some old and new results.

There are shown to be many ε-Hermitian spaces, and an isometry criterion is stated which holds under MAℵ1 and is false under 2ℵ0< 2ℵ1.

13.1. If ‘[p f a]’ is in K′, we will say that ‘p’ is a value of ‘f’ at ‘a’.

13.2. If ‘a’ and ‘b’ are rational U-reals and if ‘b’ is not less than ‘a’, then ‘{a, b}’ will be called a rational U-interval.

13.3. If ‘f’ has a value at ‘d’, if ‘d’ is within a U-interval ‘{c, e}’, and if all values of ‘f’ at U-reals with ‘{c, e}’ are within the U-interval ‘{r, t}’, then we will say that ‘{c, e}’ restricts ‘f’ to ‘{r, t}’ at ‘d’, and that ‘{c, e}’ is an ‘f’-restrictive correlate of ‘d’ with respect to ‘{r, t}’.

13.4. If ‘d’ is within ‘{a, b}’, we will say that ‘{a, b}’ “contains” ‘d’.

13.5. If ‘f’ has a value at ‘d’ and if corresponding to every U-interval ‘{r, t}’ that contains a value of ‘f’ at ‘d’ there is an ‘f’-restrictive correlate of ‘d’ with respect to ‘{r, t}’, then ‘f’ will be said to be “continuous” at ‘d’. Without loss of generality the ‘f’-restrictive correlate can be required to be a rational U-interval.

13.6. If ‘f’ is continuous at every U-real in ‘{a, b}’, we will say that ‘f’ is continuous in ‘{a, b}’.

13.7. Theorem. If ‘k’ is a positive U-real and ‘f’ is continuous in a U-interval ‘{a, b}’, then ‘{a, b}’ is covered by the class S of rational U-intervals that are ‘f’-restrictive correlates of rational U-reals in ‘{a, b}’ with respect to those rational U-intervals ‘{r, t)’ that contain values of ‘f’ at rational U-reals in ‘{a, b}’ and that are such that’∣t − r∣‘ is equal to ‘k’ (in the sense of 10.10).

A model companion is shown to exist for the theory of partial differential fields of characteristic zero equipped with free operators that commute with the derivations. The free operators here are those introduced in [R. Moosa and T. Scanlon, Model theory of fields with free operators in characteristic zero, Journal of Mathematical Logic 14(2), 2014]. The proof relies on a new lifting lemma in differential algebra: a differential version of Hensel’s Lemma for local finite algebras over differentially closed fields.

We extend Ahlbrandt and Ziegler’s reconstruction results ([1]) to the metric setting: we show that separably categorical structures are determined, up to bi-interpretability, by their automorphism groups.

A proof-theoretic characterization of the primitive recursive functions is the Σ1-definable functions in IΣ1 as is shown in Mints [4], Parsons [5], and [8].

Then what is a proof-theoretic characterization of Grzegorzyk's hierarchy? First we discuss a related previous work. In Clote and Takeuti [2], we introduced a theory TAC that corresponds to the computational complexity class AC. TAC has a very weak form of induction. We assign a rank to a proof in TAC in the following way. The rank of a proof P in TAC is the nesting number of inductions used in P. Then TACi is defined to be the subtheory of TAC whose proof has a rank ≤ i. We proved that TACi corresponds to the class ACi.

In this paper we introduce a theory IepΣ1 which is equivalent to IΣ1. Then we define the rank of a proof in IepΣ1 as the nesting number of inductions in the proof and prove that the proofs with rank ≤ i correspond to Grzegorcyk's hierarchy for i > 0.

We also prove that the system that has proofs with rank 0 is actually equivalent to I Δ0. These facts are interesting since it is proved in [10] that the theory isomorphic to TAC∘ by RSUV isomorphism is a conservative extension of I Δo. Therefore there is some analogy between the class AC and the primitive recursive functions.