bluuebunny/crossref_metadata_2025 huggingface dataset:
Linear orderings under one-one reducibility
Authors: Young Paul R.
Published: May 2006

In [2], Fischer has shown the existence of a bounded-truth-table degree of unsolvability which contains a collection of many-one degrees which has, under many-one reducibility, the order type, ω, of the positive integers. In [1; pg. 124], Dekker and Myhill give a construction which shows that the many-one degree of any simple set contains a collection of one-one degrees of simple sets which has, under one-one reducibility, the order type (ω + ω*) ·ω. A basic result of recursive function theory (due to Myhill) is that the creative sets form a many-one degree which consists of a single one-one degree (i.e. a single recursive isomorphism type).

It is well known that the recursive sets form three many-one degrees. Two of these, the degrees of the empty set and of the set of all integers, consist of single one-one degrees.
Hierarchies of Boolean algebras
Authors: Feiner Lawrence
Published: May 2006

A denumerable structure is said to be recursive iff its universe is a recursive subset of the natural numbers and its relations and operations are recursive. For example, the standard model of number theory is recursive. A structure is said to be recursively presentable iff it is isomorphic to a recursive structure. For example, a Boolean algebra generated by ℵ0 free generators is easily seen to be recursively presentable. (For basic facts concerning Boolean algebras, the reader is referred to R. Sikorski [9] and A. Tarski and A. Mostowski [10].)
Definability in the monadic second-order theory of
successor
Authors: Richard Buchi J. , Landweber Lawrence H.
Published: May 2006

Let be a
relational system whereby D is a nonempty set and
P1 is an
m1-ary relation on D. With
we associate the (weak) monadic second-order theory
consisting of the first-order predicate calculus
with individual variables ranging over D; monadic predicate
variables ranging over (finite) subsets of D; monadic
predicate quantifiers; and constants corresponding to P1,
P2, …. We will often use ambiguously to mean also the set of true sentences
of .
Probability logic
Authors: Burgess John P.
Published: May 2006

In this paper we introduce a system S5U, formed by adding
to the modal system S5 a new connective U, Up being read
“probably”. A few theorems are derived in S5U, and the
system is provided with a decision procedure. Several decidable extensions
of S5U are discussed, and probability logic is related to
plurality quantification.
Omitting types of prenex formulas
Authors: Chang C. C.
Published: May 2006

In the literature, a type Γ is a set of formulas ϕ(ν0) in the one free variable ν0. A model M realizes Γ if there is an element a of M such that

M ╞ ϕ [a] for all ϕ ∈ Γ.

A model M omits Γ if no element of M realizes Γ. Evidently, the two statements:

(*) M realizes Γ

and

(**) M omits Γ
A method of modelling the formalism of set theory in axiomatic set theory
Authors: Kruse A. H.
Published: May 2006

As is well known, some paradoxes arise through inadequate analysis of the meanings of terms in a language, an adequate analysis showing that the paradoxes arise through a lack of separation of an object theory and a metatheory. Under such an adequate analysis in which parts of the metatheory are modelled in the object theory, the paradoxes give way to remarkable theorems establishing limitations of the object theory.

Such a modelling is often accomplished by a Gödel numbering. Here we shall use a somewhat different technique in axiomatic set theory, from which we shall reap a few results having the effect of comparing the strength of various axiom schema of comprehension for sets and classes (cf. the numbered results of §§5–7). Similar results were obtained by A. Mostowski [7] using Gödel numbering (cf. 5.3 and 7.3 below).
Degrees of unsolvability of constructible sets of integers
Authors: Boolos George , Putnam Hilary
Published: May 2006

Why the Post-Kleene arithmetical hierarchy of degrees of (recursive) unsolvability was extended into the transfinite is not clear. Perhaps it was thought that if a hierarchy of sufficiently fine structure could be described that would include all sets of integers, some light might be thrown on the Continuum Hypothesis, and its truth or falsity possibly even ascertained. There is also some evidence in the 1955 papers of Kleene (cf. Kleene [2], [3], [4]) that it was once hoped that a theorem for the analytical hierarchy analogous to the result of Post and Kleene
An addendum
Authors: Kleene S. C.
Published: May 2006

This addendum supplies details of the proof in 3.6 of our paper Disjunction and existence under implication in elementary intuition-istic formalisms in this Journal, vol. 27 (1962), pp. 11–18, as promised in Footnote 8 of that paper (p. 16 lines 11 and 16, for “├” read “|”).

A congruence-substitution (or free substitution with change of bound variables) on a formula E with result F consists in, simultaneously, substituting for each of the free variables of E in all its free occurrences a respective term and replacing each bound occurrence of a variable in E by a respective variable, so that (a) each image in F of a free occurrence of a variable in E is free (IM p. 410) and (b) each image in F of a bound occurrence of a variable in E is bound by the corresponding quantifier (i.e. if the j-th quantifier in E binds the original occurrence, then the j-th quantifier in F binds the image).
Natural models and Ackermann-type set theories
Authors: Lake John
Published: May 2006

Our results concern the natural models of Ackermann-type set theories, but they can also be viewed as results about the definability of ordinals in certain sets.

