bluuebunny/crossref_metadata_2025_split huggingface dataset:
Weak partition relations and measurability
Authors: Spector Mitchell 
Published: May 2006

The concept of "partition relation" has proven to be extremely important in the development of the theory of large cardinals. This is due in good part to the fact that the ordinal numbers which appear as parameters in partition relations provide a natural way to define a detailed hierarchy of the corresponding large cardinal axioms. In particular, the study of cardinals satisfying Ramsey-Erdös-style partition relations has yielded a great number of very interesting large cardinal axioms which lie in strength strictly between inaccessibility and measurability. It is the purpose of this paper to show that this phenomenon does not occur if we use infinite exponent partition relations; no such partition relation has consistency strength strictly between inaccessibility and measurability. We also give a complete determination of which infinite exponent partition relations hold, assuming that there is no inner model of set theory with a measurable cardinal.Our notation is standard. If F is a function and x is a set, then F″x denotes the range of F on x. If X is a set of ordinals and α is an ordinal, then [X]α is the collection of all subsets of X of order type α. We identify a member of [X]α with a strictly increasing function from α to X. If p ∈ [X]α and q ∈ [α]β, then the composition of p with q, which we denote pq, is a member of [X]β.
Decision problems concerning properties of finite sets of equations
Authors: Kalfa Cornelia 
Published: May 2006

In this paper a general method of proving the undecidability of a property P, for finite sets Σ of equations of a countable algebraic language, is presented. The method is subsequently applied to establish the undecidability of the following properties, in almost all nontrivial such languages:1. The first-order theory generated by the infinite models of Σ is complete.2. The first-order theory generated by the infinite models of Σ is model-complete.3. Σ has the joint-embedding property.4. The first-order theory generated by the models of Σ with more than one element has the joint-embedding property.5. The first-order theory generated by the infinite models of Σ has the joint-embedding property.A countable algebraic language ℒ is a first-order language with equality, with countably many nonlogical symbols but without relation symbols, ℒ is trivial if it has at most one operation symbol, and this is of rank one. Otherwise, ℒ is nontrivial. An ℒ-equation is a sentence of the form , where φ and ψ are ℒ-terms. The set of ℒ-equations is denoted by Eqℒ. A set of sentences is said to have the joint-embedding property if any two models of it are embeddable in a third model of it.If P is a property of sets of ℒ-equations, the decision problem of P for finite sets of ℒ-equations is the problem of the existence or not of an algorithm for deciding whether, given a finite Σ ⊂ Eqℒ, Σ has P or not.
Splitting properties of r.e. sets and degrees
Authors: Downey R. G. , Welch L. V. 
Published: May 2006

A pair of r.e. sets A1, A2 are said to split an r.e. set A (written A1 Δ A2 = A) if A1 ∩ A2 = ∅ and A1 ∪ A2 = A. In the literature there are various results asserting certain splitting properties hold for all r.e. sets. For example Sacks' splitting theorem (cf. [So]) asserts that an r.e. nonrecursive set A may be split into a pair of Turing incomparable r.e. sets A1, A2, and Lachlan's splitting theorem [La5] asserts that A may be split into a pair of r.e. sets A1, A2 for which there exists an r.e. set B with B ⊕ A1, B ⊕ A2 <TA and with the infinum of the Turing degrees of B ⊕ A1 and B ⊕ A2 existing in the upper semilattice of r.e. degrees.Two of the earliest observations establishing that splitting properties possessed by some r.e. sets are not possessed by others, are Lachlan's nondiamond theorem [La1] (and so, in particular, no complete r.e. set can be split nontrivially with degree theoretic inf 0) and the Yates-Lachlan construction of a minimal pair (a pair of nonzero r.e. degrees with inf 0). Other examples of this phenomenon, which are not obtained by interpreting degree theoretic results in the r.e. sets, are Lachlan's construction of nonmitotic r.e. sets [La2] (sets which cannot be split into a pair of r.e. sets of the same degree) and, later, Ladner's [Ld1, 2] and Ingrassia's [In] analysis of their degrees.
Distributive ideals and partition relations
Authors: Johnson C. A. 
Published: May 2006

