bluuebunny/crossref_metadata_2025_split huggingface dataset:
Model completeness of the new strongly minimal sets
Authors: Holland Kitty L. 
Published: May 2006

Boris Zil'ber conjectured that all strongly minimal theories are bi-interpretable with one of the “classical” sorts: theories of algebraically closed fields, theories of infinite vector spaces over division rings and theories with trivial algebraic closure relations. Hrushovski produced the first two classes of counterexample to this conjecture in [10] and [9]. Subsequently, in [8], the author gave an explicit axiomatization of a special case of [9] from which model completeness could quickly be deduced. It was unclear at that writing whether the model completeness result was true in the general case or was due to peculiarities of the case under consideration. The main new result of this paper is model completeness, not only of the general case in [9], but also of the theories described in [10]. Specifically, we present a general framework in which producing a strongly minimal theory is reduced to finding an elementary class of theories satisfying certain requirements (see below). We present the theories of [10] and [9] as special instances of such theories, giving an explicit axiomatization from which model completeness immediately follows in each case.We hope by presenting these constructions in parallel, using common language and extracting common elements, to make easier both the exploitation of the ideas involved in their making and their comparison with other recent constructions of a similar flavor. For a selection of such constructions, see [6], [1], [2] and [3]. For more general background, see [2], [4] and [11].
Quantifier elimination for neocompact sets
Authors: Keisler H. Jerome 
Published: May 2006

AbstractWe shall prove quantifier elimination theorems for neocompact formulas, which define neocompact sets and are built from atomic formulas using finite disjunctions, infinite conjunctions, existential quantifiers, and bounded universal quantifiers. The neocompact sets were first introduced to provide an easy alternative to nonstandard methods of proving existence theorems in probability theory, where they behave like compact sets. The quantifier elimination theorems in this paper can be applied in a general setting to show that the family of neocompact sets is countably compact. To provide the necessary setting we introduce the notion of a law structure. This notion was motivated by the probability law of a random variable. However, in this paper we discuss a variety of model theoretic examples of the notion in the light of our quantifier elimination results.
Chains of end elementary extensions of models of set theory
Authors: Villaveces Andrés 
Published: May 2006

AbstractLarge cardinals arising from the existence of arbitrarily long end elementary extension chains over models of set theory are studied here. In particular, we show that the large cardinals obtained in this fashion (‘unfoldable cardinals’) lie in the boundary of the propositions consistent with ‘V = L’ and the existence of 0#. We also provide an ‘embedding characterisation’ of the unfoldable cardinals and study their preservation and destruction by various forcing constructions.
Cartesian isomorphisms are symmetric monoidal: A justification of linear logic
Authors: Došen Kosta , Petrić Zoran 
Published: May 2006

AbstractIt is proved that all the isomorphisms in the cartesian category freely generated by a set of objects (i.e., a graph without arrows) can be written in terms of arrows from the symmetric monoidal category freely generated by the same set of objects. This proof yields an algorithm for deciding whether an arrow in this free cartesian category is an isomorphism.
No elementary embedding from v into v is definable from parameters
Authors: Suzuki Akira 
Published: May 2006

In 1970, Kenneth Kunen showed that there is no non-trivial elementary embedding of the universe V into itself [2] using the axiom of choice. Kunen remarked in his paper that the result can be formalized in Morse-Kelley theory of sets and classes. In this paper, we will work within ZF, Zermelo-Fraenkel axioms, and deal with embeddings definable with a formula and a parameter.In ZF, a “class” is usually synonymous with “property”, that is a class definable with a parameter, C = {x: φ(x,p)}, where φ is a formula in the language [∈}. Using this convention, let j be a class. Then “j is an elementary embedding of V into V” is not a single statement but a schema of statements “j preserves ψ” for each formula ψ. We prove that this schema is expressible in the language {∈} by a single formula:Lemma. An embedding j: V → V is elementary iff j preservesψ.Here ψ(α, ψ, a) is the property “a is an ordinal, φ is a formula and Vα.”The lemma is of course a schema of lemmas, one for each formula denning j and for each ψ to be preserved.Using this we prove our theorem in ZF (again, a schema of theorems.):Theorem 1.1. There is no nontrivial definable elementary embedding j: V → V.Many symbols and their definitions follow those used by Drake's book [1]. The formula Sat expresses the satisfaction relation . The formula Fmla(u) expresses that u is the Gödel-set for a formula.
Relative enumerability in the difference hierarchy
Authors: Arslanov Marat M. , Laforte Geoffrey L. , Slaman Theodore A. 
Published: May 2006

