bluuebunny/crossref_metadata_2025_split huggingface dataset:
Set theoretic properties of Loeb measure
Authors: Miller Arnold W. 
Published: May 2006

AbstractIn this paper we ask the question: to what extent do basic set theoretic properties of Loeb measure depend on the nonstandard universe and on properties of the model of set theory in which it lies? We show that, assuming Martin's axiom and κ-saturation, the smallest cover by Loeb measure zero sets must have cardinality less than κ. In contrast to this we show that the additivity of Loeb measure cannot be greater than ω1. Define cof(H) as the smallest cardinality of a family of Loeb measure zero sets which cover every other Loeb measure zero set. We show that card(⌊log2(H)⌋) ≤ cof (H) ≤ card(2H), where card is the external cardinality. We answer a question of Paris and Mills concerning cuts in nonstandard models of number theory. We also present a pair of nonstandard universes M ≼ N and hyperfinite integer H ∈ M such that H is not enlarged by N, 2H contains new elements, but every new subset of H has Loeb measure zero. We show that it is consistent that there exists a Sierpiński set in the reals but no Loeb-Sierpiński set in any nonstandard universe. We also show that it is consistent with the failure of the continuum hypothesis that Loeb-Sierpiński sets can exist in some nonstandard universes and even in an ultrapower of a standard universe.
On topological spaces equivalent to ordinals
Authors: Flum Jörg , Martinez Juan Carlos 
Published: May 2006

AbstractLet L be one of the topological languages Lt, (L∞ω)t and (Lκω)t. We characterize the topological spaces which are models of the L-theory of the class of ordinals equipped with the order topology. The results show that the role played in classical model theory by the property of being well-ordered is taken over in the topological context by the property of being locally compact and scattered.
The independence of Peano's fourth axiom from Martin-Löf's type theory without universes
Authors: Smith Jan M. 
Published: May 2006

In Hilbert and Ackermann [2] there is a simple proof of the consistency of first order predicate logic by reducing it to propositional logic. Intuitively, the proof is based on interpreting predicate logic in a domain with only one element. Tarski [7] and Gentzen [1] have extended this method to simple type theory by starting with an individual domain consisting of a single element and then interpreting a higher type by the set of truth valued functions on the previous type.I will use the method of Hilbert and Ackermann on Martin-Löf's type theory without universes to show that ¬Eq(A, a, b) cannot be derived without universes for any type A and any objects a and b of type A. In particular, this proves the conjecture in Martin-Löf [5] that Peano's fourth axiom (∀x ϵ N)¬ Eq(N, 0, succ(x)) cannot be proved in type theory without universes. If by consistency we mean that there is no closed term of the empty type, then the construction will also give a consistency proof by finitary methods of Martin-Löf's type theory without universes. So, without universes, the logic obtained by interpreting propositions as types is surprisingly weak. This is in sharp contrast with type theory as a computational system, since, for instance, the proof that every object of a type can be computed to normal form cannot be formalized in first order arithmetic.
Isomorphic but not lower base-isomorphic cylindric set algebras
Authors: Biró B. , Shelah S. 
Published: May 2006

AbstractThis paper belongs to cylindric-algebraic model theory understood in the sense of algebraic logic. We show the existence of isomorphic but not lower base-isomorphic cylindric set algebras. These algebras are regular and locally finite. This solves a problem raised in [N 83] which was implicitly present also in [HMTAN 81]. This result implies that a theorem of Vaught for prime models of countable languages does not continue to hold for languages of any greater power.
On the transversal hypothesis and the weak kurepa hypothesis
Authors: Walker D. J. 
Published: May 2006

