This paper continues the project initiated in [5]: a model-theoretic study of the concept of cardinality within certain higher-order logics. As recommended by an editor of this Journal, I will digress to say something about the project's motivation. Then I will review some of the basic definitions from [5]; for unexplained notation the reader should consult [5].

The syntax of ordinary usage (with respect to the construction of arguments as well as the construction of individual sentences) makes it natural to classify numerals and expressions of the form ‘the number of F's’ as singular terms, expressions like ‘is prime’ or ‘is divisible by’ as predicates of what Frege called “level one”, and expressions like ‘for some natural number’ as first-order quantifier-phrases. From this syntatic classification, it is a short step—so short as to be frequently unnoticed—to a semantic thesis: that such expressions play the same sort of semantic role as is played by the paradigmatic (and nonmathematical) members of these lexical classes. Thus expressions of the first sort are supposed to designate objects (in post-Fregean terms, entities of type 0), those of the second sort to be true or false of tuples of objects, and those of the third sort to quantify over objects. All this may be summed up in Frege's dictum: “Numbers are objects.”

The present note outlines an answer to a question listed as open in our recent survey article [1], familiarity with which is assumed.

Let Γ be the class of all X ⊆ ω such that X is reducible to for some some arithmetical and some positive with Y ⊆ p(Y) for all Y.

We present a comprehensive study of the axiom schemas (induction and collection schemas for parameter free Σ n formulas) and some closely related schemas.

Tarski's writings on the concepts of truth and logical consequence rank among the most influential works in both logic and philosophy of the twentieth century. Because of this, it would be impossible to give a careful and accurate account of how far that influence reaches and of the complex route by which it spread. In logic, Tarski's methods of defining satisfaction and truth, as well as his work pioneering general model-theoretic techniques, have been entirely absorbed into the way the subject is presently done; they have become part of the fabric of contemporary logic, material presented in the initial pages of every modern textbook on the subject. In philosophy, the influence has been equally pervasive, extending not only to work in semantics and the philosophies of logic and language, but to less obviously allied areas such as epistemology and the philosophy of science as well.

Rather than try to chart the wide-ranging influence of these writings or catalog the important research they have inspired, I will concentrate on various confusions and misunderstandings that continue to surround this work. For in spite of the extensive attention the work has received in the past fifty years, especially in the philosophical literature, misunderstandings of both conceptual and historical sorts are still remarkably widespread. Indeed in the philosophical community, recent reactions to Tarski's work on truth range from Karl Popper's “intense joy and relief” at Tarski's “legitimation” of the notion [1974, p. 399], to Hilary Putnam's assessment that “as a philosophical account of truth, Tarski's theory fails as badly as it is possible for an account to fail” [1985, p. 64]. Opinions have not exactly converged.

Let L be one of the topological languages Lt, (L∞ω)t and (Lκω)t. We characterize the topological spaces which are models of the L-theory of the class of ordinals equipped with the order topology. The results show that the role played in classical model theory by the property of being well-ordered is taken over in the topological context by the property of being locally compact and scattered.

In his published work and even more in conversations, Tarski emphasized what he thought were important philosophical aspects of his work. The English translation of his more philosophical papers [56m] was dedicated to his teacher Tadeusz Kotarbiński, and in informal discussions of philosophy he often referred to the influence of Kotarbiński. Also, the influence of Leśniewski, his dissertation adviser, is evident in his early papers. Moreover, some of his important papers of the 1930s were initially given to philosophical audiences. For example, the famous monograph on the concept of truth ([33m], [35b]) was first given as two lectures to the Logic Section of the Philosophical Society in Warsaw in 1930. Second, his paper [33], which introduced the concepts of ω-consistency and ω-completeness as well as the rule of infinite induction, was first given at the Second Conference of the Polish Philosophical Society in Warsaw in 1927. Also [35c] was based upon an address given in 1934 to the conference for the Unity of Science in Prague; [36] and [36a] summarize an address given at the International Congress of Scientific Philosophy in Paris in 1935. The article [44a] was published in a philosophical journal and widely reprinted in philosophical texts. This list is of course not exhaustive but only representative of Tarski's philosophical interactions as reflected in lectures given to philosophical audiences, which were later embodied in substantial papers. After 1945 almost all of Tarski's publications and presentations are mathematical in character with one or two minor exceptions. This division, occurring about 1945, does not, however, indicate a loss of interest in philosophical questions but is a result of Tarski's moving to the Department of Mathematics at Berkeley. There he assumed an important role in the development of logic within mathematics in the United States.

We prove that cons(ZF) implies cons(ZF + Borel conjecture + there exists a Ramsey ultrafilter). We also prove some results on strong measure zero sets from the existence of generalized Luzin sets. We study the relationships between strong measure zero sets and rapid filters on ω.

We prove optimal lower bounds on the computation time for several well-known test problems on a quite realistic computational model: the random access machine. These lower bound arguments may be of special interest for logicians because they rely on finitary analogues of two important concepts from mathematical logic: inaccessible numbers and order indiscernibles.

