bluuebunny/crossref_metadata_2025_split huggingface dataset:
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

Abstract.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

Abstract.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

Abstract.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

Abstract.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 Σ.
Bi-isolation in the d.c.e. degrees
Authors: Wu Guohua 
Published: March 2005

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

A formalized version of Kleene realizability for intuitionistic first-order arithmetic HA was axiomatically characterized by Troelstra (see [2, 3.2]) as follows: for an arbitrary HA-sentence φ, HA ⊢ ∃x(x realizes φ) if and only if HA + ECT0 ⊢ φ.Many notions of realizability have been characterized in this fashion: see [2] or [3] for details. For some notions, for example extensional realizability, it is necessary to pass to an extension of HA: realizability in HA is characterized by deducibility from certain axioms in an extension of HA.The present note is concerned with modified realizability, seen as interpretation for HA. From semantical considerations (see [4]) it follows that this interpretation can be constructed as a combination of three ingredients:i) Kleene realizability;ii) Kripke forcing over a 2-element linear order P;iii) The Friedman translation [1].This will be shown in section 2. The Friedman translation (in the way we use it) introduces a new propositional constant V; hence we move to an extension HA(V) of HA. We must then define Kleene realizability and forcing for the extended language. Now let (φ)v be the result of the Friedman translation applied to φ. We obtain, in HA, that the sentence saying that φ is modified-realizable, is equivalent to the sentence which says that the statement “(φ)v is Kleene-realizable” is forced in P (see section 2).
Degree spectra of prime models
Authors: Csima Barbara F. 
Published: March 2005

Abstract.We consider the Turing degrees of prime models of complete decidable theories. In particular we show that every complete decidable atomic theory has a prime model whose elementary diagram is low. We combine the construction used in the proof with other constructions to show that complete decidable atomic theories have low prime models with added properties.If we have a complete decidable atomic theory with all types of the theory computable, we show that for every degree d with 0 < d < 0', there is a prime model with elementary diagram of degree d. Indeed, this is a corollary of the fact that if T is a complete decidable theory and L is a computable set of c.e. partial types of T, then for any degree d > 0, T has a d-decidable model omitting the nonprincipal types listed by L.
On a question of Herzog and Rothmaler
Authors: Pillay Anand , Ziegler Martin 
Published: March 2005

Herzog and Rothmaler gave the following purely topological characterization of stable theories. (See the exercises 11.3.4 – 11.3.7 in [2]).A complete theory T is stable iff for any model M and any extension M ⊂ B the restriction map S(B) → S(M) has a continuous section.In fact, if T is stable, taking the unique non-forking extension defines a continuous section of S(B) → S(A) for all subsets A of B, provided A is algebraically closed in Teq. Herzog and Rothmaler asked, if, for stable T, there is a continuous section for any subset A of B. Or, equivalently, if for any A, S(acleq(A)) → S(A) has a continuous section.This is an interesting problem, also for unstable T. Is it true that for any T and any set of parameters A the restriction map S(acl(A)) → S(A) has a continuous section? We answer the question by the following two theorems.Theorem 1. Let A be a subset of a model of T. Assume that the Boolean algebra of acl(A)-definable formulas is generated by• some countable set of formulas,• all A–definable formulas,• all formulas which are atomic over acl(A).Then S(acl(A)) → S(A) has a continuous section.The conditions of the theorems are satisfied if, for example, L and A are countable, or, if there are only countably many non-isolated types over acl(A).Theorem 2. There is a theory of Morley rank 2 and Morley degree 1 such that S(acl(∅)) → S(∅) has no continuous section.
Combinatorics for the dominating and unsplitting numbers
Authors: Aubrey Jason 
Published: March 2005

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

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

