bluuebunny/crossref_metadata_2025 huggingface dataset:
Bi-isolation in the d.c.e. degrees
Authors: Wu Guohua
Published: March 2005

In this paper, we study the bi-isolation phenomena in the d.c.e. degrees and prove that there are c.e. degrees c1 < c2 and a d.c.e. degree d ∈ (c1, c2) such that (c1, d) and (d, c2) contain no c.e. degrees. Thus, the c.e. degrees between c1 and c2 are all incomparable with d. We also show that there are d.c.e. degrees d1 < d2 such that (d1, d2) contains a unique c.e. degree.
A partial analysis of modified realizability
Authors: van Oosten Jaap
Published: March 2005

A formalized version of Kleene realizability for intuitionistic first-order arithmetic HA was axiomatically characterized by Troelstra (see [2, 3.2]) as follows: for an arbitrary HA-sentence φ, HA ⊢ ∃x(x realizes φ) if and only if HA + ECT0 ⊢ φ.

Many notions of realizability have been characterized in this fashion: see [2] or [3] for details. For some notions, for example extensional realizability, it is necessary to pass to an extension of HA: realizability in HA is characterized by deducibility from certain axioms in an extension of HA.

The present note is concerned with modified realizability, seen as interpretation for HA. From semantical considerations (see [4]) it follows that this interpretation can be constructed as a combination of three ingredients:

i) Kleene realizability;

ii) Kripke forcing over a 2-element linear order P;

iii) The Friedman translation [1].

This will be shown in section 2. The Friedman translation (in the way we use it) introduces a new propositional constant V; hence we move to an extension HA(V) of HA. We must then define Kleene realizability and forcing for the extended language. Now let (φ)v be the result of the Friedman translation applied to φ. We obtain, in HA, that the sentence saying that φ is modified-realizable, is equivalent to the sentence which says that the statement “(φ)v is Kleene-realizable” is forced in P (see section 2).
Degree spectra of prime models
Authors: Csima Barbara F.
Published: March 2005

We consider the Turing degrees of prime models of complete decidable theories. In particular we show that every complete decidable atomic theory has a prime model whose elementary diagram is low. We combine the construction used in the proof with other constructions to show that complete decidable atomic theories have low prime models with added properties.

If we have a complete decidable atomic theory with all types of the theory computable, we show that for every degree d with 0 < d < 0', there is a prime model with elementary diagram of degree d. Indeed, this is a corollary of the fact that if T is a complete decidable theory and L is a computable set of c.e. partial types of T, then for any degree d > 0, T has a d-decidable model omitting the nonprincipal types listed by L.
Formalized token models and duality in semantics: an algebraic approach
Authors: Hansen Lars
Published: March 2005

Employing the theory of Birkhoff polarities as a model of model theory yields an inductively defined dual structure which is a formalization of semantics and which allows for simple proofs of some new results for model theory.
On a question of Herzog and Rothmaler
Authors: Pillay Anand , Ziegler Martin
Published: March 2005

Herzog and Rothmaler gave the following purely topological characterization of stable theories. (See the exercises 11.3.4 – 11.3.7 in [2]).

A complete theory T is stable iff for any model M and any extension M ⊂ B the restriction map S(B) → S(M) has a continuous section.

In fact, if T is stable, taking the unique non-forking extension defines a continuous section of S(B) → S(A) for all subsets A of B, provided A is algebraically closed in Teq. Herzog and Rothmaler asked, if, for stable T, there is a continuous section for any subset A of B. Or, equivalently, if for any A, S(acleq(A)) → S(A) has a continuous section.

This is an interesting problem, also for unstable T. Is it true that for any T and any set of parameters A the restriction map S(acl(A)) → S(A) has a continuous section? We answer the question by the following two theorems.

Theorem 1. Let A be a subset of a model of T. Assume that the Boolean algebra of acl(A)-definable formulas is generated by

• some countable set of formulas,

• all A–definable formulas,

• all formulas which are atomic over acl(A).

Then S(acl(A)) → S(A) has a continuous section.

The conditions of the theorems are satisfied if, for example, L and A are countable, or, if there are only countably many non-isolated types over acl(A).

Theorem 2. There is a theory of Morley rank 2 and Morley degree 1 such that S(acl(∅)) → S(∅) has no continuous section.
Combinatorics for the dominating and unsplitting numbers
Authors: Aubrey Jason
Published: March 2005

In this paper we introduce a new property of families of functions on the Baire space, called pseudo-dominating, and apply the properties of these families to the study of cardinal characteristics of the continuum. We show that the minimum cardinality of a pseudo-dominating family is min {τ, ∂}. We derive two corollaries from the proof:τ≥ min{∂, u} and min{∂, τ} = min{∂, τσ}. We show that if a dominating family is partitioned into fewer that s pieces, then one of the pieces is pseudo-dominating. We finally show thatu<gimplies that every unbounded family of functions is pseudo-dominating, and that the Filter Dichotomy principle is equivalent to every unbounded family of functions being finitely pseudo-dominating.
Semi-bounded relations in ordered modules
Authors: Belegradek Oleg
Published: March 2005

