R. K. Meyer once gave precise form to the question of whether relevant implication can be defined in any modal system, and his answer was ‘no’. In the present paper, we extend S4, first with propositional quantifiers, to the system S4π+; and then with definite propositional descriptions, to the system S4π+ip. We show that relevant implication can in some sense be defined in the modal system S4π+ip, although it cannot be defined in S4π+.

According to [4, p. 1154], a complete L-theory T eliminates imaginaries just in case for every L-formula φ(x1,… , xm, y1, …, yn), every model M of T, and every ā Є Mn, there is a subset A of M's domain with the following property: if N ≽ M and f is an automorphism of N, then

if and only if

Among the several equivalent conditions discussed in [4, p. 1155], one may single out the following: if T is a complete theory in which two distinct objects are definable, T eliminates imaginaries just in case every T-definable n-ary equivalence relation may be defined by a formula

where g is a T-definable n-ary function taking k-tuples as values (for some natural number k).

Say that an L-structure M eliminates imaginaries just in case Th(M) does. If L is the language of rings with unit, [4, p. 1158] shows that any algebraically closed field eliminates imaginaries, and [2, p. 629] points out that any real-closed field eliminates imaginaries.

A standard result in topological dynamics is the existence of minimal subsystem. It is a direct consequence of Zorn's lemma: given a compact topological space X with a map f: X→X, the set of compact non empty subspaces K of X such that f(K) ⊆ K ordered by inclusion is inductive, and hence has minimal elements. It is natural to ask for a point-free (or formal) formulation of this statement. In a previous work [3], we gave such a formulation for a quite special instance of this statement, which is used in proving a purely combinatorial theorem (van de Waerden's theorem on arithmetical progression).

In this paper, we extend our analysis to the case where X is a boolean space, that is compact totally disconnected. In such a case, we give a point-free formulation of the existence of a minimal subspace for any continuous map f: X→X. We show that such minimal subspaces can be described as points of a suitable formal topology, and the “existence” of such points become the problem of the consistency of the theory describing a generic point of this space. We show the consistency of this theory by building effectively and algebraically a topological model. As an application, we get a new, purely algebraic proof, of the minimal property of [3]. We show then in detail how this property can be used to give a proof of (a special case of) van der Waerden's theorem on arithmetical progression, that is “similar in structure” to the topological proof [6, 8], but which uses a simple algebraic remark (Proposition 1) instead of Zorn's lemma. A last section tries to place this work in a wider context, as a reformulation of Hilbert's method of introduction/elimination of ideal elements.