Ackermann's set theory A was introduced in [1] and it is now formulated in the first order predicate calculus with identity, using ∈ for membership and an individual constant V for the class of all sets. We use the letters ϕ, χ, θ, and χ to stand for formulae which do not contain V and capital Greek letters to stand for any formulae. Then, the axioms of A* are the universal closures of

where all the free variables are shown in A4 and z does not occur in the Θ of A2. A is the theory A* − A5.

Most of our notation is standard (for instance, α, β, γ, δ, κ, λ, ξ are variables ranging over ordinals) and, in general, we follow the notation of [7]. When x ⊆ Rα, we use Df(Rα, x) for the set of those elements of Rα which are definable in 〈Rα, ∈〉, using a first order ∈-formula and parameters from x.

We refer the reader to [7] for an outline of the results which are known about A, but we shall summarise those facts which are frequently used in this paper.
Axiom systems for first order logic with finitely many variables
Authors: Johnson James S.
Published: May 2006

J. D. Monk has shown that for first order languages with finitely many variables there is no finite set of schema which axiomatizes the universally valid formulas. There are such finite sets of schema which axiomatize the formulas valid in all structures of some fixed finite size.
Chang's conjecture and powers of singular cardinals
Authors: Magidor Menachem
Published: May 2006

In [2] Galvin and Hajnal showed, as a corollary to a more general result, that if , is a strong limit cardinal, then . They established similar bounds for powers of singular cardinals of cofinality greater than ω. Jech and Prikry in [3] showed that the Galvin-Hajnal bound can be improved if we assume that ω1 carries an ω2 saturated ω1 complete, nontrivial ideal. (See [7] for definitions), namely: under the given assumption provided is a strong limit cardinal.

In this paper we show that the same conclusion can be derived from Chang's Conjecture (see below) which is, at least consistencywise, a weaker assumption than the existence of an ω2 saturated ideal on ω1. We do not know if assumptions like these are necessary for obtaining the result.

Our notations and terminology should be understood by any reader acquainted with set theory. Chang's Conjecture is the following model theoretic assumption introduced by C. C. Chang:

which is deciphered as follows: Every structure 〈A, R,…〉 in a countable type where ∣A∣ = ω2, R ⊆ A, ∣R∣ = ω1 has an elementary substructure: 〈A′,R′,…〉 where ∣A′∣ = ω1 and ∣R′∣ = ω0. The consistency of Chang's Conjecture modulo the existence of Ramsey cardinals is claimed in [5].
An interpolation lemma for the pure implicational calculus
Authors: Edelstein Roy
Published: May 2006

Although a variety of proofs are available for the Craig-Lyndon Interpolation Lemma, they all seem to make essential use of negation, with the result that they are inapplicable to deductive theories in which negation cannot be expressed. It is here shown that this use of negation can be avoided by extending the Interpolation Lemma to the pure implicational calculus PCI.

Determinate Parameter Lemma. For each formula A, ⊨PA ⊃ A for some sentence parameter PA occurring in A.

Proof. By induction on the construction of A.

Interpolation Lemma For PCI. Let Γ be the set of sentence parameters common to A and C.If ⊨A ⊃ and C is not valid, then there is a formula B containing no sentence parameter not in Y such that ⊨A ⊃ B and ⊨B ⊃ C.

Proof. Since ⊨PA ⊃ A by the Determinate Parameter Lemma and ⊨A ⊃ C, ⊨PA ⊃ C. But C is by hypothesis an invalid formula, so PA must occur in C as well as in A. Thus PA Є Γ.
Countable initial segments of the degrees of unsolvability
Authors: Lachlan A. H. , Lebeuf R.
Published: May 2006

In this paper we show that any countable upper semilattice with zero can be embedded as an initial segment of the degrees of unsolvability. This provides a characterization of the order types of the countable initial segments of the degrees since any such initial segment is trivially an initial segment of a countable upper semilattice. Let a segment S of the degrees be a set of degrees such that, if a, b Є S and a < c < b, then c Є S. One may readily observe that our result also characterizes the order types of all countable segments of the degrees of unsolvability.
Derived rules of inference related to the continuity of effective operations
Authors: Beeson Michael J.
Published: May 2006

In [B1] and [B2] we have shown that the classical theorems on the continuity of effective operations are not derivable in various constructive formal systems. The purpose of this paper is to establish that these systems are closed under the corresponding rules of inference, which have the form: If e can be proved to be (the index of) an effective operation, then e can be proved to be continuous. In fact we establish closure under apparently stronger rules of the form, if e can be proved to be an effective operation, then e* can be proved to be (the index of) a modulus of continuity for e, where e* is canonically obtained from e.

We again deal with two kinds of effective operations: (i) partial operations on partial arguments, and (ii) total operations on total arguments. The continuity theorem for operations of kind (i) is due to Myhill-Shepherdson [MS] and is called MS; for kind (ii) is due to Kreisel, Lacombe, and Shoenfield [KLS] and is called KLS. We also deal with effective operations on the (recursive) real numbers, which are of kind (ii). In [B1], [B2] it is shown that KLS and MS are derivable in in-tuitionistic arithmetic HA from Markov's principle MP (this follows from examination of the classical proofs); that they do not imply MP in HA; and that they are not derivable in HA. (These theorems remain true when HA is replaced by various stronger systems.) The derived rules to be established in this paper therefore represent nontrivial closure properties of the systems to which they apply.
Uniformly defined descending sequences of degrees
Authors: Friedman Harvey
Published: May 2006

