bluuebunny/crossref_metadata_2025_split huggingface dataset:
Nowhere simple sets and the lattice of recursively enumerable sets
Authors: Shore Richard A. 
Published: May 2006

Ever since Post [4] the structure of recursively enumerable sets and their classification has been an important area in recursion theory. It is also intimately connected with the study of the lattices and of r.e. sets and r.e. sets modulo finite sets respectively. (This lattice theoretic viewpoint was introduced by Myhill [3].) Key roles in both areas have been played by the lattice of r.e. supersets, , of an r.e. set A (along with the corresponding modulo finite sets) and more recently by the group of automorphisms of and . Thus for example we have Lachlan's deep result [1] that Post's notion of A being hyperhypersimple is equivalent to (or ) being a Boolean algebra. Indeed Lachlan even tells us which Boolean algebras appear as —precisely those with Σ3 representations. There are also many other simpler but still illuminating connections between the older typology of r.e. sets and their roles in the lattice . (r-maximal sets for example are just those with completely uncomplemented.) On the other hand, work on automorphisms by Martin and by Soare [8], [9] has shown that most other Post type conditions on r.e. sets such as hypersimplicity or creativeness which are not obviously lattice theoretic are in fact not invariant properties of .In general the program of analyzing and classifying r.e. sets has been directed at the simple sets. Thus the subtypes of simple sets studied abound — between ten and fifteen are mentioned in [5] and there are others — but there seems to be much less known about the nonsimple sets. The typologies introduced for the nonsimple sets begin with Post's notion of creativeness and add on a few variations. (See [5, §8.7] and the related exercises for some examples.) Although there is a classification scheme for r.e. sets along the simple to creative line (see [5, §8.7]) it is admitted to be somewhat artificial and arbitrary. Moreover there does not seem to have been much recent work on the nonsimple sets.
Relation of Leśniewski's mereology to Boolean algebra
Authors: Clay Robert E. 
Published: May 2006

It has been stated by Tarski [5] and “proved” by Grzegorczyk [3] that:
(A) The models of mereology and the models of complete Boolean algebra with zero deleted are identical.Proved has been put in quotes, not because Grzegorczyk's proof is faulty but because the system he describes as mereology is in fact not Leśniewski's mereology.Leśniewski's first attempt at describing the collective class, i.e. mereology, was done in ordinary language with no rigorous logical foundation. In describing the collective class, he needed to use the notion of distributive class. So as to clearly distinguish and expose the interplay between the two notions of class, he introduced his calculus of name (name being the distributive notion), which is also called ontology, since he used the primitive term “is.” At this stage, mereology included ontology. Then, in order to have a logically rigorous system, he developed as a basis, a propositional calculus with quantifiers and semantical categories (types), called protothetic. At this final stage, what is properly called mereology includes both protothetic and ontology.What Grzegorczyk describes as mereology is even weaker than Leśniewski's initial version. To quote from [3]:
“In order to emphasize these formal relations let us consider the systems of axioms of mereology for another of its primitive terms, namely for the term “ingr” defined as follows:A ingr B.≡.A is a part B ∨ A is identical to B.The proposition “A ingr B” can be read “A is contained in B” or after Leśniewski, “A is ingredient of B”.”
One more aspect of forcing and omitting types
Authors: Adamowicz Zofia 
Published: May 2006

As has been shown by the investigations of some mathematicians, there are numerous analogies between forcing and omitting types. Evidence of that can also be found in the application of forcing to model theory. Both methods use the Rasiowa-Sikorski lemma on the existence in a Boolean algebra of an ultrafilter intersecting every dense set from a given denumerable family.In this paper we will not use the terms Cohen forcing and omitting types in their original sense. We shall deal mainly with the Scott-Boolean kind of forcing as a transformation of Cohen's idea and with methods used in logic that consist in finding a suitable ultrafilter in the Lindenbaum-Tarski algebra for a given theory and defining canonical models—under the name of omitting types.The two methods will be confronted to show that Cohen's forcing stems from logical methods. Attention will also be drawn to some differences between forcing in set theory and the general methods of logic.In logic we construct a model by defining relations in a set of constants. In particular when defining a model for set theory we define a certain relation E in a set of constants. It is usually immaterial what E is, in particular whether it is the true relation of membership up to isomorphism.
Semantics of the infinitistic rules of proof
Authors: Apt Krzysztof Rafal 
Published: May 2006

