bluuebunny/crossref_metadata_2025_split huggingface dataset:
Relevant entailment—semantics and formal systems
Authors: Avron Arnon 
Published: May 2006

This work results from an attempt to give the vague notion of relevance a concrete semantical interpretation. The idea is that propositions may be divided into different “domains of relevance”. Each “domain” has its own “T” and “F” values, and propositions “belonging” to one domain can never entail propositions “belonging” to another, unconnected one.The semantics we have developed were found to correspond to an already known system, which we call here RMI⥲. Its axioms are the implication-negation axioms of the system RM ([1, Chapter 5]). However, as Meyer has shown, RM is not a conservative extension of RMI⥲, since RMI⥲ has the sharing-of-variables property ([5], and [1, pp. 148–149[), which the implication-negation fragment of RM has not.RMI⥲ has four advantages in comparison to its more famous sister R⥲ (the pure intentional fragment of the system R; see [1]):a) It has a very natural (from a relevance point of view) many-valued semantics, the simple form of which we describe here.b) RMI⥲, ⊢ A1 → [A2 → (… → (An → A) …)] iff there is a proof of A from the set {A1, …, An} that actually uses all the members of this set. In R⥲, this holds only if we talk about “sequences” instead of “sets”. This is somewhat less intuitive (see [1, pp. 394–395]).c) RMI⥲ is a maximal “natural” relevance logic, in the sense that every proper extension of it limits the number of “domains of relevance” (§III).
Espaces ultramétriques
Authors: Delon Françoise 
Published: May 2006

Un espace ultramétrique est un ensemble muni d'une distance à valeurs dans un ordre total avec premier élément et pour laquelle tout triangle est isocèle avex deux grands côtés égaux. Les deux cas importants d'espaces ultramétriques sont:(1) les corps valués lorsqu'on ne considère que leur structure métrique, et(2) les ensembles Aλ, où λ est un ensemble bien ordonné, munis de la distance d(α, β) = inf {γ ∈ λ; α(γ) ≠ β(γ)} si α ≠ β et d(α, β) = 0 sinon; distance à valeurs dans l'ordre inverse de λ enrichi d'un premier élément 0.Nous étudions ces structures dans un langage comportant un seul type de variables, les points de l'espace, et un prédicat à quatre places traduisant l'ordre sur les distancesNous définissons la notion d'espace riche, qui est la modèle-complétion relative à un ensemble des distances fixé: un espace est riche si et seulement s'il est existentiellement clos dans toute extension qui n'ajoute pas de nouvelle distance. Les deux exemples précédemment donnés, espaces Aλ et corps valués, fournissent des espaces riches. La suite de l'article s'attache à la description des espaces riches.
Co-immune subspaces and complementation inV∞
Authors: Downey R. 
Published: May 2006

AbstractWe examine the multiplicity of complementation amongst subspaces ofV∞. A subspaceVis acomplementof a subspaceWifV∩W= {0} and (V∪W)* =V∞. A subspace is calledfully co-r.e.if it is generated by a co-r.e. subset of a recursive basis ofV∞. We observe that every r.e. subspace has a fully co-r.e. complement.Theorem.If S is any fully co-r.e. subspace then S has a decidable complement.We give an analysis of other types of complementsSmay have. For example, ifSis fully co-r.e. and nonrecursive, thenShas a (nonrecursive) r.e. nowhere simple complement.We impose the condition of immunity upon our subspaces.Theorem.SupposeVis fully co-r.e. ThenVis immune iff there exist M1,M2∈L(V∞),with M1supermaximal and M2k-thin, such that M1, ⊕V=M2⊕V=V∞.Corollary.SupposeVis any r.e. subspace with a fully co-r.e. immune complement W(e.g.,Vis maximal orVis h-immune). Then there exist an r.e. supermaximal subspace M and a decidable subspace D such thatV⊕W=M⊕W=D⊕W=V∞.We indicate how one may obtain many further results of this type. Finally we examine a generalization of the concepts of immunity and soundness. A subspaceVofV∞isnowhere soundif (i) for allQ ∈ L(V∞)ifQ⊃VthenQ =V∞, (ii)Vis immune and (iii) every complement ofVis immune. We analyse the existence (and ramifications of the existence) of nowhere sound spaces.
Weak strong partition cardinals
Authors: Henle J. M. 
Published: May 2006

