bluuebunny/crossref_metadata_2025_split huggingface dataset:
First order topological structures and theories
Authors: Pillay Anand 
Published: May 2006

In this paper we introduce the notion of a first order topological structure, and consider various possible conditions on the complexity of the definable sets in such a structure, drawing several consequences thereof.Our aim is to develop, for a restricted class of unstable theories, results analogous to those for stable theories. The “material basis” for such an endeavor is the analogy between the field of real numbers and the field of complex numbers, the former being a “nicely behaved” unstable structure and the latter the archetypal stable structure. In this sense we try here to situate our work on o-minimal structures [PS] in a general topological context. Note, however, that the p-adic numbers, and structures definable therein, will also fit into our analysis.In the remainder of this section we discuss several ways of studying topological structures model-theoretically. Eventually we fix on the notion of a structure in which the topology is “explicitly definable” in the sense of Flum and Ziegler [FZ]. In §2 we introduce the hypothesis that every definable set is a Boolean combination of definable open sets. In §3 we introduce a “dimension rank” on (closed) definable sets. In §4 we consider structures on which this rank is defined, and for which also every definable set has a finite number of definably connected definable components. We show that prime models over sets exist under such conditions.
Open induction and the true theory of rationals
Authors: Adamowicz Zofia 
Published: May 2006

In the paper we prove the following theorem:Theorem. There is a model N of open induction in which the set of primes is bounded and N is such that its field of fractions 〈N*, +, ·, <〉 is elementarily equivalent to 〈Q, +, ·, <〉 (the standard rationals).We fix an ω1-saturated model 〈M, +, ·, <〉 of PA. Let 〈M*, +, ·, <〉 denote the field of fractions of M. The model N that we are looking for will be a substructure of 〈M*, +, ·, <〉.If A ⊆ M* then let Ā denote the ring generated by A within M*, Ậ the real closure of A, and A* the field of fractions generated by A. We haveLet J ⊆ M. Then 〈M*, +, ·〉 is a linear space over J*. If x1,…,xk ∈ M*, we shall say that x1,…,xk are J-independent if 〈1, x1,…, xk〉 are J*-independent in the usual sense. As usual, we extend the notion of J-independence to the case of infinite sets.If A ⊆ M* and X ⊆ A, then we say that X is a J-basis of A if X is a maximal subset of A which is J-independent.
An analytic completeness theorem for logics with probability quantifiers
Authors: Hoover Douglas N. 
Published: May 2006

AbstractWe give a completeness theorem for a logic with probability quantifiers which is equivalent to the logics described in a recent survey paper of Keisler [K]. This result improves on the completeness theorems in [K] in that it works for languages with function symbols and produces a model whose universe is an analytic subset of the real line, and whose relations and functions are Borel relative to this universe.
Monotone but not positive subsets of the Cantor space
Authors: Dougherty Randall 
Published: May 2006

A subset of the Cantor space ω2 is called monotone iff it is closed upward under the partial ordering ≤ defined by x ≤ y iff x(n) ≤ y(n) for all n ∈ ω. A set is -positive (-positive) iff it is monotone and -positive set is a countable union of -positive sets; a -positive set is a countable intersection of -positive sets. (See Cenzer [2] for background information on these concepts.) It is clear that any -positive set is and monotone; the converse holds for n ≤ 2 [2] and was conjectured by Dyck to hold for greater n. In this note, we will disprove this conjecture by giving examples of monotone sets (for n ≥ 3) which are not even -positive.First we note a few isomorphisms. The space (ω2, ≤) is isomorphic to the space (ω2 ≥), so instead of monotone and positive sets we may construct hereditary and negative sets (the analogous notions with “closed upward” replaced by “closed downward”). Also, (ω2, ≤) is isomorphic to ((ω), ⊆), where denotes the power set operator, or to ((S), ⊆) for any countably infinite set S.In order to remove extraneous notation from the proofs, we state the results in an abstract form (whose generality is deceptive).
On the existence of extensional partial combinatory algebras
Authors: Bethke Ingemarie 
Published: May 2006