A relation on a linearly ordered structure is called semi-bounded if it is definable in an expansion of the structure by bounded relations. We study ultimate behavior of semi-bounded relations in an ordered module M over an ordered commutative ring R such that M/rM is finite for all nonzero r ϵ R. We consider M as a structure in the language of ordered R-modules augmented by relation symbols for the submodules rM, and prove several quantifier elimination results for semi-bounded relations and functions in M. We show that these quantifier elimination results essentially characterize the ordered modules M with finite indices of the submodules rM. It is proven that (1) any semi-bounded k-ary relation on M is equal, outside a finite union of k-strips, to a k-ary relation quantifier-free definable in M, (2) any semibounded function from Mk to M is equal, outside a finite union of k-strips, to a piecewise linear function, and (3) any semi-bounded in M endomorphism of the additive group of M is of the form x ↦ σx, for some σ from the field of fractions of R.
Ladder gaps over stationary sets
Authors: Abraham Uri , Shelah Saharon
Published: March 2005

For a stationary set S ⊆ ω1, and a ladder system C over S, a new type of gaps called C-Hausdorff is introduced and investigated. We describe a forcing model of ZFC in which, for some stationary set S, for every ladder C over S, every gap contains a subgap that is C-Hausdorff. But for every ladder E over ω1 ∖ S there exists a gap with no subgap that is E-Hausdorff.

A new type of chain condition, called polarized chain condition, is introduced. We prove that the iteration with finite support of polarized c.c.c. posets is again a polarized c.c.c. poset.
Schnorr randomness
Authors: Downey Rodney G. , Griffiths Evan J.
Published: March 2005

Schnorr randomness is a notion of algorithmic randomness for real numbers closely related to Martin-Löf randomness. After its initial development in the 1970s the notion received considerably less attention than Martin-Löf randomness, but recently interest has increased in a range of randomness concepts. In this article, we explore the properties of Schnorr random reals, and in particular the c.e. Schnorr random reals. We show that there are c.e. reals that are Schnorr random but not Martin-Löf random, and provide a new characterization of Schnorr random real numbers in terms of prefix-free machines. We prove that unlike Martin-Löf random c.e. reals, not all Schnorr random c.e. reals are Turing complete, though all are in high Turing degrees. We use the machine characterization to define a notion of “Schnorr reducibility” which allows us to calibrate the Schnorr complexity of reals. We define the class of “Schnorr trivial” reals, which are ones whose initial segment complexity is identical with the computable reals, and demonstrate that this class has non-computable members.
Degrees of unsolvability of continuous functions
Authors: Miller Joseph S.
Published: March 2005

We show that the Turing degrees are not sufficient to measure the complexity of continuous functions on [0, 1]. Computability of continuous real functions is a standard notion from computable analysis. However, no satisfactory theory of degrees of continuous functions exists. We introduce the continuous degrees and prove that they are a proper extension of the Turing degrees and a proper substructure of the enumeration degrees. Call continuous degrees which are not Turing degrees non-total. Several fundamental results are proved: a continuous function with non-total degree has no least degree representation, settling a question asked by Pour-El and Lempp; every non-computable f ∈ [0,1] computes a non-computable subset of ℕ there is a non-total degree between Turing degrees a <Tb iff b is a PA degree relative to a; ⊆ 2ℕ is a Scott set iff it is the collection of f-computable subsets of ℕ for some f ∈ [0,1] of non-total degree; and there are computably incomparable f, g ∈ [0,1] which compute exactly the same subsets of ℕ. Proofs draw from classical analysis and constructive analysis as well as from computability theory.
Π11 relations and paths through
Authors: Goncharov Sergey S. , Harizanov Valentina S. , Knight Julia F. , Shore Richard A.
Published: March 2005

When bounds on complexity of some aspect of a structure are preserved under isomorphism, we refer to them as intrinsic. Here, building on work of Soskov [34], [33], we give syntactical conditions necessary and sufficient for a relation to be intrinsically on a structure. We consider some examples of computable structures and intrinsically relations R. We also consider a general family of examples of intrinsically relations arising in computable structures of maximum Scott rank.

For three of the examples, the maximal well-ordered initial segment in a Harrison ordering, the superatomic part of a Harrison Boolean algebra, and the height-possessing part of a Harrison p-group, we show that the Turing degrees of images of the relation in computable copies of the structure are the same as the Turing degrees of paths through Kleene's . With this as motivation, we investigate the possible degrees of these paths. We show that there is a path in which ∅′ is not computable. In fact, there is one in which no noncomputable hyperarithmetical set is computable. There are paths that are Turing incomparable, or Turing incomparable over a given hyperarithmetical set. There is a pair of paths whose degrees form a minimal pair. However, there is no path of minimal degree.
An incompleteness theorem for βn-models
Authors: Mummert Carl , Simpson Stephen G.
Published: March 2005

Let n be a positive integer. By a βn-model we mean an ω-model which is elementary with respect to formulas. We prove the following βn-model version of Gödel's Second Incompleteness Theorem. For any recursively axiomatized theory S in the language of second order arithmetic, if there exists a βn-model of S, then there exists a βn-model of S + “there is no countable βn-model of S”. We also prove a βn-model version of Löb's Theorem. As a corollary, we obtain a βn-model which is not a βn+1-model.
On spectra of sentences of monadic second order logic with counting
Authors: Fischer E. , Makowsky J. A.
Published: March 2005

