bluuebunny/crossref_metadata_2025 huggingface dataset:
Coinductive ℵ0-categorical theories
Authors: Schmerl James H.
Published: May 2006

Let L be a countable language which contains only constant and relation symbols but no function symbols. All theories considered here will be L-theories. A theory is coinductive if it can be axiomatized by a set of ∃∀ sentences, and a structure is coinductive if its theory is.

The object of this paper is to show that coinductive ℵ0-categorical structures are especially simple. First, they are ω-stable with Morley rank ≤ 1; and second, they have simple algebraic closures, by which is meant that the algebraic closure of the union of two sets is the union of their algebraic closures. While these two properties do not characterize coinductive ℵ0-categorical structures, they do characterize those structures which are cellular.

We will say that a countable structure is cellular if there is a finite subset A0 ⊆ A and there are equivalence relations E and F on A∖A0 such that the following hold:

(1) There are only finitely many E-classes.

(2) If C is an E-class and D an F-class, then ∣C ∩ D ∣ = 1.

(3) If a0, a1, …, ak − 1, b0, b1, …, bk − 1 Є A, then 〈a0, a1, …,ak − 1〉 and 〈b0,b1, …, bk − 1〉, satisfy the same quantifier-free formulas provided that:

(a) if i < k and either ai Є A0 or bi Є A0, then ai = bi;

(b) if i < k, then ai; and bi are E-equivalent; and

(c) if i, j < k, then ai; is F-equivalent to aj if bj is F-equivalent to bj.

The main result of this paper is the following theorem.

Theorem 1. Ifis coinductive and ℵ0-categorical, thenis cellular.

The results of this paper were obtained independently of similar results obtained by Lachlan which can be found in [4] and [5]. The proofs here are quite different.
Addendum to “The truth is never simple”
Authors: Burgess John P.
Published: May 2006

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.
Cardinality logics. Part II: Definability in languages based on ‘exactly’
Authors: Hodes Harold
Published: May 2006

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.”
Definability and initial segments of c-degrees
Authors: Lubarsky Robert S.
Published: May 2006

We combine two techniques of set theory relating to mininal degrees of constructibility. Jensen constructed a minimal real which is additionally a singleton. Groszek built an initial segment of order type 1 + α*, for any ordinal α. This paper shows how to force a singleton such that the c-degrees beneath it, all represented by reals, are of type 1 + α*, for many ordinals α. We also examine the definability α needs to be so represented by a real.
Degree theoretical splitting properties of recursively enumerable sets
Authors: Ambos-Spies Klaus , Fejer Peter A.
Published: May 2006

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.
Weak cylindric set algebras and weak subdirect indecomposability
Authors: Andréka H. , Németi I. , Thompson R. J.
Published: May 2006

In this note we prove that the abstract property “weakly subdirectly indecomposable” does not characterize the class IWsα of weak cylindric set algebras. However, we give another (similar) abstract property characterizing IWsα. The original property does characterize the directed unions of members of IWsα iff α is countable. Free algebras will be shown to satisfy the original property.
Infinitary combinatorics and modal logic
Authors: Blass Andreas
Published: May 2006

We show that the modal propositional logic G, originally introduced to describe the modality “it is provable that”, is also sound for various interpretations using filters on ordinal numbers, for example the end-segment filters, the club filters, or the ineffable filters. We also prove that G is complete for the interpretation using end-segment filters. In the case of club filters, we show that G is complete if Jensen's principle □κ holds for all κ < ℵω; on the other hand, it is consistent relative to a Mahlo cardinal that G be incomplete for the club filter interpretation.
Intuitionistic modal logic and set theory
Authors: Lano K.
Published: May 2006

The mathematical treatment of the concepts of vagueness and approximation is of increasing importance in artificial intelligence and related research. The theory of fuzzy sets was created by Zadeh [Z] to allow representation and mathematical manipulation of situations of partial truth, and proceeding from this a large amount of theoretical and applied development of this concept has occurred. The aim of this paper is to develop a natural logic and set theory that is a candidate for the formalisation of the theory of fuzzy sets. In these theories the underlying logic of properties and sets is intuitionistic, but there is a subset of formulae that are ‘crisp’, classical and two-valued, which represent the certain information. Quantum logic or logics weaker than intuitionistic can also be adopted as the basis, as described in [L]. The relationship of this theory to the intensional set theory MZF of [Gd] and the global intuitionistic set theory GIZF of Takeuti and Titani [TT] is also treated.
Some properties of the syntactic p-recursion categories generated by consistent, recursively enumerable extensions of Peano arithmetic.
Authors: Paola Robert A. Di , Montagna Franco
Published: May 2006