In this paper the theory of the core model K is applied to study certain combinatorial principles. These principles concern the existence of families of almost disjoint functions. The first, the transversal hypothesis, is defined as follows.Definition. The transversal hypothesis for κ, T(κ), is the following assertion:There is a sequence 〈fν: ν < κ+〉 such that(a) fν: κ → κ regressively for ν < κ+, and(b) if ν < ξ < κ+, then there is γ < κ such that fν(α) ≠ fξ(α) whenever γ < α < κ.T(κ) is a simple consequence of the Kurepa hypothesis for κ, i.e. the assertion, KH(κ), that there is a family F ⊂ P(κ) such that and card({X ∩ α: X ϵ F}) ≤ α for ω < α < κ.The second principle to be studied, the weak Kurepa hypothesis, is a statement of strength intermediate between the Kurepa and transversal hypotheses.Definition. The weak Kurepa hypothesis for κ, wKH(κ), is the following assertion:There is a sequence 〈bν: ν < κ+〉 such that(a) bν ⊂ κ for ν < κ+, and(b) for each limit λ < κ there is Fλ: {bν ∩ λ: ν < κ+} → λ such that setting fν(λ) = Fλ(bν ∩ λ) for ν < κ+ and limit λ < κ, if ν < ξ < κ+ there is γ < κ such that fν(λ) ≠ fξ(λ) whenever γ < λ < κ and λ is a limit.
Jump embeddings in the Turing degrees
Authors: Hinman Peter G. , Slaman Theodore A. 
Published: May 2006

Since its introduction in [K1-Po], the upper semilattice of Turing degrees has been an object of fascination to practitioners of the recursion-theoretic art. Starting from relatively simple concepts and definitions, it has turned out to be a structure of enormous complexity and richness. This paper is a contribution to the ongoing study of this structure.Much of the work on Turing degrees may be formulated in terms of the embeddability of certain first-order structures in a structure whose universe is some set of degrees and whose relations, functions, and constants are natural degree-theoretic ones. Thus, for example, we know that if {P, ≤P) is a partial ordering of cardinality at most ℵ1 which is locally countable—each point has at most countably many predecessors—then there is an embeddingwhere D is the set of all Turing degrees and <T is Turing reducibility. If (P, ≤P) is a countable partial ordering, then the image of the embedding may be taken to be a subset of R, the set of recursively enumerable degrees. Without attempting to make the notion completely precise, we shall call embeddings of the first sort global, in contrast to local embeddings which impose some restrictions on the image set.
A universal inductive inference machine
Authors: Osherson Daniel N. , Stob Michael , Weinstein Scott 
Published: May 2006

AbstractA paradigm of scientific discovery is defined within a first-order logical framework. It is shown that within this paradigm there exists a formal scientist that is Turing computable and universal in the sense that it solves every problem that any scientist can solve. It is also shown that universal scientists exist for no regular logics that extend first-order logic and satisfy the Löwenheim-Skolem condition.
A note on subgroups of the automorphism group of a saturated model, and regular types
Authors: Pillay A. 
Published: May 2006

AbstractLet M be a saturated model of a superstable theory and let G = Aut(M). We study subgroups H of G which contain G(A), A the algebraic closure of a finite set, generalizing results of Lascar [L] as well as giving an alternative characterization of the simple superstable theories of [P]. We also make some observations about good, locally modular regular types p in the context of p-simple types.
A note on direct sums of Friedbergnumberings
Authors: Kummer Martin 
Published: May 2006

We show that a translator ƒ: ω → ω from a Gödelnumbering φ into a direct sum η of a r.e. family of Friedbergnumberings satisfies ƒ ≰T0′. In particular, η cannot be a Gödelnumbering.In the following we use standard notation (cf.[3]): for i ≥ 1, Pi (respectively, Ri) is the set of partial (total) recursive i-place functions; φ is a Gödel numbering of P1. By φi, s we denote a recursive standard approximation for φi, i.e., φi, s is a finite function, φi, s ⊆ φi, s + 1, φi, s ⊆ φi, φi = ⋃ {φi, s ∣ s ≥ 0}, and a canonical index for φi, s can be computed uniformly in i, s (cf.[3, p. 16 f]).We call v ∈ P2 a numbering of P1 iff {λx.v(i, x)}i ∈ ω = P1; we denote λx.v(i, x) by vi. Let v and γ be numberings of P1. A total function g: ω → ω is called a translator from v into γ iff ∀i: vi = γg(i).
Equational logic of partial functions under Kleene equality: a complete and an incomplete set of rules
Authors: Robinson Anthony 
Published: May 2006

