In analogy to ω-logic, one defines M-logic for an arbitrary structure M (see [5],[6]). In M-logic only those structures are considered in which a special part, determined by a fixed unary predicate, is isomorphic to M. Let L be the similarity type of M and T its complete theory. We say that M-logic is κ-compact if it satisfies the compactness theorem for sets of < κ sentences. In this paper we introduce the related notion of compactness for expandability: a model M is κ-compactly expandable if for every extension T′ ⊇ T of cardinality < κ, if every finite subset of T′ can be satisfied in an expansion of M, then T′ can also be satisfied in an expansion of M. Moreover, M is compactly expandable if it is ∥M∥+-compactly expandable. It turns out that M-logic is κ-compact iff M is κ-compactly expandable.

Whereas for first-order logic consistency and finite satisfiability are the same, consistency with T and finite satisfiability in M are, in general, no longer the same thing. We call the model Mκ-expandable if every consistent extension T′ ⊇ T of cardinality < κ can be satisfied in an expansion of M. We say that M is expandable if it is ∥M∥+-expandable. Here we study the relationship between saturation, expandability and compactness for expandability. There is a close parallelism between our results about compactly expandable models and some theorems of S. Shelah about expandable models, which are in fact expressed in terms of categoricity of PC-classes (see [7, Th. VI.5.3, VI.5.4 and VI.5.5]). Our results could be obtained directly from these theorems of Shelah if expandability and compactness for expandability were the same notion.

Two countable filters on ω are incompatible if they have no common infinite pseudointersection. Letting (Pf) denote the minimal size of a maximal uncountable family of pairwise incompatible countable filters on ω, we prove the consistency of t < a(Pf).

If S, T are stationary subsets of a regular uncountable cardinal κ, we say that S reflects fully in T, S < T, if for almost all α ∈ T (except a nonstationary set) S ∩ α stationary in α. This relation is known to be a well-founded partial ordering. We say that a given poset P is realized by the reflection ordering if there is a maximal antichain 〈Xp: p ∈ P〉 of stationary subsets of Reg(κ) so that

We prove that if , and P is an arbitrary well-founded poset of cardinality ≤ κ+ then there is a generic extension where P is realized by the reflection ordering on κ.

Suppose that G is a group that is not finitely generated. Then the cofinality of G, written c(G), is denned to be the least cardinal λ such that G can be expressed as the union of a chain of λ proper subgroups. If κ is an infinite cardinal, then Sym(κ) denotes the group of all permutations of the set κ = {α∣α < κ}. In [1], Macpherson and Neumann proved that c(Sym(κ)) > κ for all infinite cardinals κ. In [4], we proved that it is consistent that c(Sym(ω)) and 2ω can be any two prescribed regular cardinals, subject only to the obvious requirement that c(Sym(ω)) ≤ 2ω. Our first result in this paper is the analogous result for regular uncountable cardinals κ.

Theorem 1.1. Let V ⊨ GCH. Let κ, θ, λ ∈ V be cardinals such that

(i) κ and θ are regular uncountable, and

(ii) κ < θ ≤ cf(λ).

Then there exists a notion of forcing ℙ, which preserves cofinalities and cardinalities, such that if G is ℙ-generic then V[G] ⊨ c(Sym(κ)) = θ ≤ λ = 2κ.

Theorem 1.1 will be proved in §2. Our proof is based on a very powerful uniformization principle, which was shown to be consistent for regular uncountable cardinals in [2].

We prove that a number of axioms, each a consequence of PFA (the Proper Forcing Axiom) are equivalent. In particular we show that TOP (the Thinning-out Principle as introduced by Baumgartner in the Handbook of set-theoretic topology), is equivalent to the following statement: If I is an ideal on ω1 with ω1 generators, then there exists an uncountable X ⊆ ω1, such that either [X]ω ∩ I = ∅ or [X]ω ⊆ I.

The structure of the 1-degrees included in an m-degree with a maximal set together with the 1-reducibility relation is characterized. For this a special sublattice of the lattice of recursively enumerable sets under the set-inclusion is used.

In this paper it is shown that the meet-inaccessible degrees are dense in R. The construction uses an 0′-priority argument. As a consequence, the meet-inaccessible degrees and the meet-accessible degrees give a partition of R into two sets, either of which is a nontrivial dense subset of R and generates R − {0} under joins (thus an automorphism base of R).