AbstractWe show that the intersection of the class of 2-REA degrees with that of the ω-r.e. degrees consists precisely of the class of d.r.e. degrees. We also include some applications and show that there is no natural generalization of this result to higher levels of the REA hierarchy.
There are many almost strongly minimal generalizedn-gons that do not interpret an infinite group
Authors: Debonis Mark J. , Nesin Ali 
Published: May 2006

Generalizedn-gons are certain geometric structures (incidence geometries) that generalize the concept of projective planes (the nontrivial generalized 3-gons are exactly the projective planes).In a simplified world, every generalizedn-gon of finite Morley rank would be an algebraic one, i.e., one of the three families described in [9] for example. To our horror, John Baldwin [2], using methods discovered by Hrushovski [7], constructed ℵ1-categorical projective planes which are not algebraic. The projective planes that Baldwin constructed fail to be algebraic in a dramatic way.Indeed, every algebraic projective plane over an algebraically closed field is Desarguesian [12]. In particular, an algebraically closed field (isomorphic to the base field) can be interpreted in every one of them. However, in the projective planes that Baldwin constructed, one cannot even interpret an infinite group.In this article we show that the same phenomenon occurs for the generalizedn-gons ifn≥ 3 is an odd integer. For each suchnwe constructmany nonisomorphic generalizedn-gons of finite Morley rank that do not interpret an infinite group. As one may expect, our method is inspired by Hrushovski and Baldwin, and we follow Baldwin's line of approach. Quite often our proofs are a verification of the fact that the proofs of Baldwin [2] forn= 3 carry over to an arbitrary positive odd integern(which is sometimes far from being obvious). As in [2], we begin by defining a certain collection of finite graphsK* and a binary relation ≤ on these graphs. We show that (K*, ≤) satisfies the amalgamation property.
Ultrafilters which extend measures
Authors: Benedikt Michael 
Published: May 2006

AbstractWe study classes of ultrafilters on ω defined by a natural property of the Loeb measure in the Nonstandard Universe corresponding to the ultrafilter. This class, the Property M ultrafilters, is shown to contain all ultrafilters built up by taking iterated products over collections of pairwise nonisomorphic selective ultrafilters. Results on Property M ultrafilters are applied to the construction of extensions of probability measures, and to the study of measurable reductions between ultrafilters.
Minimum propositional proof length is NP-hard to linearly approximate
Authors: Alekhnovich Michael , Buss Sam , Moran Shlomo , Pitassi Toniann 
Published: May 2006

AbstractWe prove that the problem of determining the minimum propositional proof length is NP-hard to approximate within a factor of . These results are very robust in that they hold for almost all natural proof systems, including: Frege systems, extended Frege systems, resolution. Horn resolution, the polynomial calculus, the sequent calculus, the cut-free sequent calculus, as well as the polynomial calculus. Our hardness of approximation results usually apply to proof length measured either by number of symbols or by number of inferences, for tree-like or dag-like proofs. We introduce the Monotone Minimum (Circuit) Satisfying Assignment problem and reduce it to the problems of approximation of the length of proofs.
Power-like models of set theory
Authors: Enayat Ali 
Published: May 2006

