bluuebunny/crossref_metadata_2025 huggingface dataset:
Ultrafilters on the natural numbers
Authors: Barney Christopher
Published: March 2005

We study the problem of existence and generic existence of ultrafilters onω. We prove a conjecture of Jörg Brendle's showing that there is an ultrafilter that is countably closed but is not an ordinal ultrafilter under CH. We also show that Canjar's previous partial characterization of the generic existence of Q-points is the best that can be done. More simply put, there is no normal cardinal invariant equality that fully characterizes the generic existence of Q-points. We then sharpen results on generic existence with the introduction ofσ-compact ultrafilters. We show that the generic existence of said ultrafilters is equivalent to. This result, taken along with our result that there exists aKσ, non-countably closed ultrafilter under CH, expands the size of the class of ultrafilters that were known to fit this description before. From the core of the proof, we get a new result on the cardinal invariants of the continuum, i.e., the cofinality of the sets withσ-compact closure is.
Transfer methods for o-minimal topology
Authors: Berarducci Alessandro , Otero Margarita
Published: March 2005

LetMbe an o-minimal expansion of an ordered field. Letφbe a formula in the language of ordered domains. In this note we establish some topological properties which are transferred fromφMtoφRand vice versa. Then, we apply these transfer results to give a new proof of a result ofM. Edmundo—based on the work of A. Strzebonski—showing the existence of torsion points in any definably compact group defined in an o-minimal expansion of an ordered field.
A proof–technique in uniform space theory
Authors: Bridges Douglas , Vîţă Luminiţa
Published: March 2005

In the constructive theory of uniform spaces there occurs a technique of proof in which the application of a weak form of the law of excluded middle is circumvented by purely analytic means. The essence of this proof–technique is extracted and then applied in several different situations.
Expansions of geometries
Authors: Baldwin John T.
Published: March 2005

For n < ω, expand the structure (n, S, I, F) (with S the successor relation, I, F as the initial and final element) by forming graphs with edge probability n−α for irrational α, with 0 < α < 1. The sentences in the expanded language, which have limit probability 1, form a complete and stable theory.
Positive abstraction and extensionality
Authors: Hinnion Roland , Libert Thierry
Published: March 2005

It is proved in this paper that the positive abstraction scheme is consistent with extensionality only if one drops equality out of the language. The theory obtained is then compared with GPK, a well-known set theory based on an extended positive comprehension scheme.
Fat sets and saturated ideals
Authors: Krueger John
Published: March 2005

We strengthen a theorem of Gitik and Shelah [6] by showing that if κ is either weakly inaccessible or the successor of a singular cardinal andSis a stationary subset of κ such thatNSκ↾Sis saturated then κ ∖Sis fat. Using this theorem we derive some results about the existence of fat stationary sets. We then strengthen some results due to Baumgartner and Taylor [2], showing in particular that ifIis aλ+++-saturated normal ideal onPκλthen the conditions of beingλ+-preserving, weakly presaturated, and presaturated are equivalent forI.
Discouraging results for ultraimaginary independence theory
Authors: Ben-Yaacov Itay
Published: March 2005

Dividing independence for ultraimaginaries is neither symmetric nor transitive. Moreover, any notion of independence satisfying certain axioms (weaker than those for independence in a simple theory) and denned for all ultraimaginary sorts, is necessarily trivial.
Strong normalization proof with CPS-translation for second order classical natural deduction
Authors: Nakazawa Koji , Tatsuta Makoto
Published: March 2005

This paper points out an error of Parigot's proof of strong normalization of second order classical natural deduction by the CPS-translation, discusses erasing-continuation of the CPS-translation, and corrects that proof by using the notion of augmentations.
Existential definability with bounds on archimedean valuations
Authors: Shlapentokh Alexandra
Published: March 2005

We show that a solution to Hilbert's Tenth Problem in the rings of algebraic integers and bigger subrings of number fields where it is currently not known, is equivalent to a problem of bounding archimedean valuations over non-real number fields.
Non-well-foundedness of well-orderable power sets
Authors: Forster T. E. , Truss J. K.
Published: March 2005

Tarski [5] showed that for any setX, its setω(X) of well-orderable subsets has cardinality strictly greater than that ofX, even in the absence of the axiom of choice. We construct a Fraenkel-Mostowski model in which there is an infinite strictly descending sequence under the relation ∣ω(X)∣ = ∣Y∣. This contrasts with the corresponding situation for power sets, where use of Hartogs' ℵ-function easily establishes that there can be no infinite descending sequence under the relation.
The approximation structure of a computably approximable real
Authors: Barmpalias George
Published: March 2005

A new approach for a uniform classification of the computably approximable real numbers is introduced. This is an important class of reals, consisting of the limits of computable sequences of rationals, and it coincides with the 0′-computable reals. Unlike some of the existing approaches, this applies uniformly to all reals in this class: to each computably approximable real x we assign a degree structure, the structure of all possible ways available to approximate x. So the main criterion for such classification is the variety of the effective ways we have to approximate a real number. We exhibit extreme cases of such approximation structures and prove a number of related results.
Differential forms in the model theory of differential fields
Authors: Pierce David
Published: March 2005

