Let be a finite relational language and α = (αR: R ∈ ) a tuple with 0 < αR ≤ 1 for each R ∈ . Consider a dimension function

where each eR(A) is the number of realizations of R in A. Let Kα be the class of finite structures A such that δα (X) ≥ 0 for any substructure X of A. We show that the theory of the generic model of Kα is AE-axiomatizable for any α.

We find the model completion of the theory modules over , where is a finitely generated commutative algebra over a field K. This is done in a context where the field K and the module are represented by sorts in the theory, so that constructible sets associated with a module can be interpreted in this language. The language is expanded by additional sorts for the Grassmanians of all powers of Kn, which are necessary to achieve quantifier elimination.

The result turns out to be that the model completion is the theory of a certain class of “big” injective modules. In particular, it is shown that the class of injective modules is itself elementary. We also obtain an explicit description of the types in this theory.

Let L[E] be an iterable tame extender model. We analyze to which extent L[E] knows fragments of its own iteration strategy. Specifically, we prove that inside L[E], for every cardinal κ which is not a limit of Woodin cardinals there is some cutpoint t < κ such that Jκ[E] is iterable above t with respect to iteration trees of length less than κ.

As an application we show L[E] to be a model of the following two cardinals versions of the diamond principle. If λ > κ > ω1 are cardinals, then holds true, and if in addition λ is regular, then holds true.

Equivalences and translations between consequence relations abound in logic. The notion of equivalence can be denned syntactically, in terms of translations of formulas, and order-theoretically, in terms of the associated lattices of theories. W. Blok and D. Pigozzi proved in [4] that the two definitions coincide in the case of an algebraizable sentential deductive system. A refined treatment of this equivalence was provided by W. Blok and B. Jónsson in [3]. Other authors have extended this result to the cases of κ-deductive systems and of consequence relations on associative, commutative, multiple conclusion sequents. Our main result subsumes all existing results in the literature and reveals their common character. The proofs are of order-theoretic and categorical nature.

A cylindric algebra atom structure is said to be strongly representable if all atomic cylindric algebras with that atom structure are representable. This is equivalent to saying that the full complex algebra of the atom structure is a representable cylindric algebra. We show that for any finite n ≥ 3, the class of all strongly representable n-dimensional cylindric algebra atom structures is not closed under ultraproducts and is therefore not elementary.

Our proof is based on the following construction. From an arbitrary undirected, loop-free graph Γ, we construct an n-dimensional atom structure , and prove, for infinite Γ, that is a strongly representable cylindric algebra atom structure if and only if the chromatic number of Γ is infinite. A construction of Erdős shows that there are graphs Γk(k < ω) with infinite chromatic number, but having a non-principal ultraproduct ΠDΓk whose chromatic number is just two. It follows that is strongly representable (each k < ω) but is not.

We show how to formalize approximate counting via hash functions in subsystems of bounded arithmetic, using variants of the weak pigeonhole principle. We discuss several applications, including a proof of the tournament principle, and an improvement on the known relationship of the collapse of the bounded arithmetic hierarchy to the collapse of the polynomial-time hierarchy.

We present a solution to the problem of denning a counterpart in Algebraic Set Theory of the construction of internal sheaves in Topos Theory. Our approach is general in that we consider sheaves as determined by Lawvere-Tierney coverages, rather than by Grothendieck coverages, and assume only a weakening of the axioms for small maps originally introduced by Joyal and Moerdijk, thus subsuming the existing topos-theoretic results.

By recent work on some conjectures of Pillay, each definably compact group in a saturated o-minimal structure is an extension of a compact Lie group by a torsion free normal divisible subgroup, called its infinitesimal subgroup. We show that the infinitesimal subgroup is cohomologically acyclic. This implies that the functorial correspondence between definably compact groups and Lie groups preserves the cohomology.

Elementary Recursive Nonstandard Analysis, in short ERNA, is a constructive system of nonstandard analysis with a PRA consistency proof, proposed around 1995 by Patrick Suppes and Richard Sommer. It is built on a previous system by Rolando Chuaqui and Patrick Suppes, which was recently reconsidered by Michal Rössler and Emil Jeřábek. A Π1-transfer principle has already been added to ERNA and the consistency of the resulting theory proved in PRA. Here, we equip ERNA with Σ2-transfer and a saturation principle, while keeping the consistency proof inside PRA. We show that the extended theory allows for generalized transfer, a basic tool of nonstandard analysis, and interprets several strong theories, like BΣ2 and IΣ2.

We study when classes can have the disjoint amalgamation property for a proper initial segment of cardinals.

For every natural number k, there is a class Kk, defined by a sentence in Lω1,ω that has no models of cardinality greater than ℶk + 1, but Kk has the disjoint amalgamation property on models of cardinality less than or equal to ℵk − 3 and has models of cardinality ℵk − 1.