This paper answers some questions which naturally arise from the Spector-Gandy proof of their theorem that the π11 sets of natural numbers are precisely those which are defined by a Σ11 formula over the hyperarithmetic sets. Their proof used hierarchies on recursive linear orderings (H-sets) which are not well orderings. (In this respect they anticipated the study of nonstandard models of set theory.) The proof hinged on the following fact. Let e be a recursive linear ordering. Then e is a well ordering if and only if there is an H-set on e which is hyperarithmetic. It was implicit in their proof that there are recursive linear orderings which are not well orderings, on which there are H-sets. Further information on such nonstandard H-sets (often called pseudohierarchies) can be found in Harrison [4]. It is natural to ask: on which recursive linear orderings are there H-sets?

In Friedman [1] it is shown that there exists a recursive linear ordering e that has no hyperarithmetic descending sequences such that no H-set can be placed on e. In [1] it is also shown that if e is a recursive linear ordering, every point of which has an immediate successor and either has finitely many predecessors or is finitely above a limit point (heretofore called adequate) such that an H-set can be placed on e, then e has no hyperarithmetic descending sequences. In a related paper, Friedman [2] shows that there is no infinite sequence xn of codes for ω-models of the arithmetic comprehension axiom scheme such that each xn+ 1 is a set in the ω-model coded by xn, and each xn+1 is the unique solution of P(xn, xn+1) for some fixed arithmetic P.
Large and small existentially closed structures
Authors: Simmons H.
Published: May 2006

The generic structures introduced by Abraham Robinson are now well established in model theory. Anyone who works with these structures soon begins to feel that, in some sense, the infinite generic structures are large and the finite generic structures are small. Here ‘large’ and ‘small’ do not refer to the cardinality of the structures but are used in the way we describe saturated structures as large and atomic structures as small. In this paper I isolate what I consider to be the large and small existentially closed (e.c.) structures and attempt to determine their role in the class of all e.c. structures.

In the usual context of model theory we are concerned with elementary embeddings and all formulas. E.c. structures are concerned with all embeddings and ∃1-formulas. Thus we need to look at ∃1-analogues of saturated and atomic structures. These ∃1-saturated structures have been around for some time; they are just the existentially universal structures. The corresponding ∃1-atomic structures are not new here (they appear in [8]) but I believe that this paper will add much to the understanding of them.

The bulk of this paper is in §§2 and 4. §2 deals with ∃1-atomic structures, and §4 is concerned with the ∃1-analogues of several results in Vaught's paper [12].

A similar program has been carried out by Pouzet in [6], [7], [8]; however, there the significance of e.c. and e.c. structures is not realized and consequently some of the simplicity of the situation is lost.
Projective planes of infinite but isolic order
Authors: Dekker J. C. E.
Published: May 2006

The main purpose of this paper is to show how partial recursive functions and isols can be used to generalize the following three well-known theorems of combinatorial theory.

(I) For every finite projective plane Π there is a unique number n such that Π has exactly n2 + n + 1 points and exactly n2 + n + 1 lines.

(II) Every finite projective plane of order n can be coordinatized by a finite planar ternary ring of order n. Conversely, every finite planar ternary ring of order n coordinatizes a finite projective plane of order n.

(III) There exists a finite projective plane of order n if and only if there exist n − 1 mutually orthogonal Latin squares of order n.
Equivalence of some definitions of recursion in a higher type object
Authors: Lowenthal F.
Published: May 2006

In [4] Kleene gave a definition of recursive functionals of finite type. Later Sacks [5] and Harrington [2] gave definitions of recursion in normal functionals of finite type. These definitions, that Sacks and Harrington assumed equivalent as far as normal objects are concerned, are nevertheless very different: Kleene's definition is given in terms of an inductive definition; Sacks uses simultaneously a hierarchy (the SσF's) and induction on the ordinals and on the type; Harrington's universe does not use the induction on the type but uses a hierarchy as Shoenfield [6]. In this paper we prove in detail that, as was expected, the three definitions are equivalent.
Copeland algebras
Authors: Demaree Daniel B.
Published: May 2006

It is well known that the laws of logic governing the sentence connectives—“and”, “or”, “not”, etc.—can be expressed by means of equations in the theory of Boolean algebras. The task of providing a similar algebraic setting for the full first-order predicate logic is the primary concern of algebraic logicians. The best-known efforts in this direction are the polyadic algebras of Halmos (cf. [2]) and the cylindric algebras of Tarski (cf. [3]), both of which may be described as Boolean algebras with infinitely many additional operations. In particular, there is a primitive operator, cκ, corresponding to each quantification, ∃υκ. In this paper we explore a version of algebraic logic conceived by A. H. Copeland, Sr., and described in [1], which has this advantage: All operators are generated from a finite set of primitive operations.

Following the theory of cylindric algebras, we introduce, in the natural way, the classes of Copeland set algebras (SCpA), representable Copeland algebras (RCpA), and Copeland algebras of formulas. Playing a central role in the discussion is the set, Γ, of all equations holding in every set algebra. The reason for this is that the operations in a set algebra reflect the notion of satisfaction of a formula in a model, and hence an equation expresses the fact that two formulas are satisfied by the same sequences of objects in the model. Thus to say that an equation holds in every set algebra is to assert that a certain pair of formulas are logically equivalent.
Negative solution of the decision problem for sentences true in every subalgebra of 〈N, +〉
Authors: Mckenzie Ralph
Published: May 2006