When equational logic for partial functions is interpreted using Kleene equality as the predicate, the relation of logical consequence may be said to express what identities of partial functions follow from a given set of identities. In the analogous situation for total functions, there is a complete set of inference rules consisting of reflexivity, symmetry, transitivity, replacement, and substitution; in the case of partial functions, unrestricted substitution fails to be a valid inference rule, and there remains the question of how to obtain a complete set of rules. The first part of the present paper shows that completeness cannot be obtained by a mere restriction of the substitution rule, for a counterexample shows that even a rule allowing substitution in all consequentially valid instances fails, in conjunction with the other four rules, to yield a complete set of rules.The second part of the paper defines a combined rule of transitivity-substitution which, in conjunction with reflexivity, symmetry, replacement, and substitution only of variables, yields a complete set of rules. The new rule is first stated in a form that allows an unbounded number of premises, and then is altered to a three-premise form. In both forms, the rule suffers from the shortcoming that in its formulation an auxiliary notion of conditional existence is involved, which is given by a recursive syntactic definition. As a result, the set of instantiations of the rule is recursively enumerable, but not (apparently) recursive (assuming a recursive set of premises).
Partially ordered sets and the independence property
Authors: Schmerl James H. 
Published: May 2006

AbstractNo theory of a partially ordered set of finite width has the independence property, generalizing Poizat's corresponding result for linearly ordered sets. In fact, a question of Poizat concerning linearly ordered sets is answered by showing, moreover, that no theory of a partially ordered set of finite width has the multi-order property. It then follows that a distributive lattice is not finite-dimensional iff its theory has the independence property iff its theory has the multi-order property.
Higher order reflection principles
Authors: Marshall R. M. Victoria 
Published: May 2006

In [1] and [2] there is a development of a class theory, whose axioms were formulated by Bernays and based on a reflection principle. See [3]. These axioms are formulated in first order logic with ∈:(A1)Extensionality.(A2)Class specification. Ifϕis a formula andAis not free inϕ, thenNote that “xis a set“ can be written as “∃u(x∈u)”.(A3)Subsets.Note also that “B⊆A” can be written as “∀x(x∈B→x∈A)”.(A4)Reflection principle. Ifϕ(x)is a formula, thenwhere “uis a transitive set” is the formula “∃v(u∈v) ∧ ∀x∀y(x∈y∧y∈u→x∈u)” andϕPuis the formulaϕrelativized to subsets ofu.(A5)Foundation.(A6)Choice for sets.We denote byB1the theory with axioms (A1) to (A6).The existence of weakly compact and-indescribable cardinals for everynis established inB1by the method of defining all metamathematical concepts forB1in a weaker theory of classes where the natural numbers can be defined and using the reflection principle to reflect the satisfaction relation; see [1]. There is a proof of the consistency ofB1assuming the existence of a measurable cardinal; see [4] and [5]. In [6] several set and class theories with reflection principles are developed. In them, the existence of inaccessible cardinals and some kinds of indescribable cardinals can be proved; and also there is a generalization of indescribability for higher-order languages using only class parameters.The purpose of this work is to develop higher order reflection principles, including higher order parameters, in order to obtain other large cardinals.
U-meager sets when the cofinality and the coinitiality of U are uncountable
Authors: Živaljević Boško 
Published: May 2006

AbtractWe prove that every countably determined set C is U-meager if and only if every internal subset A of C is U-meager, provided that the cofinality and coinitiality of the cut U are both uncountable. As a consequence we prove that for such cuts a countably determined set C which intersects every U-monad in at most countably many points is U-meager. That complements a similar result in [KL]. We also give some partial solutions to some open problems from [KL]. We prove that the set , where H is an infinite integer, cannot be expressed as a countable union of countably determined sets each of which is U-meager for some cut U with min{cf(U), ci(U)} ≥ ω1. Also, every Borel, or countably determined set C which is U-meager for every cut U is a countable union of Borel, or countably determined sets respectively, which are U-nowhere dense for every cut U. Further, the class of Borel U-meager sets for min{cf(U),ci(U)} ≥ ω1 coincides with the least family of sets containing internal U-meager sets and closed with respect to the operation of countable union and intersection. The same is true if the phrase “U-meager sets” is replaced by “U-meager for every cut U.”
Working below a high recursively enumerable degree
Authors: Shore Richard A. , Slaman Theodore A. 
Published: May 2006

