bluuebunny/crossref_metadata_2025_split huggingface dataset:
Minimal invariant spaces in formal topology
Authors: Coquand Thierry 
Published: May 2006

A standard result in topological dynamics is the existence of minimal subsystem. It is a direct consequence of Zorn's lemma: given a compact topological space X with a map f: X→X, the set of compact non empty subspaces K of X such that f(K) ⊆ K ordered by inclusion is inductive, and hence has minimal elements. It is natural to ask for a point-free (or formal) formulation of this statement. In a previous work [3], we gave such a formulation for a quite special instance of this statement, which is used in proving a purely combinatorial theorem (van de Waerden's theorem on arithmetical progression).In this paper, we extend our analysis to the case where X is a boolean space, that is compact totally disconnected. In such a case, we give a point-free formulation of the existence of a minimal subspace for any continuous map f: X→X. We show that such minimal subspaces can be described as points of a suitable formal topology, and the “existence” of such points become the problem of the consistency of the theory describing a generic point of this space. We show the consistency of this theory by building effectively and algebraically a topological model. As an application, we get a new, purely algebraic proof, of the minimal property of [3]. We show then in detail how this property can be used to give a proof of (a special case of) van der Waerden's theorem on arithmetical progression, that is “similar in structure” to the topological proof [6, 8], but which uses a simple algebraic remark (Proposition 1) instead of Zorn's lemma. A last section tries to place this work in a wider context, as a reformulation of Hilbert's method of introduction/elimination of ideal elements.
AD and patterns of singular cardinals below Θ
Authors: Apter Arthur W. 
Published: May 2006

AbstractUsing Steel's recent result that assuming AD, in L[ℝ] below Θ, κ is regular iff κ is measurable, we mimic below Θ certain earlier results of Gitik. In particular, we construct via forcing a model in which all uncountable cardinals below Θ are singular and a model in which the only regular uncountable cardinal below Θ is ℵ1.
Omitting types in incomplete theories
Authors: Casanovas Enrique , Farré Rafel 
Published: May 2006

AbstractWe characterize omissibility of a type, or a family of types, in a countable theory in terms of non-existence of a certain tree of formulas. We extend results of L. Newelski on omitting < covK non-isolated types. As a consequence we prove that omissibility of a family of < covK types is equivalent to omissibility of each countable subfamily.
The consistency of ZFC + 2ℵ0 > ℵω + ℐ(ℵ2) = ℐ(ℵω)
Authors: Gilchrist Martin , Shelah Saharon 
Published: May 2006

Let κ be an uncountable cardinal and the edges of a complete graph with κ vertices be colored with ℵ0 colors. For the Erdős-Rado theorem implies that there is an infinite monochromatic subgraph. However, if , then it may be impossible to find a monochromatic triangle. This paper is concerned with the latter situation. We consider the types of colorings of finite subgraphs that must occur when . In particular, we are concerned with the case ℵ1 ≤ κ ≤ ℵω.The study of these color patterns (known as identities) has a history that involves the existence of compactness theorems for two cardinal models [4]. When the graph being colored has size ℵ1, the identities that must occur ((ℵ1)) have been classified by Shelah [6]. If the graph has size greater than or equal to ℵω the identities that must occur ((ℵω)) have also been classified in [5]. This leaves open the question of how the sets (ℵm) (2 ≤ m < ω) fit between (ℵ1) and ⊆ (ℵω). Some progress in this direction has been made in the paper [2]. It is there shown that if ZFC is consistent then so is for each m < ω. The number of colors is fixed at ℵ0 as it is the natural place to start and the results here can be generalized to more colors. We first give some definitions and establish some notation.
sets of reals
Authors: Bagaria Joan , Woodin W. Hugh 
Published: May 2006