Abstract.A model = (M. E, …) of Zermelo-Fraenkel set theory ZF is said to be 0-like. where E interprets ∈ and θ is an uncountable cardinal, if ∣M∣ = θ but ∣{b ∈ M: bEa}∣ < 0 for each a ∈ M, An immediate corollary of the classical theorem of Keisler and Morley on elementary end extensions of models of set theory is that every consistent extension of ZF has an ℵ1-like model. Coupled with Chang's two cardinal theorem this implies that if θ is a regular cardinal 0 such that 2<0 = 0 then every consistent extension of ZF also has a 0+-like model. In particular, in the presence of the continuum hypothesis every consistent extension of ZF has an ℵ2-like model. Here we prove:Theorem A. If 0 has the tree property then the following are equivalent for any completion T of ZFC:(i) T has a 0-like model.(ii) Ф ⊆ T. where Ф is the recursive set of axioms {∃κ (κ is n-Mahlo and “Vκis a Σn-elementary submodel of the universe”): n ∈ ω}.(iii) T has a λ-like model for every uncountable cardinal λ.Theorem B. The following are equiconsistent over ZFC:(i) “There exists an ω-Mahlo cardinal”.(ii) “For every finite language , all ℵ2-like models of ZFC() satisfy the schemeФ().
An open mapping theorem for o-minimal structures
Authors: Johns Joseph 
Published: May 2006

We fix an arbitrary o-minimal structure (R, ω, …), where (R, <) is a dense linearly ordered set without end points. In this paper “definable” means “definable with parameters from R”, We equip R with the interval topology and Rn with the induced product topology. The main result of this paper is the following.Theorem. Let V ⊆ Rnbe a definable open set and suppose that f: V → Rnis a continuous injective definable map. Then f is open, that is, f(U) is open whenever U is an open subset of V.Woerheide [6] proved the above theorem for o-minimal expansions of a real closed field using ideas of homology. The case of an arbitrary o-minimal structure remained an open problem, see [4] and [1]. In this paper we will give an elementary proof of the general case.Basic definitions and notation. A box B ⊆ Rn is a Cartesian product of n definable open intervals: B = (a1, b1) × … × (an, bn) for some ai, bi, ∈ R ∪ {−∞, +∞}, with ai < bi, Given A ⊆ Rn, cl(A) denotes the closure of A, int(A) denotes the interior of A, bd(A) ≔ cl(A) − int(A) denotes the boundary of A, and ∂A ≔ cl(A) − A denotes the frontier of A, Finally, we let π: Rn → Rn− denote the projection map onto the first n − 1 coordinates.Background material. Without mention we will use notions and facts discussed in [5] and [3]. We will also make use of the following result, which appears in [2].
Shelah's work on non-semi-proper iterations, II
Authors: Schlindwein Chaz 
Published: May 2006

One of the main goals in the theory of forcing iteration is to formulate preservation theorems for not collapsing ω1 which are as general as possible. This line leads from c.c.c. forcings using finite support iterations to Axiom A forcings and proper forcings using countable support iterations to semi-proper forcings using revised countable support iterations, and more recently, in work of Shelah, to yet more general classes of posets. In this paper we concentrate on a special case of the very general iteration theorem of Shelah from [5, chapter XV]. The class of posets handled by this theorem includes all semi-proper posets and also includes, among others, Namba forcing.In [5, chapter XV] Shelah shows that, roughly, revised countable support forcing iterations in which the constituent posets are either semi-proper or Namba forcing or P[W] (the forcing for collapsing a stationary co-stationary subset ofwith countable conditions) do not collapse ℵ1. The iteration must contain sufficiently many cardinal collapses, for example, Levy collapses. The most easily quotable combinatorial application is the consistency (relative to a Mahlo cardinal) of ZFC + CH fails + whenever A ∪ B = ω2 then one of A or B contains an uncountable sequentially closed subset. The iteration Shelah uses to construct this model is built using P[W] to “attack” potential counterexamples, Levy collapses to ensure that the cardinals collapsed by the various P[W]'s are sufficiently well separated, and Cohen forcings to ensure the failure of CH in the final model.In this paper we give details of the iteration theorem, but we do not address the combinatorial applications such as the one quoted above.These theorems from [5, chapter XV] are closely related to earlier work of Shelah [5, chapter XI], which dealt with iterated Namba and P[W] without allowing arbitrary semi-proper forcings to be included in the iteration. By allowing the inclusion of semi-proper forcings, [5, chapter XV] generalizes the conjunction of [5, Theorem XI.3.6] with [5, Conclusion XI.6.7].
Strong 0-1 laws in finite model theory
Authors: Lotfallah Wafik Boulos 
Published: May 2006