Fields of characteristic zero with several commuting derivations can be treated as fields equipped with aspaceof derivations that is closed under the Lie bracket. The existentially closed instances of such structures can then be given a coordinate-free characterization in terms of differential forms. The main tool for doing this is a generalization of the Frobenius Theorem of differential geometry.
Elementary properties of the Boolean hull and reduced quotient functors
Authors: Dickmann M. A. , Miraglia F.
Published: March 2005

In [12] we proved the following isotropy-reflection principle:

Theorem. Let F be a formally real field and let Fp denote its Pythagorean closure. The natural embedding of reduced special groups from Gred(F) into Gred(Fp) = G(FP) induced by the inclusion of fields, reflects isotropy.

Here Gred(F) denotes the reduced special group (with underlying group Ḟ/ΣḞ2) associated to the field F, henceforth assumed formally real; cf. [11], Chapter 1, §3, for details.

The result proved in [12] is, in fact, more general. For example, the Pythagorean closure Fp can be replaced in the statement above by the intersection of all real closures of F (inside a fixed algebraic closure). Similar statements hold, more generally, for all relative Pythagorean closures of F in the sense of Becker [3], Chapter II, §3.

Since the notion of isotropy of a quadratic form can be expressed by a first-order formula in the natural language LSG for special groups (with the coefficients as parameters), this result raises the question whether the embedding ιFFp: Gred(F) ↪ G (Fp) is elementary. Further, since the LSG-formula expressing isotropy is positive-existential, one may also ask whether ιFFp reflects all (closed) formulas ofthat kind with parameters in Gred(F).

In this paper we give a negative answer to the first of these questions, for a vast class of formally real (non-Pythagorean) fields F (Prop. 5.1). This follows from rather general preservation results concerning the “Boolean hull” and the “reduced quotient” operations on special groups.
A hierarchy for the plus cupping Turing degrees
Authors: Wang Yong , Li Angsheng
Published: March 2005

We say that a computably enumerable (c. e.) degree a is plus-cupping, if for every c.e. degree x with 0 < x ≤ a, there is a c. e. degree y ≠ 0′ such that x ∨ y = 0′. We say that a is n-plus-cupping, if for every c. e. degree x, if 0 < x ≤ a, then there is a lown c. e. degree I such that x ∨ I = 0′. Let PC and PCn be the set of all plus-cupping, and n-plus-cupping c. e. degrees respectively. Then PC1 ⊆ PC2 ⊆ PC3 = PC. In this paper we show that PC1 ⊂ PC2, so giving a nontrivial hierarchy for the plus cupping degrees. The theorem also extends the result of Li, Wu and Zhang [14] showing that LC1 ⊂ LC2, as well as extending the Harrington plus-cupping theorem [8].
Embedding jump upper semilattices into the Turing degrees
Authors: Montalbán Antonio
Published: March 2005

We prove that every countable jump upper semilattice can be embedded in, where a jump upper semilattice (jusl) is an upper semilattice endowed with a strictly increasing and monotone unary operator that we call jump, andis the jusl of Turing degrees. As a corollary we get that the existential theory of 〈D, ≤T, ∨, ′〉 is decidable. We also prove that this result is not true about jusls with 0, by proving that not every quantifier free 1-type of jusl with 0 is realized in. On the other hand, we show that every quantifier free 1-type of jump partial ordering (jpo) with 0 is realized in. Moreover, we show that if every quantifier free type,p(x1,…,xn), of jpo with 0, which contains the formulax1≤ 0(m)& … &xn≤ 0(m)for somem, is realized in, then every quantifier free type of jpo with 0 is realized in.

We also study the question of whether every jusl with the c.p.p. and sizeis embeddable in. We show that forthe answer is no, and that forκ= ℵ1it is independent of ZFC. (It is true if MA(κ) holds.)
Classical and constructive hierarchies in extended intuitionistic analysis
Authors: Moschovakis Joan Rand
Published: March 2005

This paper introduces an extension of Kleene's axiomatization of Brouwer's intuitionistic analysis, in which the classical arithmetical and analytical hierarchies are faithfully represented as hierarchies of the domains of continuity. A domain of continuity is a relation R(α) on Baire space with the property that every constructive partial functional defined on {α: R(α)} is continuous there. The domains of continuity for coincide with the stable relations (those equivalent in to their double negations), while every relation R(α) is equivalent in to ∃βA(α, β) for some stable A(α, β) (which belongs to the classical analytical hierarchy).

The logic of is intuitionistic. The axioms of include countable comprehension, bar induction, Troelstra's generalized continuous choice, primitive recursive Markov's Principle and a classical axiom of dependent choices proposed by Krauss. Constructive dependent choices, and constructive and classical countable choice, are theorems, is maximal with respect to classical Kleene function realizability, which establishes its consistency. The usual disjunction and (recursive) existence properties ensure that preserves the constructive sense of “or” and “there exists.”
Isomorphisms of splits of computably enumerable sets
Authors: Cholak Peter A. , Harrington Leo A.
Published: March 2005

We show that if A and are automorphic via Φ then the structures (A) and () are Δ30-isomorphic via an isomorphism Ψ induced by Φ. Then we use this result to classify completely the orbits of hhsimple sets.
Universally Baire sets and definable well-orderings of the reals
Authors: Friedman SY D. , Schindler Ralf
Published: March 2005

