bluuebunny/crossref_metadata_2025_split huggingface dataset:
U-Lusin sets in hyperfinite time lines
Authors: Jin Renling 
Published: May 2006

AbstractIn an ω-saturated nonstandard universe a cut is an initial segment of the hyperintegers which is closed under addition. Keisler and Leth in [KL] introduced, for each given cut U, a corresponding U-topology on the hyperintegers by letting O be U-open if for any x ϵ O there is a y greater than all the elements in U such that the interval [x − y,x + y] ⊆ O. Let U be a cut in a hyperfinite time line , which is a hyperfinite initial segment of the hyperintegers. A subset B of is called a U-Lusin set in if B is uncountable and for any Loeb-Borel U-meager subset X of , B ⋂ X is countable. Here a Loeb-Borel set is an element of the σ-algebra generated by all internal subsets of : In this paper we answer some questions of Keisler and Leth about the existence of U-Lusin sets by proving the following facts. (1) If U = x/N = {y ϵ : ∀n ϵ ℕ(y < x/n)} for some x ϵ , then there exists a U-Lusin set of power κ if and only if there exists a Lusin set of the reals of power κ. (2) If U ≠ x/N but the coinitiality of U is ω, then there are no U-Lusin sets if CH fails. (3) Under ZFC there exists a nonstandard universe in which U-Lusin sets exist for every cut U with uncountable cofinality and coinitiality. (4) In any ω2-saturated nonstandard universe there are no U-Lusin sets for all cuts U except U = x/N.
Relation algebras of every dimension
Authors: Maddux Roger D. 
Published: May 2006

AbstractConjecture (1) of [Ma83] is confirmed here by the following result: if 3 ≤ α < ω, then there is a finite relation algebra of dimension α, which is not a relation algebra of dimension α + 1. A logical consequence of this theorem is that for every finite α ≥ 3 there is a formula of the form S ⊆ T (asserting that one binary relation is included in another), which is provable with α + 1 variables, but not provable with only α variables (using a special sequent calculus designed for deducing properties of binary relations).
On Boolean algebras and integrally closed commutative regular rings
Authors: Nagayama Misao 
Published: May 2006

AbstractIn this paper we consider properties, related to model-completeness, of the theory of integrally closed commutative regular rings. We obtain the main theorem claiming that in a Boolean algebra B, the truth of a prenex Σn-formula whose parameters ai, partition B, can be determined by finitely many conditions built from the first entry of Tarski invariant T(ai)'s, n-characteristic D(n, ai)'s and the quantities S(ai, l) and S′(ai, l) for l < n. Then we derive two important theorems. One claims that for any Boolean algebras A and B, an embedding of A into B preserving D(n, a) for all a ϵ A is a Σn-extension. The other claims that the theory of n-separable Boolean algebras admits elimination of quantifiers in a simple definitional extension of the language of Boolean algebras. Finally we translate these results into the language of commutative regular rings.
On the Schur-Zassenhaus theorem for groups of finite Morley rank
Authors: Borovik Alexandre V. , Nesin Ali 
Published: May 2006