The existence of End Elementary Extensions of modelsM of ZFC is related to the ordinal height of M, according to classical results due to Keisler, Morley and Silver. In this paper, we further investigate the connection between the height of M and the existence of End Elementary Extensions of M. In particular, we prove that the theory ‘ZFC + GCH + there exist measurable cardinals + all inaccessible non weakly compact cardinals are possible heights of models with no End Elementary Extensions’ is consistent relative to the theory ‘ZFC + GCH + there exist measurable cardinals + the weakly compact cardinals are cofinal in ON’. We also provide a simpler coding that destroys GCH but otherwise yields the same result.

We define a new type of “shatter function” for set systems that satisfies a Sauer–Shelah type dichotomy, but whose polynomial-growth case is governed by Shelah’s two-rank instead of VC dimension. We identify the least exponent bounding the rate of growth of the shatter function, the quantity analogous to VC density, with Shelah’s $\omega $ -rank.

Le plus souvent, la logique reste une discipline à la périphérie des mathématiques, qu’elle observe de l’extérieur, sans y pénétrer vraiment. C’est un discours sur les mathematiques qui ne dit rien au mathématicien; il n’y reconnait pas son activité favorite, ni ne croit qu’elle puisse avoir une influence sur sa pratique.

L’illustration la plus extrême de cette tradition, ce sont les “reverse mathematics” de Harvey Friedman, qui connaissent le succès que l’on sait. Je veux parler ici d’une tendance toute opposée, secrétée par les développements contemporains de la théorie des modèles, qui promet des positions beaucoup plus directes.

Elle se cristalise autour de l’étude des groupes stables; l’apparition de groupes n’a rien d’inattendu dans un contexte mathématiquement signifiant: un groupe, c’est ce qui garantit une structure non-triviale (ceci n’est pas un simple argument terroriste: il y a des théoremes pour le soutenir); quant à la stabilité, c’est une hypothèse de controle structurel, au large champ d’application, et qu’on pourra dépasser quand seront résolus les problèmes posés dans le cadre stable.

We refine results of Gannon [6, Theorem 4.7] and Simon [22, Lemma 2.8] on convergence of Morley sequences. We then introduce the notion of eventual$NIP$, as a property of a model, and prove a variant of [15, Corollary 2.2]. Finally, we give new characterizations of generically stable types (for countable theories) and reinforce the main result of Pillay [17] on the model-theoretic meaning of Grothendieck’s double limit theorem.

Given a sound first-order p-time theory T capable of formalizing syntax of first-order logic we define a p-time function $g_T$ that stretches all inputs by one bit and we use its properties to show that T must be incomplete. We leave it as an open problem whether for some T the range of $g_T$ intersects all infinite ${\mbox {NP}}$ sets (i.e., whether it is a proof complexity generator hard for all proof systems).

A propositional version of the construction shows that at least one of the following three statements is true:

1. 1. There is no p-optimal propositional proof system (this is equivalent to the non-existence of a time-optimal propositional proof search algorithm).

2. 2. $E \not \subseteq P/poly$.

3. 3. There exists function h that stretches all inputs by one bit, is computable in sub-exponential time, and its range $Rng(h)$ intersects all infinite ${\text {NP}}$ sets.

We give a new characterization of the cardinal invariant $\mathfrak {d}$ as the minimal cardinality of a family $\mathcal {D}$ of tall summable ideals such that an ultrafilter is rapid if and only if it has non-empty intersection with all the ideals in the family $\mathcal {D}$. On the other hand, we prove that in the Miller model, given any family $\mathcal {D}$ of analytic tall p-ideals such that $\vert \mathcal {D}\vert <\mathfrak {d}$, there is an ultrafilter $\mathcal {U}$ which is an $\mathscr {I}$-ultrafilter for all ideals $\mathscr {I}\in \mathcal {D}$ at the same time, yet $\mathcal {U}$ is not a rapid ultrafilter. As a corollary, we obtain that in the Miller model, given any analytic tall p-ideal $\mathscr {I}$, $\mathscr {I}$-ultrafilters are dense in the Rudin–Blass ordering, generalizing a theorem of Bartoszyński and S. Shelah, who proved that in such model, Hausdorff ultrafilters are dense in the Rudin–Blass ordering. This theorem also shows some limitations about possible generalizations of a theorem of C. Laflamme and J. Zhu.