The dominical categories were introduced by Di Paola and Heller, as a first step toward a category-theoretic treatment of the generalized first Godel incompleteness theorem [1]. In his Ph.D. dissertation [7], Rosolini subsequently defined the closely related p-categories, which should prove pertinent to category-theoretic representations of incompleteness for intuitionistic systems. The precise relationship between these two concepts is as follows: every dominical category is a pointed p-category, but there are p-categories, indeed pointed p-isotypes (all pairs of objects being isomorphic) with a Turing morphism that are not dominical. The first of these assertions is an easy consequence of the fact that in a dominical category C by definition the near product functor when restricted to the subcategory Ct, of total morphisms of C (as “total” is defined in [1]) constitutes a bona fide product such that the derived associativity and commutativity isomorphisms are natural on C × C × C and C × C, respectively, as noted in [7]. As to the second, p-recursion categories (that is, pointed p-isotypes having a Turing morphism) that are not dominical were defined and studied by Montagna in [6], the syntactic p-categories ST and S′T associated with consistent, recursively enumerable extensions of Peano arithmetic, PA. These merit detailed investigation on several counts.
Saturating ultrafilters on N
Authors: Fremlin D. H. , Nyikos P. J.
Published: May 2006

We discuss saturating ultrafilters on N, relating them to other types of non-principal ultrafilter. (a) There is an (ω,c)-saturating ultrafllter on N iff 2λ≤ c for everyλ <c and there is no cover ofRby fewer than c nowhere dense sets, (b) Assume Martin's axiom. Then, for any cardinalκ, a nonprincipal ultrafllter on N is (ω, κ)-saturating iff it is almostκ-good. In particular, (i)p(κ)-point ultrafilters are (ω, κ)-saturating, and (ii) the set of (ω, κ)-saturating ultrafilters is invariant under homeomorphisms ofβN/N. (c) It is relatively consistent with ZFC to suppose that there is a Ramseyp(c)-point ultrafilter which is not (ω, c)-saturating.
Diverse classes
Authors: Baldwin John T.
Published: May 2006

Let I(μ, Κ) denote the number of nonisomorphic models of power μ and IE(μ, Κ) the number of nonmutually embeddable models. We define in this paper the notion of a diverse class and use it to prove a number of results. The major result is Theorem B: For any diverse class Κ and μ greater than the cardinality of the language of Κ,

From it we deduce both an old result of Shelah, Theorem C: If T is countable and λ0 > ℵ0 then for every μ > ℵ0, IE(μ, T) ≥ min(2μ, ⊐2), and an extension of that result to uncountable languages, Theorem D: If ∣T∣ < 2ωλ0 > ∣T∣, and ∣D(T)∣ = ∣T∣ then for μ > ∣T∣,
On hyper-torre isols
Authors: Downey Rod
Published: May 2006

As Dekker [3] suggested, certain fragments of the isols can exhibit an arithmetic rather more resembling that of the natural numbers than the general isols do. One such natural fragment is Barback's “tame models” (cf. [2], [6] and [7]), whose roots go back to Nerode [8]. In this paper we study another variety of such fragments: the hyper-torre isols introduced by Ellentuck [4]. Let Y denote an infinite isol with D(Y) the collection of all isols A ≤ f∧(Y) for some recursive and combinational unary function f. (Here, as usual, f∧ is the Myhill-Nerode extension of f to the isols).
Uniformization principles
Authors: Mekler Alan H. , Shelah Saharon
Published: May 2006

It is consistent that for many cardinals λ there is a family of at least λ+ unbounded subsets of λ which have uniformization properties. In particular if it is consistent that a supercompact cardinal exists, then it is consistent that ℵω has such a family. We have applications to point set topology, Whitehead groups and reconstructing separable abelian p-groups from their socles.
Sacks forcing sometimes needs help to produce a minimal upper bound
Authors: Lubarsky Robert S.
Published: May 2006

Does every countable set of hyperdegrees have a minimal upper bound?

This question remains unanswered. In this paper, we extend the known results.

The standard way to construct minimal upper bounds for degrees is to force with pointed perfect trees. This works for hyperdegrees, in the right context. Sacks [Sa] showed that if an admissible set A satisfies Σ1 DC, then forcing with its uniformly hyperarithmetically pointed perfect trees yields a minimal upper bound for the degrees in A.

A next question is whether Σ1DC is necessary. Abramson [A] built an admissible set such that Sacks forcing, or anything like it, would not produce a minimal upper bound. He left open the question, though, whether there is such a bound for his set.

We answer this question affirmatively.

In §II we summarize the previous relevant results, including Steel forcing. In §III we give a construction different from Abramson's of an admissible set for which Sacks forcing does not produce the desired bound. We present this alternative because it is different (although still based on Steel forcing), simpler than the original, and fully illustrates the technique of finding the bound, which applies equally well to the earlier example. §IV describes the construction of the bound. §V closes with questions.

I thank Professor Sy Friedman for bringing this problem to my attention. This paper is dedicated to Professor Alexander Kechris on the occasion of his fortieth birthday, and to the Los Angeles VIGOL on its tenth anniversary.
Powers of the ideal of Lebesgue measure zero sets
Authors: Burke Maxim R.
Published: May 2006

