bluuebunny/crossref_metadata_2025 huggingface dataset:
Modal analysis of generalized rosser sentences
Authors: Švejdar Vítězslav
Published: May 2006

A modal theory Z using the Guaspari witness comparison signs ≤, < is developed. The theory Z is similar to, but weaker than, the theory R of Guaspari and Solovay. Nevertheless, Z proves the independence of the Rosser fixed-point. A Kripke semantics for Z is presented and some arithmetical interpretations of Z are investigated. Then Z is enriched to ZI by adding a new modality sign for interpretability and by axioms expressing some facts about interpretability of theories. Two arithmetical interpretations of ZI are presented. The proofs of the validity of the axioms of ZI in arithmetical interpretations use some strengthening of Solovay's result about interpretability in Gödel-Bernays set theory.
Random models and the Gödel case of the decision problem
Authors: Gurevich Yuri , Shelah Saharon
Published: May 2006

In a paper of 1933 Gödel proved that every satisfiable first-order ∀2∃* sentence has a finite model. Actually he constructed a finite model in an ingenious and sophisticated way. In this paper we use a simple and straightforward probabilistic argument to establish existence of a finite model of an arbitrary satisfiable ∀2∃* sentence.
A tableau system of proof for predicate-functor logic with identity
Authors: Grünberg Teo
Published: May 2006

Quine has given a method for eliminating the bound variables in first-order predicate logic establishing thus a variable-free formulation called predicate-functor logic. The purpose of this paper is to give an autonomous and complete proof procedure for Quine's predicate-functor logic with identity, without presupposing axioms or inference rules for quantification theory or, for that matter, any other logic.
The relative efficiency of propositional proof systems
Authors: Cook Stephen A. , Reckhow Robert A.
Published: May 2006

We are interested in studying the length of the shortest proof of a propositional tautology in various proof systems as a function of the length of the tautology. The smallest upper bound known for this function is exponential, no matter what the proof system. A question we would like to answer (but have not been able to) is whether this function has a polynomial bound for some proof system. (This question is motivated below.) Our results here are relative results.

In §§2 and 3 we indicate that all standard Hilbert type systems (or Frege systems, as we call them) and natural deduction systems are equivalent, up to application of a polynomial, as far as minimum proof length goes. In §4 we introduce extended Frege systems, which allow introduction of abbreviations for formulas. Since these abbreviations can be iterated, they eliminate the need for a possible exponential growth in formula length in a proof, as is illustrated by an example (the pigeonhole principle). In fact, Theorem 4.6 (which is a variation of a theorem of Statman) states that with a penalty of at most a linear increase in the number of lines of a proof in an extended Frege system, no line in the proof need be more than a constant times the length of the formula proved.
Failures of the interpolation lemma in quantified modal logic
Authors: Fine Kit
Published: May 2006

Beth's Definability Theorem, and consequently the Interpolation Lemma, fail for the version of quantified S5 that is presented in Kripke's [6]. These failures persist when the constant domain axiom-scheme ∀x□φ ≡ □∀xφ is added to S5 or, indeed, to any weaker extension of quantificational K.

§1 reviews some standard material on quantificational modal logic. This is in contrast to quantified intermediate logics for, as Gabbay [6] has shown, the Interpolation Lemma holds for the logic CD with constant domains and for several of its extensions. §§2—4 establish the negative results for the systems based upon S5. §5 establishes a more general negative result and, finally, §6 considers some positive results and open problems. A basic knowledge of classical and modal quantificational logic is presupposed.

Let me briefly review the relevant model theory for quantified modal logic. Further details can be found in [3] or [7].

The language is obtained from the language for classical first-order logic with identity by adding a unary operator □ for necessity. The atomic formula ‘Ex’ is used as an abbreviation for ‘∃y(y = x)’ and may be read as ‘x exists’.
Another algorithm for bracket abstraction
Authors: Turner D. A.
Published: May 2006

This short article presents an algorithm for bracket abstraction [1] which avoids a combinatorial explosion in the size of the resulting expression when applied repeatedly for abstraction in a series of variables. It differs from a previous solution [2] in introducing only a finite number of additional combinators and in not requiring that all the variables to be abstracted be treated together in a single operation.
Recursively presented Abelian groups: Effective p-Group theory. I
Authors: Lin Charlotte
Published: May 2006

The study of effectiveness in classical mathematics is rapidly expanding, through recent research in algebra, topology, model theory, and functional analysis. Well-known contributors are Barwise (Wisconsin), Crossley (Monash), Dekker (Rutgers), Ershoff (Novosibirsk), Feferman (Stanford), Harrington (Berkeley), Mal′cev (Novosibirsk), Morley (Cornell), Nerode (Cornell), Rabin (Hebrew University), Shore (Cornell). Further interesting work is due to Kalantari (University of California, Santa Barbara), Metakides (Rochester), Millar (Wisconsin), Remmel (University of California, San Diego), Nurtazin (Novosibirsk). Areas investigated include enumerated algebras, models of complete theories, vector spaces, fields, orderings, Hilbert spaces, and boolean algebras.