It was shown by Taiclin [6], and independently announced by Tarski [7], that the elementary theory of commutative cancellation semigroups is hereditarily undecidable. In his proof Tarski exhibited a subsemigroup of 〈N, ·〉, the natural numbers with multiplication, whose theory is both hereditarily and essentially undecidable. (The details of his construction were published by V. H. Dyson [1].) In connection with these results, Tarski suggested to the author that it would be of interest to solve the decision problem for the theory K which consists of all elementary sentences which are true in every subalgebra (i.e. every subsemigroup) of 〈N, +〉. The object of this note is to prove that the theory K is hereditarily undecidable.
-arithmetic and transfinite induction
Authors: Rose H. E.
Published: May 2006

A hierarchy of systems of quantifier-free elementary recursive arithmetics, based on the Grzegorczyk hierarchy of functions, was set up in [2] and some meta-mathematical properties of these systems were developed. The Grzegorczyk hierarchy has been extended recently, mainly by Löb and Wainer [5], and our metamathematical developments may be similarly extended; the αth member of this hierarchy of formal systems will be denoted -arithmetic throughout. The main result in [2] was: For α > 1, -arithmetic can be proved consistent in -arithmetic. In this paper we shall continue this work in particular, beginning with this consistency result, we shall find (for α > 1) the order type of the weakest simple transfinite induction scheme which is independent of -arithmetic, thus giving a ‘measure of the complexity of derivations’ of these systems. For example we shall show that transfinite induction on a sequence of type ωω is a nonderivable rule of primitive recursive arithmetic (-arithmetic). This particular result was proved by Guard in [4] by a specialisation of a version of Gentzen's proof that ∈0-transfinite induction is independent of some standard formal systems of arithmetic with quantifiers. These methods can be adapted to our hierarchy but require what we might term an ‘ωω-jump’—that is if β is the largest ordinal for which transfinite induction up to β is derivable in the system in question then a scheme of transfinite induction up to β·ωω is independent. The proof presented in this paper requires only an ‘ω-jump’ and allows more precise results to be obtained for the systems in the extended Grzegorczyk hierarchy; it is also more direct and less proof-theoretic in character. We show that the consistency of -arithmetic (for α > 1) can be proved in a system obtained by adding to -arithmetic a transfinite induction scheme up to ω2, and that this induction scheme can be adapted to obtain the required result by increasing the ordinal and simultaneously decreasing the complexity of the functions involved in the induction scheme (detailed definitions of these concepts will be given in the next section).
Recursively presentable prime models
Authors: Harrington Leo
Published: May 2006

It is well known that a decidable theory possesses a recursively presentable model. If a decidable theory also possesses a prime model, it is natural to ask if the prime model has a recursive presentation. This has been answered affirmatively for algebraically closed fields [5], and for real closed fields, Hensel fields and other fields [3]. This paper gives a positive answer for the theory of differentially closed fields, and for any decidable ℵ1-categorical theory.

The language of a theory T is denoted by L(T). All languages will be presumed countable. An x-type of T is a set of formulas with free variables x, which is consistent with T and which is maximal in this property. A formula with free variables x is complete if there is exactly one x-type containing it. A type is principal if it contains a complete formula. A countable model of T is prime if it realizes only principal types. Vaught has shown that a complete countable theory can have at most one prime model up to isomorphism.

If T is a decidable theory, then the decision procedure for T equips L(T) with an effective counting. Thus the formulas of L(T) correspond to integers. The integer a formula φ(x) corresponds to is generally called the Gödel number of φ(x) and is denoted by ⌜φ(x)⌝. The usual recursion theoretic notions defined on the set of integers can be transferred to L(T). In particular a type Γ is recursive with index e if {⌜φ⌝.; φ ∈ Γ} is a recursive set of integers with index e.
Decidability of some intuitionistic predicate theories
Authors: Gabbay Dov M.
Published: May 2006