In a series of papers [K2], [K3], [K4], E. M. Kleinberg established the extensive properties of what are now called “strong partition cardinals”, cardinals satisfying for all λ < κ. The purpose of this note is to show that all these consequences and the results in [H] and [W] can be obtained from the weaker relation and many from .We assume the reader is generally familiar with Kleinberg's machinery and with the definition of . We recall that a cardinal κ satisfies iff for every partition F: [κ]κ → A there is a p ∈ [κ]κ such that F″ [p]κ ≠ A. We take the liberty of regarding a p ∈ [κ]κ both as a subset of κ and as a function from κ to κ. We assume DC throughout.§1. From. Our results stem from the observation that the proofs in the papers cited above only require homogeneous sets for certain classes of partitions.Definition. A partition F: [κ]κ → λ, λ < λ, is called clopen if for all p ∈ [κ]κ there is an α < κ such that whenever -clopen is the assertion that all clopen partitions have homogeneous sets (Spector-Watro).
Infinite subscripts from infinite exponents
Authors: Baumgartner James E. , Henle James M. 
Published: May 2006

Definition. For ordinals α ≤ κ, = [X]α = {p ⊆ X ∣ ot (p) = α}. For α ≤, κ, κ a cardinal, holds iff for every partition F: [Κ]κ → A, there is an X ∈ [Κ]κ with F constant on [X]α. X is called homogeneous for F. When A = 2 the subscript is omitted.It has been known since the sixties that for finite exponents all such properties are equivalent, i.e., κ→ (κ)2 iff for all n < ω, β < κ. The infinite case is much more difficult, though it is not actually known to be different. The usual methods for dealing with partitions fail, and as the weakest of these properties violates the Axiom of Choice, many techniques are unavailable.It is extremely unlikely that an infinite exponent can be increased, but infinite subscripts are generally possible.Theorem. If ∥ α ∥ · 2 ≤ α, then κ → (κ)α implies for all λ < κ.In §1, we show the subscript can be any λ < κ. In §2 we extend this to 2λ. In §3 we discuss the possibilities with limited amounts of well-ordered choice, and apply the theorem to the problem of obliging ordinals. Except in §3, we assume no choice. For the story of finite exponents, see [1]. For the relationship between infinite-exponent partition relations and choice, see [4].
Finitely generic models of TUH, for certain model companionable theories T
Authors: Point Francoise 
Published: May 2006

The starting point of this work was Saracino and Wood's description of the finitely generic abelian ordered groups [S-W].We generalize the result of Saracino and Wood to a class ∑UH of subdirect products of substructures of elements of a class ∑, which has some relationships with the discriminator variety V(∑t) generated by ∑. More precisely, let ∑ be an elementary class of L-algebras with theory T. Burris and Werner have shown that if ∑ has a model companion then the existentially closed models in the discriminator variety V(∑t) form an elementary class which they have axiomatized. In general it is not the case that the existentially closed elements of ∑UH form an elementary class. For instance, take for ∑ the class ∑0 of linearly ordered abelian groups (see [G-P]).We determine the finitely generic elements of ∑UH via the three following conditions on T:(1) There is an open L-formula which says in any element of ∑UH that the complement of equalizers do not overlap.(2) There is an existentially closed element of ∑UH which is an L-reduct of an element of V(∑t) and whose L-extensions respect the relationships between the complements of the equalizers.(3) For any models A, B of T, there exists a model C of TUH such that A and B embed in C.(Condition (3) is weaker then “T has the joint embedding property”. It is satisfied for example if every model of T has a one-element substructure. Condition (3) implies that ∑UH has the joint embedding property and therefore that the class of finitely generic elements of ∑UH is complete.)
Strongly majorizable functionals of finite type: A model for barrecursion containing discontinuous functionals
Authors: Bezem Marc 
Published: May 2006

AbstractIn this paper a model for barrecursion is presented. It has as a novelty that it contains discontinuous functionals. The model is based on a concept called strong majorizability. This concept is a modification of Howard's majorizability notion; see [T, p. 456].
Syntactic translations and provably recursive functions
Authors: Leivant Daniel 
Published: May 2006