All known structural extensions of the substructural logic $\textbf{FL}_{\textbf{e}}$ , the Full Lambek calculus with exchange/commutativity (corresponding to subvarieties of commutative residuated lattices axiomatized by $\{\vee , \cdot , 1\}$ -equations), have decidable theoremhood; in particular all the ones defined by knotted axioms enjoy strong decidability properties (such as the finite embeddability property). We provide infinitely many such extensions that have undecidable theoremhood, by encoding machines with undecidable halting problem. An even bigger class of extensions is shown to have undecidable deducibility problem (the corresponding varieties of residuated lattices have undecidable word problem); actually with very few exceptions, such as the knotted axioms and the other prespinal axioms, we prove that undecidability is ubiquitous. Known undecidability results for non-commutative extensions use an encoding that fails in the presence of commutativity, so and-branching counter machines are employed. Even these machines provide encodings that fail to capture proper extensions of commutativity, therefore we introduce a new variant that works on an exponential scale. The correctness of the encoding is established by employing the theory of residuated frames.

Cohesive powers of computable structures are effective analogs of ultrapowers, where cohesive sets play the role of ultrafilters. Let $\omega $, $\zeta $, and $\eta $ denote the respective order-types of the natural numbers, the integers, and the rationals when thought of as linear orders. We investigate the cohesive powers of computable linear orders, with special emphasis on computable copies of $\omega $. If $\mathcal {L}$ is a computable copy of $\omega $ that is computably isomorphic to the usual presentation of $\omega $, then every cohesive power of $\mathcal {L}$ has order-type $\omega + \zeta \eta $. However, there are computable copies of $\omega $, necessarily not computably isomorphic to the usual presentation, having cohesive powers not elementarily equivalent to $\omega + \zeta \eta $. For example, we show that there is a computable copy of $\omega $ with a cohesive power of order-type $\omega + \eta $. Our most general result is that if $X \subseteq \mathbb {N} \setminus \{0\}$ is a Boolean combination of $\Sigma _2$ sets, thought of as a set of finite order-types, then there is a computable copy of $\omega $ with a cohesive power of order-type $\omega + \boldsymbol {\sigma }(X \cup \{\omega + \zeta \eta + \omega ^*\})$, where $\boldsymbol {\sigma }(X \cup \{\omega + \zeta \eta + \omega ^*\})$ denotes the shuffle of the order-types in X and the order-type $\omega + \zeta \eta + \omega ^*$. Furthermore, if X is finite and non-empty, then there is a computable copy of $\omega $ with a cohesive power of order-type $\omega + \boldsymbol {\sigma }(X)$.

For which infinite cardinals $\kappa $ is there a partition of the real line ${\mathbb R}$ into precisely $\kappa $ Borel sets? Work of Lusin, Souslin, and Hausdorff shows that ${\mathbb R}$ can be partitioned into $\aleph _1$ Borel sets. But other than this, we show that the spectrum of possible sizes of partitions of ${\mathbb R}$ into Borel sets can be fairly arbitrary. For example, given any $A \subseteq \omega $ with $0,1 \in A$, there is a forcing extension in which ${A = \{ n :\, \text {there is a partition of } {{\mathbb R}} \text { into }\aleph _n\text { Borel sets}\}}$. We also look at the corresponding question for partitions of ${\mathbb R}$ into closed sets. We show that, like with partitions into Borel sets, the set of all uncountable $\kappa $ such that there is a partition of ${\mathbb R}$ into precisely $\kappa $ closed sets can be fairly arbitrary.

We introduce and study (weakly) semi-equational theories, generalizing equationality in stable theories (in the sense of Srour) to the NIP context. In particular, we establish a connection to distality via one-sided strong honest definitions; demonstrate that certain trees are semi-equational, while algebraically closed valued fields are not weakly semi-equational; and obtain a general criterion for weak semi-equationality of an expansion of a distal structure by a new predicate.

We present sound and complete sequent calculi for the modal mu-calculus with converse modalities, aka two-way modal mu-calculus. Notably, we introduce a cyclic proof system wherein proofs can be represented as finite trees with back-edges, i.e., finite graphs. The sequent calculi incorporate ordinal annotations and structural rules for managing them. Soundness is proved with relative ease as is the case for the modal mu-calculus with explicit ordinals. The main ingredients in the proof of completeness are isolating a class of non-wellfounded proofs with sequents of bounded size, called slim proofs, and a counter-model construction that shows slimness suffices to capture all validities. Slim proofs are further transformed into cyclic proofs by means of re-assigning ordinal annotations.