We investigate the cofinality of the partial order κ of functions from a regular cardinal κ into the ideal of Lebesgue measure zero subsets of R. We show that when add () = κ and the covering lemma holds with respect to an inner model of GCH, then cf (κ) = max{cf(κκ), cf([cf()]κ)}. We also give an example to show that the covering assumption cannot be removed.
Embedding the diamond in the Σ2 enumeration degrees
Authors: Ahmad Seema
Published: May 2006

Lachlan [5] has shown that it is not possible to embed the diamond lattice in the r.e. Turing degrees while preserving least and greatest elements; that is, there do not exist incomparable r.e. Turing degrees a and b such that a ∧ b = 0 and a ∨ b = 0′. Cooper [3] has compared the r.e. Turing degrees to the enumeration degrees below 0e′ and has asked if the two structures are elementarily equivalent.

In this paper we show that such an embedding is possible in the Σ2enumeration degrees, which implies a negative answer to Cooper's question.

Theorem. There are low enumeration degreesaandbsuch thata ∧ b = 0eanda ∨ b = 0e′.

Lower case italic letters denote elements of ω while upper case italic letters denote subsets of ω. D, E and F are reserved for finite sets, and K for ′. If D = {x0, x1, …, xn} then the canonical index of D is , and the canonical index of is ∅. Dx denotes the set with canonical index x. {Wi}i∈ω is any fixed standard listing of the r.e. sets, and <·, ·> is any fixed recursive bijection from ω × ω to ω.

Intuitively, A is enumeration reducible to B if there is an effective algorithm for producing an enumeration of A from any enumeration of B. There is a natural one-to-one correspondence between all such algorithms and the r.e. sets.
Isomorphisms and nonisomorphisms of graph models
Authors: Schellinx Harold
Published: May 2006

In this paper the existence or nonexistence of isomorphic mappings between graph models for the untyped lambda calculus is studied. It is shown that Engeler's is DA completely determined, up to isomorphism, by the cardinality of its ‘atom-set’ A. A similar characterization is given for a collection of graph models of the -type; from this some propositions regarding automorphisms are obtained. Also we give an indication of the complexity of the first-order theory of graph models by showing that the second-order theory of first-order definable elements of a graph model is first-order expressable in the model.
A formal theory of objects, space and time
Authors: Blizard Wayne D.
Published: May 2006

The two statements “Two different objects cannot occupy the same place at the same time” and “An object cannot be in two different places at the same time” are axioms of our everyday understanding of objects, space and time. We develop a first-order theory OST (Objects, Space and Time) in which formal equivalents of these two statements are taken as axioms. Using the theory OST, we uncover other fundamental principles of objects, space and time. We attempt to understand the logical nature of these principles, to investigate their formal consequences, and to identify logical alternatives to them. For easy reference, all of the nonlogical axioms of OST are listed together at the end of §2. In §3, we introduce two possible extensions of OST.
Remarks on the Church-Rosser Property
Authors: López-Escobar E. G. K.
Published: May 2006

A reduction algebra is defined as a set with a collection of partial unary functions (called reduction operators). Motivated by the lambda calculus, the Church-Rosser property is defined for a reduction algebra and a characterization is given for those reduction algebras satisfying CRP and having a measure respecting the reductions. The characterization is used to give (with 20/20 hindsight) a more direct proof of the strong normalization theorem for the impredicative second order intuitionistic propositional calculus.
Subgroups of stable groups
Authors: Wagner Frank
Published: May 2006

We define the notion of generic for an arbitrary subgroup H of a stable group, and show that H has a definable hull with the same generic properties. We then apply this to the theory of stable fields.
Mathematics as natural science
Authors: Goodman Nicolas D.
Published: May 2006

Mathematics is a natural science whose great generality makes many philosophers think of it as a supernatural science, consisting of truths derived independently of experience about objects not given in experience. Some mathematicians, like Simpson [16], try to defend mathematics from the resulting objection that it is merely a mental game by first conceding that most of it is meaningless and then trying to save what is left by some technical tour de force. Some physicists, like Wigner [20], admit that mathematics is applicable to the world, but declare themselves unable to understand what makes its applications possible. Both Simpson's worries and Wigner's puzzlement can be relieved if we assimilate mathematics more closely to the other natural sciences.
Partitions of products
Authors: Di Prisco Carlos A. , Henle James M.
Published: May 2006

We will consider some partition properties of the following type: given a function F: ωω →2, is there a sequence H0, H1, … of subsets of ω such that F is constant on ΠiεωHi? The answer is obviously positive if we allow all the Hi's to have exactly one element, but the problem is nontrivial if we require the Hi's to have at least two elements. The axiom of choice contradicts the statement “for all F: ωω→ 2 there is a sequence H0, H1, H2,… of subsets of ω such that {i|(Hi) ≥ 2} is infinite and F is constant on ΠHi”, but the infinite exponent partition relation ω(ω)ω implies it; so, this statement is relatively consistent with an inaccessible cardinal. (See [1] where these partition properties were considered.)