A recursively enumerable splitting of an r.e. set A is a pair of r.e. sets B and C such that A = B ∪ C and B ∩ C = ⊘. Since for such a splitting deg A = deg B ∪ deg C, r.e. splittings proved to be a quite useful notion for investigations into the structure of the r.e. degrees. Important splitting theorems, like Sacks splitting [S1], Robinson splitting [R1] and Lachlan splitting [L3], use r.e. splittings.

Since each r.e. splitting of a set induces a splitting of its degree, it is natural to study the relation between the degrees of r.e. splittings and the degree splittings of a set. We say a set A has the strong universal splitting property (SUSP) if each splitting of its degree is represented by an r.e. splitting of itself, i.e., if for deg A = b ∪ c there is an r.e. splitting B, C of A such that deg B = b and deg C = c. The goal of this paper is the study of this splitting property.

In the literature some weaker splitting properties have been studied as well as splitting properties which imply failure of the SUSP.

§0. Introduction and material background. The present paper is devoted to the study of intermediate propositional logics, and it is based on [Be, §§1 and 2].

§2 (§§0 and 1 are introductory) concerns the axiomatization of finite logics. In the literature several effective procedures to axiomatize finite logics are present (cf., for instance, [MK] and [Wr]), but, in each case, the number of propositional variables which are used is redundant. In this direction, Theorem 2.2 provides (a) a criterion to determine, given a finite logic L, the least n such that L is axiomatizable by formulas in n variables, and (b) an effective axiomatization by an n-formula. As a corollary we obtain a negative answer to Problem 7.10 of [Ho/On], showing that there is no connection between the slice to which L belongs and the number of propositional variables necessary to axiomatize L.

The principal results of the paper are in §3. In fact, a great deal of research has been done on the correspondence between conditions on the relation of Kripke-structures from one side, and axioms added to Int from the other. In this section we (a) introduce the concept of finitely separable class of Kripke-frames, and show, by means of several examples, that this concept is “wide”, in the sense that all the most studied classes of frames determined by semantical conditions are finitely separable; (b) show that each finitely separable class is axiomatizable, and that the axioms can be found by means of semantical considerations only; and (c) establish the finite model property for all the finitely separable logics.

As a contribution to definability theory in the spirit of Tarski's classical work on (R, <, 0, 1, +, ·) we extend here part of his results to the structure

Here exp ∣[0, 1] and sin ∣[0, π] are the restrictions of the exponential and sine function to the closed intervals indicated; formally we identify these restricted functions with their graphs and regard these as binary relations on R. The superscript “RE” stands for “restricted elementary” since, given any elementary function, one can in general only define certain restrictions of it in RRE.

Let (RRE, constants) be the expansion of RRE obtained by adding a name for each real number to the language. We can now formulate our main result as follows.

Theorem. (RRE, constants) is strongly model-complete.

This means that every formula ϕ(X1, …, Xm) in the natural language of (RRE, constants) is equivalent to an existential formula

with the extra property that for each x ∈ Rm such that ϕ(x) is true in RRE there is exactly one y ∈ Rn such that ψ(x, y) is true in RRE. (Here ψ is quantifier free.)

In this paper we consider the problem of lifting properties of the Fréchet ideal Iκ = {X ⊆ κ: ∣X∣ < κ} on a regular uncountable cardinal κ, to an analogue about Iκλ , the ideal of not unbounded subsets of Pκλ. With this in mind, in §1 we introduce and study the class of seminormal λ-generated ideals on Pκλ. We shall see that ideals belonging to this class display properties which are clearly analogous to those of the Fréchet ideal on κ (for instance, with regard to saturation, normality and weak selectivity) and yet are closely related to Iκλ . Our results here show that if λ<λ = λ, then many restrictions of Iκλ are weakly selective, nowhere precipitous and, quite suprisingly, seminormal (but nowhere normal). These latter two results suggest the question of whether any restriction of Iκλ can ever be normal. In §2 we prove that if κ is strongly inaccessible, λ<κ = 2 λ and NS κλ , the ideal of nonstationary subsets of Pκλ, has a mild selective property, then NS κλ ∣A = Iκλ ∣A for some stationary A ⊆ Pκλ.

In [1] Baumgartner showed that if κ is weakly compact and P is the collection of indescribable subsets of κ, then P → (P, κ)2. As a Pκλ analogue of indescribability, Carr (see [3]–[5]) introduced the λ-Shelah property, but was unable to derive the natural Pκλ analogue of Baumgartner's result, (where NSh κλ is the normal ideal on Pκλ induced by the λ-Shelah property). In §3 we show that the problem lies in the fact that, as far as we know, NSh κλ is not sufficiently distributive, and derive conditions which are sufficient and, in a sense, necessary to yield partitions related to .