AbstractWe introduce a new framework for asymptotic probabilities of sentences, in which we have a σ-additive measure on the sample space of all sequencesA= {} of finite models, where the universe ofis {1,2, …, n}. and use this framework to strengthen 0-1 laws for logics.
Nonstandard analysis in topology: nonstandard and standard compactifications
Authors: Salbany S. , Todorov Todor 
Published: May 2006

AbstractLet (X, T) be a topological space and *X a nonstandard extension of X. Sets of the form *G. where G ∈ T, form a base for the “standard” topology ST on *X. The topological space (*X, ST) will be used to study compactifications of (X, T) in a systematic way.
A lambda proof of the P-W theorem
Authors: Hirokawa Sachio , Komori Yuichi , Nagayama Misao 
Published: May 2006

AbstractThe logical system P-W is an implicational non-commutative intuitionistic logic denned by axiom schemes B − (b → c) → (a → b) → a → c. B′ = (a → b) → (b → c) → a → c. I - a → a with the rules of modus ponens and substitution. The P-W problem is a problem asking whether α - β holds if α → β and β → α are both provable in P-W. The answer is affirmative. The first to prove this was E. P. Martin by a semantical method.In this paper, we give the first proof of Martin's theorem based on the theory of simply typed λ-calculus. This proof is obtained as a corollary to the main theorem of this paper, shown without using Martin's Theorem, that any closed hereditary right-maximal linear (HRML) λ-term of type α → α is βη-reducible to λxx. Here the HRML λ-terms correspond, via the Curry-Howard isomorphism, to the P-W proofs in natural deduction style.
Properties of ideals on the generalized Cantor spaces
Authors: Kraszewski Jan 
Published: May 2006

AbstractWe define a class of productiveσ-ideals of subsets of the Cantor space 2ω and observe that both σ-ideals of meagre sets and of null sets are in this class. From every productive σ-ideal we produce a σ-ideal of subsets of the generalized Cantor space 2κ. In particular, starting from meagre sets and null sets in 2ω we obtain meagre sets and null sets in 2ω, respectively. Then we investigate additivity, covering number, uniformity and cofinality of . For example, we show thatOur results generalizes those from [5].
The Moral Sense
Authors: Wilson James Q. 
Published: May 2006

The central problem for social science is to explain social order. How do people manage to live together? One can discern two ways of answering that question. The first view is normative and communal: people learn from their culture customs that provide an internal compass guiding them to act in ways that minimize conflict and ensure comity. The second view is rationalistic and individualistic: order is created by explicit and implicit agreements entered into by self-seeking individuals to avert the worst consequences of their predatory instincts. In the first view, order is natural and prior to any social contract or government institution; in the second, it is contrived and dependent on agreements and sanctions. Rules are obeyed in the first case because they have moral force, in the second because they convey personal advantage. In the first view, compliance is automatic and general; in the second, it is strategic and uncertain.The normative view has been under heavy attack for several decades for at least three reasons: it seems to imply a complacent functionalism; it appears to minimize or deny the value of conflict; and it lacks the theoretical power found in the assumption that people always seek their own interests. I believe that one can grant, up to a point, all of these objections and still be left dissatisfied with the alternative, namely, that social order is contrived, based on calculation, and dependent on individual assent.
Three uses of the Herbrand-Gentzen theorem in relating model theory and proof theory
Authors: Craig William 
Published: May 2006

One task of metamathematics is to relate suggestive but nonelementary modeltheoretic concepts to more elementary proof-theoretic concepts, thereby opening up modeltheoretic problems to proof-theoretic methods of attack. Herbrand's Theorem (see [8] or also [9], vol. 2) or Gentzen's Extended Hauptsatz (see [5] or also [10]) was first used along these lines by Beth [1]. Using a modified version he showed that for all first-order systems a certain modeltheoretic notion of definability coincides with a certain proof theoretic notion. In the present paper the Herbrand-Gentzen Theorem will be applied to generalize Beth's results from primitive predicate symbols to arbitrary formulas and terms.This may be interpreted as showing that (apart from some relatively minor exceptions which will be made apparent below) the expressive power of each first-order system is rounded out, or the system is functionally complete, in the following sense: Any functional relationship which obtains between concepts that are expressible in the system is itself expressible and provable in the system.A second application is concerned with the hierarchy of second-order formulas. A certain relationship is shown to hold between first-order formulas and those second-order formulas which are of the form (∃T1)…(∃Tk)A or (T1)…(Tk)A with A being a first-order formula. Modeltheoretically this can be regarded as a relationship between the class AC and the class PC⊿ of sets of models, investigated by Tarski in [12] and [13].
The pure calculus of entailment
Authors: Anderson Alan Ross , Belnap Nuel D. 
Published: May 2006

