bluuebunny/crossref_metadata_2025_split huggingface dataset:
On the structure of semialgebraic sets over p-adic fields
Authors: Scowcroft Philip , van den Dries Lou 
Published: May 2006

In his Singular points of complex hypersurfaces Milnor proves the following “curve selection lemma” [10, p. 25]:Let V ⊂ Rm be a real algebraic set, and let U ⊂ Rm be an open set defined by finitely many polynomial inequalities:Lemma 3.1. If U ∩ V contains points arbitrarily close to the origin (that is if 0 ∈ Closure (U ∩ V)) then there exists a real analytic curvewith p(0) = 0 and with p(t) ∈ U ∩ V for t > 0.Of course, this result will also apply to semialgebraic sets (finite unions of sets U ∩ V), and by Tarski's theorem such sets are exactly the sets obtained from real varieties by means of the finite Boolean operations and the projection maps Rn+1 → Rn. If, in this tiny extension of Milnor's result, we replace ‘R’ everywhere by ‘Qp’, we obtain a p-adic curve selection lemma, a version of which we will prove in this essay. Semialgebraic sets, in the p-adic context, may be defined just as they are over the reals: namely, as those sets obtained from p-adic varieties by means of the finite Boolean operations and the projection maps . Analytic maps are maps whose coordinate functions are given locally by convergent power series.
Operative vs. combinatory spaces
Authors: Ivanov Lyubomir 
Published: May 2006

The algebraic systems of combinatory spaces [3] and operative spaces [1] have been designed to provide appropriate settings for the development of abstract recursion theory. As shown in [1, Chapter 27], these systems are closely related; namely, every combinatory space has a companion operative space with a storing operation St such that Skordev recursiveness in the former equals st-recursiveness in the latter. The problem of characterization of those operative spaces which have companion combinatory spaces was solved in [2] by introducing a class of operative spaces called Skordev spaces and showing that these give an alternative axiomatics of Skordev's combinatory spaces.In this paper we study operative spaces with two special constants S1 and S2 which, in computer science terms, axiomatize the availability of stacking facility. We establish that any such space has a Skordev subspace and, moreover, all Skordev spaces can be obtained in this way. The construction ensures that st-recursiveness in the Skordev space concerned is equivalent to recursiveness in S1 and S2 in the wider operative space. Therefore, it quite unexpectedly turns out that Skordev recursiveness can be expressed via relative recursiveness in operative spaces in a straightforward manner, without employing higher spaces as done in [1].
Hereditarily finite Finsler sets
Authors: Booth David 
Published: May 2006

Hereditarily finite sets are sets which are finite, whose members are finite, the members of whose members are finite, and so on. In ZF there are but countably many such sets; they constitute Vω. Were ZF to lose its axiom of regularity, however, one could not guarantee that the number of hereditarily finite sets would remain countable.In Mostowski set theory, in which atomic sets are permissible, each atom, in isolation, would form a hereditarily finite collection. The number of hereditarily finite sets could be anything one should choose.Even in a world that did not permit the free adjunction of arbitrary, meaningless atoms, the number of hereditarily finite sets could remain large. In Finsler set theory, it is shown as Theorem 22, below, that there are uncountably many hereditarily finite sets.The reader who is interested in this paradoxical sounding fact can turn directly to §4 after grasping these introductory concepts. §3 is an exhaustive list of the smallest Finsler sets; it is hoped that this list will prove useful in checking future attempts to classify the finite Finsler sets.Finsler set theory is not a firmly axiomatized theory. It is, at its present stage, a family of theories undergoing evolution. It permits the usual mathematical operations with sets. One can employ ordinal numbers, cardinal numbers, and the usual methods of Cantorian set theory freely. But there is a somewhat different interpretation attached to the concept “set” than one is used to in Zermelo-Fraenkel set theory, ZF.
The role of parameters in bar rule and bar induction
Authors: Rathjen Michael 
Published: May 2006

AbstractFor several subsystems of second order arithmeticTwe show that the proof-theoretic strength ofT+ (bar rule) can be characterized in terms ofT+ (bar induction)□, where the latter scheme arises from the scheme of bar induction by restricting it to well-orderings with no parameters. In addition, we demonstrate that,ACA0+ (bar rule) andACA0+ (bar induction)□prove the same-sentences.
The Σ21 theory of axioms of symmetry
Authors: Weitkamp Galen 
Published: May 2006