This paper is devoted to the study of the infinitistic rules of proof i.e. those which admit an infinite number of premises. The best known of these rules is the ω-rule. Some properties of the ω-rule and its connection with the ω-models on the basis of the ω-completeness theorem gave impulse to the development of the theory of models for admissible fragments of the language . On the other hand the study of representability in second order arithmetic with the ω-rule added revealed for the first time an analogy between the notions of re-cursivity and hyperarithmeticity which had an important influence on the further development of generalized recursion theory.The consideration of the subject of infinitistic rules in complete generality seems to be reasonable for several reasons. It is not completely clear which properties of the ω-rule were essential for the development of the above-mentioned topics. It is also worthwhile to examine the proof power of infinitistic rules of proof and what distinguishes them from finitistic rules of proof.What seemed to us the appropriate point of view on this problem was the examination of the connection between the semantics and the syntax of the first order language equipped with an additional rule of proof.
Elementary extensions of countable models of set theory
Authors: Hutchinson John E. 
Published: May 2006

AbstractWe prove the following extension of a result of Keisler and Morley. Suppose is a countable model of ZFC and c is an uncountable regular cardinal in . Then there exists an elementary extension of which fixes all ordinals below c, enlarges c, and either (i) contains or (ii) does not contain a least new ordinal.Related results are discussed.
Complete types and the natural numbers
Authors: Knight Julia F. 
Published: May 2006

In this paper it is shown that, for any complete type Σ omitted in the structure , or in any expansion of having only countably many relations and operations, there is a proper elementary extension of (or of ) which omits Σ. This result (which was announced in [2]) is used to answer a question of Malitz on complete -sentences. The result holds also for countable families of types.A type is a countable set of formulas with just the variable υ free. A structure is said to omit a type Σ if no element of satisfies all of the formulas of Σ. For example, omits the type Σω = {υ ≠ n: n ∈ ω}, since n fails to satisfy υ ≠ n. (Here n is the constant symbol standing for n.)A type Σ is said to be complete with respect to a theory T if the set of sentences T ∪ Σ(e) generates a complete theory, where Σ(e) is the result of replacing υ by the new constant e in all of the formulas of Σ. The type Σω is clearly not complete with respect to Th(). (For any structure Th(), Th() is the set of all sentences true in .)
Théories d'arbres
Authors: Parigot Michel 
Published: May 2006

Les arbres sont les ordres partiels qui vérifient l'axiome supplémental ∀x∀y∀z(y ≤x ∧z ≤ x → y ≤ z ∨ z ≤ y), i.e. l'ensemble des minorants de chaque élément est totalement ordonné.Le principal résultat de cet article concerne l'instabilité des arbres: nous prouvons (§2) qu'aucune théorie d'arbre n'a la propriété d'indépendance, ce qui généralise un theoreme de Poizat [3] sur les ordres totaux. II s'en suit au moyen d'un resultat d'interprétation [4] qu'aucune théorie de structure arborescente n'a la propriété d'indépendance; en particulier ceci vaut pour les arbres colorés.Le §3 est consacré aux arbres stables. II est prouvé qu'un arbre est stable ssi il est superstable ssi il est de hauteur bornée. Sous l'hypothèse de stabilité, les arbres premiers, minimaux, et strictement minimaux sont caractérisés en termes d'al-gébricité.
Refinements of Vaught's normal from theorem
Authors: Harnik Victor 
Published: May 2006