We will also consider partitions into any finite number of pieces, and we will prove some facts about partitions into ω-many pieces.

Given a partition F: ωω → k, we say that H0, H1…, a sequence of subsets of ω, is homogeneous for F if F is constant on ΠHi. We say the sequence H0, H1,… is nonoverlapping if, for all i ∈ ω, ∪Hi > ∩Hi+1.

The sequence 〈Hi: i ∈ ω〉 is of type 〈α0, α1,…〉 if, for every i ∈ ω, ∣Hi∣ = αi.

We will adopt the usual notation for polarized partition relations due to Erdös, Hajnal, and Rado.

means that for every partition F: κ1 × κ2 × … × κn→δ there is a sequence H0, H1,…, Hn such that Hi ⊂ κi and ∣Hi∣ = αi for every i, 1 ≤ i ≤ n, and F is constant on H1 × H2 × … × Hn.
Logic, sheaves, and factorization systems
Authors: Monro G. P.
Published: May 2006

In this paper we extend the models for the “logic of categories” to a wider class of categories than is usually considered. We consider two kinds of logic, a restricted first-order logic and the full higher-order logic of elementary topoi.

The restricted first-order logic has as its only logical symbols ∧, ∃, Τ, and =. We interpret this logic in a category with finite limits equipped with a factorization system (in the sense of [4]). We require to satisfy two additional conditions: ⊆ Monos, and any pullback of an arrow in is again in . A category with a factorization system satisfying these conditions will be called an EM-category.

The interpretation of the restricted logic in EM-categories is given in §1. In §2 we give an axiomatization for the logic, and in §§3 and 5 we give two completeness proofs for this axiomatization. The first completeness proof constructs an EM-category out of the logic, in the spirit of Makkai and Reyes [8], though the construction used here differs from theirs. The second uses Boolean-valued models and shows that the restricted logic is exactly the ∧, ∃-fragment of classical first-order logic (adapted to categories). Some examples of EM-categories are given in §4.

