The completeness proof for first-order logic by Rasiowa and Sikorski [13] is a simplification of Henkin's proof [7] in that it avoids the addition of infinitely many new individual constants. Instead they show that each consistent set of formulae can be extended to a maximally consistent set, satisfying the following existence property: if it contains (∃x)ϕ it also contains some substitution ϕ(y/x) of a variable y for x. In Feferman's review [5] of [13], an improvement, due to Tarski, is given by which the proof gets a simple algebraic form.

Sambin [16] used the same method in the setting of formal topology [15], thereby obtaining a constructive completeness proof. This proof is elementary and can be seen as a constructive and predicative version of the one in Feferman's review. It is a typical, and simple, example where the use of formal topology gives constructive sense to the existence of a generic object, satisfying some forcing conditions; in this case an ultrafilter satisfying the existence property.

In order to get a formal topology on the set of first-order formulae, Sambin used the Dedekind-MacNeille completion to define a covering relation ⊲DM. This method, by which an arbitrary poset can be extended to a complete poset, was introduced by MacNeille [9] and is a generalization of the construction of real numbers from rationals by Dedekind cuts. It is also possible to define an inductive cover, ⊲I, on the set of formulae, which can also be used to give canonical models, see Coquand and Smith [3].

Using projectivity groups, we classify some polygons with strongly minimal point rows and show in particular that no infinite quadrangle can have sharply 2-transitive projectivity groups in which the point stabilizers are abelian. In fact, we characterize the finite orthogonal quadrangles Q(4,2). Q− (5.2) and Q(4,3) by this property. Finally we show that the sets of points, lines and flags of any ℵ1-categorical polygon have Morley degree 1.

§1. Introduction. Russell's type-theory can be seen as a theory of properties, relations, and propositions (PRPs) (in short, a property theory). It relies on rigid type distinctions at the grammatical level to circumvent the property theorist's major problem, namely Russell's paradox, or, more generally, the paradoxes of predication. Type theory has arguably been the standard property theory for years, often taken for granted, and used in many applications. In particular, Montague [27] has shown how to use a type-theoretical property-theory as a foundation for natural language semantics.

In recent years, it has been persuasively argued that many linguistic and ontological data are best accounted for by using a type-free property theory. Several type-free property theories, typically with fine-grained identity conditions for PRPs, have therefore been proposed as potential candidates to play a foundational role in natural language semantics, or for related applications in formal ontology and the foundations of mathematics (Bealer [6], Cocchiarella [18], Turner [35], etc.).

Attempts have then been made to combine some such property theory with a Montague-style approach in natural language semantics. Most notably, Chierchia and Turner [15] propose a Montague-style semantic analysis of a fragment of English, by basically relying on the type-free system of Turner [35]. For a similar purpose Chierchia [14] relies on one of the systems based on homogeneous stratification due to Cocchiarella. Cocchiarella's systems have also been used for applications in formal ontology, inspired by Montague's account of quantifier phrases as, roughly, properties of properties (see, e.g., Cocchiarella [17], [19], Landini [25], Orilia [29]).

We introduce a new framework for asymptotic probabilities of sentences, in which we have a σ-additive measure on the sample space of all sequences A = {} of finite models, where the universe of is {1,2, …, n}. and use this framework to strengthen 0-1 laws for logics.

We present a variety of (ω, ∞)-distributive forcings which when applied to models of Martin's Maximum separate certain well known reflection principles. In particular, we do this for the reflection principles SR, SRα (α ≤ ω1), and SRP.

Several attempts have been done to distinguish “positive” information in an arbitrary first order theory, i.e., to find a well behaved class of closed sets among the definable sets. In many cases, a definable set is said to be closed if its conjugates are sufficiently distinct from each other. Each such definition yields a class of theories, namely those where all definable sets are constructible, i.e., boolean combinations of closed sets. Here are some examples, ordered by strength:

Weak normality describes a rather small class of theories which are well understood by now (see, for example, [P]). On the other hand, normalization is so weak that all theories, in a suitable context, are normalizable (see [HH]). Thus equational theories form an interesting intermediate class of theories. Little work has been done so far. The original work of Srour [S1, S2, S3] adopts a point of view that is closer to universal algebra than to stability theory. The fundamental definitions and model theoretic properties can be found in [PS], though some easy observations are missing there. Hrushovski's example of a stable non-equational theory, the first and only one so far, is described in the unfortunately unpublished manuscript [HS]. In fact, it is an expansion of the free pseudospace constructed independently by Baudisch and Pillay in [BP] as an example of a strictly 2-ample theory. Strong equationality, defined in [Hr], is also investigated in [HS].

If G is an omega-stable group with a normal definable subgroup H, then the Sylow-2-subgroups G/H are the images of the Sylow-2-subgroups of G.

Zusammenfassung. Sei G eine omega-stabile Gruppe und H ein definierbarer Normalteiler von G. Dann sind die Sylow-2-Untergruppen von G/H Bilder der Sylow-2-Untergruppen von G.

We characterise explicitly the decidable predicates on integers of Infinite Time Turing machines, in terms of admissibility theory and the constructible hierarchy. We do this by pinning down ζ, the least ordinal not the length of any eventual output of an Infinite Time Turing machine (halting or otherwise); using this the Infinite Time Turing Degrees are considered, and it is shown how the jump operator coincides with the production of mastercodes for the constructible hierarchy; further that the natural ordinals associated with the jump operator satisfy a Spector criterion, and correspond to the Lζ-stables. It also implies that the machines devised are “Σ2 Complete” amongst all such other possible machines. It is shown that least upper bounds of an “eventual jump” hierarchy exist on an initial segment.

In this paper we prove the equiconsistency of “Every ω1 –tree which is first order definable over (, ε) has a cofinal branch” with the existence of a reflecting cardinal. We also prove that the addition of MA to the definable tree property increases the consistency strength to that of a weakly compact cardinal. Finally we comment on the generalization to higher cardinals.

We present two different types of models where, for certain singular cardinals λ of uncountable cofinality, λ → (λ, ω + 1)2, although λ is not a strong limit cardinal, We announce, here, and will present in a subsequent paper, [7], that, for example, consistently, and consistently, .

Some cardinal invariants from Cichoń's diagram can be characterized using the notion of cut-and-choose games on cardinals. In this paper we give another way to characterize those cardinals in terms of infinite games. We also show that some properties for forcing, such as the Sacks Property, the Laver Property and ωω-boundingness, are characterized by cut-and-choose games on complete Boolean algebras.

Let Π be a complete théorie of pseudo-finite fields. In this article we prove that, in the langage of fields to which we add a unary predicate for a substructure, the theory of non trivial elementary pairs of models of Π has completions, that is, the maximum that could exist.

For a theory T in L, Tσ is the theory of the models of T with an automorphism σ. If T is an unstable model complete theory without the independence property, then Tσ has no model companion. If T is an unstable model complete theory and Tσ has the amalgamation property, then Tσ has no model companion. If T is model complete and has the fcp, then Tσ has no model completion.

Preferential structures are probably the best examined semantics for nonmonotonic and deontic logics: in a wider sense, they also provide semantical approaches to theory revision and update, and other fields where a preference relation between models is a natural approach. They have been widely used to differentiate the various systems of such logics, and their construction is one of the main subjects in the formal investigation of these logics. We introduce new techniques to construct preferential structures for completeness proofs. Since our main interest is to provide general techniques, which can be applied in various situations and for various base logics (propositional and other), we take a purely algebraic approach, which can be translated into logics by easy lemmata, in particular, we give a clean construction via indexing by trees for transitive structures, this allows us to simplify the proofs of earlier work by the author, and to extend the results given there.