We show that the spectrum of a sentence ϕ in Counting Monadic Second Order Logic (CMSOL) using one binary relation symbol and finitely many unary relation symbols, is ultimately periodic, provided all the models of ϕ are of clique width at most k, for some fixed k. We prove a similar statement for arbitrary finite relational vocabularies τ and a variant of clique width for τ-structures. This includes the cases where the models of ϕ are of tree width at most k. For the case of bounded tree-width, the ultimate periodicity is even proved for Guarded Second Order Logic GSOL. We also generalize this result to many-sorted spectra, which can be viewed as an analogue of Parikh's Theorem on context-free languages, and its analogues for context-free graph grammars due to Habel and Courcelle.

Our work was inspired by Gurevich and Shelah (2003), who showed ultimate periodicity of the spectrum for sentences of Monadic Second Order Logic where only finitely many unary predicates and one unary function are allowed. This restriction implies that the models are all of tree width at most 2, and hence it follows from our result.
Lovely pairs of models: the non first order case
Authors: Ben-Yaacov Itay
Published: March 2005

We prove that for every simple theory T (or even simple thick compact abstract theory) there is a (unique) compact abstract theory whose saturated models are the lovely pairs of T. Independence-theoretic results that were proved in [5] when is a first order theory are proved for the general case: in particular is simple and we characterise independence.
The complexity of continuous embeddability between dendrites
Authors: Marcone Alberto , Rosendal Christian
Published: March 2005

We show that the quasi-order of continuous embeddability between finitely branching dendrites (a natural class of fairly simple compacta) is -complete. We also show that embeddability between countable linear orders with infinitely many colors is -complete.
On some small cardinals for Boolean algebras
Authors: Mckenzie Ralph , Monk J. Donald
Published: March 2005

Assume that all algebras are atomless. (1) Spind(A × B) = Spind(A) ∪ Spind(B). (2) Spind(Ai). Now suppose that κ and λ are infinite cardinals, with κ uncountable and regular and with κ < λ. (3) There is an atomless Boolean algebra A such that u(A) = κ and i(A) = λ. (4) If λ is also regular, then there is an atomless Boolean algebra A such that t(A) = s(A) = κ and α (A) = λ. All results are in ZFC, and answer some problems posed in Monk [01] and Monk [∞].
Reverse mathematics and the equivalence of definitions for well and better quasi-orders
Authors: Cholak Peter , Marcone Alberto , Solomon Reed
Published: March 2005

In reverse mathematics, one formalizes theorems of ordinary mathematics in second order arithmetic and attempts to discover which set theoretic axioms are required to prove these theorems. Often, this project involves making choices between classically equivalent definitions for the relevant mathematical concepts. In this paper, we consider a number of equivalent definitions for the notions of well quasi-order and better quasi-order and examine how difficult it is to prove the equivalences of these definitions.

As usual in reverse mathematics, we work in the context of subsystems of second order arithmetic and take RCA0 as our base system. RCA0 is the subsystem formed by restricting the comprehension scheme in second order arithmetic to formulas and adding a formula induction scheme for formulas. For the purposes of this paper, we will be concerned with fairly weak extensions of RCA0 (indeed strictly weaker than the subsystem ACA0 which is formed by extending the comprehension scheme in RCA0 to cover all arithmetic formulas) obtained by adjoining certain combinatorial principles to RCA0. Among these, the most widely used in reverse mathematics is Weak König's Lemma; the resulting theory WKL0 is extensively documented in [11] and elsewhere.

We give three other combinatorial principles which we use in this paper. In these principles, we use k to denote not only a natural number but also the finite set {0, …, k − 1}.
Every polynomial-time 1-degree collapses if and only if P = PSPACE
Authors: Fenner Stephen A. , Kurtz Stuart A. , Royer James S.
Published: March 2005

A set A is m-reducible (or Karp-reducible) to B if and only if there is a polynomial-time computable function f such that, for all x, x ∈ A if and only if f(x) ∈ B. Two sets are:

• 1-equivalent if and only if each is m-reducible to the other by one-one reductions;

• p-invertible equivalent if and only if each is m-reducible to the other by one-one, polynomial-time invertible reductions; and

• p-isumorphic if and only if there is an m-reduction from one set to the other that is one-one, onto, and polynomial-time invertible.

In this paper we show the following characterization.

Theorem. The following are equivalent:

(a) P = PSPACE.

(b) Every two 1-equivalent sets are p-isomorphic.

(c) Every two p-invertible equivalent sets are p-isomorphic.
Patterns of paradox
Authors: Cook Roy T.
Published: March 2005

We begin with a prepositional languageLpcontaining conjunction (Λ), a class of sentence names {Sα}αϵA, and a falsity predicateF. We (only) allow unrestricted infinite conjunctions, i.e., given any non-empty class of sentence names {Sβ}βϵB,

is a well-formed formula (we will useWFFto denote the set of well-formed formulae).

The language, as it stands, is unproblematic. Whether various paradoxes are produced depends on which names are assigned to which sentences. What is needed is a denotation function:

For example, theLPsentence “F(S1)” (i.e.,Λ{F(S1)}), combined with a denotation functionδsuch thatδ(S1)“F(S1)”, provides the (or, in this context, a)Liar Paradox.