The Schur-Zassenhaus Theorem is one of the fundamental theorems of finite group theory. Here is its statement:Fact1.1 (Schur-Zassenhaus Theorem). Let G be a finite group and let N be a normal subgroup of G. Assume that the order ∣N∣ is relatively prime to the index [G:N]. Then N has a complement in G and any two complements of N are conjugate in G.The proof can be found in most standard books in group theory, e.g., in [S, Chapter 2, Theorem 8.10]. The original statement stipulated one ofNorG/Nto be solvable. Since then, the Feit-Thompson theorem [FT] has been proved and it forces eitherNorG/Nto be solvable. (The analogous Feit-Thompson theorem for groups of finite Morley rank is a long standing open problem).The literal translation of the Schur-Zassenhaus theorem to the finite Morley rank context would state that in a groupGof finite Morley rank a normal π-Hall subgroup (if it exists at all) has a complement and all the complements are conjugate to each other. (Recall that a groupHis called aπ-group, where π is a set of prime numbers, if elements ofHhave finite orders whose prime divisors are from π. Maximal π-subgroups of a groupGare called π-Hall subgroups. They exist by Zorn's lemma. Since a normal π-subgroup ofGis in all the π-Hall subgroups, if a group has a normal π-Hall subgroup then this subgroup is unique.)The second assertion of the Schur-Zassenhaus theorem about the conjugacy of complements is false in general. As a counterexample, consider the multiplicative group ℂ* of the complex number field ℂ and consider thep-Sylow for any primep, or even the torsion part of ℂ*. LetHbe this subgroup.Hhas a complement, but this complement is found by Zorn's Lemma (consider a maximal subgroup that intersectsHtrivially) and the use of Zorn's Lemma is essential. In fact, by Zorn's Lemma, any subgroup that has a trivial intersection withHcan be extended to a complement ofH. Since ℂ* is abelian, these complements cannot be conjugated to each other.
Precipitous towers of normal filters
Authors: Burke Douglas R. 
Published: May 2006

In this paper we investigate towers of normal filters. These towers were first used by Woodin (see [15]). Woodin proved that if δ is a Woodin cardinal and P is the full stationary tower up to δ (P<δ) or the countable version (Q<δ), then the generic ultrapower is closed under < δ sequences (so the generic ultrapower is well-founded) ([14]). We show that if ℙ is a tower of height δ, δ supercompact, and the filters generating ℙ are the club filter restricted to a stationary set, then the generic ultrapower is well-founded (ℙ is precipitous). We also give some examples of non-precipitous towers. We also show that every normal filter can be extended to a V-ultrafilter with well-founded ultrapower in some generic extension of V (assuming large cardinals). Similarly for any tower of inaccessible height. This is accomplished by showing that there is a stationary set that projects to the filter or the tower and then forcing with P<δ below this stationary set.An important idea in our proof of precipitousness (Theorem 6.4) has the following form in Woodin's proof. If are maximal antichains (i Є ω and δ Woodin) then there is a κ < δ such that each Ai ∩ Vκ is semiproper, i.e.,contains a club (relative to ∣ a∣ < κ).
Two remarks on the Lifschitz realizability topos
Authors: Oosten Jaap Van 
Published: May 2006

The purpose of this note is to clarify two points about the topos Lif, introduced in [13] as a generalization of Lifschitz' realizability ([9, 12]). Lif is a subtopos of Hyland's Effective topos ([1]). The points I want to make are:Remark 1. Lif is the largest subtopos of satisfying the axiom (O):where denotes partial recursive application, and “∈ Tot” means that e and f range over codes for total recursive functions. One may read (O) as the statement “The union of two -sets is again a -set”. That is, let be a subtopos of . Then (O) is true in for the standard interpretation (the variables range over the natural numbers object of , etc.) if and only if the inclusion ↣ factors through the inclusion Lif ↣ .Remark 2. Like , Lif contains at least two weakly complete internal full subcategories, thus providing us with more models of polymorphism and other impredicative type theories.The principle (O) has some standing in the history of constructive mathematics:- H. Friedman has proved that (O) is equivalent to a formulation of intuitionistic completeness of the intuitionistic predicate calculus for Tarskian semantics; see [8]. This is not to imply that this result is of immediate relevance to Lif: Friedman works in a system of analysis, a theory of lawless sequences with an axiom of “open data” for arithmetical formulas, which at least for the domain of all functions from N to N fails in Lif. However, there might exist a “nonstandard model” of arithmetic and a corresponding system of analysis, in which we may be able to carry out his proof.- Moreover, Remark 2 entails that Lif should provide us with models of synthetic domain theory (for an exposition, see [3]), and one with the nice property that the dual of one of the axioms (axiom 7 in [3]) comes for free, by (O).
Fluted formulas and the limits of decidability
Authors: Purdy William C. 
Published: May 2006

AbstractIn the predicate calculus, variables provide a flexible indexing service which selects the actual arguments to a predicate letter from among possible arguments that precede the predicate letter (in the parse of the formula). In the process of selection, the possible arguments can be permuted, repeated (used more than once), and skipped. If this service is withheld, so that arguments must be the immediately preceding ones, taken in the order in which they occur, the formula is said to be fluted. Quine showed that if a fluted formula contains only homogeneous conjunction (conjoins only subformulas of equal arity), then the satisfiability of the formula is decidable. It remained an open question whether the satisfiability of a fluted formula without this restriction is decidable. This paper answers that question.
Ultrafilters generated by a closed set of functions
Authors: Bishop Greg 
Published: May 2006

AbstractLet κ and λ be infinite cardinals, a filter on κ and a set of functions from κ to κ. The filter is generated by if consists of those subsets of κ which contain the range of some element of . The set is <λ-closed if it is closed in the <λ-topology on κκ. (In general, the <λ-topology on IA has basic open sets all such that, for all i ∈ I, Ui ⊆ A and ∣{i ∈ I: Ui ≠ A} ∣<λ.) The primary question considered in this paper asks “Is there a uniform ultrafilter on κ which is generated by a closed set of functions?” (Closed means <ω-closed.) We also establish the independence of two related questions. One is due to Carlson: “Does there exist a regular cardinal κ and a subtree T of <κκ such that the set of branches of T generates a uniform ultrafilter on κ?”; and the other is due to Pouzet: “For all regular cardinals κ, is it true that no uniform ultrafilter on κ is it true that no uniform ultrafilter on κ analytic?”We show that if κ is a singular, strong limit cardinal, then there is a uniform ultrafilter on κ which is generated by a closed set of increasing functions. Also, from the consistency of an almost huge cardinal, we get the consistency of CH + “There is a uniform ultrafilter on ℵ1 which is generated by a closed set of increasing functions”. In contrast with the above results, we show that if Κ is any cardinal, λ is a regular cardinal less than or equal to κ and ℙ is the forcing notion for adding at least (κ<λ)+ generic subsets of λ, then in VP, no uniform ultrafilter on κ is generated by a closed set of functions.
Comparing notions of similarity for uncountable models
Authors: Huuskonen Taneli 
Published: May 2006

AbstractThe present article, which is a revised version of part of [Hu1], deals with various relations between models which might serve as exact formulations for the vague concept “similar” or “almost isomorphic”. One natural class of such formulations is equivalence in a given logic. Another way to express similarity is by potential isomorphism, i.e., isomorphism in some extension of the set-theoretic universe. The class of extensions may be restricted to give different notions of potential isomorphism. A third method is to study the winning strategies for an Ehrenfeucht-Fraïssé-game played between the two models, and the properties of the resulting equivalence and nonequivalence trees.The basic question studied here is whether one such notion of similarity implies another. Some implications and counterexamples listed in this part are previously known or trivial, but all are mentioned for completeness' sake. Only models of cardinality ℵ1 are considered. Some results are therefore connected with the Continuum Hypothesis.
Jensen's Σ* theory and the combinatorial content of V = L
Authors: Friedman Sy D. 
Published: May 2006

An awkward feature of the standard fine structure theory of the Jα's (see Jensen [72]) is that special parameters are required to make good sense of the notion of “Σn Skolem hull”, parameters which may not be preserved in condensation arguments.The purpose of this article is to indicate how a reformulation of Jensen's Σ* theory (developed for the study of core models) can be used to provide a more satisfactory treatment of uniformization, hulls, and Skolem functions for the Jα's. Then we use this approach to fine structure to formulate a principle intended to capture the combinatorial content of the axiom V = L.
The liar paradox and fuzzy logic
Authors: Hájek Petr , Paris Jeff , Shepherdson John 
Published: May 2006

AbstractCan one extend crisp Peano arithmetic PA by a possibly many-valued predicate Tr(x) saying “xis true” and satisfying the “dequotation schema”for all sentences φ? This problem is investigated in the frame of Łukasiewicz infinitely valued logic.
A free pseudospace
Authors: Baudisch Andreas , Pillay Anand 
Published: May 2006

In this paper we construct a non-CM-trivial stable theory in which no infinite field is interpretable. In fact our theory will also be trivial and ω-stable, but of infinite Morley rank. A long term aim would be to find a nonCM-trivial theory which has finite Morley rank (or is even strongly minimal) and does not interpret a field. The construction in this paper is direct, and is a “3-dimensional” version of the free pseudoplane. In a sense we are cheating: the original point of the notion ofCM-triviality was to describe the geometry of a strongly minimal set, or even of a regular type. In our example, non-CM-triviality will come from the behaviour of three orthogonal regular types.A stable theory is said to beCM-trivial if wheneverA⊆Band acl(Ac) ∩ acl(B) = acl(A) inTeq, then Cb(stp(c/A)) ⊆ Cb(stp(c/B)). ( An infinite stable field will not beCM-trivial.) The notion is due to Hrushovski [3], where he gave several equivalent definitions, as well as showing that his new strongly minimal sets constructed “ab ovo” wereCM-trivial. The notion was studied further in [6] where it was shown thatCM-trivial groups of finite Morley rank are nilpotent-by-finite. These results were generalized in various ways to the superstable case in [8].
Liftez les sylows! Une suite à “Sous-groupes périodiques d'un groupe stable”
Authors: Poizat Bruno , Wagner Frank O. 
Published: May 2006

AbstractIfGis an omega-stable group with a normal definable subgroupH, then the Sylow-2-subgroupsG/Hare the images of the Sylow-2-subgroups ofG.Zusammenfassung.SeiGeine omega-stabile Gruppe undHein definierbarer Normalteiler vonG. Dann sind die Sylow-2-Untergruppen von G/H Bilder der Sylow-2-Untergruppen vonG.
Filtral powers of structures
Authors: Ouwehand P. , Rose H. 
Published: May 2006

AbstractAmong the results of this paper are the following:1. Every Boolean (ultra)power is the union of an updirected elementary family of direct ultrapowers.2. Under certain conditions, a finitely iterated Boolean ultrapower is isomorphic to a single Boolean ultrapower.3. A ω-bounded filtral power is an elementary substructure of a filtral power.4. Let be an elementary class closed under updirected unions (e.g., if is an amalgamation class); then is closed under finite products if and only if is closed under reduced products if and only if is a Horn class.
The complexity of the core model
Authors: Mitchell William J. 
Published: May 2006

AbstractIf there is no inner model with a cardinal κ such that ο(κ) = κ++ then the set K ∩ Hω1 is definable over Hω1 by a Δ4 formula, and the set of countable initial segments of the core model is definable over Hω1 by a Π3 formula. We show that if there is an inner model with infinitely many measurable cardinals then there is a model in which is not definable Σ3 by any Σ3 formula, and K ∩ Hω1 is not definable by any boolean combination of Σ3 formulas.
Definability and definable groups in simple theories
Authors: Pillay Anand 
Published: May 2006

AbstractWe continue the study of simple theories begun in [3] and [5]. We first find the right analogue of definability of types. We then develop the theory of generic types and stabilizers for groups definable in simple theories. The general ideology is that the role of formulas (or definability) in stable theories is replaced by partial types (or ∞-definability) in simple theories.
Automorphisms moving all non-algebraic points and an application to NF
Authors: Körner Friederike 
Published: May 2006

AbstractSection 1 is devoted to the study of countable recursively saturated models with an automorphism moving every non-algebraic point. We show that every countable theory has such a model and exhibit necessary and sufficient conditions for the existence of automorphisms moving all non-algebraic points. Furthermore we show that there are many complete theories with the property that every countable recursively saturated model has such an automorphism.In Section 2 we apply our main theorem from Section 1 to models of Quine's set theory New Foundations (NF) to answer an old consistency question. If NF is consistent, then it has a model in which the standard natural numbers are a definable subclass ℕ of the model's set of internal natural numbers Nn. In addition, in this model the class of wellfounded sets is exactly.
Witnessing functions in bounded arithmetic and search problems
Authors: Chiari Mario , Krajíček Jan 
Published: May 2006

AbstractWe investigate the possibility to characterize (multi)functions that are-definable with smalli(i= 1, 2, 3) in fragments of bounded arithmeticT2in terms of natural search problems defined over polynomial-time structures. We obtain the following results:(1) A reformulation of known characterizations of (multi)functions that areand-definable in the theoriesand.(2) New characterizations of (multi)functions that areand-definable in the theory.(3) A new non-conservation result: the theoryis not-conservative over the theory.To prove that the theoryis not-conservative over the theory, we present two examples of a-principle separating the two theories:(a) the weak pigeonhole principle WPHP(a2,f, g) formalizing that no functionfis a bijection betweena2andawith the inverseg,(b) the iteration principle Iter(a, R, f) formalizing that no functionfdefined on a strict partial order ({0,…, a},R) can have increasing iterates.
Changing cardinal invariants of the reals without changing cardinals or the reals
Authors: Mildenberger Heike 
Published: May 2006

AbstractWe show: The procedure mentioned in the title is often impossible. It requires at least an inner model with a measurable cardinal. The consistency strength of changingandfrom a regularκto some regularδ<κis a measurable of Mitchell orderδ. There is an application to Cichoń's diagram.
Relational semantics and a relational proof system for full Lambek calculus
Authors: MacCaull Wendy 
Published: May 2006

AbstractIn this paper we give relational semantics and an accompanying relational proof theory for full Lambek calculus (a sequent calculus which we denote by FL). We start with the Kripke semantics for FL as discussed in [11] and develop a second Kripke-style semantics, RelKripke semantics, as a bridge to relational semantics. The RelKripke semantics consists of a set with two distinguished elements, two ternary relations and a list of conditions on the relations. It is accompanied by a Kripke-style valuation system analogous to that in [11]. Soundness and completeness theorems with respect to FL hold for RelKripke models. Then, in the spirit of the work of Orlowska [14], [15], and Buszkowski and Orlowska [3], we develop relational logic RFL. The adjective relational is used to emphasize the fact that RFL has a semantics wherein formulas are interpreted as relations. We prove that a sequent Γ → α in FL is provable if and only if a translation,t(γ1● … ● γn⊃ α)ευu, has a cut-complete fundamental proof tree. This result isconstructive: that is, if a cut-complete proof tree fort(γ1● … ● γn⊃ α)ευuis not fundamental, we can use the failed proof search to build a relational countermodel fort(γ1● … ● γn⊃ α)ευuand from this, build a RelKripke countermodel for γ1● … ● γn⊃ α. These results allow us to add FL, the basic substructural logic, to the list of those logics of importance in computer science with a relational proof theory.
An absoluteness principle for Borel sets
Authors: Hjorth Greg 
Published: May 2006

The purpose of these notes is to describe an absoluteness principle due to Jacques Stern and discuss some applications to the general study of Borel sets. This paper will not be engaged in independence results, but in proving outright theorems about the Borel hierarchy.Roughly speaking, Stern's absoluteness principle states that if a certain set can be introduced into the universe by forcing, then it can be introduced by some small forcing notion.The notation , and so on, will be defined in Section 1; this gives a notational system for describing the complexity of Borel sets beyond Fσ or Gδ. The “universe” refers to the totality of all sets. “Forcing” refers to Paul Cohen's technique for, in some sense, changing this totality by the introduction of new sets. Here “small” means relatively small cardinality.The size of this small forcing notion is roughly the ath iteration of the power set operation. Just to get an idea of what this theorem might be saying, we can argue that under certain conditions, if a closed set can be introduced by forcing, then it exists already. There are a number of other qualifications that need to be made to this rough description, and we will come to them later.Unlike, say, Shoenfield absoluteness, Stern's absoluteness can only be made understood in the terminology of forcing. Since forcing is typically associated with the pursuit of independence results, we could easily assume that Stern's work has little relevance in proving positive theorems about the Borel hierarchy.However, this would be untrue. Using abstract and indirect metamathematical arguments, and availing ourselves of Stern's absoluteness principle, we will prove a string of ZFC theorems for which no direct proof is known.
Frege proof system and TNC°
Authors: Takeuti Gaisi 
Published: May 2006

A Frege proof systemFis any standard system of prepositional calculus, e.g., a Hilbert style system based on finitely many axiom schemes and inference rules. An Extended Frege systemEFis obtained fromFas follows. AnEF-sequence is a sequence of formulas ψ1, …, ψκsuch that eachψiis either an axiom ofF, inferred from previous ψuand ψv(= ψu→ ψi) by modus ponens or of the formq↔ φ, whereqis an atom occurring neither in φ nor in any of ψ1,…,ψi−1. Suchq↔ φ, is called an extension axiom andqa new extension atom. AnEF-proof is anyEF-sequence whose last formula does not contain any extension atom. In [12], S. A. Cook and R. Reckhow proved that the pigeonhole principlePHPhas a simple polynomial sizeEF-proof and conjectured thatPHPdoes not admit polynomial sizeF-proof. In [5], S. R. Buss refuted this conjecture by furnishing polynomial sizeF-proof forPHP. Since then the important separation problem of polynomial sizeFand polynomial sizeEFhas not shown any progress.In [11], S. A. Cook introduced the systemPV, a free variable equational logic whose provable functional equalities are ‘polynomial time verifiable’ and showed that the metamathematics ofFandEFcan be developed inPVand the soundness ofEFproved inPV. In [3], S. R. Buss introduced the first order systemand showed thatis essentially a conservative extension ofPV. There he also introduced a second order system(BD).
Wadge hierarchy and Veblen hierarchy Part I: Borel sets of finite rank
Authors: Duparc J. 
Published: May 2006

AbstractWe consider Borel sets of finite rank A ⊆ ∧ω where cardinality of Λ is less than some uncountable regular cardinal . We obtain a “normal form” of A, by finding a Borel set Ω, such that A and Ω continuously reduce to each other. In more technical terms: we define simple Borel operations which are homomorphic to ordinal sum, to multiplication by a countable ordinal, and to ordinal exponentiation of base , under the map which sends every Borel set A of finite rank to its Wadge degree.