Let n ≥ 3 be an integer. We show that it is consistent (relative to the consistency of n − 2 strong cardinals) that every Σ1n-set of reals is universally Baire yet there is a (lightface) projective well-ordering of the reals. The proof uses “David's trick” in the presence of inner models with strong cardinals.
A theory for Log-Space and NLIN versus co-NLIN
Authors: Pollett Chris
Published: March 2005

The use of Nepomnjaščiǐ's Theorem in the proofs of independence results for bounded arithmetic theories is investigated. Using this result and similar ideas, it is shown that at least one ofS1orTLSdoes not prove the Matiyasevich-Robinson-Davis-Putnam Theorem. It is also established thatTLSdoes not prove a statement that roughly means nondeterministic linear time is equal to co-nondeterministic linear time. HereS1is a conservative extension of the well-studied theoryIΔ0andTLSis a theory for LOGSPACE reasoning.
The axiom of choice and combinatory logic
Authors: Cantini Andrea
Published: March 2005

We combine a variety of constructive methods (including forcing, realizability, asymmetric interpretation), to obtain consistency results concerning combinatory logic with extensionality and (forms of) the axiom of choice.
Ranked partial structures
Authors: Carlson Timothy J.
Published: March 2005

The theory of ranked partial structures allows a reinterpretation of several of the standard results of model theory and first-order logic and is intended to provide a proof-theoretic method which allows for the intuitions of model theory. A version of the downward Löwenheim-Skolem theorem is central to our development. In this paper we will present the basic theory of ranked partial structures and their logic including an appropriate version of the completeness theorem.
Simple stable homogeneous groups
Authors: Berenstein Alexander
Published: March 2005

We generalize tools and results from first order stable theories to groups inside a simple stable strongly homogeneous model.
Cardinal-preserving extensions
Authors: Friedman Sy D.
Published: March 2005

A classic result of Baumgartner-Harrington-Kleinberg [1] implies that assuming CH a stationary subset of ω1 has a CUB subset in a cardinal-perserving generic extension of V, via a forcing of cardinality ω1. Therefore, assuming that ω2L is countable: {X ∈ L ∣ X ⊆ ω1L and X has a CUB subset in a cardinal-preserving extension of L} is constructive, as it equals the set of constructible subsets of ω1L which in L are stationary. Is there a similar such result for subsets of ω2L? Building on work of M. Stanley [9], we show that there is not. We shall also consider a number of related problems, examining the extent to which they are “solvable” in the above sense, as well as denning a notion of reduction between them.
Partitioning large vector spaces
Authors: Schmerl James H.
Published: March 2005

The theme of this paper is the generalization of theorems about partitions of the sets of points and lines of finite-dimensional Euclidean spaces ℝdto vector spaces over ℝ of arbitrary dimension and, more generally still, to arbitrary vector spaces over other fields so long as these fields are not too big. These theorems have their origins in the following striking theorem of Sierpiński [12] which appeared a half century ago.

Sierpiński's Theorem.The Continuum Hypothesis is equivalent to: There is a partition{X, Y, Z}ofℝ3such that if ℓ is a line parallel to the x-axis[respectively:y-axis, z-axis]then X∩ℓ[respectively:Y∩ℓ, Z∩ℓ]is finite.

The history of this theorem and some of its subsequent developments are discussed in the very interesting article by Simms [13]. Sierpiński's Theorem was generalized by Kuratowski [9] to partitions of ℝn+2inton+ 2 sets obtaining an equivalence with. The geometric character that Sierpiński's Theorem and its generalization by Kuratowski appear to have is bogus, since the lines parallel to coordinate axes are essentially combinatorial, rather than geometric, objects. The following version of Kuratowski's theorem emphasizes its combinatorial character.

Kuratowski's Theorem.Let n < ω and A be any set. Then∣A∣ ≤ ℵnif and only if there is a partition P:An+2→n+ 2such that if i≤n+ 1and ℓ is a line parallel to the i-th coordinate axis, then{x∈ℓ:P(x) =i}is finite.
An application of Kochen's theorem
Authors: Laskowski Michael C.
Published: March 2005

We describe the Ax-Kochen definable subsets of the value group of a Hensel field and apply our results to a problem on identifying invariant factors in Hecke algebras.
Recovering ordered structures from quotients of their automorphism groups
Authors: Giraudet M. , Truss J. K.
Published: March 2005

We show that the ‘tail’ of a doubly homogeneous chain of countable cofinality can be recognized in the quotient of its automorphism group by the subgroup consisting of those elements whose support is bounded above. This extends the authors' earlier result establishing this for the rationals and reals. We deduce that any group is isomorphic to the outer automorphism group of some simple lattice-ordered group.
A computably categorical structure whose expansion by a constant has infinite computable dimension
Authors: Hirschfeldt Denis R. , Khoussainov Bakhadyr , Shore Richard A.
Published: March 2005

Cholak, Goncharov, Khoussainov, and Shore [1] showed that for each k > 0 there is a computably categorical structure whose expansion by a constant has computable dimension k. We show that the same is true with k replaced by ω. Our proof uses a version of Goncharov's method of left and right operations.
Parallel strategies
Authors: Pudlák Pavel
Published: March 2005