To give a more interesting example,Yablo's Paradox[4] can be reconstructed within this framework.Yablo's Paradoxconsists of an ω-sequence of sentences {Sk}kϵωwhere, for eachnϵω:

WithinLPan equivalent construction can be obtained using infinite conjunction in place of universal quantification - the sentence names are {Si}iϵωand the denotation function is given by:

We can express this in more familiar terms as:

etc.
Leibnizian models of set theory
Authors: Enayat Ali
Published: March 2005

A model is said to be Leibnizian if it has no pair of indiscernibles. Mycielski has shown that there is a first order axiom LM (the Leibniz-Mycielski axiom) such that for any completion T of Zermelo-Fraenkel set theory ZF. T has a Leibnizian model if and only if T proves LM. Here we prove:

Theorem A. Every complete theory T extending ZF + LM has nonisomorphic countable Leibnizian models.

Theorem B. If κ is a prescribed definable infinite cardinal ofa complete theory T extending ZF + V = OD, then there are nonisomorphic Leibnizian models of T of power ℵ1such thatis ℵ1-like.

Theorem C. Every complete theory T extendingZF + V = ODhas nonisomorphic ℵ1-like Leibnizian models.
On the intuitionistic strength of monotone inductive definitions
Authors: Tupailo Sergei
Published: March 2005

We prove here that the intuitionistic theory T0↾ + UMIDN. or even EETJ↾ + UMIDN, of Explicit Mathematics has the strength of –CA0. In Section 1 we give a double-negation translation for the classical second-order μ-calculus, which was shown in [Mö02] to have the strength of –CA0. In Section 2 we interpret the intuitionistic μ-calculus in the theory EETJ↾ + UMIDN. The question about the strength of monotone inductive definitions in T0 was asked by S. Feferman in 1982, and — assuming classical logic — was addressed by M. Rathjen.
Dividing in the algebra of compact operators
Authors: Berenstein Alexander
Published: March 2005

We interpret the algebra of finite rank operators as imaginaries inside a Hilbert space. We prove that the Hilbert space enlarged with these imaginaries has built-in canonical bases.
Wellfoundedness proofs by means of non-monotonic inductive definitions I: Π20-operators
Authors: Arai Toshiyasu
Published: March 2005

In this paper, we prove the wellfoundedrtess of recursive notation systems for reflecting ordinals up to Π3-reflection by relevant inductive definitions.
Diophantine properties of sets definable in o-minimal structures
Authors: Wilkie A. J.
Published: March 2005

Let be an o-minimal expansion of the ordered field of real numbers , and let S be an -definable subset (parameters allowed unless otherwise stated) of ℝn. In this note I investigate questions concerning the distribution of points on S with integer coordinates. My main theorem gives an estimate which, though probably far from best possible, at least shows that the o-minimal assumption does have diophantine consequences. This is, perhaps, surprising in view of the flexibility that we now seem to have in constructing o-minimal expansions of (see, e. g. [7], [8], [9]).
On the construction of effectively random sets
Authors: Merkle Wolfgang , Mihailović Nenad
Published: March 2005

We present a comparatively simple way to construct Martin-Löf random and rec-random sets with certain additional properties, which works by diagonalizing against appropriate martingales. Reviewing the result of Gács and Kučera, for any given set X we construct a Martin-Löf random set from which X can be decoded effectively.

By a variant of the basic construction we obtain a rec-random set that is weak truth-table autoreducible and we observe that there are Martin-Löf random sets that are computably enumerable self-reducible. The two latter results complement the known facts that no rec-random set is truth-table autoreducible and that no Martin-Löf random set is Turing-autoreducible [8, 24].
Filtering unification and most general unifiers in modal logic
Authors: Ghilardi Silvio , Sacchetti Lorenzo
Published: March 2005

We characterize (both from a syntactic and an algebraic point of view) the normalK4-logics for which unification is filtering. We also give a sufficient semantic criterion for existence of most general unifiers, covering natural extensions ofK4.2+(i.e., of the modal system obtained fromK4 by adding to it, as a further axiom schemata, the modal translation of the weak excluded middle principle).
Every 2-random real is Kolmogorov random
Authors: Miller Joseph S.
Published: March 2005

We study reals with infinitely many incompressible prefixes. Call A ∈ 2ωKolmogorov random if . where C denotes plain Kolmogorov complexity. This property was suggested by Loveland and studied by Martin-Löf. Schnorr and Solovay. We prove that 2-random reals are Kolmogorov random. Together with the converse—proved by Nies. Stephan and Terwijn [11]—this provides a natural characterization of 2-randomness in terms of plain complexity. We finish with a related characterization of 2-randomness.
Almost everywhere domination
Authors: Dobrinen Natasha L. , Simpson Stephen G.
Published: March 2005

A Turing degree a is said to be almost everywhere dominating if, for almost all X ∈ 2ω with respect to the “fair coin” probability measure on 2ω, and for all g: ω → ω Turing reducible to X, there exists f: ω → ω of Turing degree a which dominates g. We study the problem of characterizing the almost everywhere dominating Turing degrees and other, similarly defined classes of Turing degrees. We relate this problem to some questions in the reverse mathematics of measure theory.
Theories of presheaf type
Authors: Beke Tibor
Published: March 2005