It is shown that if κ is an uncountable successor cardinal in L[0#], then there is a normal tree T ϵ L[0#] of height κ such that 0# ∉ L[T], yet T is < κ-distributive in L[0#]. A proper class version of this theorem yields an analogous L[0#]-definable tree such that distinct branches in the presence of 0# collapse the universe. A heretofore unutilized method for constructing in L[0#] generic objects for certain L-definable forcings and “exotic sequences”, combinatorial principles introduced by C. Gray, are used in constructing these trees.

In his Singular points of complex hypersurfaces Milnor proves the following “curve selection lemma” [10, p. 25]:

Let V ⊂ R m be a real algebraic set, and let U ⊂ R m be an open set defined by finitely many polynomial inequalities:

Lemma 3.1. If U ∩ V contains points arbitrarily close to the origin (that is if 0 ∈ Closure (U ∩ V)) then there exists a real analytic curve

with p(0) = 0 and with p(t) ∈ U ∩ V for t > 0.

Of course, this result will also apply to semialgebraic sets (finite unions of sets U ∩ V), and by Tarski's theorem such sets are exactly the sets obtained from real varieties by means of the finite Boolean operations and the projection maps R n+1 → R n . If, in this tiny extension of Milnor's result, we replace ‘R’ everywhere by ‘Q p ’, we obtain a p-adic curve selection lemma, a version of which we will prove in this essay. Semialgebraic sets, in the p-adic context, may be defined just as they are over the reals: namely, as those sets obtained from p-adic varieties by means of the finite Boolean operations and the projection maps . Analytic maps are maps whose coordinate functions are given locally by convergent power series.

In the paper mentioned in the title (this Journal, vol. 52 (1987), pp. 208–213), it is shown that if ⊨ “V = HC is recursively inaccessible” is ω-standard -nonstandard, then = s.p.() has at most four r. e. degrees. They are 0 = deg(∅), = deg{e ∣ We is a recursive well-ordering of ω}, = deg{R ∣ ⊨ “R codes a well-ordering”}, and ∨ . Furthermore, 0 < < ∨ and 0 < . Then it is claimed that < < ∨ and = ∨ if are each possible. In fact, < < ∨ always.

The mistake in the argument is that the model ≤ T is really a structure on a set, which we may as well take as ω: there is an R ⊆ ω × ω, R ≤ T , and ‹ω, R› ≃ . So a copy of coded as a relation on ω is ≤ over . But there is no reason to think that the restriction of the isomorphism of and ‹ω, R› to is Σ 1().

Baur a défini la notion d'extension séparée de corps valués et montré que toute extension d'un corps maximal est séparée. Nous prouvons que, si (K, υ) est henselien et de caractéristique résiduelle nulle, alors (K, υ) ⊂ (L, w) est séparée ssi L est linéairement disjoint sur K de toute extension immédiate de K.

Separated and immediate extensions of valued fields. The notion of separated extension of valued fields was introduced by Baur. He showed that extensions of maximal fields are separated. We prove that, when (K, υ) is Henselian with residual characteristic 0, then (K, υ) ⊂ (L, w) is separated iff L is linearly disjoint over K from each immediate extension of K.

Let M be an o-minimal structure or a p-adically closed field. Let be the space of complete n-types over M equipped with the following topology: The basic open sets of are of the form Ũ = {p ∈ Sn (M): U ∈ p} for U an open definable subset of Mn . is a spectral space. (For M = K a real closed field, is precisely the real spectrum of K[X 1, …, Xn ]; see [CR].) We will equip with a sheaf of LM -structures (where LM is a suitable language). Again for M a real closed field this corresponds to the structure sheaf on (see [S]). Our main point is that when Th(M) has definable Skolem functions, then if p ∈ , it follows that M(p), the definable ultrapower of M at p, can be factored through Mp , the stalk at p with respect to the above sheaf. This depends on the observation that if M ≺ N, a ∈ Nn and f is an M-definable (partial) function defined at a, then there is an open M-definable set U ⊂ Nn with a ∈ U, and a continuous M-definable function g:U → N such that g(a) = f(a).

In the case that M is an o-minimal expansion of a real closed field (or M is a p-adically closed field), it turns out that M(p) can be recovered as the unique quotient of Mp which is an elementary extension of M.

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.

If θ is any singular cardinal of cofinality ω 1, we produce a forcing extension in which MA holds below θ but fails at θ. The failure is due to a partial order which splits a gap of size θ in .

A dilator D is a functor from ON to itself commuting with direct limits and pull-backs. A dilator D is a flower iff D(x) is continuous. A flower F is regular iff F(x) is strictly increasing and F(f)(F(z)) = F(f(z)) (for f ϵ ON(x,y), z ϵ X).

Equalization is the following axiom: if F, G ϵ Flr (class of regular flowers), then there is an H ϵ Flr such that F ° H = G ° H. From this we can deduce that if ℱ is a set ⊆ Flr, then there is an H ϵ Flr which is the smallest equalizer of ℱ (it can be said that H equalizes ℱ iff for every F, G ϵ ℱ we have F ° H = G ° H). Equalization is not provable in set theory because equalization for denumerable flowers is equivalent to -determinacy (see a forthcoming paper by Girard and Kechris).

Therefore it is interesting to effectively find, by elementary means, equalizers even in the simplest cases. The aim of this paper is to prove Girard and Kechris's conjecture: “ is the (smallest) equalizer for Flr < ω” (where Flr < ω denotes the set of finite regular flowers). We will verify that is an equalizer of Flr < ω; we will sketch the proof that it is the smallest one at the end of the paper. We will denote by H.