AbstractThe axiom of symmetry (Aℵ0) asserts that for every function F: ω2 → ω2 there is a pair of reals x and y in ω2 so that y is not in the countable set {(F(x))n: n< ω} coded by F(x) and x is not in the set coded by F(y). A(Γ) denotes axiom Aℵ0 with the restriction that graph(F) belongs to the pointclass Γ. In §2 we prove A(). In §3 we show A(), A() and ω2 ⊈ L are equivalent. In §4 several effective versions of A(REC) are examined.
Near-equational and equational systems of logic for partial functions. I
Authors: Craig William 
Published: May 2006

Equational logic for total functions is a remarkable fragment of first-order logic. Rich enough to lend itself to many uses, it is also quite austere. The only predicate symbol is one for a notion of equality, and there are no logical connectives. Proof theory for equational logic therefore is different from proof theory for other logics and, in some respects, more transparent. The question therefore arises to what extent a logic with a similar proof theory can be constructed when expressive power is increased.The increase mainly studied here allows one both to consider arbitrary partial functions and to express the condition that a function be total. A further increase taken into account is equivalent to a change to universal Horn sentences for partial and for total functions.Two ways of increasing expressive power will be considered. In both cases, the notion of equality is modified and nonlogical function symbols are interpreted as ranging over partial functions, instead of ranging only over total functions. In one case, the only further change is the addition of symbols that denote logical functions, such as the binary projection functionAethat maps each pair ‹a0,a1› of elements of a setAinto the elementa0. An addition of this kind results in a language, and also in a system of logic based on this language, which we callequationalIn the other case, instead of adding a symbol forAe, one admits those special universal Horn sentences in which the conditions expressed by the antecedent are, in a sense, pure conditions of existence. Languages and systems of logic that result from a change of this kind will be callednear-equational. According to whether the number of existence conditions that one may express in antecedents is finite or arbitrary, the resulting language and logic shall befiniteorinfinitary, respectively. Each of our finite near-equational languages turns out to be equivalent to one of our equational languages, and vice versa.
Nonfinite axiomatizability results for cylindric and relation algebras
Authors: Maddux Roger D. 
Published: May 2006

AbstractThe set of equations which use only one variable and hold in all representable relation algebras cannot be derived from any finite set of equations true in all representable relation algebras. Similar results hold for cylindric algebras and for logic with finitely many variables. The main tools are a construction of nonrepresentable one-generated relation algebras, a method for obtaining cylindric algebras from relation algebras, and the use of relation algebras in defining algebraic semantics for first-order logic.
A new proof of Sahlqvist's theorem on modal definability and completeness
Authors: Sambin G. , Vaccaro V. 
Published: May 2006

There are not many global results on modal logics. One of these is the following theorem by Sahlqvist on completeness and correspondence for a wide class of modal formulae (including many well known logics, e.g. D, T, B, S4, K4, S5, …) (see [S]).Sahlqvist's Theorem. Let A be any modal formula which is equivalent to a conjunction of formulae of the form □m(A1 → A2), where m ≥ 0, A2 is positive and A1 is obtained from propositional variables and their negations applying ∧, ∨, ♢, and □ in such a way that no positive occurrence of a variable is in a subformula of the form B1 ∨ B2 or ♢ B1 within the scope of some □. Then A corresponds effectively to a first order formula, and L + A is canonical whenever Lis a canonical logic.A formula A satisfying the above conditions is henceforth called a Sahlqvist formula. Unfortunately, till now, the only complete proof was the original proof of Sahlqvist (a proof of the correspondence half has also been given by van Benthem [vB]). It is so complicated and long that even in an advanced textbook of modal logic [HC] it has not found a place. Here, by considering general frames as topological spaces, an attitude which we developed in [TD], we give a proof of Sahlqvist's theorem simplified to such an extent that one can easily grasp the key idea on which it is based and apply the resulting algorithm to specific modal formulae in a straightforward manner, suitable even for implementation on a personal computer. This key idea also improves on previous preliminary work in the same direction (see [S1], [S2]).
Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion
Authors: Jockusch C. G. , Lerman M. , Soare R. I. , Solovay R. M. 
Published: May 2006