Syntactic translations of classical logic C into intuitionistic logic I are well known (see [Kol25], [Gli29], [Göd32], [Kre58b], [M063], [Cel69] and [Lei71]). Harvey Friedman [Fri78] used a translation of a similar nature, from I into itself, to reprove a theorem of Kreisel [Kre58a] that various theories based on I are closed under Markov's rule: if ¬¬∃x.α is a theorem, where x is a numeric variable and α is a primitive recursive relation, then ∃x.α is a theorem. Composing this with Gödel's translation from classical to intuitionistic theories, it follows that the functions provably recursive in the classical version of the theories considered are provably recursive already in their intuitionistic version. This conservation result is important in that it guarantees that no information about the convergence of recursive functions is lost when proofs are restricted to constructive logic, thus removing a potential objection to the use of constructive logic in reasoning about programs (see [C078] for example). Conversely, no objection can be raised by intuitionists to proofs of formulas that use classical reasoning, because such proofs can be converted to constructive proofs (this has been exploited extensively; see [Smo82]).Proofs of closure under Markov's rule had required, until Friedman's proof, a relatively sophisticated mathematical apparatus. The chief method used Godel's “Dialectica” interpretation (see [Tro73, §3]). Other proofs used cut-elimination, provable reflection for subsystems [Gir73], and Kripke models [Smo73]. Moreover, adapting these proofs to new theories had required that the underlying meta-mathematical techniques be adapted first, not always a trivial step.
On the consistency of self-referential systems
Authors: Sobrinho J. Zimbarg 
Published: May 2006

In [2], Hiller and myself have introduced what we have called self-referential systems. Under this name we categorize models of a theory whose predicates refer to objects which are themselves predicates of the language—this particular interpretation being considered as the intended one. is formulated in a language whose variables are typed: as types become “larger”, the corresponding objects become “smaller”; for this reason, we have suggestively chosen types to be negative integers: 0, −1, −2, and so on.The consistency of has been questioned several times, and it has also been referred to as an “intriguing possibility”. Under such motivation, we are most willing to present a consistency proof for , and we do it relative to the theory ZFC + “there exists a Ramsey cardinal”. The only use of the Ramsey cardinal is to justify the existence of 0#, and the existence of 0# is known to be weaker than the existence of a Ramsey cardinal. For this reason, we note that the minimum we need for our proof is the existence of the set 0#.To begin with, we prove that the consistency of implies the existence of intended models for : these are models in which every element is definable by a one-free-variable formula of the language. In intended models we also show that the axiom holds, and, besides, these models possess -indescribable cardinals. These two results imply the relative consistency of with respect to and, moreover, that any proof of the consistency of cannot be carried out without the use of some large cardinal axiom: such an axiom which, when added to ZFC, produces a theory equiconsistent to —if it exists—remains unknown. At the end of this article we finally exhibit the consistency proof of , our main result.
Seminormal λ-generated ideals on Pκλ
Authors: Johnson C. A. 
Published: May 2006

In this paper we consider the problem of lifting properties of the Fréchet ideal Iκ = {X ⊆ κ: ∣X∣ < κ} on a regular uncountable cardinal κ, to an analogue about Iκλ, the ideal of not unbounded subsets of Pκλ. With this in mind, in §1 we introduce and study the class of seminormal λ-generated ideals on Pκλ. We shall see that ideals belonging to this class display properties which are clearly analogous to those of the Fréchet ideal on κ (for instance, with regard to saturation, normality and weak selectivity) and yet are closely related to Iκλ. Our results here show that if λ<λ = λ, then many restrictions of Iκλ are weakly selective, nowhere precipitous and, quite suprisingly, seminormal (but nowhere normal). These latter two results suggest the question of whether any restriction of Iκλ can ever be normal. In §2 we prove that if κ is strongly inaccessible, λ<κ = 2λ and NSκλ, the ideal of nonstationary subsets of Pκλ, has a mild selective property, then NSκλ∣A = Iκλ∣A for some stationary A ⊆ Pκλ.In [1] Baumgartner showed that if κ is weakly compact and P is the collection of indescribable subsets of κ, then P → (P, κ)2. As a Pκλ analogue of indescribability, Carr (see [3]–[5]) introduced the λ-Shelah property, but was unable to derive the natural Pκλ analogue of Baumgartner's result, (where NShκλ is the normal ideal on Pκλ induced by the λ-Shelah property). In §3 we show that the problem lies in the fact that, as far as we know, NShκλ is not sufficiently distributive, and derive conditions which are sufficient and, in a sense, necessary to yield partitions related to .
Weakly minimal groups of unbounded exponent
Authors: Loveys James 
Published: May 2006