Suppose λ is a singular cardinal of uncountable cofinality κ. For a model of cardinality λ, let No() denote the number of isomorphism types of models of cardinality λ which are L∞λ-equivalent to . In [7] Shelah considered inverse κ-systems of abelian groups and their certain kind of quotient limits Gr()/ Fact(). In particular Shelah proved in [7, Fact 3.10] that for every cardinal Μ there exists an inverse κ-system such that consists of abelian groups having cardinality at most Μκ and card(Gr()/ Fact()) = Μ. Later in [8, Theorem 3.3] Shelah showed a strict connection between inverse κ-systems and possible values of No (under the assumption that θκ < λ for every θ < λ): if is an inverse κ-system of abelian groups having cardinality < λ, then there is a model such that card() = λ and No() = card(Gr()/ Fact()). The following was an immediate consequence (when θκ < λ for every θ < λ): for every nonzero Μ < λ or Μ = λκ there is a model , of cardinality λ with No() = Μ. In this paper we show: for every nonzero Μ ≤ λκ there is an inverse κ-system of abelian groups having cardinality < λ such that card(Gr()/ Fact()) = Μ (under the assumptions 2κ < λ and θ<κ < λ for all θ < λ when Μ > λ), with the obvious new consequence concerning the possible value of No. Specifically, the case No() = λ is possible when θκ > λ for every λ < λ.

We study the following classes:

● Q* (r1A1…..rkAk) which is defined to be the collection of all sets that can be computed by a Turing machine that on any input makes a total of ri, queries to Ai, for all i ∈ {1..… k}.

● Q(r1A1…..rkAk) which is defined like Q* (r1A1….. rkAk) except that queries to Ai, must be made before queries to Ai+1 for all i ∈ {1….. k – 1}.

● QC(r1A1….. rkAk) which is defined like Q{r1A1….. rkAk) except that the Turing machine must halt even if given incorrect answers to some of its queries.

We show that if A1 ….. Ak are jumps that are not too close together, then all three of these classes are identical and are not changed if we permute (r1…..rkAk). This extends a result of Beigel's [1]. Since the second class is not affected by permutations, we say that these sets commute with each other. We also show that jumps that are too close together may not commute. We also characterize the commutative sequences of sets obtained by iterating the jump operation through an ordinal notation.

The relationship between killing ideals and adding reals by forcings is analysed.

We define classes Φn of formulae of first-order arithmetic with the following properties:

(i) Every φ ϵ Φn is classically equivalent to a Πn-formula (n ≠ 1, Φ1 := Σ1).

(ii)

(iii) IΠn and iΦn (i.e., Heyting arithmetic with induction schema restricted to Φn-formulae) prove the same Π2-formulae.

We further generalize a result by Visser and Wehmeier. namely that prenex induction within intuitionistic arithmetic is rather weak: After closing Φn both under existential and universal quantification (we call these classes Θn) the corresponding theories iΘn still prove the same Π2-formulae. In a second part we consider iΔ0 plus collection-principles. We show that both the provably recursive functions and the provably total functions of are polynomially bounded. Furthermore we show that the contrapositive of the collection-schema gives rise to instances of the law of excluded middle and hence .

We prove that each Σ20 set which is hypersimple relative to ∅′ is noncuppable in the structure of the Σ20 enumeration degrees. This gives a connection between properties of Σ20 sets under inclusion and and the Σ20 enumeration degrees. We also prove that some low non-computably enumerable enumeration degree contains no set which is simple relative to ∅′.

There are properties of finite structures that are expressible with the use of Hilbert's ∈-operator in a manner that does not depend on the actual interpretation for ∈-terms. but not expressible in plain first-order. This observation strengthens a corresponding result of Gurevich, concerning the invariant use of an auxiliary ordering in first-order logic over finite structures. The present result also implies that certain non-deterministic choice constructs, which have been considered in database theory, properly enhance the expressive power of first-order logic even as far as deterministic queries are concerned, thereby answering a question raised by Abiteboul and Vianu.