Some of the most striking results in modern set theory have emerged from the study of simply-definable sets of real numbers. Indeed, simple questions like: what are the posible cardinalities?, are they measurable?, do they have the property of Baire?, etc., cannot be answered in ZFC.When one restricts the attention to the analytic sets, i.e., the continuous images of Borel sets, then ZFC does provide an answer to these questions. But this is no longer true for the projective sets, i.e., all the sets of reals that can be obtained from the Borel sets by taking continuous images and complements. In this paper we shall concentrate on particular projective classes, the , and using forcing constructions we will produce models of ZFC where, for some n, all , sets have some specified property. For the definition and basic facts about the projective classes , and , as well as the Kleene (or lightface) classes , and , we refer the reader to Moschovakis [19].The first part of the paper is about measure and category. Early in this century, Luzin [16] and Luzin-Sierpiński [17] showed that all analytic (i.e., ) sets of reals are Lebesgue measurable and have the property of Baire.
The undecidability of second order linear logic without exponentials
Authors: Lafont Yves 
Published: May 2006

AbstractRecently, Lincoln, Scedrov and Shankar showed that the multiplicative fragment of second order intuitionistic linear logic is undecidable, using an encoding of second order intuitionistic logic. Their argument applies to the multiplicative-additive fragment, but it does not work in the classical case, because second order classical logic is decidable. Here we show that the multiplicative-additive fragment of second order classical linear logic is also undecidable, using an encoding of two-counter machines originally due to Kanovich. The faithfulness of this encoding is proved by means of the phase semantics.
Grzegorcyk's hierarchy and IepΣ1
Authors: Takeuti Gaisi 
Published: May 2006

A proof-theoretic characterization of the primitive recursive functions is the Σ1-definable functions in IΣ1 as is shown in Mints [4], Parsons [5], and [8].Then what is a proof-theoretic characterization of Grzegorzyk's hierarchy? First we discuss a related previous work. In Clote and Takeuti [2], we introduced a theory TAC that corresponds to the computational complexity class AC. TAC has a very weak form of induction. We assign a rank to a proof in TAC in the following way. The rank of a proof P in TAC is the nesting number of inductions used in P. Then TACi is defined to be the subtheory of TAC whose proof has a rank ≤ i. We proved that TACi corresponds to the class ACi.In this paper we introduce a theory IepΣ1 which is equivalent to IΣ1. Then we define the rank of a proof in IepΣ1 as the nesting number of inductions in the proof and prove that the proofs with rank ≤ i correspond to Grzegorcyk's hierarchy for i > 0.We also prove that the system that has proofs with rank 0 is actually equivalent to I Δ0. These facts are interesting since it is proved in [10] that the theory isomorphic to TAC∘ by RSUV isomorphism is a conservative extension of I Δo. Therefore there is some analogy between the class AC and the primitive recursive functions.
Mixed systems
Authors: Ash C. J. , Knight J. F. 
Published: May 2006

In [A1]–[A4] there is an abstract description, in terms of “α-systems”, of the object of a nested priority construction, and there is a metatheorem listing conditions which guarantee the success of the construction. The metatheorem has different versions, with later versions becoming simpler and more general. The information needed to meet the requirements is enumerated by a function, where α is an arbitrary recursive ordinal. All other objects associated with the α-system are r.e. In the basic metatheorem, the requirements must all be at level α, although there is a special result, for limit α, which allows one requirement at each level in an increasing sequence with limit α. There are other abstract descriptions of nested priority arguments in [K1], [K2], [K3], and [L-L].A typical use of α-systems is that in [B], where it is shown that, for a relation R on a recursive structure , under suitable assumptions, if R does not have a “recursive Σα” definition in , then there is a recursive isomorphic copy of in which the image of R is not . There is no difficulty in generalizing this to make each of infinitely many relations not , when the assumptions are uniformly satisfied and each relation has no recursive Σα definition. However, the metatheorems for α-systems do not apply to the situation where we have several (even two) relations Ri, which do not have recursive Σβi definitions and whose images we wish to make not for distinct βi. An even more basic problem is to construct a recursive copy of a recursive structure via an isomorphism whose restriction to various sets Ui, is not If βi, = α for all i, then we can use an (α + 1)-system; otherwise, the old metatheorems do not apply.
A solution to the completeness problem for weakly aggregative modal logic
Authors: Apostoli Peter , Brown Bryson 
Published: May 2006