The restricted logic is powerful enough to handle relations, and in §6 we assign to each EM-category a bicategory of relations Rel() and a category of “functional relations” fr. fr is shown to be a regular category, and it turns out that Rel( and Rel(fr) are biequivalent bicategories. In §7 we study complete objects in an EM-category where an object of is called complete if every functional relation into is yielded by a unique morphism into . We write c for the full subcategory of consisting of the complete objects. Complete objects have some, but not all, of the properties that sheaves have in a category of presheaves.
Amenable versus hyperfinite Borel equivalence relations
Authors: Kechris Alexander S.
Published: May 2006

LetXbe a standard Borel space (i.e., a Polish space with the associated Borel structure), and letEbe acountableBorel equivalence relation onX, i.e., a Borel equivalence relationEfor which every equivalence class [x]Eis countable. By a result of Feldman-Moore [FM],Eis induced by the orbits of a Borel action of a countable groupGonX.

The structure of general countable Borel equivalence relations is very little understood. However, a lot is known for the particularly important subclass consisting of hyperfinite relations. A countable Borel equivalence relation is calledhyperfiniteif it is induced by a Borel ℤ-action, i.e., by the orbits of a single Borel automorphism. Such relations are studied and classified in [DJK] (see also the references contained therein). It is shown in Ornstein-Weiss [OW] and Connes-Feldman-Weiss [CFW] that for every Borel equivalence relationEinduced by a Borel action of a countable amenable groupGonXand for every (Borel) probability measure μ onX, there is a Borel invariant setY⊆Xwith μ(Y) = 1 such thatE↾Y(= the restriction ofEtoY) is hyperfinite. (Recall that a countable group G isamenableif it carries a finitely additive translation invariant probability measure defined on all its subsets.) Motivated by this result, Weiss [W2] raised the question of whether everyEinduced by a Borel action of a countable amenable group is hyperfinite. Later on Weiss (personal communication) showed that this is true forG= ℤn. However, the problem is still open even for abelianG. Our main purpose here is to provide a weaker affirmative answer for general amenableG(and more—see below). We need a definition first. Given two standard Borel spacesX, Y, auniversally measurableisomorphism betweenXandYis a bijection ƒ:X→Ysuch that both ƒ, ƒ-1are universally measurable. (As usual, a mapg:Z→W, withZandWstandard Borel spaces, is calleduniversally measurableif it is μ-measurable for every probability measure μ onZ.) Notice now that to assert that a countable Borel equivalence relation onXis hyperfinite is trivially equivalent to saying that there is a standard Borel spaceYand a hyperfinite Borel equivalence relationFonY, which isBorelisomorphic toE, i.e., there is a Borel bijection ƒ:X→YwithxEy⇔ ƒ(x)Fƒ(y). We have the following theorem.
Quasi-endomorphisms in small stable groups
Authors: Wagner Frank O.
Published: May 2006

We generalise various properties of quasiendomorphisms from groups with regular generic to small abelian groups. In particular, for a small stable abelian group such that no infinite definable quotient is connected-by-finite, the ring of quasi-endomorphisms is locally finite. Under some additional assumptions, it decomposes modulo some nil ideal into a sum of finitely many matrix rings.
Les automorphismes d'un ensemble fortement minimal
Authors: Lascar Daniel
Published: May 2006

Let be a countable saturated structure, and assume that D(v) is a strongly minimal formula (without parameter) such that is the algebraic closure of D(). We will prove the two following theorems:

Theorem 1. If G is a subgroup of Aut() of countable index, there exists a finite set A in such that every A-strong automorphism is in G.

Theorem 2. Assume that G is a normal subgroup of Aut() containing an element g such that for all n there exists X ⊆ D() such that Dim(g(X)/X) > n. Then every strong automorphism is in G.
Scott analysis of pseudotypes
Authors: Newelski Ludomir
Published: May 2006

This is a continuation of [N2]. We find a Borel definition of Q-isolation. We pursue a topological and Scott analysis of pseudotypes on S(Q).
Lattice of algebraically closed sets in one-based theories
Authors: Low Lee Fong
Published: May 2006

Let T be a one-based theory. We define a notion of width, in the case of T having the finiteness property, for the lattice of finitely generated algebraically closed sets and prove

Theorem. Let T be one-based with the finiteness property. If T is of bounded width, then every type in T is nonorthogonal to a weight one type. If T is countable, the converse is true.
On the ring of differentially-algebraic entire functions
Authors: Rubel Lee A.
Published: May 2006

Let be the ring of all entire functions of one complex variable, and let DA be the subring of those entire functions that are differentially algebraic (DA); that is, they satisfy a nontrivial algebraic differential equation.

where P is a non-identically-zero polynomial in its n + 2 variables. It seems not to be known whether DA is elementarily equivalent to . This would mean that DA and have exactly the same true statements about them, in the first-order language of rings. (Roughly speaking, a sentence about a ring R is first-order if it has finite length and quantifies only over elements (i.e., not subsets or functions or relations) of R.) It follows from [NAN] that DA and are not isomorphic as rings, but this does not answer the question of elementary equivalence.
A Spector-Gandy theorem for cPCd() classes
Authors: Lavine Shaughan
Published: May 2006

Let be an admissible structure. A cPCd() class is the class of all models of a sentence of the form , where is an -r.e. set of relation symbols and Φ is an -r.e. set of formulas of ℒ∞,ω that are in . The main theorem is a generalization of the following: Let be a pure countable resolvable admissible structure such that is not Σ-elementarily embedded in HYP(). Then a class K of countable structures whose universes are sets of urelements is a cPCd() class if and only if for some Σ formula σ (with parameters from ), is in K if and only if is a countable structure with universe a set of urelements and σ, where , the smallest admissible set above relative to , is a generalization of HYP to structures with similarity type Σ over that is defined in this article. Here we just note that when Lα is admissible, HYPLα() is Lβ() for the least β ≥ α such that Lβ() is admissible, and so, in particular, that is just HYP() in the usual sense when has a finite similarity type.

The definition of is most naturally formulated using Adamson's notion of a +-admissible structure (1978). We prove a generalization from admissible to +-admissible structures of the well-known truncation lemma. That generalization is a key theorem applied in the proof of the generalized Spector-Gandy theorem.
A model and its subset
Authors: Newelski Ludomir
Published: May 2006

We try to count the number of countable models M of T with a fixed set Q = Φ(M) of realizations of a type Φ. Also, for stable T, we define an ordinal rank measuring multiplicity of types, with additivity properties similar to those of U-rank.
Imaginary modules
Authors: Kucera T. G. , Prest M.
Published: May 2006

It was a fundamental insight of Shelah that the equivalence classes of a definable equivalence relation on a structure M often behave like (and indeed must be treated like) the elements of the structure itself, and that these so-called imaginary elements are both necessary and sufficient for developing many aspects of stability theory. The expanded structure Meq was introduced to make this insight explicit and manageable. In Meq we have “names” for all things (subsets, relations, functions, etc.) “definable” inside M. Recent results of Bruno Poizat allow a particularly simple and more or less algebraic modification of Meq in the case that M is a module. It is the purpose of this paper to describe this nearly algebraic structure in such a way as to make the usual algebraic tools of the model theory of modules readily available in this more general context. It should be pointed out that some of our discussion has been part of the “folklore” of the subject for some time; it is certainly time to make this “folklore” precise, correct, and readily available.

Modules have proved to be good examples of stable structures. Not, we mean, in the sense that they are well-behaved (which, in the main, they are), but in the sense that they are straightforward enough to provide comprehensible illustrations of concepts while, at the same time, they have turned out to be far less atypical than one might have supposed. Indeed, a major feature of recent stability theory has been the ubiquitous appearance of modules or more general “abelian structures” in abstract stable structures.
Quasiunitriangular groups
Authors: Belegradek O. V.
Published: May 2006

For a ring with unit R, which need not be associative, denote the group of upper unitriangular 3 × 3 matrices over R by UT3(R). Let e1 = (1,0,0), e2 = (0,1,0), where (α, β, γ) denotes the matrix

Denote the expanded group (UT3(R), e1, e2) by (R). A. 1. Mal′cev [M] gave an algebraic characterization of the expanded groups of the form (R) as follows. Let h1, h2 be elements of a group H; then (H, h1, h2) is isomorphic to (R), for some R, if and only if

(i) H is 2-step nilpotent;

(ii) CH(hi) are abelian, i = 1,2;

(iii) CH(h1) ∩ CH(h2) = Z(H);

(iv) [CH(h1),h2] = [h1, CH(h2)] = Z(H);

(v) Z(H) is a direct summand in both CH(hi).

(In [M] condition (v) is a bit stronger; the version above is presented in [B2].)

A pair (h1, h2) of elements of a group H is said to be a base if (H, h1, h2) satisfies the conditions (i)–(iv). A. I. Mal′cev [M] found a uniform way of first order interpreting a ring Ring(H, h1, h2) in any group with a base (H, h1, h2); in particular, Ring((R)) ≃ R.
Every n-generic degree is a minimal cover of an n-generic degree
Authors: Kumabe Masahiro
Published: May 2006

The notions of forcing and generic set were introduced by Cohen in 1963 to prove the independence of the Axiom of Choice and the Continuum Hypothesis in set theory. Let ω be the set of natural numbers, i.e., {0,1,2,3,…}. A string is a mapping from an initial segment of ω into {0,1}. We identify a set A ⊆ ω to with its characteristic function.

We now consider a set generic over the arithmetic sets. A set A ⊆ ω is called n-generic if it is Cohen-generic for n-quantifier arithmetic. This is equivalent to saying that for every -set of strings S, there is a σ ⊂ A such that σ ∈ S or (∀v ≥ σ)(v ∉ S). By degree we mean Turing degree (of unsolvability). We call a degree n-generic if it has an n-generic representative. For a degree a, let D(≤a) denote the set of degrees which are recursive in a.

Before Cohen's work, there was a precursor of the notion of forcing in recursion theory. Friedberg showed that for every degree b above the complete degree 0', i.e., the degree of a complete r.e. set, there is a degree a such that a′ = a ⋃ 0′ = b. He actually proved this result by using the notion of forcing for statements.
Algebraic types and automorphism groups
Authors: Tsuboi Akito
Published: May 2006

Galois theory states that if L is a certain algebraic extension (called a Galois extension) of a field K, then there is a one-to-one correspondence (called a Galois correspondence) between subfields M, K ⊂ M ⊂ L and subgroups of the automorphism groups of L fixing the elements in K.

A subfield of a field L can be considered as a substructure of L in general model theory. However, a substructure is a subset closed under functions which are interpretations of function symbols in a given language, so the notion of substructure may change if we expand the language by adding definable notions. On the other hand a definably closed substructure is a subset which is closed under all definable functions, and it does not change by such expansions. If we are interested in subfields of an algebraically closed field of characteristic 0, these two notions are the same. But in a field of prime characteristic they are not equal. Speaking roughly, a Galois extension of a field K is an extension whose subfields are relatively definably closed. Poizat [4] showed that if a structure M has elimination of imaginaries there is a kind of Galois correspondence between definably closed substructures and subgroups of bijective elementary mappings of M.

In this paper, using Poizat's result we study algebraic types. As is well known, one motivation for developing the Galois theory was to show the unsolvability of equations with degree ≥ 5. We want to take this unsolvability as a special case of general phenomena. For this purpose, we introduce several notions which are stronger than mere algebraicity and study relations between these notions and groups of bijective elementary mappings. (See Theorems 3.7 and 3.9.)
Minimal upper bounds for arithmetical degrees
Authors: Kumabe Masahiro
Published: May 2006

This paper was inspired by Lerman [14] in which he proved various properties of upper bounds for the arithmetical degrees. The degrees which are upper bounds for the arithmetical degrees were first studied by Hodes [5] and Enderton and Putnam [5]. Enderton and Putnam [5] showed that if a is an upper bound for the arithmetical degrees, then a(2) ≥ 0(ω). This area was further studied by Hodes [5], Knight, Lachlan and Soare [12], Jockusch and Simpson [12], and Sacks [17].

Enderton and Putnam [5] and Sacks [17] have combined to show that 0(ω) is the least degree in {a(2): a is an upper bound for the arithmetical degrees}. So there seem to be some analogies between the degrees of upper bounds for the arithmetical degrees and the degrees below 0(2). But Sacks [17] showed an important difference between these two structures; namely, the Turing jumps of upper bounds for the arithmetical degrees have no least element. In Lerman [14], a systematic investigation of properties of the jumps of upper bounds for the arithmetical degrees was suggested, which could lead to a definition of the jump operator over the elementary theory of the partial ordering of the degrees. Although Cooper [5] found a degree-theoretic definition of the jump operator, Lerman's plan is still interesting.

We say a degree a is generic if there is a representative A of a such that A is Cohen generic for the arithmetical sentences. By Jockusch [5], the statement that A is Cohen generic for the arithmetical sentences is equivalent to saying that for any arithmetical set S of binary strings, there is a σ extended by A such that σ is in S or no extension of σ is in S. First, we investigate the relation between generic degrees and upper bounds for the arithmetical degrees. In the case D(≤ 0′), the set of degrees below 0′, it is well known that any nonrecursive r.e. degree bounds a 1-generic degree (Cohen generic for Σ1 sentences). Jockusch and Ponser [12] showed that any degree a with a″ >T (a ∪ 0′)′ bounds a 1-generic degree.
On one-based theories
Authors: Bouscaren E. , Hrushovski E.
Published: May 2006

We know from [H1], [H2] that in a stable theory, given a nontrivial locally modular regular type q, one can define a group with generic domination equivalent to q, and that the dependence relation on q can be analyzed in terms of this group. In a stable one-based theory, every regular type is locally modular; hence, this result holds for every nontrivial regular type. We show here that, in fact, in a stable one-based theory, a similar type of construction can be done without the assumption of regularity. More precisely, we show that for any type q, the nontrivial part of q can be analyzed by generics of groups and that any nontrivial relation can be described by affine relations (Theorem A).

This construction is then used to answer a question about homogeneity in pairs of models which is still open in the case of arbitrary stable theories (Theorem C).
Axiomatizing a category of categories
Authors: McLarty Colin
Published: May 2006

Elementary axioms describe a category of categories. Theorems of category theory follow, including some on adjunctions and triples. A new result is that associativity of composition in categories follows from cartesian closedness of the category of categories. The axioms plus an axiom of infinity are consistent iff the axioms for a well-pointed topos with separation axiom and natural numbers are. The theory is not finitely axiomatizable. Each axiom is independent of the others. Further independence and definability results are proved. Relations between categories and sets, the latter defined as discrete categories, are described, and applications to foundations are discussed.
Free-variable axiomatic foundations of infinitesimal analysis: A fragment with finitary consistency proof
Authors: Chuaqui Rolando , Suppes Patrick
Published: May 2006

In treatises or advanced textbooks on theoretical physics, it is apparent that the way mathematics is used is very different from what is to be found in books of mathematics. There is, for example, no close connection between books on analysis, on the one hand, and any classical textbook in quantum mechanics, for example, Schiff, [11], or quite recent books, for example Ryder, [10], on quantum field theory. The differences run a good deal deeper than the fact that the books on theoretical physics are not written in the definition-theorem-proof style characteristic of pure mathematics. Although a good many propositions are proved in the books on physics, there are almost with exception no existential proofs, and consequently there is no really serious systematic use of quantifiers. Another important characteristic is the free use of infinitesimals. In fact, most results would not lose anything, from a physicist's point of view, by leaving them in approximate form, i.e., instead of strict equalities or inequalities, using equalities or inequalities only up to an infinitesimal.

The discrepancy between the way mathematics is ordinarily done in theoretical physics and the way it is built up from a foundational standpoint in any of the standard modern views raises the question of whether it might be possible to construct quite directly a rigorous foundation that reflects a significant part of this standard practice in theoretical physics. Other parts of standard practice in physics, for example, the use of physically intuitive but nonrigorous arguments, are not present in our system.
y= 2xVS.y= 3x
Authors: Stolboushkin Alexei , Niwiński Damian
Published: May 2006

We show that no formula of first order logic using linear ordering and the logical relationy= 2xcan define the property that the size of a finite model is divisible by 3. This answers a long-standing question which may be of relevance to certain open problems in circuit complexity.
Rothberger's property and partition relations
Authors: Scheepers Marion
Published: May 2006

Let X be an infinite but separable metric space. An open cover of X is said to be large if for each x ϵ X the set {U ϵ : x ϵ U} is infinite. The symbol Λ denotes the collection of large open covers of X. An open cover of X is said to be an ω-cover if for each finite subset F of X there is a U ϵ such that F ⊆ U, and X is not a member of , X is said to have Rothberger's property if there is for every sequence (n : n = 1,2,3,…) of open covers of X a sequence (Un : n = 1,2,3,…) such that:

(1) for each n, Un is a member of n, and

(2) {Un: n = 1,2,3,…} is a cover of X.

Rothberger introduced this property in his paper [2]. For convenience we let denote the collection of all open covers of X.

In [3] it was shown that X has Rothberger's property if, and only if, the following partition relation is true for large open covers of X:

This partition relation means:

for every large cover of X, for every coloring

such that for each U ϵ and each large cover there is an i with a large cover of X,

either there is a large cover such that f({A, B}) = 0 whenever {A,B} ϵ ,

or else there is a which is not point–finite such that f{{A, B}) = 1 whenever {A, B} ϵ .
Asymptotic conditional probabilities: The non-unary case
Authors: Grove Adam J. , Halpern Joseph Y. , Koller Daphne
Published: May 2006

Motivated by problems that arise in computing degrees of belief, we consider the problem of computing asymptotic conditional probabilities for first-order sentences. Given first-order sentences φ and θ, we consider the structures with domain {1, …, N} that satisfy θ, and compute the fraction of them in which φ is true. We then consider what happens to this fraction as N gets large. This extends the work on 0-1 laws that considers the limiting probability of first-order sentences, by considering asymptotic conditional probabilities. As shown by Liogon'kiĭ [24], if there is a non-unary predicate symbol in the vocabulary, asymptotic conditional probabilities do not always exist. We extend this result to show that asymptotic conditional probabilities do not always exist for any reasonable notion of limit. Liogon'kiĭ also showed that the problem of deciding whether the limit exists is undecidable. We analyze the complexity of three problems with respect to this limit: deciding whether it is well-defined, whether it exists, and whether it lies in some nontrivial interval. Matching upper and lower bounds are given for all three problems, showing them to be highly undecidable.
A version of o-minimality for the p-adics
Authors: Haskell Deirdre , Macpherson Dugald
Published: May 2006

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).
Nondefinability results for expansions of the field of real numbers by the exponential function and by the restricted sine function
Authors: Bianconi Ricardo
Published: May 2006