Suppose T is a first order intuitionistic theory (more precisely, a theory of Heyting's predicate calculus, e.g., abelian groups, one unary function, dense linear order, etc.) presented to us by a set of axioms (denoted also by) T.

Question. Is T decidable?

One knows that if the classical counterpart of T (i.e., take the same axioms but with the classical predicate calculus as the underlying logic) is not decidable, then T cannot be decidable. The problem remains for theories whose classical counterpart is decidable. In [8], sufficient conditions for undecidability were given, and several intuitionistic theories such as abelian groups and unary functions (both with decidable equality) were shown to be undecidable. In this note we show decidability results (see Theorems 1 and 2 below), and compare these results with the undecidability results previously obtained. The method we use is the reduction-method, described fully in [12] and widely applied in [3], which is applied here roughly as follows:

Let T be a given theory of Heyting's predicate calculus. We know that Heyting's predicate calculus is complete for the Kripke-model type of semantics. We choose a class M of Kripke models for which T is complete, i.e., all axioms of T are valid in any model of the class and whenever φ is not a theorem of T, φ is false in some model of M.
Imbedding of the quantum logic in the modal system of Brower
Authors: Dishkant Herman
Published: May 2006

We lean upon the usual variant of the logic of quantum mechanics [1]. Here the propositions correspond to the results of the quantum experiments. A beautiful essay [2] may be connected with a conservation of semantics. But we try to broaden the semantics, admitting propositions about the possibility of results of experiments. Doing so, we fulfil the old wish of W. A. Fock, who attracts our attention to the importance of the modal categories for the interpretation of the quantum theory [3].

We begin with the formal description of the modal system Br+. The alphabet contains the signs ~, ∨ and Ↄ (negation, alternative and the sign of necessity), the set V of the prepositional variables and parentheses. The rules of formation are: if A ∈ V, then A is a proposition; if X and Y are propositions, then ~ X, X ∨ Y and Ↄ X are propositions also; there are no other propositions. ℬ will design the set of all propositions.

The rules of transformation are the following:

.

Here X, Y ∈ ℬ. The sign ⊨ denotes the derivability in Br+ (in one step here).
On finite lattices of degrees of constructibility
Authors: Adamowicz Zofia
Published: May 2006

We shall prove the following theorem:

Theorem. For any finite lattice there is a model of ZF in which the partial ordering of the degrees of constructibility is isomorphic with the given lattice.

Let M be a standard countable model of ZF satisfying V = L. Let K be the given finite lattice. We shall extend M by forcing.

The paper is divided into two parts. The first part concerns the definition of the set of forcing conditions and some properties of this set expressible without the use of generic filters.

We define first a representation of a lattice and then the set of conditions. In Lemmas 1, 2 we show that there are some canonical isomorphisms between some conditions and that a single condition has some canonical automorphisms.

In Lemma 3 and Definition 7 we show some methods of defining conditions. We shall use those methods in the second part to define certain conditions with special properties.

Lemma 4 gives a connection between the sets P and Pk (see Definitions 4 and 5). It is next employed in the second part in Lemma 10 in an essential way.

Indeed, Lemma 10 is necessary for Lemma 13, which is the crucial point of the whole construction. Lemma 5 is also employed in Lemma 13 (exactly in its Corollary).

The second part of the paper is devoted to the examination of the structure of degrees of constructibility in a generic model. First, we show that degrees of some “sections” of a generic real (Definition 9) form a lattice isomorphic with K. Secondly, we show that there are no other degrees in the generic model; this is the most difficult property to obtain by forcing. We prove, in two stages, that it holds in our generic models. We first show, by using special properties of the forcing conditions, that sets of ordinal numbers have no other degrees. Then we show that the degrees of sets of ordinals already determine the degrees of other sets.
A Δ02 theory of regressive isols
Authors: Ellentuck Erik
Published: May 2006

We examine the action of unary functions on the regressive isols. A manageable theory is produced and we find that such a function maps ⋀R into ⋀ if and only if it is eventually R↑ increasing and maps ⋀R into ⋀R if and only if it is eventually recursive increasing. Our paper concludes with a discussion of other methods for extending functions to ⋀R.
Two variable implicational calculi of prescribed many-one degrees of unsolvability
Authors: Hughes Charles E.
Published: May 2006

A constructive proof is given which shows that every nonrecursive r.e. many-one degree is represented by the family of decision problems for partial implicational propositional calculi whose well-formed formulas contain at most two distinct variable symbols.
Ordinal recursion, and a refinement of the extended Grzegorczyk hierarchy
Authors: Wainer S. S.
Published: May 2006

It is well known that iteration of any number-theoretic function f, which grows at least exponentially, produces a new function f′ such that f is elementary-recursive in f′ (in the Csillag-Kalmar sense), but not conversely (since f′ majorizes every function elementary-recursive in f). This device was first used by Grzegorczyk [3] in the construction of a properly expanding hierarchy {ℰn: n = 0, 1, 2, …} which provided a classification of the primitive recursive functions. More recently it was shown in [7] how, by iterating at successor stages and diagonalizing over fundamental sequences at limit stages, the Grzegorczyk hierarchy can be extended through Cantor's second number-class. A problem which immediately arises is that of classifying all recursive functions, and an answer to this problem is to be found in the general results of Feferman [1]. These results show that although hierarchies of various types (including the above extensions of Grzegorczyk's hierarchy) can be produced, which range over initial segments of the constructive ordinals and which do provide complete classifications of the recursive functions, these cannot be regarded as classifications “from below”, since the method of assigning fundamental sequences at limit stages must be highly noneffective. We therefore adopt the more modest aim here (as in [7], [12], [14]) of characterising certain well-known (effectively generated) subclasses of the recursive functions, by means of hierarchies generated in a natural manner, “from below”.
Almost disjoint sets and Martin's axiom
Authors: Wage Michael L.
Published: May 2006

We present a number of results involving almost disjoint sets and Martin's axiom. Included is an example, due to K. Kunen, of a c.c.c. partial order without property K whose product with every c.c.c. partial order is c.c.c.
Intensional logic in extensional language
Authors: Parsons Charles
Published: May 2006

Frege's conception of reference has been interpreted as calling for a completely extensional language, on the grounds that according to it the reference of a complex expression is a function of the references of its parts. To meet this demand and still allow for oblique contexts, one uses Frege's idea that in an oblique context an expression has as reference what is ordinarily its sense.