The Martin-Steel coarse inner model theory is employed in obtaining new results in descriptive set theory. determinacy implies that for every thin equivalence relation there is a real, N, over which every equivalence class is generic—and hence there is a good (N#) wellordering of the equivalence classes. Analogous results are obtained for and quasilinear orderings and determinacy is shown to imply that every prewellorder has rank less than .

Martin's axiom is equivalent to the statement that the universe is absolute under ccc forcing extensions for Σ1 sentences with a subset of κ, , as a parameter.

I solve here some problems left open in “T-convexity and Tame Extensions” [9]. Familiarity with [9] is assumed, and I will freely use its notations. In particular, T will denote a complete o-minimal theory extending RCF, the theory of real closed fields. Let (, V) ⊨ Tconvex, let = V/m(V) be the residue field, with residue class map x ↦ : V ↦ , and let υ: → Γ be the associated valuation. “Definable” will mean “definable with parameters”. The main goal of this article is to determine the structure induced by (, V) on its residue fieldand on its value group Γ. In [9] we expanded the ordered field to a model of T as follows. Take a tame elementary substructure ′ of such that R′ ⊆ V and R′ maps bijectively onto under the residue class map, and make this bijection into an isomorphism ′ ≌ of T-models. (We showed such ′ exists, and that this gives an expansion of to a T-model that is independent of the choice of ′.).

Finitary sketches, i.e., sketches with finite-limit and finite-colimit specifications, are proved to be as strong as geometric sketches, i.e., sketches with finite-limit and arbitrary colimit specifications. Categories sketchable by such sketches are fully characterized in the infinitary first-order logic: they are axiomatizable by σ-coherent theories, i.e., basic theories using finite conjunctions, countable disjunctions, and finite quantifications. The latter result is absolute; the equivalence of geometric and finitary sketches requires (in fact, is equivalent to) the non-existence of measurable cardinals.

Let L0, L1 and L2 be countable languages with L ∩ L1 = L0. Let M0 be an L0-structure and Mi, an expansion of M0 to an Li,-structure (i = 1,2). We will call an L1 ∪ L2-structure M an amalgamation of M1 and M2 if M∣Li ≅ Mi, (i = 1,2). Let's consider the following problem.

(*) Suppose that both M1 and M2 belong to the class . Can we always find an amalgamation M in ?

Of course the existence of such an amalgamation depends on the class L. Some examples of and the answers are given below.

1. = Countably saturated strongly minimal structures with the DMP In [3], Hrushovski showed that any two strongly minimal theories formulated in totally different languages have a common extension which is still strongly minimal and with the DMP (DMP is the property that states that if a point is sufficiently close to ā, then φ(, ) has the same rank and the same degree as φ(, ā).) His proof essentially shows that if L0 = ∅ then any two countably saturated strongly minimal structures with the DMP have a strongly minimal amalgamation. Also he gave an example that shows the condition L0 = ∅ is necessary.

2. = ℵ1-categorical countable structures. Let M1 be the structure (ℚ, +) and let M2 be the {E, F}-structure defined by: (i) E is an equivalence relation which divides the universe into two infinite classes A and B, (ii) F is a bijection between A and B.

Applying the seed concept to Prikry tree forcing ℙμ, I investigate how well ℙμ preserves the maximality property of ordinary Prikry forcing and prove that ℙμ, Prikry sequences are maximal exactly when μ admits no non-canonical seeds via a finite iteration. In particular, I conclude that if μ is a strongly normal supercompactness measure, then ℙμ Prikry sequences are maximal, thereby proving, for a large class of measures, a conjecture of W. Hugh Woodin's.

We consider small-weight Cutting Planes (CP*) proofs; that is, Cutting Planes (CP) proofs with coefficients up to Poly(n). We use the well known lower bounds for monotone complexity to prove an exponential lower bound for the length of CP* proofs, for a family of tautologies based on the clique function. Because Resolution is a special case of small-weight CP, our method also gives a new and simpler exponential lower bound for Resolution.

We also prove the following two theorems: (1) Tree-like CP* proofs cannot polynomially simulate non-tree-like CP* proofs. (2) Tree-like CP* proofs and Bounded-depth-Frege proofs cannot polynomially simulate each other.

Our proofs also work for some generalizations of the CP* proof system. In particular, they work for CP* with a deduction rule, and also for any proof system that allows any formula with small communication complexity, and any set of sound rules of inference.

In this paper we formulate a notion similar to o-minimality but appropriate for the p-adics. The paper is in a sense a sequel to [11] and [5]. In [11] a notion of minimality was formulated, as follows. Suppose that L, L+ are first-order languages and + is an L+-structure whose reduct to L is . Then + is said to be -minimal if, for every N+ elementarily equivalent to +, every parameterdefinable subset of its domain N+ is definable with parameters by a quantifier-free L-formula. Observe that if L has a single binary relation which in is interpreted by a total order on M, then we have just the notion of strong o-minimality, from [13]; and by a theorem from [6], strong o-minimality is equivalent to o-minimality. If L has no relations, functions, or constants (other than equality) then the notion is just strong minimality.

In [11], -minimality is investigated for a number of structures . In particular, the C-relation of [1] was considered, in place of the total order in the definition of strong o-minimality. The C-relation is essentially the ternary relation which naturally holds on the maximal chains of a sufficiently nice tree; see [1], [11] or [5] for more detail, and for axioms. Much of the motivation came from the observation that a C-relation on a field F which is preserved by the affine group AGL(1,F) (consisting of permutations (a,b) : x ↦ ax + b, where a ∈ F \ {0} and b ∈ F) is the same as a non-trivial valuation: to get a C-relation from a valuation ν, put C(x;y,z) if and only if ν(y − x) < ν(y − z).

We study a generalization of the splitting number s to uncountable cardinals. We prove that 𝔰(κ) > κ+ for a regular uncountable cardinal κ implies the existence of inner models with measurables of high Mitchell order. We prove that the assumption 𝔰(ℵω) > ℵω+1 has a considerable large cardinal strength as well.

This article is concerned with functions k assigning a cardinal number to each infinite Boolean algebra (BA), and the behaviour of such functions under ultraproducts. For some common functions k we have

for others we have ≤ instead, under suitable assumptions. For the function π character we go into more detail. More specifically, ≥ holds when F is regular, for cellularity, length, irredundance, spread, and incomparability. ≤ holds for π. ≥ holds under GCH for F regular, for depth, π, πχ, χ, h-cof, tightness, hL, and hd. These results show that ≥ can consistently hold in ZFC since if V = L holds then all uniform ultrafilters are regular. For π-character we prove two more results: (1) If F is regular and ess , then

(2) It is relatively consistent to have , where A is the denumerable atomless BA.

A thorough analysis of what happens without the assumption that F is regular can be found in Rosłanowski, Shelah [8] and Magidor, Shelah [5]. Those papers also mention open problems concerning the above two possible inequalities.

We investigate the algebraic structure of the upper semi-lattice formed by the recursively enumerable Turing degrees. The following strong generalization of Lachlan's Nonsplitting Theorem is proved: Given n ≥ 1, there exists an r.e. degree d such that the interval [d, 0′] ⊂ R admits an embedding of the n-atom Boolean algebra preserving (least and) greatest element, but also such that there is no (n + 1 )-tuple of pairwise incomparable r.e. degrees above d which pairwise join to 0′ (and hence, the interval [d, 0′] ⊂ R does not admit a greatest-element-preserving embedding of any lattice which has n + 1 co-atoms, including ). This theorem is the dual of a theorem of Ambos-Spies and Soare, and yields an alternative proof of their result that the theory of R has infinitely many one-types.

Elimination of imaginaries for 1-variable definable equivalence relations is proved for a theory of algebraically closed valued fields with new sorts for the disc spaces. The proof is constructive, and is based upon a new framework for proving elimination of imaginaries, in terms of prototypes which form a canonical family of formulas for defining each set that is definable with parameters. The proof also depends upon the formal development of the tree-like structure of valued fields, in terms of valued trees, and a decomposition of valued trees which is used in the coding of certain sets of discs.

Translations from Lambda calculi into combinatory logics can be used to avoid some implementational problems of the former systems. However, this scheme can only be efficient if the translation produces short output with a small number of combinators, in order to reduce the time and transient storage space spent during reduction of combinatory terms. In this paper we present a combinatory system and an abstraction algorithm, based on the original bracket abstraction operator of Schönfinkel [9]. The algorithm introduces at most one combinator for each abstraction in the initial Lambda term. This avoids explosive term growth during successive abstractions and makes the system suitable for practical applications. We prove the correctness of the algorithm and establish some relations between the combinatory system and the Lambda calculus.

In this note it is shown that in explicit mathematics the strong power type axiom is inconsistent with (uniform) elementary comprehension and discuss some general aspects of power types in explicit mathematics.

In this paper we investigate towers of normal filters. These towers were first used by Woodin (see [15]). Woodin proved that if δ is a Woodin cardinal and P is the full stationary tower up to δ (P<δ) or the countable version (Q<δ), then the generic ultrapower is closed under < δ sequences (so the generic ultrapower is well-founded) ([14]). We show that if ℙ is a tower of height δ, δ supercompact, and the filters generating ℙ are the club filter restricted to a stationary set, then the generic ultrapower is well-founded (ℙ is precipitous). We also give some examples of non-precipitous towers. We also show that every normal filter can be extended to a V-ultrafilter with well-founded ultrapower in some generic extension of V (assuming large cardinals). Similarly for any tower of inaccessible height. This is accomplished by showing that there is a stationary set that projects to the filter or the tower and then forcing with P<δ below this stationary set.

An important idea in our proof of precipitousness (Theorem 6.4) has the following form in Woodin's proof. If are maximal antichains (i Є ω and δ Woodin) then there is a κ < δ such that each Ai ∩ Vκ is semiproper, i.e.,

contains a club (relative to ∣ a∣ < κ).

This work is inspired by the correspondence of Malcev between rings and groups. Let A be a domain with unit, and S a multiplicative group of invertible elements. We define AS as the structure obtained from A by restraining the multiplication to A × S, and σ(AS) as the group of functions from A to A of the form x → xa + b, where (a, b) belongs to S × A. We show that AS and σ(As) are interpretable in each other, and then, that we can transfer some properties between classes (or theories) of “reduced” domains and corresponding groups, such as being elementary, axiomatisability (for classes), decidability, completeness, or, in some cases, existence of a model-completion (for theories).

We study the extensions of the additive group of A by the group S, acting by right multiplication, and show that sometimes σ(AS) is the unique extension of this type. We also give conditions allowing us to eliminate parameters appearing in interpretations.

We emphasize the case where the domain is a division ring K and S is its multiplicative group K×. Here, the interpretations can always be done without parameters. If the centre of K contains more than two elements, then σ(K) is the only extension of the additive group of K by its multiplicative group acting by right multiplication, and the class of all such σ(K)'s is elementary and finitely axiomatisable. We give, in particular, an axiomatisation for this class and for the class of σ(K)'s where K is an algebraically closed field of characteristic 0. From these results it follows that some classical model-companion results about theories of fields can be translated and restated as results about theories of solvable groups of class 2.

Let DO denote the principle: Every infinite set has a dense linear ordering. DO is compared to other ordering principles such as O, the Linear Ordering principle, KW, the Kinna-Wagner Principle, and PI, the Prime Ideal Theorem, in ZF, Zermelo-Fraenkel set theory without AC, the Axiom of Choice.

The main result is:

Theorem. AC ⇒ KW ⇒ DO ⇒ O, and none of the implications is reversible in ZF + PI.

The first and third implications and their irreversibilities were known. The middle one is new. Along the way other results of interest are established. O, while not quite implying DO, does imply that every set differs finitely from a densely ordered set. The independence result for ZF is reduced to one for Fraenkel-Mostowski models by showing that DO falls into two of the known classes of statements automatically transferable from Fraenkel-Mostowski to ZF models. Finally, the proof of PI in the Fraenkel-Mostowski model leads naturally to versions of the Ramsey and Ehrenfeucht-Mostowski theorems involving sets that are both ordered and colored.