It is a theorem of Rowbottom [12] that ifκis measurable andIis a normal prime ideal onκ, then for eachλ<κ,In this paper a natural structural property of ideals, distributivity, is considered and shown to be related to this and other ideal theoretic partition relations.The set theoretical terminology is standard (see [7]) and background results on the theory of ideals may be found in [5] and [8]. Throughoutκwill denote an uncountable regular cardinal, andIa proper, nonprincipal,κ-complete ideal onκ.NSκis the ideal of nonstationary subsets ofκ, andIκ= {X⊆κ∣∣X∣<κ}. IfA∈I+(=P(κ) −I), then anI-partitionofAis a maximal collectionW⊆,P(A) ∩I+so thatX∩ Y ∈IwheneverX, Y∈W, X≠Y. TheI-partitionWis said to be disjoint if distinct members ofWare disjoint, and in this case, fordenotes the unique member ofWcontainingξ. A sequence 〈Wα∣α<η} ofI-partitions ofAis said to be decreasing if wheneverα<β<ηandX∈Wβthere is aY∈Wαsuch thatX⊆Y. (i.e.,WβrefinesWα).
A generalization of the limit lemma and clopen games
Authors: Clote Peter 
Published: May 2006

AbstractWe give a new characterization of the hyperarithmetic sets: a set X of integers is recursive in eα if and only if there is a Turing machine which computes X and “halts” in less than or equal to the ordinal number ωα of steps. This result represents a generalization of the well-known “limit lemma” due to J. R. Shoenfield [Sho-1] and later independently by H. Putnam [Pu] and independently by E. M. Gold [Go]. As an application of this result, we give a recursion theoretic analysis of clopen determinacy: there is a correlation given between the height α of a well-founded tree corresponding to a clopen game A ⊆ ωω and the Turing degree of a winning strategy ƒ for one of the players—roughly, ƒ can be chosen to be recursive in 0α and this is the best possible (see §4 for precise results).
On the relation between choice and comprehension principles in second order arithmetic
Authors: Cantini Andrea 
Published: May 2006

AbstractWe give a new elementary proof of the comparison theorem relating and ; the proof does not use Skolem theories.By the same method we prove:a) , for suitable classes of sentences;b) proves the consistency of , for finite k, and hence is stronger than .a) and b) answer a question of Feferman and Sieg.
Theories with finitely many models
Authors: Thomas Simon 
Published: May 2006

If L is a first order language and n is a natural number, then Ln is the set of formulas which only make use of the variables x1,…,xn. While every finite structure is determined up to isomorphism by its theory in L, the same is no longer true in Ln. This simple observation is the source of a number of intriguing questions. For example, Poizat [2] has asked whether a complete theory in Ln which has at least two nonisomorphic finite models must necessarily also have an infinite one. The purpose of this paper is to present some counterexamples to this conjecture.Theorem. For each n ≤ 3 there are complete theories in L2n−2andL2n−1having exactly n + 1 models.In our notation and definitions, we follow Poizat [2]. To test structures for elementary equivalence in Ln, we shall use the modified Ehrenfeucht-Fraïssé games of Immerman [1]. For convenience, we repeat his definition here.Suppose that L is a purely relational language, each of the relations having arity at most n. Let and ℬ be two structures for L. Define the Ln game on and ℬ as follows. There are two players, I and II, and there are n pairs of counters a1, b1, …, an, bn. On each move, player I picks up any of the counters and places it on an element of the appropriate structure.
The inclusion-exclusion principle for finitely many isolated sets
Authors: Dekker J. C. E. 
Published: May 2006

AbstractA nonnegative integer is called a number, a collection of numbers a set and a collection of sets a class. We write ε for the set of all numbers, o for the empty set, N(α) for the cardinality of α, ⊂ for inclusion and ⊂+ for proper inclusion. Let α, β1,…, βk be subsets of some set υ. Then α′ stands for υ−α and β1 … βk for β1 ∩ … ∩ βk. For subsets α1, …, αr of υ we write:Note that α0 = υ, hence s0 = N(υ). If the set υ is finite, the classical inclusion-exclusion principle (abbreviated IEP) statesIn this paper we generalize (a) and(b) to the case where α1, …, αr are subsets of some countable but isolated set υ. Then the role of the cardinality N(α) of the set α is played by the RET (recursive equivalence type) Req α of α. These generalizations of (a) and (b) are proved in §3. Since they involve recursive distinctness, this notion is discussed in §2. In §4 we consider a natural extension of “the sum of the elements of a finite set σ” to the case where σ is countable. §5 deals with valuations, i.e., certain mappings μ from classes of isolated sets into the collection Λ of all isols which permit us to further generalize IEP by substituting μ(α) for Req α.
Model companions for finitely generated universal Horn classes
Authors: Burris Stanley 
Published: May 2006