Let us say that a geometric theory T is of presheaf type if its classifying topos is (equivalent to) a presheaf topos. (We adhere to the convention that geometric logic allows arbitrary disjunctions, while coherent logic means geometric and finitary.) Write Mod(T) for the category of Set-models and homomorphisms of T. The next proposition is well known; see, for example, MacLane–Moerdijk [13], pp. 381-386, and the textbook of Adámek–Rosický [1] for additional information:

Proposition 0.1. For a category , the following properties are equivalent:

(i) is a finitely accessible category in the sense of Makkai–Paré [14], i.e., it has filtered colimits and a small dense subcategory of finitely presentable objects

ii) is equivalent to Pts, the category of points of some presheaf topos

(iii) is equivalent to the free filtered cocompletion (also known as Ind-) of a small category .

(iv) is equivalent to Mod(T) for some geometric theory of presheaf type.

Moreover, if these are satisfied for a given , then the —in any of (i), (ii) and (iii)—can be taken to be the full subcategory of consisting of finitely presentable objects. (There may be inequivalent choices of , as it is in general only determined up to idempotent completion; this will not concern us.)

This seems to completely solve the problem of identifying when T is of presheaf type: check whether Mod(T) is finitely accessible and if so, recover the presheaf topos as Set-functors on the full subcategory of finitely presentable models. There is a subtlety here, however, as pointed out (probably for the first time) by Johnstone [10].
Minimal complements for degrees below 0′
Authors: Lewis Andrew
Published: March 2005

It is shown that for every (Turing) degree 0 < a < 0′ there is a minimal degree m < 0′ such that a ∨ m = 0′ (and therefore a ∧ m = 0).
A structural investigation on formal topology: coreflection of formal covers and exponentiability
Authors: Maietti Maria Emilia , Valentini Silvio
Published: March 2005

We present and study the category of formal topologies and some of its variants. Two main results are proven. The first is that, for any inductively generated formal cover, there exists a formal topology whose cover extends in the minimal way the given one. This result is obtained by enhancing the method for the inductive generation of the cover relation by adding a coinductive generation of the positivity predicate. Categorically, this result can be rephrased by saying that inductively generated formal topologies are coreflective into inductively generated formal covers.

The second result is that unary formal covers are exponentiable in the category of inductively generated formal covers and hence, thanks to the coreflection, unary formal topologies are exponentiable in the category of inductively generated formal topologies.

From a localic point of view the exponentiability of unary formal topologies means that algebraic dcpos are exponentiable in the category of open locales. But, the coreflection theorem states that open locales are coreflective in locales and hence, as a consequence of well-known impredicative results on exponentiable locales, it allows to prove that locally compact open locales are exponentiable in the category of open locales.
Elimination theory for addition and the frobenius map in polynomial rings
Authors: Pheidas Thanases , Zahidi Karim
Published: March 2005

We develop an elimination theory for addition and the Frobenius map over rings of polynomials. As a consequence we show that if F is a countable, recursive and perfect field of positive characteristic p, with decidable theory, then the structure of addition, the Frobenius map x → xp and the property ‘x ∈ F1, over the ring of polynomials F[T], has a decidable theory.
Higher-order semantics and extensionality
Authors: Benzmüller Christoph , Brown Chad E. , Kohlhase Michael
Published: March 2005

In this paper we re-examine the semantics of classical higher-order logic with the purpose of clarifying the role of extensionality. To reach this goal, we distinguish nine classes of higher-order models with respect to various combinations of Boolean extensionality and three forms of functional extensionality. Furthermore, we develop a methodology of abstract consistency methods (by providing the necessary model existence theorems) needed to analyze completeness of (machine-oriented) higher-order calculi with respect to these model classes.
Comparing DNR and WWKL
Authors: Ambos-Spies Klaus , Kjos-Hanssen Bjørn , Lempp Steffen , Slaman Theodore A.
Published: March 2005