We investigate the effective content of the structure theory of p-groups. Recall that a p-group is a torsion abelian group in which the (finite) order of each element is some power of a fixed prime p. (In the sequel, “group” = “additively written abelian group”.)

The structure theory of p-groups is based on the two elementary notions of order and height. Recall that the order of x is the least integer n such that nx = 0. The height of x is the number of times p divides x, that is, the least n such that x = pny for some y in the group but x ≠ pn+1y for any y. If for each n ∈ ω there is a “pnth-root” yn, so that x = pnyn, then we say that x has infinite height. In 1923, Prüfer related the two notions as criteria for direct sum decomposition, proving

Theorem. Every group of bounded order is a direct sum of cyclic groups, and

Theorem. Every countable primary group with no (nonzero) elements of infinite height is a direct sum of cyclic groups.
A recursive model for arithmetic with weak induction
Authors: Adamowicz Zofia , Morales-Luna Guillermo
Published: May 2006

Before stating the results we would like to thank the referee for reorganizing the whole paper and changing its original logical terminology to an algebraical terminology.

Let Z* be a proper elementary extension of the integral domain Z. For any b ∈ Z*∖Z we define Z〈b〉 as the following subring of Z*:

It is easy to prove that the natural divisibility relation on Z〈b〉 is the restriction to Z〈b〉 of the divisibility on Z* (see Lemma 1.1 below). The much stronger statement that Z〈b〉 is algebraically closed in Z* does not hold for all b. Similarly, there are many b's such that Z〈b〉 is not a recursive ring, e.g. if the set of standard primes dividing b is not recursive then Z〈b〉 cannot be a recursive ring under any bijection with N.

Our main result is the following.

Theorem. There exists an element b ∈ Z*∖Z such that

(1) Z〈b〉 is algebraically closed in Z*,

(2) Z〈b〉 is a recursive ring, and

(3) each infinite element of Z〈b〉 is divisible by a standard integer > 1 (so the only “primes” of Z〈b〉 are the standard ones).

An easy consequence of (1) is that certain induction axioms are satisfied by Z〈b〉. This explains the title of the paper. In the last section of the paper, §3, we shall say more about this.
Sur la théorie élémentaire des corps de fonctions
Authors: Duret Jean-Louis
Published: May 2006

We study the first order theory of function fields in the language of fields by using fundamental results on curves in algebraic geometry. We give some applications; for example, using a theorem of G. Cherlin, we prove the undecidability of function fields with nonzero characteristic over an algebraically closed field.
Elementary equivalence of Cσ(K) spaces for totally disconnected, compact Hausdorff K
Authors: Heinrich S. , Henson C. Ward , Moore L. C.
Published: May 2006

This paper is a continuation of the authors' paper [7]; in particular, we give a sharper and more useful criterion for the approximate elementary equivalence of Cσ(K) spaces, where K is a totally disconnected compact Hausdorff space. (See Theorem 2 below.) As an application, we obtain a complete description of the Banach spaces X which are approximately equivalent to c0. Namely, X ≡ Ac0 iff X = Cσ(K) where K is a totally disconnected compact Hausdorff space which has a dense set of isolated points and σ is an involutory homeomorphism on K which has a unique fixed point t, and t is not an isolated point. (See Theorem 7.)

These results are derived from an analysis which we give of the elementary theories of structures (B, σ), where B is a Boolean algebra and σ is an involutory automorphism of B which leaves at most one nontrivial ultrafilter invariant. Let U(σ) denote this ultrafilter, if it exists; let U(σ) = B in case σ leaves no nontrivial ultrafilter invariant. We show that the elementary theory of (B, σ) is completely determined by the theory of (B, U(σ)) (and conversely, because U(σ) is definable in (B, σ)). This makes possible the use of the explicit invariants given by Éršov [4] for structures (B, U) where U is an ultrafilter on B. (These generalize the Tarski invariants for Boolean algebras [15].) We also use the Éršov invariants in the proof of our main result.
Finest partitions for ultrafilters
Authors: Kanamori Akihiro
Published: May 2006

If a uniform ultrafilter U over an uncountable cardinal κ is not outright countably complete, probably the next best thing is that it have a finest partition: a master function f:κ → ω with ƒ−({n}) ∉ U for each n ϵ ω such that for any g: κ → κ, either (a) it is one-to-one on a set in U, or (b) it factors through ƒ (mod U), i.e. for some function h, {α < κ ∣ h(f(α)) = g(α)} ϵ U. In this paper, it is shown that recent contructions of irregular ultrafilters over ω1 can be amplified to incorporate a finest partition.

Henceforth, let us assume that all ultrafilters are uniform.