We prove that no restriction of the sine function to any (open and nonempty) interval is definable in 〈R, +, ·, ×, <, exp, constants〉, and that no restriction of the exponential function to an (open and nonempty) interval is definable in 〈R, +, ·, <, sin0, constants〉, where sin0(x) = sin(x) for x ∈ [—π, π], and sin0(x) = 0 for all x ∉ [—π, π].
Gentzenizations of relevant logics without distribution. I
Authors: Brady Ross T.
Published: May 2006

The history of the Gentzenization of relevant logics goes back to Kripke [17], who in 1959 Gentzenized R→ and went on to prove its decidability. Formulae were separated by commas on the left side of the turnstile, the commas just representing nested implications. Kripke employed just a singleton formula to the right of the turnstile. He also considered adding negation, as well as other connectives, but it was not until 1961 that Belnap and Wallace, in [5], Gentzenized and proved its decidability, though their Gentzenization employed commas on both sides of the turnstile. Subsequently, in 1966, the logic R without distribution, now called LR (for lattice R), was Gentzenized in a similar style by Meyer in [20]. He also went on to show decidability for LR by extending Kripke's argument. Later, in 1969, Dunn Gentzenized R+ (published in [1], pp. 381–391) using two structural connectives (commas and semicolons) to the left of the turnstile, and with a single formula to the right. Here, the commas represent conjunction and the semicolons represent an intensional conjunction, called “fusion”. This is all nicely set out in McRobbie [19], where he also introduces left-handed Gentzenizations and analytic tableaux for a number of fragments of relevant logics. In 1979, further work on distributionless logic was done by Grishin, in a series of papers, including [16], in which he produced a Gentzenization of quantified RW without distribution (which we will call LRWQ), and used it to prove the decidability of this quantified logic.
On finite rigid structures
Authors: Gurevich Yuri , Shelah Saharon
Published: May 2006