Let We be the eth recursively enumerable (r.e.) set in a standard enumeration. The fixed point form of Kleene's recursion theorem asserts that for every recursive function f there exists e which is a fixed point of f in the sense that We = Wf(e). In this paper our main concern is to study the degrees of functions with no fixed points. We consider both fixed points in the strict sense above and fixed points modulo various equivalence relations on recursively enumerable sets.Our starting point for the investigation of the degrees of functions without (strict) fixed points is the following result due to M. M. Arslanov [A1, Theorem 1] and known as the Arslanov completeness criterion. Proofs of this result may also be found in [So1, Theorem 1.3] and [So2, Chapter 12], and we will give a game version of the proof in §5 of this paper.Theorem 1.1 (Arslanov). Let A be an r.e. set. Then A is complete (i.e. A has degree0′) iff there is a function f recursive in A with no fixed point.
Some restrictions on simple fixed points of the integers
Authors: McColm G. L. 
Published: May 2006

AbstractA function is recursive (in given operations) if its values are computed explicitly and uniformly in terms of other “previously computed” values of itself and (perhaps) other “simultaneously computed” recursive functions. Here, “explicitly” includes definition by cases.We investigate those recursive functions on the structure N = 〈ω, 0, succ, pred〉 that are computed in terms of themselves only, without other simultaneously computed recursive functions.
A general treatment of equivalent modalities
Authors: Bellissima Fabio , Mirolli Massimo 
Published: May 2006

The problem of the nonequivalent modalities available in certain systems is a classical problem of modal logic. In this paper we deal with this problem without referring to particular logics, but considering the whole class of normal propositional logics. Given a logic L let P(L) (the m-partition generated by L) denote the set of the classes of L-equivalent modalities. Obviously, different logics may generate the same m-partition; the first problem arising from this general point of view is therefore to determine the cardinality of the set of all m-partitions. Since, as is well known, there exist normal logics, and since one immediately realizes that there are infinitely many m-partitions, the problem consists in choosing (assuming the continuum hypothesis) between ℵ0 and . In Theorem 1.2 we show that there are m-partitions, as many as the logics.The next problem which naturally arises consists in determining, given an m-partition P(L), the number of logics generating P(L) (in symbols, μ(P(L))). In Theorem 2.1(ii) we show that ∣{P(L): μ(P(L)) = }∣ = . Now, the set {L′) = P(L)} has a natural minimal element; that is, the logic L* axiomatized by K ∪ {φ(p) ↔ ψ(p): φ, ψ are L-equivalent modalities}; P(L) and L* can be, in some sense, identified, thus making the set of m-partitions a subset of the set of logics.
On Ehrenfeucht-Fraïssé equivalence of linear orderings
Authors: Oikkonen Juha 
Published: May 2006

AbstractC. Karp has shown that if α is an ordinal with ωα = α and A is a linear ordering with a smallest element, then α and α ⊗ A are equivalent in L∞ω up to quantifer rank α. This result can be expressed in terms of Ehrenfeucht-Fraïssé games where player ∀ has to make additional moves by choosing elements of a descending sequence in α. Our aim in this paper is to prove a similar result for Ehrenfeucht-Fraïssé games of length ω1. One implication of such a result will be that a certain infinite quantifier language cannot say that a linear ordering has no descending ω1-sequences (when the alphabet contains only one binary relation symbol). Connected work is done by Hyttinen and Oikkonen in [H] and [O].
Pointless metric spaces
Authors: Gerla Giangiacomo 
Published: May 2006

In the last years several research projects have been motivated by the problem of constructing the usual geometrical spaces by admitting “regions” and “inclusion” between regions as primitives and by defining the points as suitable sequences or classes of regions (for references see [2]).In this paper we propose and examine a system of axioms for the pointless space theory in which “regions”, “inclusion”, “distance” and “diameter” are assumed as primitives and the concept of point is derived. Such a system extends a system proposed by K. Weihrauch and U. Schreiber in [5].In the sequel R and N denote the set of real numbers and the set of natural numbers, and E is a Euclidean metric space. Moreover, if X is a subset of R, then ⋁X is the least upper bound and ⋀X the greatest lower bound of X.
Undecidability of modal and intermediate first-order logics with two individual variables
Authors: Gabbay D. M. , Shehtman V. B. 
Published: May 2006