We are accustomed to regardingKas the weakest modal logic admitting of a relational semantics in the style made popular by Kripke. However, in a series of papers which demonstrates a startling connection between modal logic and the theory of paraconsistent inference, Ray Jennings and Peter Schotch have developed a generalized relational frame theory which articulates an infinite hierarchy of sublogics ofK, each expressing a species of “weakly aggregative necessity”. Recall thatKis axiomatized, in the presence ofNandRM, by the schema of “binary aggregation”For eachn≥ 1, the weakly aggregative modal logicKnis axiomatized by replacingKwith the schema of “n-ary aggregation”which is ann-ary relaxation, or weakening, ofK. Note thatK1=K.In [3], the authors claim without proof thatKnis determined by the class of framesF= (W, R), whereWis a nonempty set andRis an (n+ 1)-ary relation onW, under the generalization of Kriple's truth condition according to which □αis true at a pointwinWif and only ifαis true at one ofx1,…,xnfor allx1,…,xninWsuch thatRw, x1,…,xn.
Some questions concerning the cofinality of Sym(κ)
Authors: Sharp James D. , Thomas Simon 
Published: May 2006

Suppose thatGis a group that is not finitely generated. Then the cofinality ofG, writtenc(G), is denned to be the least cardinalλsuch thatGcan be expressed as the union of a chain ofλproper subgroups. Ifκis an infinite cardinal, then Sym(κ) denotes the group of all permutations of the setκ= {α∣α<κ}. In [1], Macpherson and Neumann proved thatc(Sym(κ)) >κfor all infinite cardinalsκ. In [4], we proved that it is consistent thatc(Sym(ω)) and 2ωcan be any two prescribed regular cardinals, subject only to the obvious requirement thatc(Sym(ω)) ≤ 2ω. Our first result in this paper is the analogous result for regular uncountable cardinalsκ.Theorem 1.1.Let V ⊨ GCH. Let κ, θ, λ ∈ V be cardinals such that(i) κ and θ are regular uncountable, and(ii)κ < θ ≤cf(λ).Then there exists a notion of forcingℙ,which preserves cofinalities and cardinalities, such that if G isℙ-generic then V[G] ⊨c(Sym(κ)) = θ ≤λ= 2κ.Theorem 1.1 will be proved in §2. Our proof is based on a very powerful uniformization principle, which was shown to be consistent for regular uncountable cardinals in [2].
The existence of finitely based lower covers for finitely based equational theories
Authors: Ježek Jaroslav , McNulty George F. 
Published: May 2006

By an equational theory we mean a set of equations from some fixed language which is closed with respect to logical consequences. We regard equations as universal sentences whose quantifier-free parts are equations between terms. In our notation, we suppress the universal quantifiers. Once a language has been fixed, the collection of all equational theories for that language is a lattice ordered by set inclusion The meet in this lattice is simply intersection; the join of a collection of equational theories is the equational theory axiomatized by the union of the collection. In this paper we prove, for languages with only finitely many fundamental operation symbols, that any nontrivial finitely axiomatizable equational theory covers some other finitely axiomatizable equational theory. In fact, our result is a little more general.There is an extensive literature concerning lattices of equational theories. These lattices are always algebraic. Compact elements of these lattices are the finitely axiomatizable equational theories. We also call themfinitely based. The largest element in the lattice is compact; it is the equational theory based on the single equationx≈y. The smallest element of the lattice is thetrivial theoryconsisting of tautological equations. For all but the simplest languages, the lattice of equational theories is intricate. R. McKenzie in [6] was able to prove in essence that the underlying language can be recovered from the isomorphism type of this lattice.
A non-standard construction of Haar measure and weak König's lemma
Authors: Tanaka Kazuyuki , Yamazaki Takeshi 
Published: May 2006

AbstractIn this paper, we show within RCA0 that weak König's lemma is necessary and sufficient to prove that any (separable) compact group has a Haar measure. Within WKL0, a Haar measure is constructed by a non-standard method based on a fact that every countable non-standard model of WKL0 has a proper initial part isomorphic to itself [10].
Property theory and the revision theory of definitions
Authors: Orilia Francesco 
Published: May 2006