In recent work, Cooper [3, 1990] has extended results of Jockusch and Shore [6, 1984] to show that the Turing jump is definable in the structure given by the Turing degrees and the ordering of Turing reducibility. In his definition of x′ from x, Cooper identifies an order-theoretic property shared by all of the degrees that are recursively enumerable in x and above x. He then shows that x′ is the least upper bound of all the degrees with this property. Thus, the jump of x is identified by comparing the recursively enumerable degrees with other degrees which are not recursively enumerable. Of course, once the jump operator is known to be definable, the relation of jump equivalence x′ = y′ is also known to be a definable relation on x and y. If we consider how much of the global theory of the Turing degrees is sufficient for Cooper's methods, it is immediately clear that his methods can be implemented to show that the jump operator and its weakening to the relation of jump equivalence are definable in any ideal closed under the Turing jump. However, his methods do not localize to , the degrees, or to the recursively enumerable degrees.This paper fits, as do Shore and Slaman [16, 1990] and [17, to appear], within the general project to develop an understanding of the relationship between the local degree-theoretic properties of a recursively enumerable set A and its jump class. For an analysis of the possibility of defining jump equivalence in , consult Shore [15, to appear] who shows that the relation x(3) = y(3) is definable. In this paper, we will restrict our attention to definitions expressed completely in ℛ (Note: All sets and degrees discussed for the remainder of this paper will be recursively enumerable.) Ultimately, one would like to find some degree-theoretic properties definable in terms of the ordering of Turing reducibility and quantifiers over the recursively enumerable degrees that would define the relation of jump equivalence or define one or more of the jump classes Hn = {w∣ wn = 0n+1} or Ln = {w ∣ wn = 0n}. Such a result could very likely then be used as a springboard to other general definability results for the recursively enumerable degrees. It would be especially interesting to know whether every recursively enumerable degree is definable and whether every arithmetical degree-invariant property of the recursively enumerable sets is definable in .
A transfer theorem for Henselian valued and ordered fields
Authors: Farré Rafel 
Published: May 2006

AbstractIn well-known papers ([A-K1], [A-K2], and [E]) J. Ax, S. Kochen, and J. Ershov prove a transfer theorem for henselian valued fields. Here we prove an analogue for henselian valued and ordered fields. The orders for which this result apply are the usual orders and also the higher level orders introduced by E. Becker in [Bl] and [B2]. With certain restrictions, two henselian valued and ordered fields are elementarily equivalent if and only if their value groups (with a little bit more structure) and their residually ordered residue fields (a henselian valued and ordered field induces in a natural way an order in its residue field) are elementarily equivalent. Similar results are proved for elementary embeddings and ∀-extensions (extensions where the structure is existentially closed).
The undecidability of the disjunction property of propositional logics and other related problems
Authors: Chagrov Alexander , Zakharyaschev Michael 
Published: May 2006