We consider combinatorial principles based on playing several two person games simultaneously. We call strategies for playing two or more games simultaneously parallel. The principles are easy consequences of the determinacy of games, in particular they are true for all finite games. We shall show that the principles fail for infinite games. The statements of these principles are of lower logical complexity than the sentence expressing the determinacy of games, therefore, they can be studied in weak axiomatic systems for arithmetic (Bounded Arithmetic). We pose several open problems about the provability of these statements in Bounded Arithmetic and related computational problems.
Finite-to-one maps
Authors: Forster Thomas
Published: March 2005

It is shown in ZF (without choice) that if there is a finite-to-one map (X) → X, then X is finite.
Additivity properties of topological diagonalizations
Authors: Bartoszynski Tomek , Shelah Saharon , Tsaban Boaz
Published: March 2005

We answer a question of Just, Miller, Scheepers and Szeptycki whether certain diagonalization properties for sequences of open covers are provably closed under taking finite or countable unions.
A short proof of the strong normalization of classical natural deduction with disjunction
Authors: David René , Nour Karim
Published: March 2005

We give a direct, purely arithmetical and elementary proof of the strong normalization of the cut-elimination procedure for full (i.e., in presence of all the usual connectives) classical natural deduction.
Proof normalization modulo
Authors: Dowek Gilles , Werner Benjamin
Published: March 2005

We define a generic notion of cut that applies to many first-order theories. We prove a generic cut elimination theorem showing that the cut elimination property holds for all theories having a so-called pre-model. As a corollary, we retrieve cut elimination for several axiomatic theories, including Church's simple type theory.
Categoricity and U-rank in excellent classes
Authors: Lessmann Olivier
Published: March 2005

Let be the class of atomic models of a countable first order theory. We prove that if is excellent and categorical in some uncountable cardinal, then each model is prime and minimal over the basis of a definable pregeometry given by a quasiminimal set. This implies that is categorical in all uncountable cardinals. We also introduce a U-rank to measure the complexity of complete types over models. We prove that the U-rank has the usual additivity properties, that quasiminimal types have U-rank 1, and that the U-rank of any type is finite in the uncountably categorical, excellent case. However, in contrast to the first order case, the supremum of the U-rank over all types may be ω (and is not achieved). We illustrate the theory with the example of free groups, and Zilber's pseudo analytic structures.
Ordering MAD families a la Katětov
Authors: Hrušák Michael , Ferreira Salvador García
Published: March 2005

An ordering (≤K) on maximal almost disjoint (MAD) families closely related to destructibility of MAD families by forcing is introduced and studied. It is shown that the order has antichains of size c and decreasing chains of length c+ bellow every element. Assuming t = c a MAD family equivalent to all of its restrictions is constructed. It is also shown here that the Continuum Hypothesis implies that for every ωω-bounding forcing ℙ of size c there is a Cohen-destructible, ℙ-indestructible MAD family. Finally, two other orderings on MAD families are suggested and an old construction of Mrówka is revisited.
The cofinality of the infinite symmetric group and groupwise density
Authors: Brendle Jörg , Losada Maria
Published: March 2005

We show that g ≤ c(Sym(ω)) where g is the groupwise density number and c(Sym(ω)) is the cofinality of the infinite symmetric group. This solves (the second half of) a problem addressed by Thomas.
The Kolmogorov-Loveland stochastic sequences are not closed under selecting subsequences
Authors: Merkle Wolfgang
Published: March 2005

It is shown that the class of Kolmogorov-Loveland stochastic sequences is not closed under selecting subsequences by monotonic computable selection rules. This result gives a strong negative answer to the question whether the Kolmogorov-Loveland stochastic sequences are closed under selecting sequences by Kolmogorov-Loveland selection rules, i.e., by not necessarily monotonic, partial computable selection rules. The following previously known results are obtained as corollaries. The Mises-Wald-Church stochastic sequences are not closed under computable permutations, hence in particular they form a strict superclass of the class of Kolmogorov-Loveland stochastic sequences. The Kolmogorov-Loveland selection rules are not closed under composition.
On countable simple unidimensional theories
Authors: Pillay Anand
Published: March 2005

We prove that any countable simple unidimensional theoryTis supersimple, under the additional assumptions thatTeliminates hyperimaginaries and that theDϕ-ranks are finite and definable.
Ample Dividing
Authors: Evans David M.
Published: March 2005

We construct a stable one-based, trivial theory with a reduct which is not trivial. This answers a question of John B. Goode. Using this, we construct a stable theory which isn-ample for all natural numbersn, and does not interpret an infinite group.
A proof-theoretic study of the correspondence of classical logic and modal logic
Authors: Kushida H. , Okada M.
Published: March 2005

It is well known that the modal logic S5 can be embedded in the classical predicate logic by interpreting the modal operator in terms of a quantifier. Wajsberg [10] proved this fact in a syntactic way. Mints [7] extended this result to the quantified version of S5; using a purely proof-theoretic method he showed that the quantified S5 corresponds to the classical predicate logic with one-sorted variable. In this paper we extend Mints' result to the basic modal logic S4; we investigate the correspondence between the quantified versions of S4 (with and without the Barcan formula) and the classical predicate logic (with one-sorted variable). We present a purely proof-theoretic proof-transformation method, reducing an LK-proof of an interpreted formula to a modal proof.
Arithmetical independence results using higher recursion theory
Authors: Arana Andrew
Published: March 2005