AbstractThe principal aim of this paper is to present a construction method for nontotal extensional combinatory algebras. This is done in §2. In §0 we give definitions of some basic notions for partial combinatory algebras from which the corresponding notions for (total) combinatory algebras are obtained as specializations. In §1 we discuss some properties of nontotal extensional combinatory algebras in general. §2 describes a “partial” variant of reflexive complete partial orders yielding nontotal extensional combinatory algebras. Finally, §3 deals with properties of the models constructed in §2, such as incompletability, having no total submodel and the pathological behaviour with respect to the interpretation of unsolvable λ-terms.
A contractionless semilattice semantics
Authors: Giambrone Steve , Meyer Robert K. , Urquhart Alasdair 
Published: May 2006

Semilattice semantics for relevant logics were discovered independently by Routley and Urquhart over 10 years ago. A semilattice semantics was first published in [10], where the weak theory of implication of [8] and [3] (i.e., R →, the pure implication fragment of the system R of relevant implication) is shown to be consistent and complete with respect to it. That result was extended in [11], But the semantics is explored in greatest detail in [12]. As reported in [4], Fine outfitted the positive semilattice semantics for R+ with a suitable Hilbert-style axiomatisation. (We refer to the system as ◡R+.) In 1980 Charlwood supplied a subscripted system of natural deduction. (See [1] and [2].) A subscripted Gentzen system was devised in [5] and [6].Obviously, the central idea of the semilattice semantics is to impose relevant-style valuations on a semilattice (with an identity) used as the underlying model structure. However, in [12] the contractionless semantics are obtained (quite reasonably) by dropping the idempotence postulate and thus changing the relatively simple semilattice structure into a commutative monoid. Here we show that the semilattice structure can be regained for positive, contractionless relevant implication. Although we have no proofs as yet, we think that this semantics will pave the way for showing completeness for the corresponding subscripted Gentzen and natural deduction systems, as well as the Hilbert-style axiomatization, ◡RW+.
Alfred Tarski's work in set theory
Authors: Levy Azriel 
Published: May 2006

Alfred Tarski started contributing to set theory at a time when the Zermelo-Fraenkel axiom system was not yet fully formulated and as simple a concept as that of the inaccessible cardinal was not yet fully defined. At the end of Tarski's career the basic concepts of the three major areas and tools of modern axiomatic set theory, namely constructibility, large cardinals and forcing, were already clearly defined and were in the midst of a rapid successful development. The role of Tarski in this development was somewhat similar to the role of Moses showing his people the way to the Promised Land and leading them along the way, while the actual entry of the Promised Land was done mostly by the next generation. The theory of large cardinals was started mostly by Tarski, and developed mostly by his school. The mathematical logicians of Tarski's school contributed much to the development of forcing, after its discovery by Paul Cohen, and to a lesser extent also to the development of the theory of constructibility, discovered by Kurt Gödel. As in other areas of logic and mathematics Tarski's contribution to set theory cannot be measured by his own results only; Tarski was a source of energy and inspiration to his pupils and collaborators, of which I was fortunate to be one, always confronting them with new problems and pushing them to gain new ground.Tarski's interest in set theory was probably aroused by the general emphasis on set theory in Poland after the First World War, and by the influence of Wactaw Sierpinski, who was one of Tarski's teachers at the University of Warsaw. The very first paper published by Tarski, [21], was a paper in set theory.
Alfred Tarski's elimination theory for real closed fields
Authors: Van Den Dries Lou 
Published: May 2006

Tarski made a fundamental contribution to our understanding of R, perhaps mathematics’ most basic structure. His theorem is the following.To any formula ϕ(X1, …, Xm) in the vocabulary {0, 1, +, ·, <} one can effectively associate two objects: (i) a quantifier free formula (X1, …, Xm) in(1) the same vocabulary, and (ii) a proofof the equivalence ϕ ↔ that uses only the axioms for real closed fields. (Reminder: real closed fields are ordered fields with the intermediate value property for polynomials.)Everything in (1) has turned out to be crucial: that arbitrary formulas are considered rather than just sentences, that the equivalence ϕ ↔ holds in all real closed fields rather than only in R; even the effectiveness of the passage from ϕ to has found good theoretical uses besides firing the imagination.We begin this survey with some history in §1. In §2 we discuss three other influential proofs of Tarski's theorem, and in §3 we consider some of the remarkable and totally unforeseen ways in which Tarski's theorem functions nowadays in mathematics, logic and computer science.I thank Ward Henson, and in particular Wilfrid Hodges without whose constant prodding and logistic support this article would not have been written.
Alfred Tarski's work on general metamathematics
Authors: Blok W. J. , Pigozzi Don 
Published: May 2006