The central notion of this paper is that of a (conjunctive) game-sentence, i.e., a sentence of the formwhere the indices ki, ji range over given countable sets and the matrix conjuncts are, say, open -formulas. Such game sentences were first considered, independently, by Svenonius [19], Moschovakis [13]—[15] and Vaught [20]. Other references are [1], [3]—[5], [10]—[12]. The following normal form theorem was proved by Vaught (and, in less general forms, by his predecessors).Theorem 0.1. Let L = L0(R). For every -sentence ϕ there is an L0-game sentence Θ such that ⊨′ ∃Rϕ ↔ Θ.(A word about the notations: L0(R) denotes the language obtained from L0 by adding to it the sequence R of logical symbols which do not belong to L0; “⊨′α” means that α is true in all countable models.)0.1 can be restated as follows.Theorem 0.1′. For every-sentence ϕ there is an L0-game sentence Θ such that ⊨ϕ → Θ and for any-sentence ϕ if ⊨ϕ → ϕ and L′ ⋂ L ⊆ L0, then ⊨ Θ → ϕ.(We sketch the proof of the equivalence between 0.1 and 0.1′.0.1 implies 0.1′. This is obvious once we realize that game sentences and their negations satisfy the downward Löwenheim-Skolem theorem and hence, ⊨′α is equivalent to ⊨α whenever α is a boolean combination of and game sentences.
On carnap and popper probability functions
Authors: Leblanc Hugues , van Fraassen Bas C. 
Published: May 2006

With PC understood to be the propositional calculus of [3], call a binary function Pr from the wffs of PC to the reals a Carnap (probability) function if it meets requirements A1—A5 in Table I (with ‘⊢…’ short in A3—A4 for ‘… is a tautology’), and call the function a Popper (probability) function if it meets requirements Bl—B6 there:Leblanc established in [3] that every Carnap function is a Popper one, and he tendered proof of the converse. As reported by Stalnaker in [5], the proof unfortunately was incomplete, a mishap due to Leblanc's abbreviating ‘Pr(A, ∼ A) = 1’ as ‘⊢ A’ when Pr is a Popper function. Borrowing from [4], Leblanc did show, as Harper notes in [2, footnote 17], that(1) If Pr is a Popper function and A is a tautology, then Pr(A, ∼ A) = 1. He did not, however, show that(2) If Pr is a Popper function and Pr(A, ∼ A) = 1, then A is a tautology.Nor could he have done so: (2) is false, as the simplest of counterexamples shows. Denied (2), Leblanc had no hope of proving that every Popper function is a Carnap one: of a Popper function Pr it is easily ascertained that Pr meets requirement A4 if and only if Pr(A, ∼ A) = 1 just in case A is a tautology.
Flipping properties in arithmetic
Authors: Kirby L. A. S. 
Published: May 2006

Flipping properties were introduced in set theory by Abramson, Harrington, Kleinberg and Zwicker [1]. Here we consider them in the context of arithmetic and link them with combinatorial properties of initial segments of nonstandard models studied in [3]. As a corollary we obtain independence resutls involving flipping properties.We follow the notation of the author and Paris in [3] and [2], and assume some knowledge of [3]. M will denote a countable nonstandard model of P (Peano arithmetic) and I will be a proper initial segment of M. We denote by N the standard model or the standard part of M. X ↑ I will mean that X is unbounded in I. If X ⊆ M is coded in M and M ≺ K, let X(K) be the subset of K coded in K by the element which codes X in M. So X(K) ⋂ M = X.Recall that M ≺IK (K is an I-extension of M) if M ≺ K and for some c∈K,In [3] regular and strong initial segments are defined, and among other things it is shown that I is regular if and only if there exists an I-extension of M.
The model of set theory generated by countably many generic reals
Authors: Blass Andreas 
Published: May 2006

AbstractAdjoin, to a countable standard model M of Zermelo-Fraenkel set theory (ZF), a countable set A of independent Cohen generic reals. If one attempts to construct the model generated over M by these reals (not necessarily containing A as an element) as the intersection of all standard models that include M ∪ A, the resulting model fails to satisfy the power set axiom, although it does satisfy all the other ZF axioms. Thus, there is no smallest ZF model including M ∪ A, but there are minimal such models. These are classified by their sets of reals, and there is one minimal model whose set of reals is the smallest possible. We give several characterizations of this model, we determine which weak axioms of choice it satisfies, and we show that some better known models are forcing extensions of it.
Stability of nilpotent groups of class 2 and prime exponent
Authors: Mekler Alan H. 
Published: May 2006

AbstractLet p be an odd prime. A method is described which given a structure M of finite similarity type produces a nilpotent group of class 2 and exponent p which is in the same stability class as M.Theorem. There are nilpotent groups of class 2 and exponent p in all stability classes.Theorem. The problem of characterizing a stability class is equivalent to characterizing the (nilpotent, class 2, exponent p) groups in that class.
Hyper-torre isols
Authors: Ellentuck Erik 
Published: May 2006

AbstractIf T is an isol let D(T) be the least set of isols which contains T and is closed under predecessors and the application of almost recursive combinatorial functions. We find an infinite regressive isol T such that the universal theory (with respect to recursive relations and almost recursive combinatorial functions) of D(T) is the same as that of the nonnegative integers.
Bounding minimal pairs
Authors: Lachlan A. H. 
Published: May 2006

A minimal pair of recursively enumerable (r.e.) degrees is a pair of degrees a, b of nonrecursive r.e. sets with the property that if c ≤ a and c ≤ b then c = 0. Lachlan [2] and Yates [4] independently proved the existence of minimal pairs. It was natural to ask whether for an arbitrary nonzero r.e. degree c there is a minimal pair a, b with a ≤ c and b ≤ c. In 1971 Lachlan and Ladner proved that a minimal pair below c cannot be obtained in a uniformly effective way from c for r.e. c ≠ 0. but the result was never published. More recently Cooper [1] showed that if c is r.e. and c′ = 0″ then there is a minimal pair below c.In this paper we prove two results:Theorem 1. There exists a nonzero r.e. degree with no minimal pair below it.Theorem 2. There exists a nonzero r.e. degree c such that, if d is r.e. and 0 < d ≤ c, then there is a minimal pair below d.The second theorem is a straightforward variation on the original minimal pair construction, but the proof of the first theorem has some novel features. After some preliminaries in §1, the first theorem is proved in §2 and the second in §3.I am grateful to Richard Ladner who collaborated with me during the first phase of work on this paper as witnessed by our joint abstract [3]. The many discussions we had about the construction required in Theorem 1 were of great help to me.
Proper classes
Authors: Maddy Penelope 
Published: May 2006

The modern problem of infinity was first raised by Aristotle who held (at least on the popular interpretation) that infinite sets exist potentially (i.e. one more number can always be counted, one more division can always be made in a line segment) but not actually (i.e. the numbers or divisions cannot all exist at one time). In fact, Aristotle not only held that completed infinities never actually exist, but also that they are impossible, that is, that the assumption that they do exist leads to contradictions. To see this, consider Aristotle's view that mathematical entities depend for their existence on the existence of primary substance in which they inhere, coupled with his view that there can be no infinite body. From these it follows that if there were actual completed infinities, infinite bodies would both exist and not exist. The details here are not so important as the idea that if a completed infinite is assumed to exist a contradiction follows.This negative attitude towards completed infinities flourished for centuries. By the mid-1500's, the German mathematician Stifel (who apparently also invented Pascal's triangle) was moved to condemn irrational numbers simply by their association with the completed infinite:… just as an infinite number is not a number, so an irrational number is not a true number, but lies hidden in a kind of cloud of infinity.About a hundred years later, Galileo further discredited the completed infinite by pointing out that line segments of different lengths can be brought into one-to-one correspondence by projection, as can the natural numbers and the perfect squares by assigning each number to its square.
The existence of countable totally nonconstructive extensions of the countable atomless Boolean algebra
Authors: Madison E. W. 
Published: May 2006

AbstractOur results concern the existence of a countable extension of the countable atomless Boolean algebra such that is a “nonconstructive” extension of . It is known that for any fixed admissible indexing φ of there is a countable nonconstructive extension of (relative to φ). The main theorem here shows that there exists an extension of such that for any admissible indexing φ of , is nonconstructive (relative to φ).Thus, in this sense a countable totally nonconstructive extension of .
Computability and the algebra of fields: Some affine constructions
Authors: Tucker J. V. 
Published: May 2006

A natural way of studying the computability of an algebraic structure or process is to apply some of the theory of the recursive functions to the algebra under consideration through the manufacture of appropriate coordinate systems from the natural numbers. An algebraic structureA= (A;σ1,…,σk) iscomputableif it possesses a recursive coordinate system in the following precise sense: associated toAthere is a pair (α, Ω) consisting of a recursive set of natural numbersΩand a surjectionα:Ω→Aso that (i) the relation defined onΩbyn≡αmiffα(n) =α(m) inAis recursive, and (ii) each of the operations ofAmay be effectively followed inΩ, that is, for each (say)r-ary operationσonAthere is anrargument recursive functiononΩwhich commutes the diagramwhereinαrisr-foldα× … ×α.This concept of a computable algebraic system is the independent technical idea of M.O.Rabin [18] and A.I.Mal'cev [14]. From these first papers one may learn of the strength and elegance of the general method of coordinatising; note-worthy for us is the fact that computability is a finiteness condition of algebra—an isomorphism invariant possessed of all finite algebraic systems—and that it serves to set upon an algebraic foundation the combinatorial idea that a system can be combinatorially presented and have effectively decidable term or word problem.
Dimension theory and homogeneity for elementary extensions of a model
Authors: Pillay Anand 
Published: May 2006

We take a fixed countable model M0, and we look at the structure of and number of its countable elementary extensions (up to isomorphism over M0). Assuming that S(M0) is countable, we prove that if N is a weakly minimal extension of , and if then there is an elementary embedding of N into M over M0), then N is homogeneous over M0. Moreover the condition that ∣S(M0)∣ = ℵ0 cannot be removed. Under the hypothesis that M0 contains no infinite set of tuples ordered by a formula, we prove that M0 has infinitely many countable elementary extensions up to isomorphism over M0. A preliminary result is that all types over M0 are definable, and moreover is definable over M0 if and only if is definable over M0 (forking symmetry). We also introduce a notion of relative homogeneity, and show that a large class of elementary extensions of M0 are relatively homogeneous over M0 (under the assumptions that M0 has no order and S(M0) is countable).I will now discuss the background to and motivation behind the results in this paper, and also the place of this paper relative to other conjectures and investigations. To simplify notation let T denote the complete diagram of M0. First, our result that if M0 has no order then T has infinitely many countable models is related to the following conjecture: any theory with a finite number (more than one) of countable models is unstable.
Extremely undecidable sentences
Authors: Boolos George 
Published: May 2006

Let ‘ϕ’, ‘χ’, and ‘ψ’ be variables ranging over functions from the sentence letters P0, P1, … Pn, … of (propositional) modal logic to sentences of P(eano) Arithmetic), and for each sentence A of modal logic, inductively define Aϕ by[and similarly for other nonmodal propositional connectives]; andwhere Bew(x) is the standard provability predicate for PA and ⌈F⌉ is the PA numeral for the Gödel number of the formula F of PA. Then for any ϕ, (−□⊥)ϕ = −Bew(⌈⊥⌉), which is the consistency assertion for PA; a sentence S is undecidable in PA iff both and , where ϕ(p0) = S. If ψ(p0) is the undecidable sentence constructed by Gödel, then ⊬PA (−□⊥→ −□p0 & − □ − p0)ψ and ⊢PA(P0 ↔ −□⊥)ψ. However, if ψ(p0) is the undecidable sentence constructed by Rosser, then the situation is the other way around: ⊬PA(P0 ↔ −□⊥)ψ and ⊢PA (−□⊥→ −□−p0 & −□−p0)ψ. We call a sentence S of PA extremely undecidable if for all modal sentences A containing no sentence letter other than p0, if for some ψ, ⊬PAAψ, then ⊬PAAϕ, where ϕ(p0) = S. (So, roughly speaking, a sentence is extremely undecidable if it can be proved to have only those modal-logically characterizable properties that every sentence can be proved to have.) Thus extremely undecidable sentences are undecidable, but neither the Godel nor the Rosser sentence is extremely undecidable. It will follow at once from the main theorem of this paper that there are infinitely many inequivalent extremely undecidable sentences.
A note on the undefinability of cuts
Authors: Paris J.B. , Dimitracopoulos C. 
Published: May 2006

