Hrushovski's generalization of the Fraisse construction has provided a rich source of examples in model theory, model theoretic algebra and random graph theory. The construction assigns to a dimension function δ and a class K of finite (finitely generated) models a countable ‘generic’ structure. We investigate here some of the simplest possible cases of this construction. The class K will be a class of finite graphs; the dimension, δ(A), of a finite graph A will be the cardinality of A minus the number of edges of A. Finally and significantly we restrict to classes which are δ-invariant. A class of finite graphs is δ-invariant if membership of a graph in the class is determined (as specified below) by the dimension and cardinality of the graph, and dimension and cardinality of all its subgraphs. Note that a generic graph constructed as in Hrushovski's example of a new strongly minimal set does not arise from a δ-invariant class.

We show there are countably many δ-invariant (strong) amalgamation classes of finite graphs which are closed under subgraph and describe the countable generic models for these classes. This analysis provides ω-stable generic graphs with an array of saturation and model completeness properties which belies the similarity of their construction. In particular, we answer a question of Baizhanov (unpublished) and Baldwin [5] and show that this construction can yield an ω-stable generic which is not saturated. Further, we exhibit some ω-stable generic graphs that are not model complete.

Let M be a countably infinite ω-categorical structure. Consider Aut(M) as a complete metric space by defining d(g, h) = Ω{2−n: g (xn) ≠ h(xn) or g−1 (xn) ≠ h−1 (xn)} where {xn : n ∈ ω} is an enumeration of M An automorphism α ∈ Aut(M) is generic if its conjugacy class is comeagre. J. Truss has shown in [11] that if the set P of all finite partial isomorphisms contains a co-final subset P1 closed under conjugacy and having the amalgamation property and the joint embedding property then there is a generic automorphism. In the present paper we give a weaker condition of this kind which is equivalent to the existence of generic automorphisms. Really we give more: a characterization of the existence of generic expansions (defined in an appropriate way) of an ω-categorical structure. We also show that Truss' condition guarantees the existence of a countable structure consisting of automorphisms of M which can be considered as an atomic model of some theory naturally associated to M. We do it in a general context of weak models for second-order quantifiers.

The author thanks Ludomir Newelski for pointing out a mistake in the first version of Theorem 1.2 and for interesting discussions. Also, the author is grateful to the referee for very helpful remarks.

Many known tools for proving expressibility bounds for first-ordér logic are based on one of several locality properties. In this paper we characterize the relationship between those notions of locality. We note that Gaifman's locality theorem gives rise to two notions: one deals with sentences and one with open formulae. We prove that the former implies Hanf's notion of locality, which in turn implies Gaifman's locality for open formulae. Each of these implies the bounded degree property, which is one of the easiest tools for proving expressibility bounds. These results apply beyond the first-order case. We use them to derive expressibility bounds for first-order logic with unary quantifiers and counting. We also characterize the notions of locality on structures of small degree.

Recently Lafont [6] showed the finite model property for the multiplicative additive fragment of linear logic (MALL) and for affine logic (LLW), i.e., linear logic with weakening. In this paper, we shall prove the finite model property for intuitionistic versions of those, i.e. intuitionistic MALL (which we call IMALL), and intuitionistic LLW (which we call ILLW). In addition, we shall show the finite model property for contractive linear logic (LLC), i.e., linear logic with contraction. and for its intuitionistic version (ILLC). The finite model property for related substructural logics also follow by our method. In particular, we shall show that the property holds for all of FL and GL−-systems except FLc and of Ono [11], that will settle the open problems stated in Ono [12].

In this paper, we show that there is no primitive recursive decision procedure for the implication-conjunction fragments of the relevant logics R, E and T, as well as for a family of related logics. The lower bound on the complexity is proved by combining the techniques of an earlier paper on the same subject [20] with a method used by Lincoln, Mitchell, Scedrov and Shankar in proving that propositional linear logic is undecidable.

The decision problem for the pure implicational fragments of E and R were solved by Saul Kripke in a tour de force of combinatorial reasoning, published only as an abstract [9]. Belnap and Wallace extended Kripke's decision procedure to the implication-negation fragment of E in [3]; an account of their decision method is to be found in [1, pp. 124–139]. The decision method extends immediately to the implication/negation fragment of R. In fact, in the case of R we can go farther: Meyer in his thesis [13] showed how to translate the logic LR, which results from R by omitting the distribution axiom, into R→⋀, so that the decision procedure can be extended to all of LR. This decision procedure has been implemented as a program Kripke by Thistlewaite, McRobbie and Meyer [17]. The program is not simply a straightforward implementation of the decision procedure; finite matrices are used extensively to prune invalid nodes from the search tree.

A notion of complexity for an arbitrary structure was defined in the book of Poizat Les petits cailloux (1995): we can define P and NP problems over a differential field K. Using the Witness Theorem of Blum et al., we prove the P-stability of the theory of differential fields: a P problem over a differential field K is still P when restricts to a sub-differential field k of K. As a consequence, if P = NP over some differentially closed field K, then P = NP over any differentially closed field and over any algebraically closed field.

In this paper a class of simple theories, called the low theories is developed, and the following is proved.

Theorem. Let T be a low theory, A a set and a, b elements realizing the same strong type over A. Then, a and b realize the same Lasear strong type over A.

We show that it is consistent with ZFC + ¬CH that there is a maximal cofinitary group (or, maximal almost disjoint group) G ≤ Sym(ω) such that G is a proper subset of an almost disjoint family A ⊆ Sym(ω) and ‖G‖ < ‖A‖. We also ask several questions in this area.

The class of all Artinian local rings of length at most l is ∀2-elementary, axiomatised by a finite set of axioms τtl. We show that its existentially closed models are Gorenstein. of length exactly l and their residue fields are algebraically closed, and, conversely, every existentially closed model is of this form. The theory oτl of all Artinian local Gorenstein rings of length l with algebraically closed residue field is model complete and the theory τtl is companionable, with model-companion oτl.

We investigate the system TRC of untyped illative combinatory logic that is equiconsistent with New Foundations. We prove that various unstratified combinators do not exist in TRC.