There has been an extensive study of substantial hypotheses, which are nonetheless weaker than countable completeness, on ultrafilters over uncountable cardinals. To survey some results and to establish a context, let us first recall the Rudin-Keisler (RK) ordering on ultrafilters: If Ui is an ultrafilter over Iii for i = 1, 2, then U1 ≤RKU2 iff there is a projecting function Ψ:I2 → I1 such that U1 = Ψ*(U2) = {X ⊆, I1∣ Ψ−1(X) ϵ U2}· U1, =RKU2 iff U1, ≤RK and U2 and U2≤RKU1; and U1<RKU2 iff U1≤RKU2 yet U1 ≠RKU2. In terms of this ordering, if an ultrafilter U has a finest partition ƒ, then ƒ*(U) over ω is maximum amongst all RK predecessors of U: for any g:κ → κ, if g*(U)  ω is indecomposable iff whenever ω < λ < κ, there is no V ≤RKU such that V is a (uniform) ultrafilter over λ.
The order indiscernibles of divisible ordered abelian groups
Authors: Rosenthal David
Published: May 2006

There has been much work in developing the interconnections between model theory and algebra. Here we look at a particular example, the divisible ordered abelian groups, and show how the indiscernibles are related to the algebraic structure. Now a divisible ordered abelian group is a model of Th (Q, +, 0, <) and so is linearly ordered by <. Thus the theory is unstable and has a large number of models. It is therefore unrealistic to expect that a simple condition will completely determine a model. Instead we would just like to obtain nice algebraic invariants.

Definition. A subset C of a divisible ordered abelian group is a set of (order) indiscernibles iff for every sequence of integers n1,…,nk and for every c1 < … < ck and d1 < … < dk in C

Note that this simplified form of indiscernibility is an immediate consequence of quantifier elimination for the theory. The above definition could be formulated in the language of +, 0, < but we have used subtraction as a matter of convenience. Similarly we may also use rational coefficients. Also note that a set of order indiscernibles is usually defined with respect to some external order. But in this case there are only two possibilities: the ordering inherited from or its reverse. So we will always assume that a set of order indiscernibles has the ordering inherited from . We may sometimes refer to a set of indiscernibles as a sequence of indiscernibles if we want to explicitly mention the ordering associated with the set.
Self-reference with negative types
Authors: Hiller A. P. , Zimbarg J.
Published: May 2006

The universe of sets, V, is usually seen as an entity structured in successive levels, each level being made up of objects and collections of objects belonging to the previous levels. This process of obtaining sets and axioms for set theory can be seen in Scott [74] and Shoenfield [77].

The approach we want to take differs from the previous one very strongly: the seeds from which we want to generate our universe of classes are to be the one-variable predicates (given by one-free-variable formulas) of the formal language we shall be using. In other words, any one-variable predicate of the language is to be represented as a class in our universe. In this sense, we view our theory as being about a self-referential language, a language whose predicates refer to objects which are predicates of the language itself.

We want, in short, a system such that: (i) any predicate may be represented by an object to be studied by the theory itself; (ii) the axioms for the theory may be derived from the general principle that we are dealing with a language that aims at describing its own predicates; and (iii) the theory should be strong enough to derive ZFC and suggest answers to the existence of large cardinals and to the continuum hypothesis.

An objection to such a project arises immediately: in view of the Russell-Zermelo paradox, how is it possible to have all predicates of the language as elements of the universe? This objection will be easy to deal with: we shall provide our language with a type structure to avoid paradox.
Idempotent ideals on abelian groups
Authors: Pelc Andrzej
Published: May 2006

An ideal I defined on a group G is called idempotent if for every A ∈ I, {g ∈ G:Ag−1 ∉ ∈ I} ∈ I. We show that a countably complete idempotent ideal on an abelian group cannot be prime but may have strong saturation properties.
Intuitionistic fuzzy logic and intuitionistic fuzzy set theory
Authors: Takeuti Gaisi , Titani Satoko
Published: May 2006

In 1965 Zadeh introduced the concept of fuzzy sets. The characteristic of fuzzy sets is that the range of truth value of the membership relation is the closed interval [0, 1] of real numbers. The logical operations ⊃, ∼ on [0, 1] which are used for Zadeh's fuzzy sets seem to be Łukasiewciz's logic, where p ⊃ q = min(1, 1 − p + q), ∼ p = 1 − p. L. S. Hay extended in [4] Łukasiewicz's logic to a predicate logic and proved its weak completeness theorem: if P is valid then P + Pn is provable for each positive integer n. She also showed that one can without losing consistency obtain completeness of the system by use of additional infinitary rule.

Now, from a logical standpoint, each logic has its corresponding set theory in which each logical operation is translated into a basic operation for set theory; namely, the relation ⊆ and = on sets are translation of the logical operations → and ↔. For Łukasiewicz's logic, P Λ (P ⊃ Q). ⊃ Q is not valid. Translating it to the set version, it follows that the axiom of extensionality does not hold. Thus this very basic principle of set theory is not valid in the corresponding set theory.
A generalization of Tennenbaum's theorem on effectively finite recursive linear orderings
Authors: Watnick Richard
Published: May 2006