Weakly minimal sets were first invented by Shelah [S] to solve Łoś' conjecture for uncountable theories. The first major result about them, which is that any nonalgebraic strong type either is of Morley rank 1 or has locally modular geometry, was proved by Buechler [B1]. Recently, Hrushovski [Hr] showed that a locally modular weakly minimal set interprets an abelian group, a result which revolutionized the study of these sets. Also Hrushovski showed that the geometry on the connected component of a weakly minimal locally modular group is that of a vector space over a division ring. This is also implicit in the result of Pillay and Hrushovski (Theorem 1.3 from [HP]) quoted below. In a sense, this completes their study, as any vector space over any division ring is in fact strongly minimal if there is no other structure. But the question remains as to what other structure such a group could have. This is the issue we address here.Some work has been done on this question; in fact, Pillay ([Pi], generalized in [HP]) has demonstrated, in the more general context of a weakly normal group A, that any definable subset of An is in fact a Boolean combination of almost 0-definable cosets of almost 0-definable subgroups. In the weakly minimal case this can be sharpened a fair bit. The case of a weakly minimal group of bounded exponent is dealt with in [HL]. Here we consider the case where the group has unbounded exponent.
Decidability problem for finite Heyting algebras
Authors: Idziak Katarzyna , Idziak Pawel M. 
Published: May 2006

AbstractThe aim of this paper is to characterize varieties of Heyting algebras with decidable theory of their finite members. Actually we prove that such varieties are exactly the varieties generated by linearly ordered algebras. It contrasts to the result of Burris [2] saying that in the case of whole varieties, only trivial variety and the variety of Boolean algebras have decidable first order theories.
On the quasi-ordering of Borel linear orders under embeddability
Authors: Louveau Alain , Saint-Raymond Jean 
Published: May 2006

AbstractWe provide partial answers to the following problem: Is the class of Borel linear orders well-quasi-ordered under embeddability? We show that it is indeed the case for those Borel orders which are embeddable in Rω, with the lexicographic ordering. For Borel orders embeddable in R2, our proof works in ZFC, but it uses projective determinacy for Borel orders embeddable in some Rn, n < ω, and hyperprojective determinacy for the general case.
Some results about Borel sets in descriptive set theory of hyperfinite sets
Authors: Živaljević Boško 
Published: May 2006

A remarkable result of Henson and Ross [HR] states that if a function whose graph is Souslin in the product of two hyperfinite sets in an ℵ1 saturated nonstandard universe possesses a certain nice property (capacity) then there exists an internal subfunction of the given one possessing the same property. In particular, they prove that every 1-1 Souslin function preserves any internal counting measure, and show that every two internal sets A and B with ∣A∣/∣B∣ ≈ 1 are Borel bijective. As a supplement to the last-mentioned result of Henson and Ross, Keisler, Kunen, Miller and Leth showed [KKML] that two internal sets A and B are bijective by a countably determined bijection if and only if ∣A∣/∣B∣ is finite and not infinitesimal.In this paper we first show that injective Borel functions map Borel sets into Borel sets, a fact well known in classical descriptive set theory. Then, we extend the result of Henson and Ross concerning the Borel bijectivity of internal sets whose quotient of cardinalities is infinitely closed to 1. We prove that two Borel sets, to which we may assign a counting measure not equal to 0 or ∞, are Borel bijective if and only if they have the same counting measure ≠0, ∞. This, together with the similar characterization for Souslin and measurable countably determined sets, extends the above-mentioned results from [HR] and [KKML].
Asymptotic probabilities of existential second-order Gödel sentences
Authors: Pacholski Leszek , Szwast WiesŁaw 
Published: May 2006

In [9] and [10] P. Kolaitis and M. Vardi proved that the 0-1 law holds for the second-order existential sentences whose first-order parts are formulas of Bernays-Schonfinkel or Ackermann prefix classes. They also provided several examples of second-order formulas for which the 0-1 law does not hold, and noticed that the classification of second-order sentences for which the 0-1 law holds resembles the classification of decidable cases of first-order prenex sentences. The only cases they have not settled are the cases of Gödel classes with and without equality.In this paper we confirm the conjecture of Kolaitis and Vardi that the 0-1 law does not hold for the existential second-order sentences whose first-order part is in Gödel prenex form with equality. The proof we give is based on a modification of the example employed by W. Goldfarb [5] in his proof that, contrary to the Gödel claim [6], the class of Gödel prenex formulas with equality is undecidable.
Indescribable cardinals and elementary embeddings
Authors: Hauser Kai 
Published: May 2006