AbstractIn an earlier paper we proved that a universal Horn class generated by finitely many finite structures has a model companion. If the language has only finitely many fundamental operations then the theory of the model companion admits a primitive recursive elimination of quantifiers and is primitive recursive. The theory of the model companion is ℵ0-categorical iff it is complete iff the universal Horn class has the joint embedding property iff the universal Horn class is generated by a single finite structure. In the last section we look at structure theorems for the model companions of universal Horn classes generated by functionally complete algebras, in particular for the cases of rings and groups.
Constructible falsity and inexact predicates
Authors: Almukdad Ahmad , Nelson David 
Published: May 2006

In 1949 Nelson [5] proposed a constructive logic in which falsity is conceived in a fashion analogous to that for intuitionistic truth. The predicate calculus N (for strong negation) was characterized by the usual axioms and rules for positive intuitionistic connectives (see Kleene [4, p. 82, la–7 and 9–12]), with the additional axiom schemata for strong negation: A ⊃ (¬A ⊃ B),Nelson's paper showed that N may be interpreted with concepts for constructive truth (P-realizability) and falsity (N-realizability). The paper also gave mappings between the intuitionistic and strong negation systems of arithmetic.These mappings are easily adapted to pure predicate calculus. One shows that intuitionistic predicate calculus I is a subsystem of N by reading the intuitionistic negation of A as A ⊃ B & ¬B in N. It is possible to map N into a subsystem of I using the definition of A′ in [5, p. 19] changing only the definition of (¬A)′ for atomic A to A ⊃ B & ¬B.
Which set existence axioms are needed to prove the Cauchy/Peano theorem for ordinary differential equations?
Authors: Simpson Stephen G. 
Published: May 2006

AbstractWe investigate the provability or nonprovability of certain ordinary mathematical theorems within certain weak subsystems of second order arithmetic. Specifically, we consider the Cauchy/Peano existence theorem for solutions of ordinary differential equations, in the context of the formal system RCA0whose principal axioms arecomprehension andinduction. Our main result is that, over RCA0, the Cauchy/Peano Theorem is provably equivalent to weak König's lemma, i.e. the statement that every infinite {0, 1}-tree has a path. We also show that, over RCA0, the Ascoli lemma is provably equivalent to arithmetical comprehension, as is Osgood's theorem on the existence of maximum solutions. At the end of the paper we digress to relate our results to degrees of unsolvability and to computable analysis.
An undecidable problem in finite combinatorics
Authors: Compton Kevin J. 
Published: May 2006

Problems of computing probabilities of statements about large, finite structures have become an important subject area of finite combinatorics. Within the last two decades many researchers have turned their attention to such problems and have developed a variety of methods for dealing with them. Applications of these ideas include nonconstructive existence proofs for graphs with certain properties by showing the properties occur with nonzero probabilities (for examples see Erdös and Spencer [ES] and Bollobás [Bo]), and determination of average running times for sorting algorithms by computing asymptotic probabilities of statements about permutations (see Knuth [Kn]). Two types of techniques recur in solutions to such problems: probabilistic techniques, such as those used by Erdös and Spencer [ES], and classical assymptotic techniques, such as those surveyed by Bender [Be] and de Bruijn [Br]. Studying this body of techniques, one notices that characteristics of these problems suggest certain methods of solution, in much the same way that the form of an integrand may suggest certain substitutions. The question arises, then, as to whether there is a systematic way to approach these problems: is there an algorithm for computing asymptotic probabilities? I will show that the answer is “no”—for any reasonable formulation, the problem of computing asymptotic probabilities is undecidable.The main theorem of the paper is Theorem 1.6, which says that there is a finitely axiomatizable class in which every first order sentence has an asymptotic probability of 0 or 1—i.e., is almost always true or almost always false in finite structures—but for which the problem of deciding whether a sentence has asymptotic probability 0 or 1 is undecidable. Heretofore, classes known to have such a 0-1 law have had decidable asymptotic probability problems (see Lynch [Ly] for examples and a discussion of previous work in the area).
A direct proof of the finite developments theorem
Authors: de Vrijer Roel 
Published: May 2006