An effective translation of the fact that any infinite ordered set contains an infinite ascending or descending sequence is that any infinite recursive set A ⊆ Q has a recursive subset with order type ω or ω*. Tennenbaum's theorem states that this translation is false, and there is a counterexample A with order type ω + ω*. Tennenbaum suggested that this counterexample is an infinite recursive linearly ordered set which is effectively finite, and that the collection of all such counterexamples could provide a concrete model of nonstandard arithmetic. The purpose of this paper is to determine the collection of order types for which there is a counterexample.

It is readily seen that any counterexample to the effective translation must have order type ω + Z · α + ω* for some α [2], [3]. Let be the collection of order types α for which there is a counterexample. As a test case, we have previously shown that contains the constructive scattered orderings [3], [4]. In this paper we determine exactly which order types are in . We easily show that if ω+ Z · α + ω* is recursive, then α is . The main result is that . Consequently, .
Ordinal definability in Jensen's model
Authors: Zadrożny Włodzimierz
Published: May 2006

In [J] R. Jensen proved that any model of ZFC can be generically extended to a model of ZFC + (∃a ⊆ ω)(V = L[a]). This extension was made via a class P of forcing conditions. One can ask what can be said about the class HOD in such extensions. In particular one can ask whether V = HOD holds in Jensen's model. A full answer to this question is given by the following assertion:

Theorem. Let N = L[a] be given by forcing with Jensen's conditions (the classP).

Then:

1. N ⊨ V ≠ HOD,

2. N ⊨ (∀n < ω)(HODn + 1 ⊈ HODω).

3. N ⊨ (∀α ≥ ω)(HODα = HODω), or equivalently HODω + 1 = HODω.

The result is established by investigating homogeneity properties of certain complete Boolean algebras that are associated with the partial orderings of forcing conditions for coding using almost disjoint sets.

We explain shortly the first of our two technical results: It is rather well known that if we have a subset then by performing threefold almost disjoint coding we come to a set a0 ⊆ ω such that ; cf. [JS]. This is achieved by iterating over almost disjoint forcing . That means we first code by a subset , of [ω1ω2) using the almost disjoint forcing conditions . Then we code by aω, contained in [ω, ω1), using forcing with over .
Effective discontinuity and a characterisation of the superjump
Authors: Hartley John P.
Published: May 2006

One of the most fundamental results of higher-type recursion theory was first proved by Thomas Grilliot [3]. He showed that the functional embodying number quantification, 2E, is computable from a type-2 object F if and only if F has an effective discontinuity. For the background to this work we recommend Normann's book [9] or his summary [10], and for an example of its many applications Normann-Wainer [11].

The purpose of §1 of this paper is to give an effective proof of the “only if” part of this result: i.e. a construction of a discontinuity of F from the information 2E = {e}F. This contrasts with Grilliot's argument which is topological and nonconstructive, and shows that “Grilliot's trick” for computing 2E from a discontinuity of F is essentially the only method.

We then apply the method to two more general situations in which it gives new results. In §2 we treat type-3 objects in which 3E is computable (assuming AC and CH), and obtain a strengthening of the result of Hartley [5, §5]. In §3 we consider the superjump and characterise it as the least among a class of functionals with a particular sort of family of discontinuities.
More on proper forcing
Authors: Shelah Saharon
Published: May 2006

§1. A counterexample and preservation of “proper + X”.

Theorem. Suppose V satisfies, , and for some A ⊆ ω1, every B ⊆ ω1, belongs to L[A].

Then we can define a countable support iterationsuch that the following conditions hold:

a) EachQiis proper and ⊩Pi “Qi, has power ℵ1”.

b) Each Qi is -complete for some simple ℵ1-completeness system.

c) Forcing with Pα = Lim adds reals.

Proof. We shall define Qi by induction on i so that conditions a) and b) are satisfied, and Ci, is a Qi-name of a closed unbounded subset of ω1. Let : ξ < ω1› ∈ L[A] be a list of all functions f which are from δ to δ for some δ < ω1 and let h: ω1 → ω1, h ∈ L[A], be defined by h(α) = Min{β: β > α and Lβ[A]⊨ “∣α∣ = ℵ0”}.

Suppose we have defined Qj for every j < i; then Pi is defined, is proper (as each Qj, j < i, is proper, and by III 3.2) and has a dense subset of power ℵ (by III 4.1). Let Gi ⊆ Pi be generic so clearly there is B ⊆ ω1, such that in V[Gi] every subset of ω1 belongs to L[A, B], The following now follows:

Fact. In V[Gi], every countableN ⥽(H(ℵ2), ∈, A, B) is isomorphic toLβ[A ∩ δ, B ∩ δ] for some β < h(δ), where δ = δ(N) = ω1, ∩ N.
Pseudo-jump operators. II: Transfinite iterations, hierarchies and minimal covers
Authors: Jockusch Carl G. , Shore Richard A.
Published: May 2006

In this paper we introduce a new hierarchy of sets and operators which we call the REA hierarchy for “recursively enumerable in and above”. The hierarchy is generated by composing (possibly) transfinite sequences of the pseudo-jump operators considered in Jockusch and Shore [1983]. We there studied pseudo-jump operators defined by analogy with the Turing jump as ones taking a set A to A ⊕ for some index e. We would now call these 1-REA operators and will extend them to α-REA operators for recursive ordinals α in analogy with the iterated Turing jump operators (A → A(α) for α < and Kleene's hyperarithmetic hierarchy. The REA sets will then, of course, be the results of applying these operators to the empty set. They will extend and generalize Kleene's H sets but will still be contained in the class of set singletons thus providing us with a new richer subclass of the set singletons which, as we shall see, is related to the work of Harrington [1975] and [1976] on the problems of Friedman [1975] about the arithmetic degrees of such singletons. Their degrees also give a natural class extending the class H of Jockusch and McLaughlin [1969] by closing it off under transfinite iterations as well as the inclusion of [d, d′] for each degree d in the class. The reason for the class being closed under this last operation is that the REA operators include all operators and so give a new hierarchy for them as well as the sets. This hierarchy also turns out to be related to the difference hierarchy of Ershov [1968], [1968a] and [1970]: every α-r.e. set is α-REA but each level of the REA hierarchy after the first extends all the way through the difference hierarchy although never entirely encompassing even the next level of the difference hierarchy.
Logics containing K4. Part II
Authors: Fine Kit
Published: May 2006

This paper establishes another very general completeness result for the logics within the field of K4. With each finite transitive frame ℭ we may associate a formula — Bℭ which validates just those frames ℑ in which ℭ is not in a certain sense embeddable (to be exact, ℭ is not the p-morphic image of any subframe of ℑ. By a subframe logic we mean the result of adding such formulas as axioms to K4. The general result is that each subframe logic has the finite model property.

There are a continuum of subframe logics and they include many of the standard ones, such as T, S4, S4.3, S5 and G. It turns out that the subframe logics are exactly those complete for a condition that is closed under subframes (any subframe of a frame satisfying the condition also satisfies the condition). As a consequence, every logic complete for a condition closed under subframes has the finite model property.

It is ascertained which of the subframe logics are compact. It turns out that the compact logics are just those whose axioms express an elementary condition. Tests are given for determining whether a given axiom expresses an elementary condition and for determining what it is in case it does.

In one respect the present general completeness result differs from most of the others in the literature. The others have usually either been what one might call logic based or formula based. They have usually either been to the effect that all of the logics containing a given logic are complete or to the effect that all logics whose axioms come from a given syntactically characterized class of formulas are complete. The present result is, by contrast, what one might call frame based. The axioms of the logics to be proved complete are characterized most directly in terms of their connection with certain frames.
A simple relationship between Buchholz's new system of ordinal notations and Takeuti's system of ordinal diagrams
Authors: Okada Mitsuhiro
Published: May 2006

Buchholz [4] simplified the system of ordinal notations of the Schütte school (cf. [12]), by using the notion of collapsing functions (cf. [5]). In this paper we give a simple relationship between Buchholz's new system of ordinal notations and Takeuti's system of ordinal diagrams. From this simple relationship it turns out that the structures of these two systems are very close.

We give two systems OT(I) (§1) and OT(I, A) (§2) of ordinal notations which are considered generalizations of Buchholz's original system, where I and A are well-ordered sets. The original system OT of Buchholz [4] is OT(ω + 1, {0}) in our sense. Here the set OT(I) of ordinal notations is defined as a subset of the set Od(I) of ordinal diagrams in [6], and the set OT(I, A) of ordinal notations as a subset of the set O(I, A) of ordinal diagrams in [14].
Term models for weak set theories with a universal set
Authors: Forster T. E.
Published: May 2006

We shall be concerned here with weak axiomatic systems of set theory with a universal set. The language in which they are expressed is that of set theory—two primitive predicates, = and ϵ, and no function symbols (though some function symbols will be introduced by definitional abbreviation). All the theories will have stratified axioms only, and they will all have Ext (extensionality: (∀x)(∀y)(x = y· ↔ ·(∀z)(z ϵ x ↔ z ϵ y))). In fact, in addition to extensionality, they have only axioms saying that the universe is closed under certain set-theoretic operations, viz. all of the form

and these will always include singleton, i.e., ι′x exists if x does (the iota notation for singleton, due to Russell and Whitehead, is used here to avoid confusion with {x: Φ}, set abstraction), and also x ∪ y, x ∩ y and − x (the complement of x). The system with these axioms is called NF2 in the literature (see [F]). The other axioms we consider will be those giving ⋃x, ⋂x, {y: y ⊆x} and {y: x ⊆ y}. We will frequently have occasion to bear in mind that 〈 V, ⊆ 〉 is a Boolean algebra in any theory extending NF2. There is no use of the axiom of choice at any point in this paper. Since the systems with which we will be concerned exhibit this feature of having, in addition to extensionality, only axioms stating that V is closed under certain operations, we will be very interested in terms of the theories in question. A T-term, for T such a theory, is a thing (with no free variables) built up from V or ∧ by means of the T-operations, which are of course the operations that the axioms of T say the universe is closed under.
Reduced coproducts of compact Hausdorff spaces
Authors: Bankston Paul
Published: May 2006

By analyzing how one obtains the Stone space of the reduced product of an indexed collection of Boolean algebras from the Stone spaces of those algebras, we derive a topological construction, the “reduced coproduct”, which makes sense for indexed collections of arbitrary Tichonov spaces. When the filter in question is an ultrafilter, we show how the “ultracoproduct” can be obtained from the usual topological ultraproduct via a compactification process in the style of Wallman and Frink. We prove theorems dealing with the topological structure of reduced coproducts (especially ultracoproducts) and show in addition how one may use this construction to gain information about the category of compact Hausdorff spaces.
Equalization of finite flowers
Authors: Berardi Stefano
Published: May 2006

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

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

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

The notion of o-minimality was formulated by Pillay and Steinhorn [PS] building on work of van den Dries [D]. Roughly speaking, a theory T is o-minimal if whenever M is a model of T then M is linearly ordered and every definable subset of the universe of M consists of finitely many intervals and points. The theory of real closed fields is an example of an o-minimal theory.

We examine the structure of the countable models for T, T an arbitrary o-minimal theory (in a countable language). We completely characterize these models, provided that T does not have 2ω countable models. This proviso (viz. that T has fewer than 2ω countable models) is in the tradition of classification theory: given a cardinal α, if T has the maximum possible number of models of size α, i.e. 2α, then no structure theorem is expected (cf. [Sh1]).

O-minimality is introduced in §1. §1 also contains conventions and definitions, including the definitions of cut and noncut. Cuts and noncuts constitute the nonisolated types over a set.

In §2 we study a notion of independence for sets of nonisolated types and the corresponding notion of dimension.

In §3 we define what it means for a nonisolated type to be simple. Such types generalize the so-called “components” in Pillay and Steinhorn's analysis of ω-categorical o-minimal theories [PS]. We show that if there is a nonisolated type which is not simple then T has 2ω countable models.
A high strongly noncappable degree
Authors: Lempp Steffen
Published: May 2006

An r.e. degree a ≠ 0, 0′ is called strongly noncappable if it has no inf with any incomparable r.e. degree. We show the existence of a high strongly noncappable degree.
A partial functions version of Church's simple theory of types
Authors: Farmer William M.
Published: May 2006

Church's simple theory of types is a system of higher-order logic in which functions are assumed to be total. We present in this paper a version of Church's system called PF in which functions may be partial. The semantics of PF, which is based on Henkin's general-models semantics, allows terms to be nondenoting but requires formulas to always denote a standard truth value. We prove that PF is complete with respect to its semantics. The reasoning mechanism in PF for partial functions corresponds closely to mathematical practice, and the formulation of PF adheres tightly to the framework of Church's system.
Quantifier elimination in separably closed fields of finite imperfectness degree
Authors: Haran Dan
Published: May 2006

The theory of separably closed fields of a fixed characteristic and a fixed imperfectness degree is clearly recursively axiomatizable. Ershov [1] showed that it is complete, and therefore decidable. Later it became clear that this theory also has the prime extension property in a suitable language (cf. [4, Proposition 1]); hence it admits quantifier elimination. The purpose of this work is to give an explicit, primitive recursive procedure for such quantifier elimination in the case of a finite imperfectness degree.
Uncountable theories that are categorical in a higher power
Authors: Laskowski Michael Chris
Published: May 2006

In this paper we prove three theorems about first-order theories that are categorical in a higher power. The first theorem asserts that such a theory either is totally categorical or there exist prime and minimal models over arbitrary base sets. The second theorem shows that such theories have a natural notion of dimension that determines the models of the theory up to isomorphism. From this we conclude that I(T,ℵα,) = ℵ0 + ∣α∣ where ℵα = the number of formulas modulo T-equivalence provided that T is not totally categorical. The third theorem gives a new characterization of these theories.
Complete local rings as domains
Authors: Stoltenberg-Hansen V. , Tucker J. V.
Published: May 2006

Contents: Introduction. §1: Computable rings and modules. §2: Ideal membership relation. §3: Effective structured domains. §4: Completion of a local ring as a domain. §5: The recursive completion. Epilogue. References.

Introduction. Completion is an important general mathematical device. Often, but not always, a completion takes the following form. Let A be a topological algebraic structure whose topology is derived from a metric. For A, a topological algebra Â and an embedding i: A → Â are constructed such that Â is a complete metric space in which A is densely embedded by i. The long list of structures for which such completions exist begins with Cantor's construction of the real number field and includes objects like the p-adic integers, Baire space, and Boolean algebras. In Bourbaki [6] a careful and thorough account of completions for arbitrary topological groups and fields is given, for which it is important to note that the topological structures need not be metrizable, but must possess a uniformity.

The effectiveness of the completion process of a computable structure A cannot be readily studied using the tools of computable algebra, simply because the resulting structure Â is almost invariably uncountable. However, in particular cases, it has been possible to define and study the substructure Ak of computable elements of Â; this has been done for the structures mentioned above, starting with the field
of recursive real numbers.

In this paper we analyse the effectivity of the completion of a local ring R. We do this using structured Scott-Ershov domains. Our study may be considered as a prototype containing methods applicable to a broad class of completions, including all the examples mentioned above, except for the real number field, which needs a generalisation of the domain concept.

A Scott-Ershov domain D formalises how a set Dt of possibly “infinite” elements, called total elements, is constructed from a set Dc of “finite” elements, called compact elements. This is achieved by means of an approximation ordering which determines a topology on D and, in particular, on Dt. Our methodology is to associate to a given topological algebra A a structured domain D(A) such that the total elements D(A)t form a topological algebra topologically isomorphic to A. In such circumstances A is said to be domain definable by D(A). The theory of computability for domains is now applied to study the effectivity of the topological algebra A.
On the elementary theory of restricted elementary functions
Authors: Dries Lou van den
Published: May 2006

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

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

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

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

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

with the extra property that for each x ∈ Rm such that ϕ(x) is true in RRE there is exactly one y ∈ Rn such that ψ(x, y) is true in RRE. (Here ψ is quantifier free.)
A system of logic for partial functions under existence-dependent kleene equality
Authors: Andréka H. , Craig W. , Németi I.
Published: May 2006

Ordinary equational logic is a connective-free fragment of first-order logic which is concerned with total functions under the relation of ordinary equality. In [AN] (see also [AN1]) and in [Cr] it has been extended in two equivalent ways into a near-equational system of logic for partial functions. The extension given in [Cr] deals with partial functions under two relationships: a relationship of existence-dependent existence and one of existence-dependent Kleene equality. For the language that involves both relationships a set of rules was given that is complete. Those rules in the set that involve only existence-dependent existence turned out to be complete for the sublanguage that involves this relationship only. In the present paper we give a set of rules that is complete for the other sublanguage, namely the language of partial functions under existence-dependent Kleene equality.

This language lacks a certain, often needed, power of expressing existence and fails, in particular, to be an extension of the language that underlies ordinary equational logic. That it possesses a fairly simple complete set of rules is therefore perhaps more of theoretical than of practical interest. The present paper is thus intended to serve as a supplement to [Cr] and, less directly, to [AN]. The subject is further rounded out, and some contrast is provided, by [Rob]. The systems of logic treated there are based on the weaker language in which partial functions are considered under the more basic relation of Kleene equality.
A note on definable Skolem functions
Authors: Scowcroft Philip
Published: May 2006

This note arose out of my efforts to understand results of van den Dries, Denef, and Weispfenning on definable Skolem functions in the elementary theory of Qp. The first person to prove their existence was van den Dries, who devised and applied a model-theoretic criterion for theories, admitting elimination of quantifiers, which also admit definable Skolem functions [3]. The proof, though elegant, does not describe how one defines the Skolem functions. In the particular case of Qp, Denef found an ingenious, easily described method for writing out the definitions [2, pp. 14–15]. Unfortunately, his argument directly applies only in the following special case: if

and there is a fixed m ≥ 1 such that

for all , then can be given as a definable function of . While this special case includes many of interest, van den Dries' theorem seems more general. Weispfenning suggested how his results on primitive-recursive quantifier elimination could produce algorithms yielding definitions of Skolem functions in the specific theories van den Dries considered [10, pp. 470–471]. Though these algorithms provide a more concrete version of van den Dries' theorem, and do not suffer the lack of generality of Denef's result, Weispfenning's argument is extremely subtle and applies only to certain theories of valued fields.
On the use of inaccessible numbers and order indiscernibles in lower bound arguments for random access machines
Authors: Maass Wolfgang
Published: May 2006

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

We consider countably additive, nonnegative, extended real-valued measures which vanish on singletons. Such a measure is universal on a set X iff it is defined on all subsets of X and is semiregular iff every set of positive measure contains a subset of positive finite measure. We study the problem of existence of a universal semiregular measure on X which is invariant under a given group of bijections of X. Moreover we discuss some properties of universal, semiregular, invariant measures on groups.
On the validity of hilbert's nullstellensatz, artin's theorem, and related results in grothendieck toposes
Authors: MacCaull W. A.
Published: May 2006

Using formally intuitionistic logic coupled with infinitary logic and the completeness theorem for coherent logic, we establish the validity, in Grothendieck toposes, of a number of well-known, classically valid theorems about fields and ordered fields. Classically, these theorems have proofs by contradiction and most involve higher order notions. Here, the theorems are each given a first-order formulation, and this form of the theorem is then deduced using coherent or formally intuitionistic logic. This immediately implies their validity in arbitrary Grothendieck toposes. The main idea throughout is to use coherent theories and, whenever possible, find coherent formulations of formulas which then allow us to call upon the completeness theorem of coherent logic. In one place, the positive model-completeness of the relevant theory is used to find the necessary coherent formulas.

The theorems here deal with polynomials or rational functions (in s indeterminates) over fields. A polynomial over a field can, of course, be represented by a finite string of field elements, and a rational function can be represented by a pair of strings of field elements. We chose the approach whereby results on polynomial rings are reduced to results about the base field, because the theory of polynomial rings in s indeterminates over fields, although coherent, is less desirable from a model-theoretic point of view. Ultimately we are interested in the models.

This research was originally motivated by the works of Saracino and Weispfenning [SW], van den Dries [Dr], and Bunge [Bu], each of whom generalized some theorems from algebraic geometry or ordered fields to (commutative, von Neumann) regular rings (with unity).
Ultrapowers without the axiom of choice
Authors: Spector Mitchell
Published: May 2006

A new method is presented for constructing models of set theory, using a technique of forming pseudo-ultrapowers. In the presence of the axiom of choice, the traditional ultrapower construction has proven to be extremely powerful in set theory and model theory; if the axiom of choice is not assumed, the fundamental theorem of ultrapowers may fail, causing the ultrapower to lose almost all of its utility. The pseudo-ultrapower is designed so that the fundamental theorem holds even if choice fails; this is arranged by means of an application of the omitting types theorem. The general theory of pseudo-ultrapowers is developed. Following that, we study supercompactness in the absence of choice, and we analyze pseudo-ultrapowers of models of the axiom of determinateness and various infinite exponent partition relations. Relationships between pseudo-ultrapowers and forcing are also discussed.
The deduction theorem for quantum logic—some negative results
Authors: Malinowski Jacek
Published: May 2006

We prove that no logic (i.e. consequence operation) determined by any class of orthomodular lattices admits the deduction theorem (Theorem 2.7). We extend those results to some broader class of logics determined by ortholattices (Corollary 2.6).
The cofinality of cardinal invariants related to measure and category
Authors: Bartoszynski Tomek , Ihoda Jaime I. , Shelah Saharon
Published: May 2006

We prove that the following are consistent with ZFC:

1. 2ω = ℵω1 + #x039A;c = ℵω1 + ΚΒ = ΚU = ω2 (for measure and category simultaneously).

2. .

This concludes the discussion about the cofinality of Κc.
A Borel reductibility theory for classes of countable structures
Authors: Friedman Harvey , Stanley Lee
Published: May 2006

We introduce a reducibility preordering between classes of countable structures, each class containing only structures of a given similarity type (which is allowed to vary from class to class). Though we sometimes work in a slightly larger context, we are principally concerned with the case where each class is an invariant Borel class (i.e. the class of all models, with underlying set = ω, of an Lω1ω sentence; from this point of view, the reducibility can be thought of as a (rather weak) sort of Lω1ω-interpretability notion). We prove a number of general results about this notion, but our main thrust is to situate various mathematically natural classes with respect to the preordering, most notably classes of algebraic structures such as groups and fields.
Finite axiomatizability for equational theories of computable groupoids
Authors: Perkins Peter
Published: May 2006

A computable groupoid is an algebra ‹N, g› where N is the set of natural numbers and g is a recursive (total) binary operation on N. A set L of natural numbers is a computable list of computable groupoids iff L is recursive, ‹N, ϕe› is a computable groupoid for each e ∈ L, and e ∈ L whenever e codes a primitive recursive description of a binary operation on N.

Theorem 1. Let L be any computable list of computable groupoids. The set {e ∈ L: the equational theory of ‹N, ϕe› is finitely axiomatizable} is not recursive.

Theorem 2. Let S be any recursive set of positive integers. A computable groupoid GS can be constructed so that S is inifinite iff GS has a finitely axiomatizable equational theory.

The problem of deciding which finite algebras have finitely axiomatizable equational theories has remained open since it was first posed by Tarski in the early 1960's. Indeed, it is still not known whether the set of such finite algebras is recursively (or corecursively) enumerable. McKenzie [7] has shown that this question of finite axiomatizability for any (finite) algebra of finite type can be reduced to that for a (finite) groupoid.