Indescribability is closely related to the reflection principles of Zermelo-Fränkel set theory. In this axiomatic setting the universe of all sets stratifies into a natural cumulative hierarchy (Vα: α ϵ On) such that any formula of the language for set theory that holds in the universe already holds in the restricted universe of all sets obtained by some stage.The axioms of ZF prove the existence of many ordinals α such that this reflection scheme holds in the world Vα. Hanf and Scott noticed that one arrives at a large cardinal notion if the reflecting formulas are allowed to contain second order free variables to which one assigns subsets of Vα. For a given collection Ω of formulas in the ϵ language of set theory with higher type variables and a unary predicate symbol they define an ordinal α to be Ω indescribable if for all sentences Φ in Ω and A ⊆ VαSince a sufficient coding apparatus is available, this definition is (for the classes of formulas that we are going to consider) equivalent to the one that one obtains by allowing finite sequences of relations over Vα, some of which are possibly k-ary. We will be interested mainly in certain standardized classes of formulas: Let (, respectively) denote the class of all formulas in the language introduced above whose prenex normal form has n alternating blocks of quantifiers of type m (i.e. (m + 1)th order) starting with ∃ (∀, respectively) and no quantifiers of type greater than m. In Hanf and Scott [1961] it is shown that in ZFC, indescribability is equivalent to inaccessibility and indescribability coincides with weak compactness.
The logic of first order intuitionistic type theory with weak sigma-elimination
Authors: Swaen M. D. G. 
Published: May 2006

AbstractVia the formulas-as-types embedding certain extensions of Heyting Arithmetic can be represented in intuitionistic type theories. In this paper we discuss the embedding of ω-sorted Heyting Arithmetic HAω into a type theory WL, that can be described as Troelstra's system with so-called weak Σ-elimination rules. By syntactical means it is proved that a formula is derivable in HAω if and only if its corresponding type in WL is inhabited. Analogous results are proved for Diller's so-called restricted system and for a type theory based on predicate logic instead of arithmetic.
Presburger arithmetic with unary predicates is Π11 complete
Authors: Halpern Joseph Y. 
Published: May 2006

AbstractWe give a simple proof characterizing the complexity of Presburger arithmetic augmented with additional predicates. We show that Presburger arithmetic with additional predicates is complete. Adding one unary predicate is enough to get hardness, while adding more predicates (of any arity) does not make the complexity any worse.
Bad groups of finite Morley rank
Authors: Corredor Luis Jaime 
Published: May 2006

AbstractWe prove the following theorem. Let G be a connected simple bad group (i.e. of finite Morley rank, nonsolvable and with all the Borel subgroups nilpotent) of minimal Morley rank. Then the Borel subgroups of G are conjugate to each other, and if B is a Borel subgroup of G, then , NG(B) = B, and G has no involutions.
Non Σn axiomatizable almost strongly minimal theories
Authors: Marker David 
Published: May 2006

Recall that a theory is said to be almost strongly minimal if in every model every element is in the algebraic closure of a strongly minimal set. In 1970 Hodges and Macintyre conjectured that there is a natural number n such that every ℵ0-categorical almost strongly minimal theory is Σn axiomatizable. Recently Ahlbrandt and Baldwin [A-B] proved that if T is ℵ0-categorical and almost strongly minimal, then T is Σn axiomatizable for some n. This result also follows from Ahlbrandt and Ziegler's results on quasifinite axiomatizability [A-Z]. In this paper we will refute Hodges and Macintyre's conjecture by showing that for each n there is an ℵ0-categorical almost strongly minimal theory which is not Σn axiomatizable.Before we begin we should note that in all these examples the complexity of the theory arises from the complexity of the definition of the strongly minimal set. It is still open whether the conjecture is true if we allow a predicate symbol for the strongly minimal set.We will prove the following result.Theorem. For every n there is an almost strongly minimal ℵ0-categorical theory T with models M and N such that N is Σn elementary but not Σn + 1 elementary.To show that these theories yield counterexamples to the conjecture we apply the following result of Chang [C].Theorem. If T is a Σn axiomatizable theory categorical in some infinite power, M and N are models of T and N is a Σn elementary extension of M, then N is an elementary extension of M.