We extend an independence result proved in [1]. We show that for alln, there is a special set of Πnsentences {φa}a ∈ Hcorresponding to elements of a linear ordering (H, <H) of order type. These sentences allow us to build completions {Ta}a ∈ Hof PA such that fora <Hb, Ta∩ Σn⊂Tb∩ Σn, withφa∈Ta, ¬φa∈Th. Our method uses the Barwise-Kreisel Compactness Theorem.
Construction of saturated quasi-minimal structure
Authors: Itai Masanori , Tsuboi Akito , Wakai Kentaro
Published: March 2005

The notion of quasi-minimal structures was denned by B. Zil'ber as a natural generalization of minimal structures. Inspired by his work, we study here basic model theoretic properties of quasi-minimal structures. Main result is the construction of ω-saturated quasi-minimal models under ω-stability assumption.
Sous-groupes de Carter dans les groupes de rang de Morley fini
Authors: Frécon Olivier
Published: March 2005

ACarter subgroupis a self-normalizing locally nilpotent subgroup. For studying these subgroups in groups of finite Morley rank, we introduce the new notion of alocally closed subgroup. We show that every solvable group of finite Morley rank has a unique conjugacy class of Carter subgroups.
Some remarks on one-basedness
Authors: O. Wagner Frank
Published: March 2005

A type analysable in one-based types in a simple theory is itself one-based.
P versus NP and computability theoretic constructions in complexity theory over algebraic structures
Authors: Mainhardt Gunther
Published: March 2005

We show that there is a structure of countably infinite signature with P = N2P and a structure of finite signature with P = N1P and N1P ≠ N2P. We give a further example of a structure of finite signature with P ≠ N1P and N1P ≠ N1P. Together with a result from [10] this implies that for each possibility of P versus NP over structures there is an example of countably infinite signature. Then we show that for some finite the class of -structures with P = N1P is not closed under ultraproducts and obtain as corollaries that this class is not ∆-elementary and that the class of -structures with P ≠ N1P is not elementary. Finally we prove that for all ƒ dominating all polynomials there is a structure of finite signature with the following properties: P ≠ N1P, N1P ≠ N2P, the levels N2TIME(ni) of N2P and the levels N1TIME(ni) of N1P are different for different i, indeed DTIME(ni′) ⊈ N2TIME(ni) if i ′ > i; DTIME(ƒ) ⊈ N2P, and N2P ⊈ DEC. DEC is the class of recognizable sets with recognizable complements. So this is an example where the internal structure of N2P is analyzed in a more detailed way. In our proofs we use methods in the style of classical computability theory to construct structures except for one use of ultraproducts.
Hindman's theorem, ultrafilters, and reverse mathematics
Authors: Hirst Jeffry L.
Published: March 2005

Assuming CH. Hindman [2] showed that the existence of certain ultrafilters on the power set of the natural numbers is equivalent to Hindman's Theorem. Adapting this work to a countable setting formalized in RCA0, this article proves the equivalence of the existence of certain ultrafilters on countable Boolean algebras and an iterated form of Hindman's Theorem, which is closely related to Milliken's Theorem. A computable restriction of Hindman's Theorem follows as a corollary.
Generic Σ31 absoluteness
Authors: Friedman Sy D.
Published: March 2005

In this article we study the strength of absoluteness (with real parameters) in various types of generic extensions, correcting and improving some results from [3]. (In particular, see Theorem 3 below.) We shall also make some comments relating this work to the bounded forcing axioms BMM, BPFA and BSPFA.

The statement “ absoluteness holds for ccc forcing” means that if a formula with real parameters has a solution in a ccc set-forcing extension of the universe V, then it already has a solution in V. The analogous definition applies when ccc is replaced by other set-forcing notions, or by class-forcing.

Theorem 1. [1] absoluteness for ccc has no strength; i.e., if ZFC is consistent then so is ZFC + absoluteness for ccc.

The following results concerning (arbitrary) set-forcing and class-forcing can be found in [3].

Theorem 2 (Feng-Magidor-Woodin). (a) absoluteness for arbitrary set-forcing is equiconsistent with the existence of a reflecting cardinal, i.e., a regular cardinal κ such that H(κ) is ∑2-elementary in V.

(b) absoluteness for class-forcing is inconsistent.

We consider next the following set-forcing notions, which lie strictly between ccc and arbitrary set-forcing: proper, semiproper, stationary-preserving and ω1-preserving. We refer the reader to [8] for the definitions of these forcing notions.

Using a variant of an argument due to Goldstern-Shelah (see [6]), we show the following. This result corrects Theorem 2 of [3] (whose proof only shows that if absoluteness holds in a certain proper forcing extension, then in L either ω1 is Mahlo or ω2 is inaccessible).
Two step iteration of almost disjoint families
Authors: Vaughan Jerry E.
Published: March 2005

Let E be an infinite set, and [E]ω the set of all countably infinite subsets of E. A family ⊂ [E]ω is said to be almost disjoint (respectively, pairwise disjoint) provided for A, B ∈ , if A ≠ B then A ∩ B is finite (respectively, A ∩ B is empty). Moreover, an infinite family A is said to be a maximal almost disjoint family provided it is an infinite almost disjoint family not properly contained in any almost disjoint family. In this paper we are concerned with the following set of topological spaces defined from (maximal) almost disjoint families of infinite subsets of the natural numbers ω.
Valuation theoretic content of the Marker-Steinhorn theorem
Authors: Tressl Marcus
Published: March 2005