Abstract.For a stationary set S ⊆ ω1, and a ladder system C over S, a new type of gaps called C-Hausdorff is introduced and investigated. We describe a forcing model of ZFC in which, for some stationary set S, for every ladder C over S, every gap contains a subgap that is C-Hausdorff. But for every ladder E over ω1 ∖ S there exists a gap with no subgap that is E-Hausdorff.A new type of chain condition, called polarized chain condition, is introduced. We prove that the iteration with finite support of polarized c.c.c. posets is again a polarized c.c.c. poset.
Schnorr randomness
Authors: Downey Rodney G. , Griffiths Evan J. 
Published: March 2005

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

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

When bounds on complexity of some aspect of a structure are preserved under isomorphism, we refer to them as intrinsic. Here, building on work of Soskov [34], [33], we give syntactical conditions necessary and sufficient for a relation to be intrinsically on a structure. We consider some examples of computable structures and intrinsically relations R. We also consider a general family of examples of intrinsically relations arising in computable structures of maximum Scott rank.For three of the examples, the maximal well-ordered initial segment in a Harrison ordering, the superatomic part of a Harrison Boolean algebra, and the height-possessing part of a Harrison p-group, we show that the Turing degrees of images of the relation in computable copies of the structure are the same as the Turing degrees of paths through Kleene's . With this as motivation, we investigate the possible degrees of these paths. We show that there is a path in which ∅′ is not computable. In fact, there is one in which no noncomputable hyperarithmetical set is computable. There are paths that are Turing incomparable, or Turing incomparable over a given hyperarithmetical set. There is a pair of paths whose degrees form a minimal pair. However, there is no path of minimal degree.
An incompleteness theorem for βn-models
Authors: Mummert Carl , Simpson Stephen G. 
Published: March 2005

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

Abstract.We show that the spectrum of a sentence ϕ in Counting Monadic Second Order Logic (CMSOL) using one binary relation symbol and finitely many unary relation symbols, is ultimately periodic, provided all the models of ϕ are of clique width at most k, for some fixed k. We prove a similar statement for arbitrary finite relational vocabularies τ and a variant of clique width for τ-structures. This includes the cases where the models of ϕ are of tree width at most k. For the case of bounded tree-width, the ultimate periodicity is even proved for Guarded Second Order Logic GSOL. We also generalize this result to many-sorted spectra, which can be viewed as an analogue of Parikh's Theorem on context-free languages, and its analogues for context-free graph grammars due to Habel and Courcelle.Our work was inspired by Gurevich and Shelah (2003), who showed ultimate periodicity of the spectrum for sentences of Monadic Second Order Logic where only finitely many unary predicates and one unary function are allowed. This restriction implies that the models are all of tree width at most 2, and hence it follows from our result.
Lovely pairs of models: the non first order case
Authors: Ben-Yaacov Itay 
Published: March 2005

Abstract.We prove that for every simple theory T (or even simple thick compact abstract theory) there is a (unique) compact abstract theory whose saturated models are the lovely pairs of T. Independence-theoretic results that were proved in [5] when is a first order theory are proved for the general case: in particular is simple and we characterise independence.
On some small cardinals for Boolean algebras
Authors: Mckenzie Ralph , Monk J. Donald 
Published: March 2005

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

In reverse mathematics, one formalizes theorems of ordinary mathematics in second order arithmetic and attempts to discover which set theoretic axioms are required to prove these theorems. Often, this project involves making choices between classically equivalent definitions for the relevant mathematical concepts. In this paper, we consider a number of equivalent definitions for the notions of well quasi-order and better quasi-order and examine how difficult it is to prove the equivalences of these definitions.As usual in reverse mathematics, we work in the context of subsystems of second order arithmetic and take RCA0 as our base system. RCA0 is the subsystem formed by restricting the comprehension scheme in second order arithmetic to formulas and adding a formula induction scheme for formulas. For the purposes of this paper, we will be concerned with fairly weak extensions of RCA0 (indeed strictly weaker than the subsystem ACA0 which is formed by extending the comprehension scheme in RCA0 to cover all arithmetic formulas) obtained by adjoining certain combinatorial principles to RCA0. Among these, the most widely used in reverse mathematics is Weak König's Lemma; the resulting theory WKL0 is extensively documented in [11] and elsewhere.We give three other combinatorial principles which we use in this paper. In these principles, we use k to denote not only a natural number but also the finite set {0, …, k − 1}.
Every polynomial-time 1-degree collapses if and only if P = PSPACE
Authors: Fenner Stephen A. , Kurtz Stuart A. , Royer James S. 
Published: March 2005