The results in this paper were motivated by the following result due to R. Solovay.Theorem 1 (Solovay). Let M be a nonstandard model of Peano's first order axioms P and let I ⊂e M (i.e. ϕ ≠ ⊂ M and I is closed under < and successor). Then for each of the functions we can define J ⊆e I in ‹M, I› such that J is closed under that function. (∣x∣ denotes [log2(x)].)Proof. Just notice that the cuts defined byare successively closed under In view of Theorem 1, the following question was raised by R. Solovay: Can we define J ⊆ I in ‹M, I› such that J is closed under exponentiation? In Theorem 2 we show that the answer is “no”. Theorem 3 is based on Theorem 2 and extends the technique to cuts which are models of subsystems of P.To prove both theorems we shall need an estimate due to R. Parikh (see [1], especially the proof of Theorem 2.2a). For the sake of completeness, and also to introduce some notation we shall sketch Parikh's estimate in the next section. At all times we shall give the easiest estimates which still work rather than the sharpest ones.
Some recent developments in higher recursion theory
Authors: Friedman Sy D. 
Published: May 2006

AbstractIn recent years higher recursion theory has experienced a deep interaction with other areas of logic, particularly set theory (fine structure, forcing, and combinatorics) and infinitary model theory. In this paper we wish to illustrate this interaction by surveying the progress that has been made in two areas: the global theory of the κ-degrees and the study of closure ordinals.