The “implicational paradoxes” are treated by most contemporary logicians somewhat as follows:“The two-valued prepositional calculus sanctions as valid many of the obvious and satisfactory inferences which we recognize intuitively as valid, such as(A→.B→C)→.A→B→.A→C,2andA→B→.B→C→.A→C;it consequently suggests itself as a candidate for a formal analysis of implication.
On logically false evidence statements
Authors: Leblanc Hugues 
Published: May 2006

Logical falsehoods are usually barred in confirmation theory from serving as evidence statements. I wish to study here some three major ways in which this restriction can be lifted.1. Consider the following axioms for the two-argument confirmation function C:A1. 0 ≤ C(h, e) ≤ 1;A2. If ⊦h ≡ h′ and ⊦e ≡ e′, then C(h, e) = C(h′, e′);A3. If ⊦e ⊃ h, then C(h, e) = 1;A4. If ⊦e ⊃ ˜(h.h′), then C(h⋁h′, e) = C(h, e)+C(h′, e);A5. C(h.h′, e) = C(h,e)×C(h′, h.e);where h, h′, e, and e′ are any four statements from a consistent language L and where ‘⊦’ is short for ‘is logically true in L.’ A1—A5 are consistent, as shown by the following construction:C1. Let all four of h, h′, e, and e′ be some logical truth lt of L, and let C(h, e) equal 1 for any two h and e;under which they become true. But they yield as consequences:and henceNo statement e of L is logically false.Since all the languages for which confirmation theories have been proposed contain logical falsehoods, (1) is undesirable. Restrictions must accordingly be placed upon some of A1—A5.
A remark on free choice sequences and the topological completeness proofs
Authors: Kreisel G. 
Published: May 2006

Below are collected some simple results on the theory of free choice sequences [4] or infinitely proceeding sequences (ips) as they are called in [5]. These results are not sufficient to settle the completeness problems for Heyting's predicate calculus [4], as formulated in [12], neither in the strong nor in the weak sense. They are published because they lead to intuitionistically valid versions of completeness proofs which have appeared in the literature, particularly [16], [17], [18], and, with certain reservations, [1].The problems considered below (except in §8) differ from those of [12] in the following respect: In [12] we were mainly concerned with formulae of Heyting's predicate calculus which were not even classically provable, and showed that the calculus was complete with respect to certain classes of these formulae. The novel feature was that we established this completeness by means of intuitionistically valid methods, in fact methods which can be formalized in Heyting's arithmetic. Here we are primarily concerned with formulae which are classically, but not intuitionistically, provable. As pointed out in [12], the nature of the completeness problem for such formulae is totally different: the class of predicates which provides the required counterexamples must come from a system (with an intuitionistically acceptable interpretation) which, unlike Heyting's arithmetic, is not a subsystem of the corresponding classical system. An example of such a system is an extension FC, given below, of Heyting's formalization of the theory of free choices.
Degrees of formal systems
Authors: Shoenfield J. R. 
Published: May 2006

In this paper we answer some of the questions left open in [2]. We use the terminology of [2]. In particular, a theory will be a formal system formulated within the first-order calculus with identity. A theory is identified with the set of Gödel numbers of the theorems of the theory. Thus Craig's theorem [1] asserts that a theory is axiomatizable if and only if it is recursively enumerable.In [2], Feferman showed that if A is any recursively enumerable set, then there is an axiomatizable theory T having the same degree of unsolvability as A. (This result was proved independently by D. B. Mumford.) We show in Theorem 2 that if A is not recursive, then T may be chosen essentially undecidable. This depends on Theorem 1, which is a result on recursively enumerable sets of some independent interest.Our second result, given in Theorem 3, gives sufficient conditions for a theory to be creative. These conditions are more general than those given by Feferman. In particular, they show that the system of Kreisel described in [2] is creative.