The interest in fragments of predicate logics is motivated by the well-known fact that full classical predicate calculus is undecidable (cf. Church [1936]). So it is desirable to find decidable fragments which are in some sense “maximal”, i.e., which become undecidable if they are “slightly” extended. Or, alternatively, we can look for “minimal” undecidable fragments and try to identify the vague boundary between decidability and undecidability. A great deal of work in this area concerning mainly classical logic has been done since the thirties. We will not give a complete review of decidability and undecidability results in classical logic, referring the reader to existing monographs (cf. Suranyi [1959], Lewis [1979], and Dreben, Goldfarb [1979]). A short summary can also be found in the well-known book Church [1956]. Let us recall only several facts. Herein we will consider only logics without functional symbols, constants, and equality.(C1) The fragment of the classical logic with only monadic predicate letters is decidable (cf. Behmann [1922]).(C2) The fragment of the classical logic with a single binary predicate letter is undecidable. (This is a consequence of Gödel [1933].)(C3) The fragment of the classical logic with a single individual variable is decidable; in fact it is equivalent to Lewis S5 (cf. Wajsberg [1933]).(C4) The fragment of the classical logic with two individual variables is decidable (Segerberg [1973] contains a proof using modal logic; Scott [1962] and Mortimer [1975] give traditional proofs.)(C5) The fragment of the classical logic with three individual variables and binary predicate letters is undecidable (cf. Surańyi [1943]). In fact this paper considers formulas of the following typeφ,ψ being quantifier-free and the set of binary predicate letters which can appear in φ or ψ being fixed and finite.
Random models and solvable Skolem classes
Authors: Goldfarb Warren 
Published: May 2006

A Skolem class is a class of formulas of pure quantification theory in Skolem normal form: closed, prenex formulas with prefixes ∀…∀∃…∃. (Pure quantification theory contains quantifiers, truth-functions, and predicate letters, but neither the identity sign nor function letters.) The Gödel Class, in which the number of universal quantifiers is limited to two, was shown effectively solvable (for satisfiability) sixty years ago [G1]. Various solvable Skolem classes that extend the Gödel Class can be obtained by allowing more universal quantifiers but restricting the combinations of variables that may occur together in atomic subformulas [DG, Chapter 2]. The Gödel Class and these extensions are also finitely controllable, that is, every satisfiable formula in them has a finite model. In this paper we isolate a model-theoretic property that connects the usual solvability proofs for these classes and their finite controllability. For formulas in the solvable Skolem classes, the property is necessary and sufficient for satisfiability. The solvability proofs implicitly relied on this fact. Moreover, for any formula in Skolem normal form, the property implies the existence of a finite model.The proof of the latter implication uses the random models technique introduced in [GS] for the Gödel Class and modified and applied in [Go] to the Maslov Class. The proof thus substantiates the claim made in [Go] that random models can be adapted to the Skolem classes of [DG, Chapter 2]. As a whole, the results of this paper provide a more general, systematic approach to finite controllability than previous methods.
Derivation rules as anti-axioms in modal logic
Authors: Venema Yde 
Published: May 2006

AbstractWe discuss a ‘negative’ way of defining frame classes in (multi)modal logic, and address the question of whether these classes can be axiomatized byderivation rules, the ‘non-ξ rules’, styled after Gabbay's Irreflexivity Rule. The main result of this paper is a metatheorem on completeness, of the following kind: If⋀is a derivation system having a set of axioms that are special Sahlqvist formulas and⋀+is the extension of⋀with a set of non-ξ rules, then⋀+is strongly sound and complete with respect to the class of frames determined by the axioms and the rules.
Additive reducts of real closed fields
Authors: Marker David , Peterzil Ya'acov , Pillay Anand 
Published: May 2006