Let M be a term of the type free λ-calculus and let be a set of occurrences of redexes in M. A reduction sequence from M which first contracts a member of and afterwards only residuals of is called a development (of M with respect to ). The finite developments theorem says that developments are always finite.There are several proofs of this theorem in the literature. A plausible strategy is to define some kind of measure for pairs (M, ), which—if M′ results from M by contracting a redex occurrence in and ′ is the set of residuals of in M′— decreases in passing from (M, ) to (M′, ′). This procedure is followed as a matter of fact in the proofs in Hyland [4] and in Barendregt [1] (both are covered in Klop [5]). If, as in the latter proof, the natural numbers are used as measures, then the measure of (M, ) will actually denote an upper bound of the number of reduction steps in a development of M with respect to .In the present proof we straightforwardly define for each pair (M, ) a natural number, which can easily be seen to indicate the exact number of reduction steps in a development of maximal length of M with respect to .
Isomorphisms between HEO and HROE, ECF and ICFE
Authors: Bezem Marc 
Published: May 2006

AbstractIn this paper it will be shown that HEO and HROE are isomorphic with respect to extensional equality. This answers a question of Troelstra [T, 2.4.12, p. 128]. The main problem is to extend effective operations to a larger domain. This will be achieved by a modification of the proof of the continuity of effective operations. Following a suggestion of A. S. Troelstra, similar results were obtained for ECF(U) and ICFE(U), where U is any universe of functions closed under “recursive in”.
The consistency of some 4-stratified subsystem of NF including NF3
Authors: Boffa Maurice , Casalegno Paolo 
Published: May 2006

As is well known, NF is a first-order theory whose language coincides with that of ZF. The nonlogical axioms of the theory are: Extensionality. (x)(y)[(z)(z ∈ x ↔ z ∈ y) → x = y].Comprehension. (Ex)(y)(y ∈ x ↔ ψ) for every stratified ψ in which x does not occur free (a formula of NF is said to be stratified if it can be turned into a formula of the simple theory of types by adding type indices (natural numbers ≥ 0) to its variables).Before stating our result, a few preliminaries are in order. Let T be the simple theory of types. If ψ is a formula of T, we denote by ψ+ the formula obtained from ψ by raising all type indices by 1. T* is the result of adding to T every axiom of the form ψ ↔ ψ+. A formula of T is n-stratified (n > 0) if it does not contain any type index ≥ n. A formula of NF is n-stratified if it can be turned into an n-stratified formula of T by adding type indices to its variables. (In practice, we shall allow ourselves to confuse an n-stratified formula of T with the corresponding n-stratified formula of NF). For n > 0, Tn (resp. ) is the subtheory of T (resp. T*) containing only n-stratified formulae. For n > 0, NFn is the subtheory of NF generated by those axioms of NF which are n-stratified. Let = 〈M0, M1,…,=, ∈〉 be a model of T.
On the role of the Baire Category Theorem and Dependent Choice in the foundations of logic
Authors: Goldblatt Robert 
Published: May 2006

AbstractThe Principle of Dependent Choice is shown to be equivalent to: the Baire Category Theorem for Čech-complete spaces (or for complete metric spaces); the existence theorem for generic sets of forcing conditions; and a proof-theoretic principle that abstracts the “Henkin method” of proving deductive completeness of logical systems. The Rasiowa-Sikorski Lemma is shown to be equivalent to the conjunction of the Ultrafilter Theorem and the Baire Category Theorem for compact Hausdorff spaces.
An AD-like model
Authors: Apter Arthur W. 
Published: May 2006