§1. Introduction.Russell's type-theory can be seen as a theory of properties, relations, and propositions (PRPs) (in short, a property theory). It relies on rigid type distinctions at the grammatical level to circumvent the property theorist's major problem, namely Russell's paradox, or, more generally, the paradoxes of predication. Type theory has arguably been the standard property theory for years, often taken for granted, and used in many applications. In particular, Montague [27] has shown how to use a type-theoretical property-theory as a foundation for natural language semantics.In recent years, it has been persuasively argued that many linguistic and ontological data are best accounted for by using a type-free property theory. Several type-free property theories, typically with fine-grained identity conditions for PRPs, have therefore been proposed as potential candidates to play a foundational role in natural language semantics, or for related applications in formal ontology and the foundations of mathematics (Bealer [6], Cocchiarella [18], Turner [35], etc.).Attempts have then been made to combine some such property theory with a Montague-style approach in natural language semantics. Most notably, Chierchia and Turner [15] propose a Montague-style semantic analysis of a fragment of English, by basically relying on the type-free system of Turner [35]. For a similar purpose Chierchia [14] relies on one of the systems based on homogeneous stratification due to Cocchiarella. Cocchiarella's systems have also been used for applications in formal ontology, inspired by Montague's account of quantifier phrases as, roughly, properties of properties (see, e.g., Cocchiarella [17], [19], Landini [25], Orilia [29]).
The real line in elementary submodels of set theory
Authors: Kunen Kenneth , Tall Franklin D. 
Published: May 2006

The use of elementary submodels has become a standard tool in set-theoretic topology and infinitary combinatorics. Thus, in studying some combinatorial objects, one embeds them in a set, M, which is an elementary submodel of the universe, V (that is, (M; Є) ≺ (V; Є)). Applying the downward Löwenheim-Skolem Theorem, one can bound the cardinality of M. This tool enables one to capture various complicated closure arguments within the simple “≺”.However, in this paper, as in the paper [JT], we study the tool for its own sake. [JT] discussed various general properties of topological spaces in elementary submodels. In this paper, we specialize this consideration to the space of real numbers, ℝ. Our models M are not in general transitive. We will always have ℝ Є M, but not usually ℝ ⊆ M. We plan to study properties of the ℝ ⋂ M's. In particular, as M varies, we wish to study whether any two of these ℝ ⋂ M's are isomorphic as topological spaces, linear orders, or fields.As usual, it takes some sleight-of-hand to formalize these notions within the standard axioms of set theory (ZFC), since within ZFC, one cannot actually define the notion (M;Є) ≺ (V;Є). Instead, one proves theorems about M such that (M;Є) ≺ (H(θ);Є), where θ is a “large enough” cardinal; here, H(θ) is the collection of all sets whose transitive closure has size less than θ.
Un principe d'ax-kochen-ershov pour des structures intermédiates entre groupes et corps valués
Authors: Delon Françoise , Simonetta Patrick 
Published: May 2006

AbstractAn Ax-Kochen-Ershov principle for intermediate structures between valued groups and valued fields.We will consider structures that we call valued B-groups and which are of the form 〈G, B, *, υ〉 where– G is an abelian group,– B is an ordered group,– υ is a valuation denned on G taking its values in B,– * is an action of B on G satisfying: ∀x ϵ G ∀ b ∈ B υ(x * b) = ν(x) · b.The analysis of Kaplanski for valued fields can be adapted to our context and allows us to formulate an Ax-Kochen-Ershov principle for valued B-groups: we axiomatise those which are in some sense existentially closed and also obtain many of their model-theoretical properties. Let us mention some applications:1. Assume that υ(x) = υ(nx) for every integer n ≠ 0 and x ϵ G, B is solvable and acts on G in such a way that, for the induced action, Z[B] ∖ {0} embeds in the automorphism group of G. Then 〈G, B, *, υ〉 is decidable if and only if B is decidable as an ordered group.2. Given a field k and an ordered group B, we consider the generalised power series field k((B)) endowed with its canonical valuation. We consider also the following structure:where k((B))+ is the additive group of k((B)), S is a unary predicate interpreting {Tb ∣ b ϵB}, and ×↾k((B))×S is the multiplication restricted to k((B)) × S, structure which is a reduct of the valued field k((B)) with its canonical cross section. Then our result implies that if B is solvable and decidable as an ordered group, then M is decidable.3. A valued B–group has a residual group and our Ax-Kochen-Ershov principle remains valid in the context of expansions of residual group and value group. In particular, by adding a residual order we obtain new examples of solvable ordered groups having a decidable theory.
Grafted frames and S1 -completeness
Authors: Zhou Beihai 
Published: May 2006