‘How can we recognize, given axioms and inference rules of a calculus, whether the calculus has such-and-such property?’ A question of this kind arises whenever we deal with a new logic system. For large families of logics, this question may be considered as an algorithmic problem, and a property is called decidable in a given family if there exists an algorithm which is capable of deciding, for a finite axiomatics of a calculus in the family, whether or not it has the property.In the class of intermediate propositional logics, for instance, nontrivial properties such as the tabularity, pretabularity, and interpolation property (Maksimova [1972, 1977]) are decidable. However, for many other important properties—decidability, finite model property, disjunction property, Halldén-completeness, etc.—effective criteria were not found in spite of considerable efforts.In this paper we show that the difficulties in investigating these properties in the classes of intermediate logics and normal modal logics containing S4 are of principal nature, since all of them turn out to be algorithmically undecidable. In other words, there are no algorithms which, given a finite set of axioms of an intermediate or modal calculus, can recognize whether or not it is decidable, Halldén-complete, has the finite model or disjunction property.The first results concerning the undecidability of properties of calculi seem to have been obtained by Linial and Post [1949], who proved the undecidability of the problem of equivalence to classical calculus in the class of all propositional calculi with the same language as the classical one and the two inference rules: modus ponens and substitution. Kuznetsov [1963] generalized this result having proved the undecidability of the problem of equivalence to any fixed intermediate calculus (for instance, to intuitionistic calculus or even the inconsistent one). However, these results will not hold if we confine ourselves only to the class of intermediate logics, though the problem of equivalence to the undecidable intermediate calculus of Shehtman [1978] is clearly undecidable in this class as well.
Nonisomorphism of lattices of recursively enumerable sets
Authors: Hammond John Todd 
Published: May 2006

Let ω be the set of natural numbers, let be the lattice of recursively enumerable subsets of ω, and let A be the lattice of subsets of ω which are recursively enumerable in A. If U, V ⊆ ω, put U =* V if the symmetric difference of U and V is finite.A natural and interesting question is then to discover what the relation is between the Turing degree of A and the isomorphism class of A. The first result of this form was by Lachlan, who proved [6] that there is a set A ⊆ ω such that A ≇ . He did this by finding a set A ⊆ ω and a set C ϵ A such that the structure ({W ϵ A∣W ⊇ C},∪,∩)/=* is a Boolean algebra and is not isomorphic to the structure ({W ϵ ∣W ⊇ D},∪,∩)/=* for any D ϵ . There is a nonrecursive ordinal which is recursive in the set A which he constructs, so his set A is not (see, for example, Shoenfield [11] for a definition of what it means for a set A ⊆ ω to be ). Feiner then improved this result substantially by proving [1] that for any B ⊆ ω, B′ ≇ B, where B′ is the Turing jump of B. To do this, he showed that for each X ⊆= ω there is a Boolean algebra which is but not and then applied a theorem of Lachlan [6] (definitions of and Boolean algebras will be given in §2). Feiner's result is of particular interest for the case B = ⊘, for it shows that the set A of Lachlan can actually be chosen to be arithmetical (in fact, ⊘′), answering a question that Lachlan posed in his paper. Little else has been known.
A recursion principle for linear orderings
Authors: Oikkonen Juha 
Published: May 2006

AbstractThe idea of this paper is to approach linear orderings as generalized ordinals and to study how they are made from their initial segments. First we look at how the equality of two linear orderings can be expressed in terms of equality of their initial segments. Then we shall use similar methods to define functions by recursion with respect to the initial segment relation. Our method is based on the use of a game where smaller and smaller initial segments of linear orderings are considered. The length of the game is assumed to exceed that of the descending sequences of elements of the linear orderings considered. By use of such game-theoretical methods we can for example extend the recursive definitions of the operations of sum, product and exponentiation of ordinals in a unique and natural way for arbitrary linear orderings. Extensions coming from direct limits do not satisfy our game-theoretic requirements in general. We also show how our recursive definitions allow very simple constructions for fixed points of functions, giving rise to certain interesting linear orderings.
On the strength of König's duality theorem for countable bipartite graphs
Authors: Simpson Stephen G. 
Published: May 2006

AbstractLet CKDT be the assertion that for every countably infinite bipartite graph G, there exist a vertex covering C of G and a matching M in G such that C consists of exactly one vertex from each edge in M. (This is a theorem of Podewski and Stefifens [12].) Let ATR0 be the subsystem of second-order arithmetic with arithmetical transfinite recursion and restricted induction. Let RCA0 be the subsystem of second-order arithmetic with recursive comprehension and restricted induction. We show that CKDT is provable in ATR0. Combining this with a result of Aharoni, Magidor, and Shore [2], we see that CKDT is logically equivalent to the axioms of ATR0, the equivalence being provable in RCA0.