In Reverse Mathematics, the axiom system DNR. asserting the existence of diagonally non-recursive functions, is strictly weaker than WWKL0 (weak weak König's Lemma).
A finite model-theoretical proof of a property of bounded query classes within PH
Authors: Kołodziejczyk Leszek Aleksander
Published: March 2005

We use finite model theory (in particular, the method of FM-truth definitions, introduced in [MM01] and developed in [K04], and a normal form result akin to those of [Ste93] and [G97]) to prove:

Let m ≥ 2. Then:

(A) If there exists k such that NP⊆ Σm TIME(nk)∩ Πm TIME(nk), then for every r there exists kr such that :

(B) If there exists a superpolynomial time-constructible function f such that NTIME(f), then additionally .

This strengthens a result by Mocas [M96] that for any r, .

In addition, we use FM-truth definitions to give a simple sufficient condition for the arity hierarchy to be strict over finite models.
Bounding prime models
Authors: Csima Barbara F. , Hirschfeldt Denis R. , Knight Julia F. , Soare Robert I.
Published: March 2005

A set X is prime bounding if for every complete atomic decidable (CAD) theory T there is a prime model of T decidable in X. It is easy to see that X = 0′ is prime bounding. Denisov claimed that every X <T 0′ is not prime bounding, but we discovered this to be incorrect. Here we give the correct characterization that the prime bounding sets X ≤τ 0′ are exactly the sets which are not low2. Recall that X is low2 if X″ ≤τ 0″. To prove that a low2 set X is not prime bounding we use a 0′ -computable listing of the array of sets {Y : Y ≤τX } to build a CAD theory T which diagonalizes against all potential X-decidable prime models of T, To prove that any non-low2X is indeed prime bounding. we fix a function f ≤TX that is not dominated by a certain 0′-computable function that picks out generators of principal types. Given a CAD theory T. we use f to eventually find, for every formula φ(x̄) con sistent with T. a principal type which contains it. and hence to build an X-decidable prime model of T. We prove the prime bounding property equivalent to several other combinatorial properties, including some related to the limitwise monotonic functions which have been introduced elsewhere in computable model theory.
The Mitchell order below rank-to-rank
Authors: Neeman Itay
Published: March 2005

We show that Mitchell order on downward closed extenders below rank-to-rank type is wellfounded.
There is no SW-complete c.e. real
Authors: Yu Liang , Ding Decheng
Published: March 2005

We prove that there is no sw-complete c.e. real, negatively answering a question in [6].
Bi-coloured fields on the complex numbers
Authors: Zilber B.
Published: March 2005

We consider two theories of “bad fields” constructed by B.Poizat using Hrushovski's amalgamation and show that these theories have natural models representable as the field of complex numbers with a distinguished subset given as a union of countably many real analytic curves. One of the two examples is based on the complex exponentiation and the proof assumes Schanuel's conjecture.
Some model theory of sheaves of modules
Authors: Prest Mike , Puninskaya Vera , Ralph Alexandra
Published: March 2005

We explore some topics in the model theory of sheaves of modules. First we describe the formal language that we use. Then we present some examples of sheaves obtained from quivers. These, and other examples, will serve as illustrations and as counterexamples. Then we investigate the notion of strong minimality from model theory to see what it means in this context. We also look briefly at the relation between global, local and pointwise versions of properties related to acyclicity.
Generalized high degrees have the complementation property
Authors: Greenberg Noam , Montalbán Antonio , Shore Richard A.
Published: March 2005

We show that if d ∈ GH1 then (≤ d) has the complementation property, i.e., for all a < d there is some b < d such that a ∧ b = 0 and a ∨ b = d.
Coordinatisation by binding groups and unidimensionality in simple theories
Authors: Shami Ziv
Published: March 2005

In a simple theory with elimination of finitary hyperimaginaries if tp(a) is real and analysable over a definable set Q, then there exists a finite sequence (ai \ i ≤ n*) ⊆ dcleq(a) with an* = a such that for every i ≤ n* if pi = tp(ai/{aj |j < i}) then Aut(pi / Q) is type-definable with its action on . A unidimensional simple theory eliminates the quantifier ∃∞ and either interprets (in Ceq) an infinite type-definable group or has the property that ACL(Q) = C for every infinite definable set Q.
Local homogeneity
Authors: Baizhanov Bektur , Baldwin John T.
Published: March 2005

We study the expansion of stable structures by adding predicates for arbitrary subsets. Generalizing work of Poizat-Bouscaren on the one hand and Baldwin-Benedikt-Casanovas-Ziegler on the other we provide a sufficient condition (Theorem 4.7) for such an expansion to be stable. This generalization weakens the original definitions in two ways: dealing with arbitrary subsets rather than just submodels and removing the ‘small’ or ‘belles paires’ hypothesis. We use this generalization to characterize in terms of pairs, the ‘triviality’ of the geometry on a strongly minimal set (Theorem 2.5). Call a set A benign if any type over A in the expanded language is determined by its restriction to the base language. We characterize the notion of benign as a kind of local homogenity (Theorem 1.7). Answering a question of [8] we characterize the property that M has the finite cover property over A (Theorem 3.9).
More on regular reduced products
Authors: Kennedy Juliette Cara , Shelah Saharon
Published: March 2005

The authors show, by means of a finitary version of the combinatorial principle of [7]. the consistency of the failure, relative to the consistency of supercompact cardinals, of the following: for all regular filters D on a cardinal λ. if Mi and Ni are elementarily equivalent models of a language of size ≤ λ, then the second player has a winning strategy in the Ehrenfeucht-Fraïssé game of length λ+ on ΠiMi/D and ΠiNi/D. If in addition 2λ = λ+ and i < λ implies |Mi| + |Ni| ≤ λ+ this means that the ultrapowers are isomorphic. This settles negatively conjecture 18 in [2].
Jonsson-like partition relations and j: V → V
Authors: Apter Arthur W. , Sargsyan Grigor
Published: March 2005

Working in the theory ”ZF + There is a nontrivial elementary embedding j : V → V“, we show that a final segment of cardinals satisfies certain square bracket finite and infinite exponent partition relations. As a corollary to this, we show that this final segment is composed of Jonsson cardinals. We then show how to force and bring this situation down to small alephs. A prototypical result is the construction of a model for ZF in which every cardinal μ ≥ ℵ2 satisfies the square bracket infinite exponent partition relation . We conclude with a discussion of some consistency questions concerning different versions of the axiom asserting the existence of a nontrivial elementary embedding j: V → V. By virtue of Kunen's celebrated inconsistency result, we use only a restricted amount of the Axiom of Choice.
Theories of arithmetics in finite models
Authors: Krynicki Michał , Zdanowski Konrad
Published: March 2005

We investigate theories of initial segments of the standard models for arithmetics. It is easy to see that if the ordering relation is definable in the standard model then the decidability results can be transferred from the infinite model into the finite models. On the contrary we show that the Σ2–theory of multiplication is undecidable in finite models. We show that this result is optimal by proving that the Σ1–theory of multiplication and order is decidable in finite models as well as in the standard model. We show also that the exponentiation function is definable in finite models by a formula of arithmetic with multiplication and that one can define in finite models the arithmetic of addition and multiplication with the concatenation operation.

We consider also the spectrum problem. We show that the spectrum of arithmetic with multiplication and arithmetic with exponentiation is strictly contained in the spectrum of arithmetic with addition and multiplication.
Model completeness of o-minimal structures expanded by Dedekind cuts
Authors: Tressl Marcus
Published: March 2005

§1. Introduction. LetMbe a totally ordered set. A (Dedekind) cutpofMis a couple (pL,pR) of subsetspL,pRofMsuch thatpL⋃pR=MandpL<pR, i.e.,a<bfor alla∈pL,b∈pR. In this article we are looking for model completeness results of o-minimal structuresMexpanded by a setpLfor a cutpofM. This means the following. LetMbe an o-minimal structure in the languageLand supposeMis model complete. LetDbe a new unary predicate and letpbe a cut of (the underlying ordered set of)M. Then we are looking for a natural, definable expansion of theL(D)-structure (M,pL) which is model complete.

The first result in this direction is a theorem of Cherlin and Dickmann (cf. [Ch-Dic]) which says that a real closed field expanded by a convex valuation ring has a model complete theory. This statement translates into the cuts language as follows. IfZis a subset of an ordered setMwe writeZ+for the cutpwithpR= {a∈M∣a>Z} andZ−for the cutqwithqL= {a∈M∣a<Z}.
Generic substitutions
Authors: Panti Giovanni
Published: March 2005

Up to equivalence, a substitution in propositional logic is an endomorphism of its free algebra. On the dual space, this results in a continuous function, and whenever the space carries a natural measure one may ask about the stochastic properties of the action. In classical logic there is a strong dichotomy: while over finitely many propositional variables everything is trivial, the study of the continuous transformations of the Cantor space is the subject of an extensive literature, and is far from being a completed task. In many-valued logic this dichotomy disappears: already in the finite-variable case many interesting phenomena occur, and the present paper aims at displaying some of these.
The finite model property for knotted extensions of propositional linear logic
Authors: van Alten C. J.
Published: March 2005

The logics considered here are the propositional Linear Logic and propositional Intuitionistic Linear Logic extended by a knotted structural rule: . It is proved that the class of algebraic models for such a logic has the finite embeddability property, meaning that every finite partial subalgebra of an algebra in the class can be embedded into a finite full algebra in the class. It follows that each such logic has the finite model property with respect to its algebraic semantics and hence that the logic is decidable.
Derivations of the Frobenius map
Authors: Kowalski Piotr
Published: March 2005

We prove that the theory of fields with a derivation of Frobenius has the model companion which is stable and admits elimination of quantifiers up to the level of the λ-functions. Along the way, we give new geometric axioms of DCFp.
The computable dimension of trees of infinite height
Authors: Miller Russell
Published: March 2005

We prove that no computable tree of infinite height is computably categorical, and indeed that all such trees have computable dimension ω. Moreover, this dimension is effectively ω, in the sense that given any effective listing of computable presentations of the same tree, we can effectively find another computable presentation of it which is not computably isomorphic to any of the presentations on the list.
Subsets of superstable structures are weakly benign
Authors: Baizhanov Bektur , Baldwin John T. , Shelah Saharon
Published: March 2005

Baizhanov and Baldwin [1] introduce the notions of benign and weakly benign sets to investigate the preservation of stability by naming arbitrary subsets of a stable structure. They connect the notion with work of Baldwin, Benedikt, Bouscaren, Casanovas, Poizat, and Ziegler. Stimulated by [1], we investigate here the existence of benign or weakly benign sets.

Definition 0.1. (1) The set A is benign in M if for every α, β ∊ M if p = tp(α/A) = tp(β/A) then tp*(α/A) = tp*(β/A) where the *-type is the type in the language L* with a new predicate P denoting A.

(2) The set A is weakly benign in M if for every α,β ∊ M if p = stp(α/A) = stp(β/A) then tp*(α/A) = tp*(β/A) where the *-type is the type in language with a new predicate P denoting A.

Conjecture 0.2 (too optimistic). If M is a model of stable theory T and A ⊆ M then A is benign.

Shelah observed, after learning of the Baizhanov-Baldwin reductions of the problem to equivalence relations, the following counterexample.

Lemma 0.3. There is an ω-stable rank 2 theory T with ndop which has a model M and set A such that A is not benign in M.
Computable categoricity of trees of finite height
Authors: Lempp Steffen , McCoy Charles , Miller Russell , Solomon Reed
Published: March 2005

We characterize the structure of computably categorical trees of finite height, and prove that our criterion is both necessary and sufficient. Intuitively, the characterization is easiest to express in terms of isomorphisms of (possibly infinite) trees, but in fact it is equivalent to a -condition. We show that all trees which are not computably categorical have computable dimension ω. Finally, we prove that for every n ≥ 1 in ω, there exists a computable tree of finite height which is Σ30-categorical but not Δn3-categorical
Interpolation for extended modal languages
Authors: ten Cate Balder
Published: March 2005

Several extensions of the basic modal language are characterized in terms of interpolation. Our main results are of the following form: Language L′ is the least expressive extension of L with interpolation. For instance, let ℳ(D) be the extension of the basic modal language with a difference operator [7], First-order logic is the least expressive extension of ℳ(D) with interpolation. These characterizations are subsequently used to derive new results about hybrid logic, relation algebra and the guarded fragment.
On the weak non-finite cover property and the n-tuples of simple structures
Authors: Vassiliev Evgueni
Published: March 2005

The weak non-finite cover property (wnfcp) was introduced in [1] in connection with “axiomatizability” of lovely pairs of models of a simple theory. We find a combinatorial condition on a simple theory equivalent to the wnfcp, yielding a direct proof that the non-finite cover property implies the wnfcp, and that the wnfcp is preserved under reducts. We also study the question whether the wnfcp is preserved when passing from a simple theory T to the theory Tp of lovely pairs of models of T (true in the stable case). While the question remains open, we show, among other things, that if (for a T with the wnfcp) Tp is low, then TP has the wnfcp. To study this question, we describe “double lovely pairs”, and, along the way, we develop the notion of a “lovely n-tuple” of models of a simple theory, which is an analogue of the notion of a beautiful tuple of models of stable theories [2].
On the definable ideal generated by nonbounding c.e. degrees
Authors: Yu Liang , Yang Yue
Published: March 2005

Let [NB]1 denote the ideal generated by nonbounding c.e. degrees and NCup the ideal of noncuppable c.e. degrees. We show that both [NB]1 ∩ NCup and the ideal generated by nonbounding and noncuppable degrees are new, in the sense that they are different from M, [NB]1 and NCup—the only three known definable ideals so far.
Fusing o-minimal structures
Authors: Wilkie A.J.
Published: March 2005

In this note I construct a proper o-minimal expansion of the ordered additive group of rationals.
On an algebra of lattice-valued logic
Authors: Hansen Lars
Published: March 2005

The purpose of this paper is to present an algebraic generalization of the traditional two-valued logic. This involves introducing a theory of automorphism algebras, which is an algebraic theory of many-valued logic having a complete lattice as the set of truth values. Two generalizations of the two-valued case will be considered, viz., the finite chain and the Boolean lattice. In the case of the Boolean lattice, on choosing a designated lattice value, this algebra has binary retracts that have the usual axiomatic theory of the propositional calculus as suitable theory. This suitability applies to the Boolean algebra of formalized token models [2] where the truth values are, for example, vocabularies. Finally, as the actual motivation for this paper, we indicate how the theory of formalized token models [2] is an example of a many-valued predicate calculus.
Relative randomness and real closed fields
Authors: Raichev Alexander
Published: March 2005

We show that for any real number, the class of real numbers less random than it, in the sense of rK-reducibility, forms a countable real closed subfield of the real ordered field. This generalizes the well-known fact that the computable reals form a real closed field.

With the same technique we show that the class of differences of computably enumerable reals (d.c.e. reals) and the class of computably approximable reals (c.a. reals) form real closed fields. The d.c.e. result was also proved nearly simultaneously and independently by Ng (Keng Meng Ng, Master's Thesis, National University of Singapore, in preparation).

Lastly, we show that the class of d.c.e. reals is properly contained in the class or reals less random than Ω (the halting probability), which in turn is properly contained in the class of c.a. reals, and that neither the first nor last class is a randomness class (as captured by rK-reducibility).
The isomorphism problem for computable Abelian p-groups of bounded length
Authors: Calvert Wesley
Published: March 2005

Theories of classification distinguish classes with some good structure theorem from those for which none is possible. Some classes (dense linear orders, for instance) are non-classifiable in general, but are classifiable when we consider only countable members. This paper explores such a notion for classes of computable structures by working out a sequence of examples.

We follow recent work by Goncharov and Knight in using the degree of the isomorphism problem for a class to distinguish classifiable classes from non-classifiable. In this paper, we calculate the degree of the isomorphism problem for Abelian p-groups of bounded Ulm length. The result is a sequence of classes whose isomorphism problems are cofinal in the hyperarithmetical hierarchy. In the process, new back-and-forth relations on such groups are calculated.
On relatively analytic and Borel subsets
Authors: Miller Arnold W.
Published: March 2005

Define to be the smallest cardinality of a function f: X→Y with I, X, Y, ⊆ 2ω such that there is no Borel function g ⊇ f. In this paper we prove that it is relatively consistent with ZFC to have b < where b is, as usual, smallest cardinality of an unbounded family in Ωω. This answers a question raised by Zapletal.

We also show that it is relatively consistent with ZFC that there exists X ⊆ 2ω such that the Borei order of X is bounded but there exists a relatively analytic subset of X which is not relatively coanalytic. This answers a question of Mauldin.