In this essay we discuss Tarski's work on what he calledthe methodology of the deductive sciences, or more briefly, borrowing the terminology of Hilbert,metamathematics, The clearest statement of Tarski's views on this subject can be found in his textbookIntroduction to logic[41m].1Here he describes the tasks of metamathematics as “the detailed analysis and critical evaluation of the fundamental principles that are applied in the construction of logic and mathematics”. He goes on to describe what these fundamental principles are: All the expressions of the discipline under consideration must be defined in terms of a small group of primitive expressions that seem immediately understandable. Furthermore, only those statements of the discipline are accepted as valid that can be deduced by precisely defined and universally accepted means from a small set of axioms whose validity seems evident. The method of constructing a discipline in strict accordance with these principles is known as thedeductive method, and the disciplines constructed in this manner are calleddeductive systems. Since contemporary mathematical logic is one of those disciplines that are subject to these principles, it itself is a deductive science. Tarski then goes on to say:“The view has become more and more common that the deductive method is the only essential feature by means of which the mathematical disciplines can be distinguished from all other sciences; not only is every mathematical discipline a deductive theory, but also, conversely, every deductive theory is a mathematical discipline”.This identification of mathematics with the deductive sciences is in our view one of the distinctive aspects of Tarski's work. Another characteristic feature is his broad view of what constitutes the domain of metamathematical investigations. A clue to this aspect of his work can also be found in Chapter 6 ofIntroduction to logic. After a discussion of the notions of completeness and consistency, he remarks that the investigations concerning these topics were among the most important factors contributing to a considerable extension of the domain of methodological studies, and caused even a fundamental change in the whole character of the methodology of deductive sciences.
Missionary mathematics
Authors: Poizat Bruno 
Published: May 2006

Le plus souvent, la logique reste une discipline à la périphérie des mathématiques, qu’elle observe de l’extérieur, sans y pénétrer vraiment. C’est un discours sur les mathematiques qui ne dit rien au mathématicien; il n’y reconnait pas son activité favorite, ni ne croit qu’elle puisse avoir une influence sur sa pratique.L’illustration la plus extrême de cette tradition, ce sont les “reverse mathematics” de Harvey Friedman, qui connaissent le succès que l’on sait. Je veux parler ici d’une tendance toute opposée, secrétée par les développements contemporains de la théorie des modèles, qui promet des positions beaucoup plus directes.Elle se cristalise autour de l’étude des groupes stables; l’apparition de groupes n’a rien d’inattendu dans un contexte mathématiquement signifiant: un groupe, c’est ce qui garantit une structure non-triviale (ceci n’est pas un simple argument terroriste: il y a des théoremes pour le soutenir); quant à la stabilité, c’est une hypothèse de controle structurel, au large champ d’application, et qu’on pourra dépasser quand seront résolus les problèmes posés dans le cadre stable.
On a theory of weak implications
Authors: Okada Mitsuhiro 
Published: May 2006