AbstractA grafted frame is a new kind of frame which combines a modal frame and some relevance frames. A grafted model consists of a grafted frame and a truth-value assignment. In this paper, the grafted frame and the grafted model are constructed and used to show the completeness of S1. The implications of S1-completeness are discussed.A grafted frame does not combine two kinds of frames simply by putting relations defined in the components together. That is, the resulting grafted frame is not in the form of <W,R,R′>, or more generally, in the form of <W, R, R′,R″>,…>, which consists of a non-empty set with several relations defined on it.1 Rather, it resembles the construction of fibering proposed by D. M. Gabbay and M. Finger (see [4] and [3]). On a grafted frame, some modal worlds, which belong to the initial modal frame, are attached by some relevance frames.However, these two semantics have important differences. Consider the combined semantics involving semantics of relevance logic and modal logic. A fibred model and a grafted model proposed in this paper differ in the following respects. First, a fibred model is constructed from a class of modal models and a class of relevance models. A grafted model consists of a grafted frame and a truth-value assignment, where the grafted frame is constructed from a modal frame and some relevance frames, and the assignment is a union of a modal truth-value assignment VM and some relevance truth-value assignments VR. VM (VR) defined in this paper is not the same as the assignment contained in a modal (relevance) model. Second, in a fibred model each relevance world is associated (or fibred) with a modal model and each modal world with a relevance model.2 To be the grafted frame on which a grafted model is based, it is enough to have some modal worlds attached by some relevance frames. Moreover, no relevance world is associated with a modal frame in the grafted frame. Third, fibred models are intended to provide an appropriate semantics to combined logics. Grafted frames and grafted models are inspired to characterize S1, which, containing only one modality □, is not a combined logic. It is shown in this paper that S1 is sort of a meta-logic of the intersection of S0.4 and F, where S0.4, a new system proposed in this paper, is in turn a meta-logic of the relevance logic.
The cylindric algebras of three-valued logic
Authors: Feldman Norman 
Published: May 2006

In this paper we consider the three-valued logic used by Kleene [6] in the theory of partial recursive functions. This logic has three truth values: true (T), false (F), and undefined (U). One interpretation of U is as follows: Suppose we have two partially recursive predicates P(x) and Q(x) and we want to know the truth value of P(x) ∧ Q(x) for a particular x0. If x0 is in the domain of definition of both P and Q, then P(x0) ∧ Q(x0) is true if both P(x0) and Q(x0) are true, and false otherwise. But what if x0 is not in the domain of definition of P, but is in the domain of definition of Q? There are several choices, but the one chosen by Kleene is that if Q(X0) is false, then P(x0) ∧ Q(x0) is also false and if Q(X0) is true, then P(x0) ∧ Q(X0) is undefined.What arises is the question about knowledge of whether or not x0 is in the domain of definition of P. Is there an effective procedure to determine this? If not, then we can interpret U as being unknown. If there is an effective procedure, then our decision for the truth value for P(x) ∧ Q(x) is based on the knowledge that is not in the domain of definition of P. In this case, U can be interpreted as undefined. In either case, we base our truth value of P(x) ∧ Q(x) on the truth value of Q(X0).
Compactness of Lobe spaces
Authors: Jin Renling , Shelah Saharon 
Published: May 2006

AbstractIn this paper we show that the compactness of a Loeb space depends on its cardinality, the nonstandard universe it belongs to and the underlying model of set theory we live in. In §1 we prove that Loeb spaces are compact under various assumptions, and in §2 we prove that Loeb spaces are not compact under various other assumptions. The results in §1 and §2 give a quite complete answer to a question of D.Ross in [9], [11] and [12].
An ordinal partition avoiding pentagrams
Authors: Larson Jean A. 
Published: May 2006

AbstractSuppose that α = γ + δ where γ ≥ δ > 0. Then there is a graph which has no independent set of order type and has no pentagram (a pentagram is a set of five points with all pairs joined by edges). In the notation of Erdős and Rado. who generalized Ramsey's Theorem to this setting.