Abstract.A set A is m-reducible (or Karp-reducible) to B if and only if there is a polynomial-time computable function f such that, for all x, x ∈ A if and only if f(x) ∈ B. Two sets are:• 1-equivalent if and only if each is m-reducible to the other by one-one reductions;• p-invertible equivalent if and only if each is m-reducible to the other by one-one, polynomial-time invertible reductions; and• p-isumorphic if and only if there is an m-reduction from one set to the other that is one-one, onto, and polynomial-time invertible.In this paper we show the following characterization.Theorem. The following are equivalent:(a) P = PSPACE.(b) Every two 1-equivalent sets are p-isomorphic.(c) Every two p-invertible equivalent sets are p-isomorphic.
Patterns of paradox
Authors: Cook Roy T. 
Published: March 2005

We begin with a prepositional languageLpcontaining conjunction (Λ), a class of sentence names {Sα}αϵA, and a falsity predicateF. We (only) allow unrestricted infinite conjunctions, i.e., given any non-empty class of sentence names {Sβ}βϵB,is a well-formed formula (we will useWFFto denote the set of well-formed formulae).The language, as it stands, is unproblematic. Whether various paradoxes are produced depends on which names are assigned to which sentences. What is needed is a denotation function:For example, theLPsentence “F(S1)” (i.e.,Λ{F(S1)}), combined with a denotation functionδsuch thatδ(S1)“F(S1)”, provides the (or, in this context, a)Liar Paradox.To give a more interesting example,Yablo's Paradox[4] can be reconstructed within this framework.Yablo's Paradoxconsists of an ω-sequence of sentences {Sk}kϵωwhere, for eachnϵω:WithinLPan equivalent construction can be obtained using infinite conjunction in place of universal quantification - the sentence names are {Si}iϵωand the denotation function is given by:We can express this in more familiar terms as:etc.
Leibnizian models of set theory
Authors: Enayat Ali 
Published: March 2005

Abstract.A model is said to be Leibnizian if it has no pair of indiscernibles. Mycielski has shown that there is a first order axiom LM (the Leibniz-Mycielski axiom) such that for any completion T of Zermelo-Fraenkel set theory ZF. T has a Leibnizian model if and only if T proves LM. Here we prove:Theorem A. Every complete theory T extending ZF + LM has nonisomorphic countable Leibnizian models.Theorem B. If κ is a prescribed definable infinite cardinal ofa complete theory T extending ZF + V = OD, then there are nonisomorphic Leibnizian models of T of power ℵ1such thatis ℵ1-like.Theorem C. Every complete theory T extendingZF + V = ODhas nonisomorphic ℵ1-like Leibnizian models.
On the intuitionistic strength of monotone inductive definitions
Authors: Tupailo Sergei 
Published: March 2005

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

Abstract.We present a comparatively simple way to construct Martin-Löf random and rec-random sets with certain additional properties, which works by diagonalizing against appropriate martingales. Reviewing the result of Gács and Kučera, for any given set X we construct a Martin-Löf random set from which X can be decoded effectively.By a variant of the basic construction we obtain a rec-random set that is weak truth-table autoreducible and we observe that there are Martin-Löf random sets that are computably enumerable self-reducible. The two latter results complement the known facts that no rec-random set is truth-table autoreducible and that no Martin-Löf random set is Turing-autoreducible [8, 24].
Filtering unification and most general unifiers in modal logic
Authors: Ghilardi Silvio , Sacchetti Lorenzo 
Published: March 2005

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