The Marker-Steinhorn Theorem (cf. [2] and [3]), says the following. If T is an o-minimal theory and M ≺ N is an elementary extension of models of T such that M is Dedekind complete in N, then for every N-definable subset X of Nk, the trace X ∩ Mk is M-definable. The original proof in [2] gives an explicit method how to construct a defining formula of X ∩ Mk out of a defining formula of X. A geometric reformulation of the Marker-Steinhorn Theorem is the definability of Hausdorff limits of families of definable sets. An explicit construction of these Hausdorff limits for expansions of the real field has recently been achieved in [1]. Both proofs and also the treatment [3] are technically involved.

Here we give a short algebraic, but not constructive proof, if T is an expansion of real closed fields. In fact we'll identify the statement of the Theorem with a valuation theoretic property of models of T (namely condition (†) below). Therefore our proof might be applicable to other elementary classes which expand fields, if a notion of dimension and a reasonable valuation theory are available.

From now on, let T be an o-minimal expansion of real closed fields. We have to show the following (cf. [2], Th. 2.1. for this formulation). If M is a model of T and p is a tame n-type over M (i.e., M is Dedekind complete in M ⟨ᾱ⟩ := dcl(Mᾱ) for some realization ᾱ of p), then p is a definable type (cf. [4], 11 .b).
A weak variation of shelah's I[ω2]
Authors: Mitchell William J.
Published: March 2005

We use a κ+-Mahlo cardinal to give a forcing construction of a model in which there is no sequence ⟨ Aβ : β < ω2 ⟩ of sets of cardinality ω1 such that

is stationary.
Analytic countably splitting families
Authors: Spinas Otmar
Published: March 2005

A family A ⊆ (ω) is called countably splitting if for every countable F ⊆ [ω]ω, some element of A splits every member of F. We define a notion of a splitting tree, by means of which we prove that every analytic countably splitting family contains a closed countably splitting family. An application of this notion solves a problem of Blass. On the other hand we show that there exists an Fσ splitting family that does not contain a closed splitting family.
First order quantifiers in monadic second order logic
Authors: Keisler H. Jerome , Lotfallah Wafik Boulos
Published: March 2005

This paper studies the expressive power that an extra first order quantifier adds to a fragment of monadic second order logic, extending the toolkit of Janin and Marcinkowski [JM01].

We introduce an operation existsn (S) on properties S that says “there are n components having S”. We use this operation to show that under natural strictness conditions, adding a first order quantifier word u to the beginning of a prefix class V increases the expressive power monotonically in u. As a corollary, if the first order quantifiers are not already absorbed in V, then both the quantifier alternation hierarchy and the existential quantifier hierarchy in the positive first order closure of V are strict.

We generalize and simplify methods from Marcinkowski [Mar99] to uncover limitations of the expressive power of an additional first order quantifier, and show that for a wide class of properties S, S cannot belong to the positive first order closure of a monadic prefix class W unless it already belongs to W.

We introduce another operation alt(S) on properties which has the same relationship with the Circuit Value Problem as reach(S) (defined in [JM01]) has with the Directed Reachability Problem. We use alt(S) to show that Πn ⊈ FO(Σn), Σn ⊈ FO(∆n). and ∆n+1 ⊈ FOB(Σn), solving some open problems raised in [Mat98].
Model theory of comodules
Authors: Crivei Septimiu , Prest Mike , Reynders Geert
Published: March 2005

The purpose of this paper is to establish some basic points in the model theory of comodules over a coalgebra. It is not even immediately apparent that there is a model theory of comodules since these are not structures in the usual sense of model theory. Let us give the definitions right away so that the reader can see what we mean.

Fix a field k. A k-coalgebra C is a k-vector space equipped with a k-linear map Δ: C → C ⊗ C, called the comultiplication (by ⊗ we always mean tensor product over k), and a k-linear map ε: C → k, called the counit, such that Δ⊗1C = 1C ⊗ Δ (coassociativity) and (1C ⊗ ε)Δ = 1C = (ε ⊗ 1C)Δ, where we identify C with both k ⊗ C and C ⊗ k. These definitions are literally the duals of those for a k-algebra: express the axioms for C′ to be a k-algebra in terms of the multiplication map μ: C′ ⊗ C′ → C′ and the “unit” (embedding of k into C′), δ: k → C′ in the form that certain diagrams commute and then just turn round all the arrows. See [5] or more recent references such as [7] for more.
Splittings of effectively speedable sets and effectively levelable sets
Authors: Omanadze Roland SH.
Published: March 2005

We prove that a computably enumerable set A is effectively speedable (effectively levelable) if and only if there exists a splitting (A0, A1) of A such that both A0 and A1 are effectively speedable (effectively levelable). These results answer two questions raised by J. B. Remmel.
A definable nonstandard model of the reals
Authors: Kanovei Vladimir , Shelah Saharon
Published: March 2005

We prove, in ZFC, the existence of a definable, countably saturated elementary extension of the reals.
Standard sets in nonstandard set theory
Authors: Andreev Petr , Hrbacek Karel
Published: March 2005

We prove that Standardization fails in every nontrivial universe definable in the nonstandard set theory BST, and that a natural characterization of the standard universe is both consistent with and independent of BST. As a consequence we obtain a formulation of nonstandard class theory in the ∈-language.
Truth definitions in finite models
Authors: Kołodziejczyk Leszek Aleksander
Published: March 2005