The purpose of this paper is to study logical implications which are much weaker than the implication of intuitionistic logic.In §1 we define the system SI (system of Simple Implication) which is obtained from intuitionistic logic by restricting the inference rules of intuitionistic implication. The implication of the system SI is called the “simple implication” and denoted by ⊃, where the simple implication ⊃ has the following properties:(1) The simple implication ⊃ is much weaker than the usual intuitionistic implication.(2) The simple implication ⊃ can be interpreted by the notion of provability, i.e., we have a very simple semantics for SI so that a sentence A ⊃ B is interpreted as “there exists a proof of B from A”.(3) The full-strength intuitionistic implication ⇒ is definable in a weak second order extension of SI; in other words, it is definable by help of a variant of the weak comprehension schema and the simple implication ⊃. Therefore, though SI is much weaker than the intuitionistic logic, the second order extension of SI is equivalent to the second order extension of the intuitionistic logic.(4) The simple implication is definable in a weak modal logic MI by the use of the modal operator and the intuitionistic implication ⇒ with full strength. More precisely, A ⊃ B is defined as the strict implication of the form ◽(A ⇒ B).In §1, we show (3) and (4). (2) is shown in §2 in a more general setting.Semantics by introduction rules of logical connectives has been studied from various points of view by many authors (e.g. Gentzen [4], Lorentzen [5], Dummett [1], [2], Prawitz [8]. Martin-Löf [7], Maehara [6]). Among them Gentzen (in §§10 and 11 of [4]) introduced such a semantics in order to justify logical inferences and the mathematical induction rule. He observed that all of the inference rules of intuitionistic arithmetic, except for those on implication and negation, are justified by means of his semantics, but justification of the inference rules on implication and negation contains a circular argument for the interpretation by introduction rules, where the natural interpretation of A ⊃ B by ⊃-introduction rule is “there exists a proof of B from A ” (cf. §11 of Gentzen [4]).
A downward Löwenheim-Skolem theorem for infinitary theories which have the unsuperstability property
Authors: Grossberg Rami 
Published: May 2006

AbstractWe present a downward Löwenheim-Skolem theorem which transfers downward formulas from L∞,ω to , ω. The simplest instance is:Theorem 1. Let λ > κ be infinite cardinals, and let L be a similarity type of cardinality κ at most. For every L-structure M of cardinality λ and every X ⊆ M there exists a model N ≺ M containing the set X of power ∣X∣ · κ such that for every pair of finite sequences a, b ∈ NThe following theorem is an application:Theorem 2. Let λ<κ, T ∈ , ω, and suppose χ is a Ramsey cardinal greater than λ. If T has the (χ, , ω)-unsuperstability property, then T has the (χ, , ω)-unsuperstability property.
The interpretability logic of Peano arithmetic
Authors: Berarducci Alessandro 
Published: May 2006

AbstractPA is Peano arithmetic. The formula InterpPA(α, β) is a formalization of the assertion that the theory PA + α interprets the theory PA + β (the variables α and β are intended to range over codes of sentences of PA). We extend Solovay's modal analysis of the formalized provability predicate of PA, PrPA(x), to the case of the formalized interpretability relation InterpPA(x, y). The relevant modal logic, in addition to the usual provability operator ‘□’, has a binary operator ‘⊳’ to be interpreted as the formalized interpretability relation. We give an axiomatization and a decision procedure for the class of those modal formulas that express valid interpretability principles (for every assignment of the atomic modal formulas to sentences of PA). Our results continue to hold if we replace the base theory PA with Zermelo-Fraenkel set theory, but not with Gödel-Bernays set theory. This sensitivity to the base theory shows that the language is quite expressive. Our proof uses in an essential way earlier work done by A. Visser, D. de Jongh, and F. Veltman on this problem.
Théories d'algèbres de Boole munies d'idéaux distingués. II
Authors: Touraille Alain 
Published: May 2006

La première partie de cet article ([10], que nous désignerons par (I) dans la suite) était consacrée à la théorie élémentaire TX des algèbres de Boole munies d'idéaux distingués indéxés dans un ensemble X. On a vu que les idéaux définissables dans un modèle de Tx forment la sous-algèbre engendrée par les idéaux distingués de l'algèbre de Heyting des idéaux de munie de l'opérateur sa défini par sa(K) = {a: a/K est sans atome}, et que la théorie de peut être caractérisée par la structure composée de l'algèbre de Heyting des idéaux définissables munie de l'opérateur sa et des idéaux distingués, et par l'application qui à tout K de fait correspondre le nombre d'atomes de /K, pris dans N ⋃ {∞}.Nous montrons maintenant que les structures possibles peuvent être définies de façon axiomatique en introduisant une classe équationnelle d'algèbres de Heyting munies d'une opération unaire, dites sa-algèbres de Heyting (en abrégé sa-AH), et en prouvant que cette classe est constituée des algèbres pouvant être plongées dans l'algèbre de Heyting des idéaux d'une algèbre de Boole, munie de l'opérateur sa. Ainsi les sont, à isomorphisme près, les sa-AH engendrées par des éléments distingués indéxés dans X; on en déduit une classification des extensions complètes de Tx en montrant que les applications qui peuvent être associées à une structure de la forme pour caractériser la théorie d'un modèle sont déterminées par leur restriction à une partie M() définie uniformément, sur laquelle elles prennent des valeurs dans (N − {0}) ⋃ {∞}, et que réciproquement toute application de M() dans (N − {0}) ⋃ {∞} est une telle restriction.
Finite and finitely separable intermediate propositional logics
Authors: Bellissima Fabio 
Published: May 2006