A purely extensional formalized intensional logic was constructed in the 1940s by Alonzo Church: his logic of sense and denotation [2], [3]. The ambiguity of the “direct” and “oblique” reference of an expression is avoided. For each denoting expression A there is an expression A denoting its sense, which then replaces A in “oblique” contexts. A consequence of this approach is that for each natural number n, in a context with n-fold embedding of intensional operators A is paraphrased by the result of iterating the operation Ã n times, so that A is treated as if it were infinitely ambiguous. Church's underlying logic is a simple theory of types, in fact just an expansion of the extensional typed λ-calculus so as to contain ωth-order predicate logic.

In this paper we study a variant of Church's logic that admits a possible-worlds semantics, i.e. a version of Church's Alternative (2) [3, pp. 4–5], [4]. This type of logic has been perspicuously formulated by David Kaplan [11], [12], and we follow his version.

In §1 we formulate Kaplan's logic L-Church-O with two alterations: the typed λ-calculus is replaced by combinators, and unlike Kaplan (but like Church) we allow concepts (that is, senses) that are not concepts of anything.
A classification of jump operators
Authors: Steel John R.
Published: May 2006

The structure (D, ≤) of the Turing degrees under Turing reducibility is quite complicated. This is true even if we restrict our attention to the substructure (R, ≤) of r.e. degrees. However, the theorems which imply that these structures are complicated all involve ad hoc constructions of sets having the desired reducibility relations. The complexity disappears when we turn to degrees occurring in nature. Of the degrees in R, only 0 and 0′ seem natural. In D, only 0, 0′, 0″, …, 0ω, 0ω+1, … (and on into the transfinite) seem natural. Thus the natural degrees appear to be wellordered, with successors given by Turing jump.

If this is true, one would like to prove it. Of course the first problem is to make the concept of naturalness more precise. The following requirements seem plausible: a natural degree should be definable, its definition should relativise to an arbitrary degree, and this relativisation should preserve reducibility relations among natural degrees. Thus to each natural degree c is associated a definable fc: D → D so that fc(0) = c and ∀d(d ≤ fc(d)). Moreover, b ≤ c iff ∀d(fb(d) ≤, fc(d)). To be specific, let us take the definability of fc to mean that fc ∈ L(R).

If P is a property of degrees, we say P holds almost everywhere (a.e.) iff ∃c∀d ≥: c P(d). For f, g: D → D, let f ≤mg iff f(d) ≤ g(d) a.e. Define f′ by f′(d) = f{d)′, and let M = {f: D → D/f ∈ L(R) ∧ d ≤ f(d) a.e.}. The following conjecture is due to D. A. Martin:

Conjecture. M is prewellordered by ≤m. If f ∈ M has rank α in ≤m, then f′ has rank α + 1.
La logique des topos
Authors: Boileau André , Joyal André
Published: May 2006

Les synthèses nouvelles par le rapprochement de disciplines mathématiques différentes constituent des événements remarquables dans l'histoire des mathématiques. Une telle synthèse semble émerger actuellement du rapprochement de:

(1) La géométrie algébrique sous la forme élaborée par Grothendieck.

(2) La logique formelle.

Le point de contact s'est effectué aux environs de 1970 par W. Lawvere et M. Tierney et l'instrument de rapprochement a été la théorie des catégories, plus particulièrement la théorie des faisceaux. Depuis ce moment, une dialectique incessante imprime un mouvement dynamique à toute une série de recherches qui visent à rapprocher les méthodes suivantes:

(1) Mathématique intuitionniste.

(2) Forcing de Cohen et Robinson.

(3) Logique algébrique.

(4) Géométrie algébrique.

(5) Géométrie différentielle et analytique.

(6) Topologie algébrique: cohomologie, homotopie.

(7) Théorie de Galois.

Certains rapprochements sont dans un stade avancé, d'autres encore embryonnaires: (6) ↔ (3).

La structure centrale qui joue le rôle d'élément provocateur et unificateur est celle de topos. Avant d'être axiomatisée par Lawvere, celle-ci a été étudiée systématiquement par l'école de Grothendieck (voir [1]) et c'est dans le contexte de la géométrie algébrique qu'elle fit son apparition. Dans cet article nous utiliserons cependant la définition de Lawvere telle qu'améliorée par Mikkelsen [12] et Kock [8].

Le but de ce travail est de présenter une version (au sens de la logique formelle) du concept de topos et d'examiner brièvement les rapports entre la théorie des topos, la logique et les mathématiques. Cette version a déjà été exposée par l'un des auteurs lors du Séminaire de Mathématiques Supérieures de l'Université de Montréal, à l'été 1974. Depuis elle a fait l'objet d'une thèse où elle a été améliorée et sa cohérence vérifiée [2]. Des systèmes différents ont été proposés simultanément par Fourman [4] et Coste [3].
On amalgamations of languages with Magidor-Malitz quantifiers
Authors: Morgenstern Carl F.
Published: May 2006

In this paper we indicate how compact languages containing the Magidor-Malitz quantifiers Qκn in different cardinalities can be amalgamated to yield more expressive, compact languages.