The paper discusses the notion of finite model truth definitions (or FM-truth definitions), introduced by M. Mostowski as a finite model analogue of Tarski's classical notion of truth definition.

We compare FM-truth definitions with Vardi's concept of the combined complexity of logics, noting an important difference: the difficulty of defining FM-truth for a logic does not depend on the syntax of , as long as it is decidable. It follows that for a natural there exist FM-truth definitions whose evaluation is much easier than the combined complexly of would suggest.

We apply the general theory to give a complexity-theoretical characterization of the logics for which the classes (prenex classes of higher order logics) define FM-truth. For any d ≥ 2, m ≥ 1 we construct a family of syntactically defined fragments of which satisfy this characterization. We also use the classes to give a refinement of known results on the complexity classes captured by .

We close with a few simple corollaries, one of which gives a sufficient condition for the existence, given a vocabulary σ, of a fixed number k such that model checking for all first order sentences over σ can be done in deterministic time nk.
Approximate Euler characteristic, dimension, and weak pigeonhole principles
Authors: Krajíček Jan
Published: March 2005

We define the notion of approximate Euler characteristic of definable sets of a first order structure. We show that a structure admits a non-trivial approximate Euler characteristic if it satisfies weak pigeonhole principle : two disjoint copies of a non-empty definable set A cannot be definably embedded into A, and principle CC of comparing cardinalities: for any two definable sets A, B either A definably embeds in B or vice versa. Also, a structure admitting a non-trivial approximate Euler characteristic must satisfy .

Further we show that a structure admits a non-trivial dimension function on definable sets if and only if it satisfies weak pigeonhole principle : for no definable set A with more than one element can A2 definably embed into A.
Forking and independence in o-minimal theories
Authors: Dolich Alfred
Published: March 2005

In the following we try to answer a simple question, “what does forking look like in an o-minimal theory”, or more generally, “what kinds of notions of independence with what kinds of properties are admissible in an o-minimal theory?” The motivation of these question begin with the study of simple theories and generalizations of simple theories. In [3] Kim and Pillay prove that the class of simple theories may be described exactly as those theories bearing a notion of independence satisfying various axioms. Thus it is natural to ask, if we weaken the assumptions as to which axioms must hold, what kind of theories do we get? Another source of motivation, also stemming from the study of simple theories, comes from the work of Shelah in [8] and [7]. Here Shelah addresses a “classification” type problem for class of models of a theory, showing that a theory will have the appropriate “structure” type property if one can construct a partially ordered set, satisfying various properties, of models of the theory. Using this criterion Shelah shows that the class of simple theories has this “structure” property, yet also that several non-simple examples do as well (though it should be pointed out that o-minimal theories can not be among these since any theory with the strict order property will have the corresponding “non-structure” property [8]). Thus one is lead to ask, what are the non-simple theories meeting this criterion, and one is once again led to study the types of independence relation a theory might bear. Finally, Shelah in [6] provides some possible definitions of what axioms for a notion of independence one should possibly look for in order to hope that theories bearing such a notion of independence should be amenable closer analysis. In studying all of the above mentioned situations it readily becomes clear that dividing and forking play a central role in all of them, even though we are no longer dealing with the simple case where we know that dividing and forking are very well behaved. All of these considerations lead one to look for classes of non-simple theories of which something is known where one can construct interesting notions of independence and consequently also say something about the nature of forking and dividing in these contexts. Given this one is naturally lead to one of the most well behaved classes of non-simple theories, namely the o-minimal theories.
A definability result for compact complex spaces
Authors: Radin Dale
Published: March 2005

A compact complex space X is viewed as a 1-st order structure by taking predicates for analytic subsets of X, X x X, … as basic relations. Let f: X → Y be a proper surjective holomorphic map between complex spaces and set Xy ≔ f−1(y). We show that the set

is analytically constructible, i.e.. is a definable set when X and Y are compact complex spaces and f: X → Y is a holomorphic map. The analogous result in the context of algebraic geometry gives rise to the definability of Morley degree.
Wild edge colourings of graphs
Authors: Džamonja Mirna , Komjáth Péter , Morgan Charles
Published: March 2005

We prove consistent, assuming there is a supercompact cardinal, that there is a singular strong limit cardinalμ, of cofinalityω, such that everyμ+-chromatic graphXonμ+has an edge colouringcofXintoμcolours for which every vertex colouringgofXinto at mostμmany colours has ag-colour class on whichctakes every value.

The paper also contains some generalisations of the above statement in whichμ+is replaced by other cardinals >μ.
Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
Authors: Krajíček Jan
Published: March 2005

This article is a continuation of our search for tautologies that are hard even for strong propositional proof systems like EF. cf. [14, 15]. The particular tautologies we study, the τ-formulas. are obtained from any /poly map g; they express that a string is outside of the range of g, Maps g considered here are particular pseudorandom generators. The ultimate goal is to deduce the hardness of the τ-formulas for at least EF from some general, plausible computational hardness hypothesis.

In this paper we introduce the notions of pseudo-surjective and iterable functions (related to free functions of [15]). These two properties imply the hardness of the τ-formulas from the function but unlike the hardness they are preserved under composition and iteration. We link the existence of maps with these two properties to the provability of circuit lower bounds, and we characterize maps g yielding hard τ-formulas in terms of a hitting set type property (all relative to a propositional proof system). We show that a proof system containing EF admits a pseudo-surjective function unless it simulates a proof system WF introduced by Jeřábek [11]. an extension of EF.