§0. Introduction and material background. The present paper is devoted to the study of intermediate propositional logics, and it is based on [Be, §§1 and 2].§2 (§§0 and 1 are introductory) concerns the axiomatization of finite logics. In the literature several effective procedures to axiomatize finite logics are present (cf., for instance, [MK] and [Wr]), but, in each case, the number of propositional variables which are used is redundant. In this direction, Theorem 2.2 provides (a) a criterion to determine, given a finite logic L, the least n such that L is axiomatizable by formulas in n variables, and (b) an effective axiomatization by an n-formula. As a corollary we obtain a negative answer to Problem 7.10 of [Ho/On], showing that there is no connection between the slice to which L belongs and the number of propositional variables necessary to axiomatize L.The principal results of the paper are in §3. In fact, a great deal of research has been done on the correspondence between conditions on the relation of Kripke-structures from one side, and axioms added to Int from the other. In this section we (a) introduce the concept of finitely separable class of Kripke-frames, and show, by means of several examples, that this concept is “wide”, in the sense that all the most studied classes of frames determined by semantical conditions are finitely separable; (b) show that each finitely separable class is axiomatizable, and that the axioms can be found by means of semantical considerations only; and (c) establish the finite model property for all the finitely separable logics.
Believing the axioms. I
Authors: Maddy Penelope 
Published: May 2006

§0. Introduction. Ask a beginning philosophy of mathematics student why we believe the theorems of mathematics and you are likely to hear, “because we have proofs!” The more sophisticated might add that those proofs are based on true axioms, and that our rules of inference preserve truth. The next question, naturally, is why we believe the axioms, and here the response will usually be that they are “obvious”, or “self-evident”, that to deny them is “to contradict oneself” or “to commit a crime against the intellect”. Again, the more sophisticated might prefer to say that the axioms are “laws of logic” or “implicit definitions” or “conceptual truths” or some such thing.Unfortunately, heartwarming answers along these lines are no longer tenable (if they ever were). On the one hand, assumptions once thought to be self-evident have turned out to be debatable, like the law of the excluded middle, or outright false, like the idea that every property determines a set. Conversely, the axiomatization of set theory has led to the consideration of axiom candidates that no one finds obvious, not even their staunchest supporters. In such cases, we find the methodology has more in common with the natural scientist's hypotheses formation and testing than the caricature of the mathematician writing down a few obvious truths and preceeding to draw logical consequences.The central problem in the philosophy of natural science is when and why the sorts of facts scientists cite as evidence really are evidence. The same is true in the case of mathematics. Historically, philosophers have given considerable attention to the question of when and why various forms of logical inference are truth-preserving. The companion question of when and why the assumption of various axioms is justified has received less attention, perhaps because versions of the “self-evidence” view live on, and perhaps because of a complacent if-thenism.
Some filters of partitions
Authors: Matet Pierre 
Published: May 2006

§0. Introduction. We started our study of filters of partitions in [15]. We shall here restrict ourselves to the consideration of filters on (ω)ω, the set of all infinite partitions of ω. §1 is an attempt to elucidate the connection between filters on (ω)ω and filters over ω. Given a filter H over ω, we define two filters FH and GH on (ω)ω, and we characterize p-points, rare ultrafilters and Ramsey ultrafilters in terms of properties of the associated filters of partitions.The remainder of the paper is devoted to the study of those filters that can be associated with Hindman's theorem and its extensions. Let us introduce some notation. Suppose * is an associative operation on ω, and let a subset A of ω and an ordinal α with 0 < α ≤ ω be given.