The language Lκ<ω, originally introduced by Magidor and Malitz [9], is a natural extension of the language L(Q) introduced by Mostowski and investigated by Fuhrken [6], [7], Keisler [8] and Vaught [13]. Intuitively, Lκ<ω is first-order logic together with quantifiers Qκn (n ∈ ω) binding n free variables which express “there is a set X of cardinality κ such than any n distinct elements of X satisfy …”, or in other words, iff the relation on determined by φ contains an n-cube of cardinality κ. With these languages one can express a variety of combinatorial statements of the type considered by Erdös and his colleagues, as well as concepts in universal algebra which are beyond the scope of first-order logic. The model theory of Lκ<ω has been further developed by Badger [1], Magidor and Malitz [10] and Shelah [12].

We refer to a language as being < κ compact if, given any set of sentences Σ of the language, if Σ is finitely satisfiable and ∣Σ∣ < κ, then Σ has a model. The phrase countably compact is used in place of <ℵ1 compact.
Antitheses in systems of relevant implication
Authors: Porte Jean
Published: May 2006

There are several ways for a formula to be “the contrary” of a thesis. When there is a negation we could call a formula an “antithesis” if it is the negation of a thesis—or its negation is a thesis—both properties being equivalent when the negation is classical.

When there is no negation or when the connective called “negation” is very different from classical negation, we are forced to look for a different notion.

Whence:

Definition 1. In a propositional calculus, a substitution antithesis—or, for short, an s-antithesis—is a formula no instance of which is a thesis.

There is another kindred notion, but only for calculi for which a deducibility has been defined:

Definition 2. A deduction antithesis—for short, a d-antithesis—is a formula from which every formula is deducible.

Both notions have been used in the study of the deducibility of certain systems (see below, §4).

In the classical propositional calculus, the s-antitheses are simply the formulas which are negations of theses (and whose negations are theses).

In S5 and in all the weaker modal propositional calculi, there are s-antitheses which are not negations of theses (and whose negations are not theses); typical examples are ¬(Mp ⊃ Lp) and ¬(p ⊃ Lp) where p is a propositional variable, and ⊃, ¬, M and L are respectively material implication, negation, possibility and necessity (see [8]).
A consistent combinatory logic with an inverse to equality
Authors: Fitch Frederic B.
Published: May 2006

In a previous paper [9] a demonstrably consistent type-free system of combinatory logic CΔ was presented. This system contained a moderately strong exten-sionality principle, the usual equations of combinatory logic, Boolean propositional connectives, unrestricted quantifiers, an unrestricted abstraction principle (“comprehension axiom”), and a limited principle of excluded middle. It also contained elementary arithmetic in its entirety, avoiding arithmetical Gödel incompleteness [14] by being ω-complete. CΔ probably can be shown to contain certain important parts of mathematical analysis, such as the theory of continuous functions, which are contained by the somewhat similar (but nonextensional) system K′ [6], [7]. A stronger system CΓ, having these same properties and more, will be formulated in the present paper. Elsewhere [13] it will be shown that the system Q of my book, Elements of combinatory logic (Yale University Press, New Haven and London, 1974), referred to below as ECL, is essentially a subsystem of CΓ, so that the consistency of CΓ guarantees that of Q.

CΓ will be stronger than both CΔ and Q in having an operator ‘ɿ’ (inverted Greek iota) which denotes the inverse of equality in the sense that ‘ɿ(= a) = a’ is a theorem of the system. Thus ‘ɿ’ denotes a function or operator which operates on a unit class to give the only member of that class. (Here ‘=a’ denotes the unit class whose only member is denoted by ‘a’.) If uninverted Greek iota, ‘ι’, is used as an abbreviation for ‘=’, the above equation could be written as ‘ɿ(ιa) = a’. Here ‘ιa’ is analogous to Bertrand Russell's well-known notation ‘ιa’, denoting a unit class. This same operator ‘ɿ’ makes it possible to transform one-many or many-one relations into the corresponding functions or operators, a kind of transformation not usually available in systems of combinatory logic [1], [2]. It also provides a method for restricting functions by restricting the corresponding relations.
Classifying positive equivalence relations
Authors: Bernardi Claudio , Sorbi Andrea
Published: May 2006

Given two (positive) equivalence relations ~1, ~2 on the set ω of natural numbers, we say that ~1 is m-reducible to ~2 if there exists a total recursive function h such that for every x, y ∈ ω, we have x ~1y iff hx ~2hy. We prove that the equivalence relation induced in ω by a positive precomplete numeration is complete with respect to this reducibility (and, moreover, a “uniformity property” holds). This result allows us to state a classification theorem for positive equivalence relations (Theorem 2). We show that there exist nonisomorphic positive equivalence relations which are complete with respect to the above reducibility; in particular, we discuss the provable equivalence of a strong enough theory: this relation is complete with respect to reducibility but it does not correspond to a precomplete numeration.

From this fact we deduce that an equivalence relation on ω can be strongly represented by a formula (see Definition 8) iff it is positive. At last, we interpret the situation from a topological point of view. Among other things, we generalize a result of Visser by showing that the topological space corresponding to a partition in e.i. sets is irreducible and we prove that the set of equivalence classes of true sentences is dense in the Lindenbaum algebra of the theory.
Degrees of recursively enumerable topological spaces
Authors: Kalantari Iraj , Remmel J. B.
Published: May 2006