A very fruitful line of research in recent years has been the application of techniques in large cardinals and forcing to the production of models in which certain consequences of the axiom of determinateness (AD) are true or in which certain “AD-like” consequences are true. Numerous results have been published on this subject, among them the papers of Bull and Kleinberg [4], Bull [3], Woodin [15], Mitchell [11], and [1], [2].Another such model will be constructed in this paper. Specifically, the following theorem is proven.Theorem 1. Con(ZFC + There are cardinals κ < δ < λ so that κ is a supercompact limit of supercompact cardinals, λ is a measurable cardinal, and δ is λ supercompact) ⇒ Con(ZF + ℵ1 and ℵ2 are Ramsey cardinals + The ℵn for 3 ≤ n ≤ ω are singular cardinals of cofinality ω each of which carries a Rowbottom filter + ℵω + 1 is a Ramsey cardinal + ℵω + 2 is a measurable cardinal).It is well known that under AD + DC, ℵ2 and ℵ2 are measurable cardinals, the ℵn for 3 ≤ n < ω are singular Jonsson cardinals of cofinality ℵ2, ℵω is a Rowbottom cardinal, and ℵω + 1 and ℵω + 2 are measurable cardinals.The proof of the above theorem will use the existence of normal ultrafilters which satisfy a certain property (*) (to be defined later) and an automorphism argument which draws upon the techniques developed in [9], [2], and [4] but which shows in addition that certain supercompact Prikry partial orderings are in a strong sense “homogeneous”. Before beginning the proof of the theorem, however, we briefly mention some preliminaries.
Typical ambiguity and the axiom of choice
Authors: Crabbé Marcel 
Published: May 2006

E. Specker has proved that the axiom of choice (AC) is false in NF [6]. Since AC is stratified, one can, according to another famous result of Specker [7], prove directly ¬AC in type theory (TT) plus some finite set of ambiguity axioms, i.e. sentences of the form φ ↔ φ+, where φ+ results from φ by adding one to its type indices.We shall in §2 of this paper give a disproof of AC directly in TT plus some axioms of ambiguity. The argument will be split into two parts. The first one (contained in Proposition 2) concerns cardinal arithmetic and has nothing to do with typical ambiguity. Though carried out in TT, it could have been done in other set theories such as Zermelo's Z or ZF. The second part is an application of this to the cardinals of the universes at different types. This is made possible through the introduction of an appropriate definition of 2α in §1 enabling one to express shifting sentences as “typed properties” of the universe, in Boffa's sense. The disproof of AC is then completed in TT plus two extra ambiguity axioms. In §3, we show that this is in a sense the best possible result: that means that every single ambiguity axiom is consistent with TT plus AC, thus giving a positive solution to a conjecture of Specker [7, p. 119].
A model in which the base-matrix tree cannot have cofinal branches
Authors: Dordal Peter Lars 
Published: May 2006

AbstractA model of ZFC is constructed in which the distributivity cardinal h is , and in which there are no ω2-towers in [ω]ω. As an immediate corollary, it follows that any base-matrix tree in this model has no cofinal branches. The model is constructed via a form of iterated Mathias forcing, in which a mixture of finite and countable supports is used.
Semi-de Morgan algebras
Authors: Sankappanavar Hanamantagouda P. 
Published: May 2006

The purpose of this paper is to define and investigate a new (equational) class of algebras, which we call semi-De Morgan algebras, as a common abstraction of De Morgan algebras and distributive pseudocomplemented lattices. We were first led to this class of algebras in 1979 (in Brazil) as a result of our attempt to extend both the well-known theorem of Glivenko (see [4, Theorem 26]) and Lakser's characterization of principal congruences to a setting more general than that of distributive pseudocomplemented lattices. In subsequent years, our work in [20] on a subvariety of Ockham algebras, first considered by Berman [3], renewed our interest in semi-De Morgan algebras by providing new examples. It seems worth mentioning that these new algebras may also turn out to be useful in resolving a conjecture made in [22] to unify certain strikingly similar results on Heyting algebras with a dual pseudocomplement (see [21]) and Heyting algebras with a De Morgan negation (see [22]).In §2 we introduce semi-De Morgan algebras and prove the main theorem, which, roughly speaking, states that certain elements of a semi-De Morgan algebra form a De Morgan algebra. Several applications then follow, including new axiomatizations of distributive pseudocomplemented lattices, Stone algebras and De Morgan algebras.