The main result of this paper is a probabilistic construction of finite rigid structures. It yields a finitely axiomatizable class of finite rigid structures where no formula with counting quantifiers defines a linear order.
Strong termination for the epsilon substitution method
Authors: Mints Grigori
Published: May 2006

Ackermann proved termination for a special order of reductions in Hilbert's epsilon substitution method for the first order arithmetic. We establish termination for arbitrary order of reductions.
Boolean operations, Borel sets, and Hausdorff's question
Authors: Dasgupta Abhijit
Published: May 2006

The study of infinitary Boolean operations was undertaken by the early researchers of descriptive set theory soon after Suslin's discovery of the important operation. The first attempt to lay down their theory in a systematic fashion was the work of Kantorovich and Livenson [5], where they call these the analytical operations. Earlier, Hausdorff had introduced the δs operations — essentially same as the monotoneω-ary Boolean operations, and Kolmogorov, independently of Hausdorff, had discovered the same objects, which were used in his study of the R operator.

The ω-ary Boolean operations turned out to be closely related to most of the classical hierarchies over a fixed Polish space X, including, e. g., the Borel hierarchy (), the difference hierarchies of Hausdorff (Dη()), the C-hierarchy (Cξ) of Selivanovski, and the projective hierarchy (): for each of these hierarchies, every level can be expressed as the range of an ω-ary Boolean operation applied to all possible sequences of open subsets of X. In the terminology of Dougherty [3], every level is “open-ω-Boolean” (if and are collections of subsets of X and I is any set, is said to be -I-Boolean if there exists an I-ary Boolean operation Φ such that = Φ, i. e. is the range of Φ restricted to all possible I-sequences of sets from ). If in addition, the space X has a basis consisting of clopen sets, then the levels of the above hierarchies are also “clopen-ω-Boolean.”