In [5], Metakides and Nerode introduced the study of recursively enumerable (r.e.) substructures of a recursively presented structure. The main line of study presented in [5] is to examine the effective content of certain algebraic structures. In [6], Metakides and Nerode studied the lattice of r.e. subspaces of a recursively presented vector space. This lattice was later studied by Kalantari, Remmel, Retzlaff and Shore. Similar studies have been done by Metakides and Nerode [7] for algebraically closed fields, by Remmel [10] for Boolean algebras and by Metakides and Remmel [8] and [9] for orderings. Kalantari and Retzlaff [4] introduced and studied the lattice of r.e. subsets of a recursively presented topological space. Kalantari and Retzlaff consideredX, a topological space with ⊿, a countable basis. This basis is coded into integers and with the help of this coding, r.e. subsets ofωgive rise to r.e. subsets ofX. The notion of “recursiveness” of a topological space is the natural next step which gives rise to the question of what should be the “degree” of an r.e. open subset ofX? It turns out that any r.e. open set partitions ⊿; into four sets whose Turing degrees become central in answering the question raised above.

In this paper we show that the degrees of the elements of the partition of ⊿ imposed by an r.e. open set can be “controlled independently” in a sense to be made precise in the body of the paper. In [4], Kalantari and Retzlaff showed that givenAany r.e. set andany r.e. open subset ofX, there exists an r.e. open set ℋ which is a subset ofand is dense in(in a topological sense) and in whichAis coded. This shows that modulo a nowhere dense set, an r.e. open set can become as complicated as desired. After giving the general technical and notational machinery in §1, and giving the particulars of our needs in §2, in §3 we prove that the set ℋ described above could be made to be precisely of degree ofA. We then go on and establish various results (both existential and universal) on the mentioned partitioning of ⊿. One of the surprising results is that there are r.e. open sets such that every element of partitioning of ⊿ is of a different degree. Since the exact wording of the results uses the technical definitions of these partitioning elements, we do not summarize the results here and ask the reader to examine §3 after browsing through §§1 and 2.
Prime and atomic models
Authors: Knight Julia F.
Published: May 2006

This paper gives some simple existence results on prime and atomic models over sets. It also contains an example in which there is no prime model over a certain set even though there is an atomic model over the set. The existence results are “local” in that they deal with just one set rather than all sets contained in models of some theory. For contrast, see the “global” results in [6] or [7, p. 200].

Throughout the paper, L is a countable language, and T is a complete L-theory with infinite models. There is a “large” model of T that contains the set X and any other sets and models to be used in a particular construction of a prime or atomic model over X.

A model is said to be prime over X if and every elementary monomorphism on X can be extended to an elementary embedding on all of . This notion is used in a variety of ways in model theory. It aids in distinguishing between models that are not isomorphic, as in Vaught [10]. It also aids in showing that certain models are isomorphic, as in Baldwin and Lachlan [1].
Σ1-compactness in languages stronger than
Authors: Cutland Nigel
Published: May 2006

One of the main results of Barwise [2] (see also [7, Chapter VIII]) showed that the s – reflection principle for a set A is equivalent to Σ1-compactness of . Here A is any transitive p.r. closed set, and is the infinitary language on A which allows conjunction and disjunction over arbitrary sets Φ Є A, and finite quantification.

In this paper we consider languages , where B is a Δ0 subset of A, which is like but we allow quantifiers ∀x and ∃x where x is any set of variables indexed by an element of B. A treatment similar to that of [2] for establishes a sufficient, and in some cases necessary, condition for to be Σ1-compact. The use of infinitary Skolem functions is intrinsic to the method, so to avoid a separate development of the rudiments of the Skolem language we actually define to have b-ary relation and function symbols for every b Є B.
More about uniform upper bounds on ideals of turing degrees
Authors: Hodes Harold T.
Published: May 2006

Let I be a countable jump ideal in = 〈The Turing degrees, ≤〉. The central theorem of this paper is:

a is a uniform upper bound on I iff a computes the join of an I-exact pair whose double jump a(1) computes.

We may replace “the join of an I-exact pair” in the above theorem by “a weak uniform upper bound on I”.

We also answer two minimality questions: the class of uniform upper bounds on I never has a minimal member; if ⋃I = Lα[A] ⋂ ωω for α admissible or a limit of admissibles, the same holds for nice uniform upper bounds.

The central technique used in proving these theorems consists in this: by trial and error construct a generic sequence approximating the desired object; simultaneously settle definitely on finite pieces of that object; make sure that the guessing settles down to the object determined by the limit of these finite pieces.
A filter lambda model and the completeness of type assignment
Authors: Barendregt Henk , Coppo Mario , Dezani-Ciancaglini Mariangiola
Published: May 2006

In [6, p. 317] Curry described a formal system assigning types to terms of the type-free λ-calculus. In [11] Scott gave a natural semantics for this type assignment and asked whether a completeness result holds.

Inspired by [4] and [5] we extend the syntax and semantics of the Curry types in such a way that filters in the resulting type structure form a domain in the sense of Scott [12]. We will show that it is possible to turn the domain of types into a λ-model, among other reasons because all λ-terms possess a type. This model gives the completeness result for the extended system. By a conservativity result the completeness for Curry's system follows.

Independently Hindley [8], [9] has proved both completeness results using term models. His method of proof is in some sense dual to ours.

For λ-calculus notation see [1].