We propose a concrete map g as a candidate function possibly pseudo-surjective or free for strong proof systems. The map is defined as a Nisan-Wigderson generator based on a random function and on a random sparse matrix. We prove that it is iterable in a particular way in resolution, yielding the output/input ratio n3 −ε (that improves upon a direct construction of Alekhnovich et al. [2]).
Parsimony hierarchies for inductive inference
Authors: Ambainis Andris , Case John , Jain Sanjay , Suraj Mandayam
Published: March 2005

Freivalds defined an acceptable programming system independent criterion for learning programs for functions in which the final programs were required to be both correct and “nearly” minimal size. i.e.. within a computable function of being purely minimal size. Kinber showed that this parsimony requirement on final programs limits learning power. However, in scientific inference, parsimony is considered highly desirable. Alim-computable functionis (by definition) one calculable by a total procedure allowed to change its mind finitely many times about its output. Investigated is the possibility of assuaging somewhat the limitation on learning power resulting from requiring parsimonious final programs by use of criteria which require the final, correct programs to be “not-so-nearly” minimal size, e.g., to be within a lim-computable function of actual minimal size. It is shown that some parsimony in the final program is thereby retained, yet learning power strictly increases. Considered, then, are lim-computable functions as above but for whichnotations forconstructive ordinals are used to bound the number of mind changes allowed regarding the output. This is a variant of an idea introduced by Freivalds and Smith. For this ordinal notation complexity bounded version of lim-computability, the power of the resultant learning criteria form finely graded, infinitely ramifying, infinite hierarchies intermediate between the computable and the lim-computable cases. Some of these hierarchies, for the natural notations determining them, are shown to be optimally tight.
On first-order sentences without finite models
Authors: Djordjević Marko
Published: March 2005

We will mainly be concerned with a result which refutes a stronger variant of a conjecture of Macpherson about finitely axiomatizable ω-categorical theories. Then we prove a result which implies that the ω-categorical stable pseudoplanes of Hrushovski do not have the finite submodel property.

Let's call a consistent first-order sentence without finite models an axiom of infinity. Can we somehow describe the axioms of infinity? Two standard examples are:

ϕ1: A first-order sentence which expresses that a binary relation < on a nonempty universe is transitive and irreflexive and that for every x there is y such that x < y.

ϕ2: A first-order sentence which expresses that there is a unique x such that, (0) for every y, s(y) ≠ x (where s is a unary function symbol),

and, for every x, if x does not satisfy (0) then there is a unique y such that s(y) = x.

Every complete theory T such that ϕ1 ϵ T has the strict order property (as defined in [10]), since the formula x < y will have the strict order property for T. Let's say that if Ψ is an axiom of infinity and every complete theory T with Ψ ϵ T has the strict order property, then Ψ has the strict order property.

Every complete theory T such that ϕ2 ϵ T is not ω-categorical. This is the case because a complete theory T without finite models is ω-categorical if and only if, for every 0 < n < ω, there are only finitely many formulas in the variables x1,…,xn, up to equivalence, in any model of T.
A completeness theorem for symmetric product phase spaces
Authors: Ehrhard Thomas
Published: March 2005

In a previous work with Antonio Bucciarelli, we introduced indexed linear logic as a tool for studying and enlarging the denotational semantics of linear logic. In particular, we showed how to define new denotational models of linear logic using symmetric product phase models (truth-value models) of indexed linear logic. We present here a strict extension of indexed linear logic for which symmetric product phase spaces provide a complete semantics. We study the connection between this new system and indexed linear logic.
A universal extender model without large cardinals in V
Authors: Mitchell William , Schindler Ralf
Published: March 2005

We construct, assuming that there is no inner model with a Woodin cardinal but without any large cardinal assumption, a model Kc which is iterable for set length iterations, which is universal with respect to all weasels with which it can be compared, and (assuming GCH) is universal with respect to set sized premice.
Implicit proofs
Authors: Krajíček Jan
Published: March 2005

We describe a general method how to construct from a prepositional proof system P a possibly much stronger proof system iP. The system iP operates with exponentially long P-proofs described “implicitly” by polynomial size circuits.

As an example we prove that proof system iEF, implicit EF, corresponds to bounded arithmetic theory and hence, in particular, polynomially simulates the quantified prepositional calculus G and the -consequences of proved with one use of exponentiation. Furthermore, the soundness of iEF is not provable in . An iteration of the construction yields a proof system corresponding to T2 + Exp and, in principle, to much stronger theories.
On almost orthogonality in simple theories
Authors: Ben-Yaacov Itay , Wagner Frank O.
Published: March 2005

1. We show that ifpis a real type which is internal in a set Σ of partial types in a simple theory, then there is a typep′ interbounded withp, which is finitely generated over Σ, and possesses a fundamental system of solutions relative to Σ.

2. Ifpis a possibly hyperimaginary Lascar strong type, almost Σ-internal, but almost orthogonal to Σω, then there is a canonical non-trivial almost hyperdefinable polygroup which multi-acts onpwhile fixing Σ generically In casepis Σ-internal andTis stable, this is the binding group ofpover Σ.