More strongly, we can have disjoint amalgamation up to ℵ∝ for ∝ < ω1, but have a bound on size of models.

For every countable ordinal ∝, there is a class K∝ defined by a sentence in Lω1,ω that has no models of cardinality greater than ℶω1, but K does have the disjoint amalgamation property on models of cardinality less than or equal to ℵ∝.

Finally we show that we can extend the ℵ∝ to ℶ∝ in the second theorem consistently with ZFC and while having ℵi ≪ ℶi for 0 < i < ∝. Similar results hold for arbitrary ordinals ∝ with ∣∝∣ = k and Lk + ω.

Each relational structure X has an associated Gaifman graph, which endows X with the properties of a graph. If x is an element of X, let Bn(x) be the ball of radius n around x. Suppose that X is infinite, connected and of bounded degree. A first-order sentence ϕ in the language of X is almost surely true (resp. a.s. false) for finite substructures of X if for every x ∈ X, the fraction of substructures of Bn(x) satisfying ϕ approaches 1 (resp. 0) as n approaches infinity. Suppose further that, for every finite substructure, X has a disjoint isomorphic substructure. Then every ϕ is a.s. true or a.s. false for finite substructures of X. This is one form of the geometric zero-one law. We formulate it also in a form that does not mention the ambient infinite structure. In addition, we investigate various questions related to the geometric zero-one law.

Higman essentially showed that if A is any language then SUBSEQ(A) is regular, where SUBSEQ(A) is the language of all subsequences of strings in A. Let s1,s2,s3,… be the standard lexico-graphic enumeration of all strings over some finite alphabet. We consider the following inductive inference problem: A(s1),A(s2),A(s3),…, learn, in the limit, a DFA for SUBSEQ(A). We consider this model of learning and the variants of it that are usually studied in Inductive Inference: anomalies, mind-changes, teams, and combinations thereof.

This paper is a significant revision and expansion of an earlier conference version [10].

We prove that Kreisel's Conjecture is true, if Peano arithmetic is axiomatised using minimality principle and axioms of identity (theory PAM). The result is independent on the choice of language of PAM. We also show that if infinitely many instances of A(x) are provable in a bounded number of steps in PAM then there exists . The results imply that PAM does not prove scheme of induction or identity schemes in a bounded number of steps.

We prove that every Turing degree a bounding some non-GL2 degree is recursively enumerable in and above (r.e.a.) some 1-generic degree.

We prove that it is decidable of a finite algebra whether it has a near-unanimity term operation, which settles a ten-year-old problem. As a consequence, it is decidable of a finite algebra in a congruence distributive variety whether it admits a natural duality.

The motivation for this paper is the following: In [4] I showed that it is inconsistent with ZFC that the Maximality Principle for directed closed forcings holds at unboundedly many regular cardinals κ (even only allowing κ itself as a parameter in the Maximality Principle for <κ-closed forcings each time). So the question is whether it is consistent to have this principle at unboundedly many regular cardinals or at every regular cardinal below some large cardinal κ (instead of ∞), and if so, how strong it is. It turns out that it is consistent in many cases, but the consistency strength is quite high.

We show that for every computable limit ordinal α, there is a computable structure that is categorical, but not relatively categorical (equivalently, it does not have a formally Scott family). We also show that for every computable limit ordinal α, there is a computable structure with an additional relation R that is intrinsically on , but not relatively intrinsically on (equivalently, it is not definable by a computable Σα formula with finitely many parameters). Earlier results in [7], [10], and [8] establish the same facts for computable successor ordinals α.

It is relatively consistent with ZFC that every countable FUfin space of weight ℵ1 is metrizable. This provides a partial answer to a question of G. Gruenhage and P. Szeptycki [GS1].

There have been numerous results showing that a measurable cardinal κ can carry exactly α normal measures in a model of GCH. where α is a cardinal at most κ++. Starting with just one measurable cardinal, we have [9] (for α = 1), [10] (for α = α++, the maximum possible) and [1] (for α = κ+, after collapsing κ++). In addition, under stronger large cardinal hypotheses, one can handle the remaining cases: [12] (starting with a measurable cardinal of Mitchell order α), [2] (as in [12], but where κ is the least measurable cardinal and α is less than κ, starting with a measurable of high Mitchell order) and [11] (as in [12], but where κ is the least measurable cardinal, starting with an assumption weaker than a measurable cardinal of Mitchell order 2). In this article we treat all cases by a uniform argument, starting with only one measurable cardinal and applying a cofinality-preserving forcing. The proof uses κ-Sacks forcing and the “tuning fork” technique of [8]. In addition, we explore the possibilities for the number of normal measures on a cardinal at which the GCH fails.