In [MP] Marker and Pillay showed that if X ⊂ Cn is constructible but (C, +, X) is not locally modular, then multiplication is definable in the structure (C, +,X). That result extended earlier results of Martin [M] and Rabinovich and Zil'ber [RZ]. Here we will examine additive reducts of R and Qp.Definition. A subset X of Rn is called semialgebraic if it is definable in the structure (R, +,·). A subset X of Rn is called semilinear if it is definable in the structure (R, +, <,λr)r∈b, where λr is the function x ↦ rx [scalar multiplication by r].Every semilinear set is a Boolean combination of sets of the form {: p () = 0} and {: q() > 0}, where p() and q() are linear polynomials.Van den Dries asked the following question: if X is semialgebraic but not semilinear, can we define multiplication in (R, +, <,X)? This was answered negatively by Pillay, Scowcroft and Steinhorn.Theorem 1.1 [PSS]. Suppose X ⊂ Rnis semialgebraic and X ⊂ Infor some bounded interval I. Then multiplication is not definable in (R, +, <,X,λr)r∈R.In particular if X = · ∣ [0, l ]2, the graph of multiplication restricted to the unit interval, then X is not semilinear so we have a negative answer to van den Dries' question. Peterzil showed that this is the only restriction.
Undecidability of the identity problem for finite semigroups
Authors: Albert Douglas , Baldinger Robert , Rhodes John 
Published: May 2006

In 1947 E. Post [28] and A. A. Markov [18] independently proved the undecidability of the word problem (or the problem of deducibility of relations) for semigroups. In 1968 V. L. Murskil [23] proved the undecidability of the identity problem (or the problem of deducibility of identities) in semigroups.If we slightly generalize the statement of these results we can state many related results in the literature and state our new results proved here. Let V denote either a (Birkhoff) variety of semigroups or groups or a pseudovariety of finite semigroups. By a very well-known theorem a (Birkhoff) variety is defined by equations or equivalently closed under substructure, surmorphisms and all products; see [7]. It is also well known that V is a pseudovariety of finite semigroups iff V is closed under substructure, surmorphism and finite products, or, equivalently, determined eventually by equations w1 = w1′, w2 = w2′, w3 = w3′,… (where the finite semigroup S eventually satisfies these equations iff there exists an n, depending on S, such that S satisfies Wj = Wj′ for j ≥ n). See [8] and [29]. All semigroups form a variety while all finite semigroups form a pseudovariety.We now consider a table (see the next page). In it, for example, the box denoting the “word” (identity) problem for the psuedovariety V” means, given a finite set of relations (identities) E and a relation (identity) u = ν, the problem of whether it is decidable that E implies u = ν inside V.
Kripke models for linear logic
Authors: Allwein Gerard , Dunn J. Michael 
Published: May 2006

AbstractWe present a Kripke model for Girard's Linear Logic (without exponentials) in a conservative fashion where the logical functors beyond the basic lattice operations may be added one by one without recourse to such things as negation. You can either have some logical functors or not as you choose. Commutativity and associativity are isolated in such a way that the base Kripke model is a model for noncommutative, nonassociative Linear Logic. We also extend the logic by adding a coimplication operator, similar to Curry's subtraction operator, which is residuated with Linear Logic's cotensor product. And we can add contraction to get nondistributive Relevance Logic. The model rests heavily on Urquhart's representation of nondistributive lattices and also on Dunn's Gaggle Theory. Indeed, the paper may be viewed as an investigation into nondistributive Gaggle Theory restricted to binary operations. The valuations on the Kripke model are three valued: true, false, and indifferent. The lattice representation theorem of Urquhart has the nice feature of yielding Priestley's representation theorem for distributive lattices if the original lattice happens to be distributive. Hence the representation is consistent with Stone's representation of distributive and Boolean lattices, and our semantics is consistent with the Lemmon-Scott representation of modal algebras and the Routley-Meyer semantics for Relevance Logic.
Decidability and undecidability of theories with a predicate for the primes
Authors: Bateman P. T. , Jockusch C. G. , Woods A. R. 
Published: May 2006

AbstractIt is shown, assuming the linear case of Schinzel's Hypothesis, that the first-order theory of the structure 〈ω; +, P〉, where P is the set of primes, is undecidable and, in fact, that multiplication of natural numbers is first-order definable in this structure. In the other direction, it is shown, from the same hypothesis, that the monadic second-order theory of 〈ω S, P〉 is decidable, where S is the successor function. The latter result is proved using a general result of A. L. Semënov on decidability of monadic theories, and a proof of Semënov's result is presented.