bluuebunny/crossref_metadata_2025 huggingface dataset:
On the existence of extensional partial combinatory algebras
Authors: Bethke Ingemarie
Published: May 2006

The principal aim of this paper is to present a construction method for nontotal extensional combinatory algebras. This is done in §2. In §0 we give definitions of some basic notions for partial combinatory algebras from which the corresponding notions for (total) combinatory algebras are obtained as specializations. In §1 we discuss some properties of nontotal extensional combinatory algebras in general. §2 describes a “partial” variant of reflexive complete partial orders yielding nontotal extensional combinatory algebras. Finally, §3 deals with properties of the models constructed in §2, such as incompletability, having no total submodel and the pathological behaviour with respect to the interpretation of unsolvable λ-terms.
Quantum logic and the classical propositional calculus
Authors: Malhas Othman Qasim
Published: May 2006

In much the same way that it is possible to construct a model of hyperbolic geometry in the Euclidean plane, it is possible to model quantum logic within the classical propositional calculus.
A contractionless semilattice semantics
Authors: Giambrone Steve , Meyer Robert K. , Urquhart Alasdair
Published: May 2006

Semilattice semantics for relevant logics were discovered independently by Routley and Urquhart over 10 years ago. A semilattice semantics was first published in [10], where the weak theory of implication of [8] and [3] (i.e., R →, the pure implication fragment of the system R of relevant implication) is shown to be consistent and complete with respect to it. That result was extended in [11], But the semantics is explored in greatest detail in [12]. As reported in [4], Fine outfitted the positive semilattice semantics for R+ with a suitable Hilbert-style axiomatisation. (We refer to the system as ◡R+.) In 1980 Charlwood supplied a subscripted system of natural deduction. (See [1] and [2].) A subscripted Gentzen system was devised in [5] and [6].

Obviously, the central idea of the semilattice semantics is to impose relevant-style valuations on a semilattice (with an identity) used as the underlying model structure. However, in [12] the contractionless semantics are obtained (quite reasonably) by dropping the idempotence postulate and thus changing the relatively simple semilattice structure into a commutative monoid. Here we show that the semilattice structure can be regained for positive, contractionless relevant implication. Although we have no proofs as yet, we think that this semantics will pave the way for showing completeness for the corresponding subscripted Gentzen and natural deduction systems, as well as the Hilbert-style axiomatization, ◡RW+.
Alfred Tarski's work in set theory
Authors: Levy Azriel
Published: May 2006

Alfred Tarski started contributing to set theory at a time when the Zermelo-Fraenkel axiom system was not yet fully formulated and as simple a concept as that of the inaccessible cardinal was not yet fully defined. At the end of Tarski's career the basic concepts of the three major areas and tools of modern axiomatic set theory, namely constructibility, large cardinals and forcing, were already clearly defined and were in the midst of a rapid successful development. The role of Tarski in this development was somewhat similar to the role of Moses showing his people the way to the Promised Land and leading them along the way, while the actual entry of the Promised Land was done mostly by the next generation. The theory of large cardinals was started mostly by Tarski, and developed mostly by his school. The mathematical logicians of Tarski's school contributed much to the development of forcing, after its discovery by Paul Cohen, and to a lesser extent also to the development of the theory of constructibility, discovered by Kurt Gödel. As in other areas of logic and mathematics Tarski's contribution to set theory cannot be measured by his own results only; Tarski was a source of energy and inspiration to his pupils and collaborators, of which I was fortunate to be one, always confronting them with new problems and pushing them to gain new ground.

Tarski's interest in set theory was probably aroused by the general emphasis on set theory in Poland after the First World War, and by the influence of Wactaw Sierpinski, who was one of Tarski's teachers at the University of Warsaw. The very first paper published by Tarski, [21], was a paper in set theory.
Alfred Tarski's elimination theory for real closed fields
Authors: Van Den Dries Lou
Published: May 2006

Tarski made a fundamental contribution to our understanding of R, perhaps mathematics’ most basic structure. His theorem is the following.

To any formula ϕ(X1, …, Xm) in the vocabulary {0, 1, +, ·, <} one can effectively associate two objects: (i) a quantifier free formula (X1, …, Xm) in

(1) the same vocabulary, and (ii) a proofof the equivalence ϕ ↔ that uses only the axioms for real closed fields. (Reminder: real closed fields are ordered fields with the intermediate value property for polynomials.)

Everything in (1) has turned out to be crucial: that arbitrary formulas are considered rather than just sentences, that the equivalence ϕ ↔ holds in all real closed fields rather than only in R; even the effectiveness of the passage from ϕ to has found good theoretical uses besides firing the imagination.

We begin this survey with some history in §1. In §2 we discuss three other influential proofs of Tarski's theorem, and in §3 we consider some of the remarkable and totally unforeseen ways in which Tarski's theorem functions nowadays in mathematics, logic and computer science.

I thank Ward Henson, and in particular Wilfrid Hodges without whose constant prodding and logistic support this article would not have been written.
Alfred Tarski's work on general metamathematics
Authors: Blok W. J. , Pigozzi Don
Published: May 2006

In this essay we discuss Tarski's work on what he calledthe methodology of the deductive sciences, or more briefly, borrowing the terminology of Hilbert,metamathematics, The clearest statement of Tarski's views on this subject can be found in his textbookIntroduction to logic[41m].1Here he describes the tasks of metamathematics as “the detailed analysis and critical evaluation of the fundamental principles that are applied in the construction of logic and mathematics”. He goes on to describe what these fundamental principles are: All the expressions of the discipline under consideration must be defined in terms of a small group of primitive expressions that seem immediately understandable. Furthermore, only those statements of the discipline are accepted as valid that can be deduced by precisely defined and universally accepted means from a small set of axioms whose validity seems evident. The method of constructing a discipline in strict accordance with these principles is known as thedeductive method, and the disciplines constructed in this manner are calleddeductive systems. Since contemporary mathematical logic is one of those disciplines that are subject to these principles, it itself is a deductive science. Tarski then goes on to say:

“The view has become more and more common that the deductive method is the only essential feature by means of which the mathematical disciplines can be distinguished from all other sciences; not only is every mathematical discipline a deductive theory, but also, conversely, every deductive theory is a mathematical discipline”.

This identification of mathematics with the deductive sciences is in our view one of the distinctive aspects of Tarski's work. Another characteristic feature is his broad view of what constitutes the domain of metamathematical investigations. A clue to this aspect of his work can also be found in Chapter 6 ofIntroduction to logic. After a discussion of the notions of completeness and consistency, he remarks that the investigations concerning these topics were among the most important factors contributing to a considerable extension of the domain of methodological studies, and caused even a fundamental change in the whole character of the methodology of deductive sciences.
Philosophical implications of Tarski's work
Authors: Suppes Patrick
Published: May 2006

In his published work and even more in conversations, Tarski emphasized what he thought were important philosophical aspects of his work. The English translation of his more philosophical papers [56m] was dedicated to his teacher Tadeusz Kotarbiński, and in informal discussions of philosophy he often referred to the influence of Kotarbiński. Also, the influence of Leśniewski, his dissertation adviser, is evident in his early papers. Moreover, some of his important papers of the 1930s were initially given to philosophical audiences. For example, the famous monograph on the concept of truth ([33m], [35b]) was first given as two lectures to the Logic Section of the Philosophical Society in Warsaw in 1930. Second, his paper [33], which introduced the concepts of ω-consistency and ω-completeness as well as the rule of infinite induction, was first given at the Second Conference of the Polish Philosophical Society in Warsaw in 1927. Also [35c] was based upon an address given in 1934 to the conference for the Unity of Science in Prague; [36] and [36a] summarize an address given at the International Congress of Scientific Philosophy in Paris in 1935. The article [44a] was published in a philosophical journal and widely reprinted in philosophical texts. This list is of course not exhaustive but only representative of Tarski's philosophical interactions as reflected in lectures given to philosophical audiences, which were later embodied in substantial papers. After 1945 almost all of Tarski's publications and presentations are mathematical in character with one or two minor exceptions. This division, occurring about 1945, does not, however, indicate a loss of interest in philosophical questions but is a result of Tarski's moving to the Department of Mathematics at Berkeley. There he assumed an important role in the development of logic within mathematics in the United States.
Missionary mathematics
Authors: Poizat Bruno
Published: May 2006

Le plus souvent, la logique reste une discipline à la périphérie des mathématiques, qu’elle observe de l’extérieur, sans y pénétrer vraiment. C’est un discours sur les mathematiques qui ne dit rien au mathématicien; il n’y reconnait pas son activité favorite, ni ne croit qu’elle puisse avoir une influence sur sa pratique.

L’illustration la plus extrême de cette tradition, ce sont les “reverse mathematics” de Harvey Friedman, qui connaissent le succès que l’on sait. Je veux parler ici d’une tendance toute opposée, secrétée par les développements contemporains de la théorie des modèles, qui promet des positions beaucoup plus directes.

Elle se cristalise autour de l’étude des groupes stables; l’apparition de groupes n’a rien d’inattendu dans un contexte mathématiquement signifiant: un groupe, c’est ce qui garantit une structure non-triviale (ceci n’est pas un simple argument terroriste: il y a des théoremes pour le soutenir); quant à la stabilité, c’est une hypothèse de controle structurel, au large champ d’application, et qu’on pourra dépasser quand seront résolus les problèmes posés dans le cadre stable.
On a theory of weak implications
Authors: Okada Mitsuhiro
Published: May 2006

The purpose of this paper is to study logical implications which are much weaker than the implication of intuitionistic logic.

In §1 we define the system SI (system of Simple Implication) which is obtained from intuitionistic logic by restricting the inference rules of intuitionistic implication. The implication of the system SI is called the “simple implication” and denoted by ⊃, where the simple implication ⊃ has the following properties:

(1) The simple implication ⊃ is much weaker than the usual intuitionistic implication.

(2) The simple implication ⊃ can be interpreted by the notion of provability, i.e., we have a very simple semantics for SI so that a sentence A ⊃ B is interpreted as “there exists a proof of B from A”.

(3) The full-strength intuitionistic implication ⇒ is definable in a weak second order extension of SI; in other words, it is definable by help of a variant of the weak comprehension schema and the simple implication ⊃. Therefore, though SI is much weaker than the intuitionistic logic, the second order extension of SI is equivalent to the second order extension of the intuitionistic logic.

(4) The simple implication is definable in a weak modal logic MI by the use of the modal operator and the intuitionistic implication ⇒ with full strength. More precisely, A ⊃ B is defined as the strict implication of the form ◽(A ⇒ B).

In §1, we show (3) and (4). (2) is shown in §2 in a more general setting.

Semantics by introduction rules of logical connectives has been studied from various points of view by many authors (e.g. Gentzen [4], Lorentzen [5], Dummett [1], [2], Prawitz [8]. Martin-Löf [7], Maehara [6]). Among them Gentzen (in §§10 and 11 of [4]) introduced such a semantics in order to justify logical inferences and the mathematical induction rule. He observed that all of the inference rules of intuitionistic arithmetic, except for those on implication and negation, are justified by means of his semantics, but justification of the inference rules on implication and negation contains a circular argument for the interpretation by introduction rules, where the natural interpretation of A ⊃ B by ⊃-introduction rule is “there exists a proof of B from A ” (cf. §11 of Gentzen [4]).
A downward Löwenheim-Skolem theorem for infinitary theories which have the unsuperstability property
Authors: Grossberg Rami
Published: May 2006

We present a downward Löwenheim-Skolem theorem which transfers downward formulas from L∞,ω to , ω. The simplest instance is:

Theorem 1. Let λ > κ be infinite cardinals, and let L be a similarity type of cardinality κ at most. For every L-structure M of cardinality λ and every X ⊆ M there exists a model N ≺ M containing the set X of power ∣X∣ · κ such that for every pair of finite sequences a, b ∈ N

The following theorem is an application:

Theorem 2. Let λ<κ, T ∈ , ω, and suppose χ is a Ramsey cardinal greater than λ. If T has the (χ, , ω)-unsuperstability property, then T has the (χ, , ω)-unsuperstability property.
The interpretability logic of Peano arithmetic
Authors: Berarducci Alessandro
Published: May 2006

PA is Peano arithmetic. The formula InterpPA(α, β) is a formalization of the assertion that the theory PA + α interprets the theory PA + β (the variables α and β are intended to range over codes of sentences of PA). We extend Solovay's modal analysis of the formalized provability predicate of PA, PrPA(x), to the case of the formalized interpretability relation InterpPA(x, y). The relevant modal logic, in addition to the usual provability operator ‘□’, has a binary operator ‘⊳’ to be interpreted as the formalized interpretability relation. We give an axiomatization and a decision procedure for the class of those modal formulas that express valid interpretability principles (for every assignment of the atomic modal formulas to sentences of PA). Our results continue to hold if we replace the base theory PA with Zermelo-Fraenkel set theory, but not with Gödel-Bernays set theory. This sensitivity to the base theory shows that the language is quite expressive. Our proof uses in an essential way earlier work done by A. Visser, D. de Jongh, and F. Veltman on this problem.
Théories d'algèbres de Boole munies d'idéaux distingués. II
Authors: Touraille Alain
Published: May 2006

La première partie de cet article ([10], que nous désignerons par (I) dans la suite) était consacrée à la théorie élémentaire TX des algèbres de Boole munies d'idéaux distingués indéxés dans un ensemble X. On a vu que les idéaux définissables dans un modèle de Tx forment la sous-algèbre engendrée par les idéaux distingués de l'algèbre de Heyting des idéaux de munie de l'opérateur sa défini par sa(K) = {a: a/K est sans atome}, et que la théorie de peut être caractérisée par la structure composée de l'algèbre de Heyting des idéaux définissables munie de l'opérateur sa et des idéaux distingués, et par l'application qui à tout K de fait correspondre le nombre d'atomes de /K, pris dans N ⋃ {∞}.

Nous montrons maintenant que les structures possibles peuvent être définies de façon axiomatique en introduisant une classe équationnelle d'algèbres de Heyting munies d'une opération unaire, dites sa-algèbres de Heyting (en abrégé sa-AH), et en prouvant que cette classe est constituée des algèbres pouvant être plongées dans l'algèbre de Heyting des idéaux d'une algèbre de Boole, munie de l'opérateur sa. Ainsi les sont, à isomorphisme près, les sa-AH engendrées par des éléments distingués indéxés dans X; on en déduit une classification des extensions complètes de Tx en montrant que les applications qui peuvent être associées à une structure de la forme pour caractériser la théorie d'un modèle sont déterminées par leur restriction à une partie M() définie uniformément, sur laquelle elles prennent des valeurs dans (N − {0}) ⋃ {∞}, et que réciproquement toute application de M() dans (N − {0}) ⋃ {∞} est une telle restriction.
Strong measure zero sets and rapid filters
Authors: Ihoda Jaime I.
Published: May 2006

We prove that cons(ZF) implies cons(ZF + Borel conjecture + there exists a Ramsey ultrafilter). We also prove some results on strong measure zero sets from the existence of generalized Luzin sets. We study the relationships between strong measure zero sets and rapid filters on ω.
Finite and finitely separable intermediate propositional logics
Authors: Bellissima Fabio
Published: May 2006

§0. Introduction and material background. The present paper is devoted to the study of intermediate propositional logics, and it is based on [Be, §§1 and 2].

§2 (§§0 and 1 are introductory) concerns the axiomatization of finite logics. In the literature several effective procedures to axiomatize finite logics are present (cf., for instance, [MK] and [Wr]), but, in each case, the number of propositional variables which are used is redundant. In this direction, Theorem 2.2 provides (a) a criterion to determine, given a finite logic L, the least n such that L is axiomatizable by formulas in n variables, and (b) an effective axiomatization by an n-formula. As a corollary we obtain a negative answer to Problem 7.10 of [Ho/On], showing that there is no connection between the slice to which L belongs and the number of propositional variables necessary to axiomatize L.

The principal results of the paper are in §3. In fact, a great deal of research has been done on the correspondence between conditions on the relation of Kripke-structures from one side, and axioms added to Int from the other. In this section we (a) introduce the concept of finitely separable class of Kripke-frames, and show, by means of several examples, that this concept is “wide”, in the sense that all the most studied classes of frames determined by semantical conditions are finitely separable; (b) show that each finitely separable class is axiomatizable, and that the axioms can be found by means of semantical considerations only; and (c) establish the finite model property for all the finitely separable logics.
Algebraic extensions in nonstandard models and Hilbert's irreducibility theorem
Authors: Yasumoto Masahiro
Published: May 2006

Let K be an algebraic number field and IK the ring of algebraic integers in K. *K and *IK denote enlargements of K and IK respectively. Let x Є *K – K. In this paper, we are concerned with algebraic extensions of K(x) within *K. For each x Є *K – K and each natural number d, YK(x,d) is defined to be the number of algebraic extensions of K(x) of degree d within *K. x Є *K – K is called a Hilbertian element if YK(x,d) = 0 for all d Є N, d > 1; in other words, K(x) has no algebraic extension within *K. In their paper [2], P. C. Gilmore and A. Robinson proved that the existence of a Hilbertian element is equivalent to Hilbert's irreducibility theorem. In a previous paper [9], we gave many Hilbertian elements of nonstandard integers explicitly, for example, for any nonstandard natural number ω, 2ωPω and 2ω(ω3 + 1) are Hilbertian elements in *Q, where pω is the ωth prime number.
Believing the axioms. I
Authors: Maddy Penelope
Published: May 2006

§0. Introduction. Ask a beginning philosophy of mathematics student why we believe the theorems of mathematics and you are likely to hear, “because we have proofs!” The more sophisticated might add that those proofs are based on true axioms, and that our rules of inference preserve truth. The next question, naturally, is why we believe the axioms, and here the response will usually be that they are “obvious”, or “self-evident”, that to deny them is “to contradict oneself” or “to commit a crime against the intellect”. Again, the more sophisticated might prefer to say that the axioms are “laws of logic” or “implicit definitions” or “conceptual truths” or some such thing.

Unfortunately, heartwarming answers along these lines are no longer tenable (if they ever were). On the one hand, assumptions once thought to be self-evident have turned out to be debatable, like the law of the excluded middle, or outright false, like the idea that every property determines a set. Conversely, the axiomatization of set theory has led to the consideration of axiom candidates that no one finds obvious, not even their staunchest supporters. In such cases, we find the methodology has more in common with the natural scientist's hypotheses formation and testing than the caricature of the mathematician writing down a few obvious truths and preceeding to draw logical consequences.

The central problem in the philosophy of natural science is when and why the sorts of facts scientists cite as evidence really are evidence. The same is true in the case of mathematics. Historically, philosophers have given considerable attention to the question of when and why various forms of logical inference are truth-preserving. The companion question of when and why the assumption of various axioms is justified has received less attention, perhaps because versions of the “self-evidence” view live on, and perhaps because of a complacent if-thenism.
Some filters of partitions
Authors: Matet Pierre
Published: May 2006

§0. Introduction. We started our study of filters of partitions in [15]. We shall here restrict ourselves to the consideration of filters on (ω)ω, the set of all infinite partitions of ω. §1 is an attempt to elucidate the connection between filters on (ω)ω and filters over ω. Given a filter H over ω, we define two filters FH and GH on (ω)ω, and we characterize p-points, rare ultrafilters and Ramsey ultrafilters in terms of properties of the associated filters of partitions.

The remainder of the paper is devoted to the study of those filters that can be associated with Hindman's theorem and its extensions. Let us introduce some notation. Suppose * is an associative operation on ω, and let a subset A of ω and an ordinal α with 0 < α ≤ ω be given.
Existentially closed algebras and boolean products
Authors: Riedel Herbert H. J.
Published: May 2006

A Boolean product construction is used to give examples of existentially closed algebras in the universal Horn class ISP(K) generated by a universal class K of finitely subdirectly irreducible algebras such that Γa(K) has the Fraser-Horn property. If ⟦a ≠ b⟧ ∩ ⟦c ≠ d ⟧ = ∅ is definable in K and K has a model companion of K-simple algebras, then it is shown that ISP(K) has a model companion. Conversely, a sufficient condition is given for ISP(K) to have no model companion.
The classification of small weakly minimal sets. II
Authors: Buechler Steven
Published: May 2006

The main result is Vaught's conjecture for weakly minimal, locally modular and non-ω-stable theories. The more general results yielding this are the following.

Theorem A. Suppose that T is a small unidimensional theory and D is a weakly minimal set, definable over the finite set B. Then for all finite A ⊂ D there are only finitely many nonalgebraic strong types over B realized in acl(A) ∩ D.

Theorem B. Suppose that T is a small, unidimensional, non-ω-stable theory such that the universe is weakly minimal and locally modular. Then for all finite A there is a finite B ⊂ cl(A) such that a ∈ cl(A) iff a ∈ cl(b) for some b ∈ B.

Recall the property (S) defined in the abstract of [B1].

Theorem C. Let T be as in Theorem B. Then, if T does not satisfy (S), T hasmany countable models.

Combining Theorem C and the results in [B1] we obtain Vaught's conjecture for such theories.
The model theory of chain-closed fields
Authors: Dickmann M. A.
Published: May 2006

The notion of a higher level ordering is a generalization of the usual notion of an order introduced by Becker in the study of sums of even powers in a field; see [1] for a general reference. A precise definition of an ordering of level 2n (level n in the terminology of [1]) is given in Definition 1.1(II) below.

In [1] Becker worked out the extension theory of fields with a higher level ordering and introduced the notion of a (generalized) real closure for such fields. For a survey of (the analog of) the Artin-Schreier theory of fields with a higher level ordering, see [2]. In [10] Jacob proved decidability, completeness and model-completeness (in a suitable language) for the theory of generalized real-closed fields. Jacob's results are in a sense optimal insofar as the nonuniqueness of generalized real closures (see [1, Chapter IV, Theorems 12 and 13]) prevents quantifier elimination results from holding in languages natural from an algebraic point of view.

The following remarkable fact stems from the work of Becker and Harman: a field having a proper ordering (i.e. one which is not just an order) of any level necessarily has an ordering of (exact) level 2n for each integer n ≥ 2, plus two usual orders, and, moreover, a tight connection holds between orderings of two consecutive levels (cf. [9, Corollary 1.4] and [1, Theorem 15, p. 37]).
Sheaves of continuous definable functions
Authors: Pillay Anand
Published: May 2006

Let M be an o-minimal structure or a p-adically closed field. Let be the space of complete n-types over M equipped with the following topology: The basic open sets of are of the form Ũ = {p ∈ Sn (M): U ∈ p} for U an open definable subset of Mn. is a spectral space. (For M = K a real closed field, is precisely the real spectrum of K[X1, …, Xn]; see [CR].) We will equip with a sheaf of LM-structures (where LM is a suitable language). Again for M a real closed field this corresponds to the structure sheaf on (see [S]). Our main point is that when Th(M) has definable Skolem functions, then if p ∈ , it follows that M(p), the definable ultrapower of M at p, can be factored through Mp, the stalk at p with respect to the above sheaf. This depends on the observation that if M ≺ N, a ∈ Nn and f is an M-definable (partial) function defined at a, then there is an open M-definable set U ⊂ Nn with a ∈ U, and a continuous M-definable function g:U → N such that g(a) = f(a).

In the case that M is an o-minimal expansion of a real closed field (or M is a p-adically closed field), it turns out that M(p) can be recovered as the unique quotient of Mp which is an elementary extension of M.
Provability of the pigeonhole principle and the existence of infinitely many primes
Authors: Paris J. B. , Wilkie A. J. , Woods A. R.
Published: May 2006

In this note we shall be interested in the following problems.

Problem 1. Can IΔ0 ⊢ ∀x∃y > x(y is prime)?

Here I Δ0 is Peano arithmetic with the induction axiom restricted to bounded (i.e. Δ0) formulae.

Problem 2. Can IΔ0 ⊢ Δ0 PHP?

Here Δ0 PHP (Δ0 pigeonhole principle) is the schema

for θ ∈ Δ0, or equivalently in IΔ0, for a Δ0 formula F(x,y)

written .

By obtaining partial solutions to Problem 2 we shall show that Problem 1 has a positive solution if IΔ0 is replaced by IΔ0 + ∀xxlog(x) exists.

Our notation will be entirely standard (see for example [3] and [4]). In particular all logarithms will be to the base 2 and in expressions like log(x), (1 + ε)x, etc. we shall always mean the integer part of these quantities.

Concerning Problem 2 we remark that it is shown in [5] that for k ∈ N and F ∈ Δ0,

As far as we know this is the best result of this form, in that we do not know how to replace log(z)k by anything larger. However, as we shall show in Theorem 1, we can do much better if we increase the difference between the sizes of the domain and range of F.

In what follows let M be a countable nonstandard model of IΔ0, and let be those subsets of M defined by Δ0 formulae with parameters from M.

Theorem 1. For k ∈ N andF ∈ Δ0,

Here log0(x) = x, logk + 1(x) = log(logk(x)).

Proof. To simplify matters, consider first the case k = 1. So assume M ⊨ alog(a) exists and with and a > 1. The idea of the proof is the following.
Mechanical learners pay a price for Bayesianism
Authors: Osherson Daniel N. , Stob Michael , Weinstein Scott
Published: May 2006

The price is failure on a class of inductive inference problems that are easily solved, in contrast, by nonBayesian mechanical learners. By “mechanical” is meant “simulable by Turing machine”.

One of the central tenets of Bayesianism, which is common to the heterogeneous collection of views which fall under this rubric, is that hypothesis change proceeds via conditionalization on accumulated evidence, the posterior probability of a given hypothesis on the evidence being computed using Bayes's theorem. We show that this strategy for hypothesis change precludes the solution of certain problems of inductive inference by mechanical means—problems which are solvable by mechanical means when the restriction to this Bayesian strategy is lifted. Our discussion proceeds as follows. After some technical preliminaries, the concept of (formal) learner is introduced along with a criterion of inferential success. Next we specify a class of inductive inference problems, and then define the notion of “Bayesian behavior” on those problems. Finally, we exhibit an inductive inference problem from the specified class such that (a) some nonmechanical Bayesian learner solves the problem, (b) some nonBayesian mechanical learner solves the problem, (c) some mechanical learner manifests Bayesian behavior on the problem, but (d) no mechanical Bayesian learner solves the problem.

Insofar as possible terminology and notation are drawn from Osherson, Stob, and Weinstein [1986].
The equivalence of determinacy and iterated sharps
Authors: Dubose Derrick Albert
Published: May 2006

We characterize, in terms of determinacy, the existence of 0## as well as the existence of each of the following: 0###, 0####, 0#####,…. For κ Є ω, we define two classes of sets, and , which lie strictly between and . We also define 01# as# and in general, 0(k+1)# as (0k#)#. We then show that the existence of 0(k + 1)# is equivalent to the determinacy of as well as the determinacy of .
A 1-generic degree which bounds a minimal degree
Authors: Kumabe Masahiro
Published: May 2006

Let ω be the set of natural numbers, i.e. {0,1,2,…}. A set A (≤ω) is called n-generic if it is Cohen-generic for n-quantifier arithmetic. As characterized by Jockusch [4], this is equivalent to saying that for every set of strings S, there is a σ < A such that σ ∈ S or ∀ν ≥ σ(ν ∉ S). When we say degree, we mean Turing degree (of unsolvability). We call a degree n-generic if it has an n-generic representative. A nonrecursive degree a is called minimal if there is no nonrecursive degree b with b < a. Jockusch [4] exhibited various properties of generic degrees, and he showed that any 2-generic degree bounds no minimal degree. Chong and Jockusch [1] showed that any 1-generic degree below 0′ bounds no minimal degree. Haught [3] refuted one of the conjectures in [1] and showed that if a is a 1-generic degree and 0 < b < a < 0′ then b is also 1-generic. We show here that there is a 1-generic degree which bounds a minimal degree. This gives an affirmative answer to questions in [1] and [4], As any 1-generic degree below 0′ bounds no minimal degree, we see that our 1-generic degree which bounds a minimal degree is not below 0′, but can be constructed recursively in 0″. Furthermore we see that the initial segments below 1-generic degrees are not order isomorphic.
Boolean algebras and orbits of the lattice of r.e sets modulo the finite sets
Authors: Cholak Peter
Published: May 2006

An important program in the study of the structure the lattice of r.e. sets modulo finite sets, is the classification of the orbits under Aut(), the automorphism group of , If Φ ∈ Aut() and Φ(We) =* Wh(e) for all e ∈ ω, then h is called a presentation of Φ. Define Autχ() to be the class of those elements of Aut() that have a presentation in the class of functions X, where for instance X might be the class of Δn functions for n ∈ ω. If Φ ∈ Autx() then we will say that Φ is an X-automorphism. Note that we only need to consider Δn- and Πn-orbits and automorphisms since if f is a Σn-presentation, then f is a total function and therefore Δn.

Definition. If X is a class of functions and ⊆ {Wi: i < ω}, then is an X-orbit iff is an orbit under Aut() and for all A, B ∈ there is a Φ ∈ Autx() satisfying Φ(A) =* B. (Here Φ: → .)

Harrington proved that the creative sets form a Δ0-orbit and Soare proved that the maximal sets form Δ3-orbit. We will show that there is no Boolean algebra such that {A: A is r.e. and ℒ*(A) ≈ ] forms a Δ2-orbit, where ℒ*(A) is the principal filter of A in ; ℒ*(A) = {B: B ⊆* A & B ∈ }. The idea behind the proof of this theorem is very similar to the proof by Soare that maximal sets do not form a Δ2-orbit (see Soare [1974] or Soare [1987]).
On Diophantine equations solvable in models of open induction
Authors: Otero Margarita
Published: May 2006

We consider IOpen, the subsystem of PA (Peano Arithmetic) with the induction scheme restricted to quantifier-free formulas.

We prove that each model of IOpen can be embedded in a model where the equation has a solution. The main lemma states that there is no polynomial f{x,y) with coefficients in a (nonstandard) DOR M such that ∣f(x,y) ∣ < 1 for every (x,y) Є C, where C is the curve defined on the real closure of M by C: x2 + y2 = a and a > 0 is a nonstandard element of M.
A metatheorem for constructions by finitely many workers
Authors: Knight J. F.
Published: May 2006

The aim of the present paper is to give some general conditions for constructions by finitely many workers. Constructions using infinitely many workers will not be considered here, although there are examples of such constructions. The original construction using the method of workers, due to Harrington [H], has a worker n for each n ∈ ω, as do the constructions in [K1] and [K2]. Marker [M] obtains a result using three workers. In [AJK], there are two constructions that use three workers. There are also two constructions that have, for an arbitrary recursive ordinal α, one worker for each β < α.

The main result here is a metatheorem, which is patterned after Proposition 1 of Ash [A]. As in [A], the object of the construction is to attach “labels” to the nodes in a highly nonrecursive path through a tree, while recursively enumerating neighborhoods of an “adherent” point in a metric space. There is a family of relations associated with the labels, and the metatheorem here and the one in [A] both say that the construction will succeed if these relations satisfy a list of properties. There are significant differences between the result here and that in [A]. One difference is that certain relations which in [A] were required to be r.e. need not be r.e. here. Another difference is that there are extra relations here, and as a result, the list of properties to be satisfied is longer and more horrible than that in [A].
Lifschitz' realizability
Authors: van Oosten Jaap
Published: May 2006

V. Lifschitz defined in 1979 a variant of realizability which validates Church's thesis with uniqueness condition, but not the general form of Church's thesis. In this paper we describe an extension of intuitionistic arithmetic in which the soundness of Lifschitz' realizability can be proved, and we give an axiomatic characterization of the Lifschitz-realizable formulas relative to this extension. By a “q-variant” we obtain a new derived rule. We also show how to extend Lifschitz' realizability to second-order arithmetic. Finally we describe an analogous development for elementary analysis, with partial continuous application replacing partial recursive application.
Nonuniformization results for the projective hierarchy
Authors: Jackson Steve , Mauldin R. Daniel
Published: May 2006

Let X and Y be uncountable Polish spaces. We show in ZF that there is a coanalytic subset P of X × Y with countable sections which cannot be expressed as the union of countably many partial coanalytic, or even PCA = , graphs. If X = Y = ωω, P may be taken to be . Assuming stronger set theoretic axioms, we identify the least pointclass such that any such coanalytic P can be expressed as the union of countably many graphs in this pointclass. This last result is extended (under suitable hypotheses) to all levels of the projective hierarchy.
A cardinality version of Beigel's nonspeedup theorem
Authors: Owings James C.
Published: May 2006

If S is a finite set, let ∣S∣ be the cardinality of S. We show that if m ∈ ω, A ⊆ ω, B ⊆ ω, and ∣i: ≤ i ≤ 2m & xi ∈ A}∣ can be computed by an algorithm which, for all x1, …, x2m, makes at most m queries to B, then A is recursive in the halting set K. If m = 1, we show that A is recursive.
A note on the multiplicative semigroup of models of Peano arithmetic
Authors: Kossak Roman , Nadel Mark , Schmerl James
Published: May 2006

In a model of Peano arithmetic, the isomorphism type of the multiplicative semigroup uniquely determines the isomorphism type of the additive semigroup. In fact, for any prime p of , the function x ↦ px is an isomorphism of the additive semigroup with the multiplicative subsemigroup of powers of p. It was observed by Jensen and Ehrenfeucht [3] that for countable models of PA, the isomorphism type of the additive semigroup (or even the additive group) determines the isomorphism type of the multiplicative semigroup. (See Theorem 3 below.)

In this note we will show that the countability restriction cannot be dropped. First, we show (as Theorem 2) that for uncountable models of PA the isomorphism type of the additive group never determines the isomorphism type of the multiplicative semigroup. Our main result is Theorem 5 in which we show that the isomorphism type of the additive semigroup need not determine the isomorphism type of the multiplicative semigroup, thereby improving upon Harnik [2], where Theorem 5 is proved under the assumption of ♢. For completeness, a sketch of the proof of the Jensen-Ehrenfeucht result is included.

The history of this paper begins with Nadel's question, asked in 1981, whether the countability assumption can be eliminated in the Jensen-Ehrenfeucht theorem. Soon afterwards, Nadel obtained the strong counterexample of Theorem 2, which applied to the additive group rather than the additive semigroup. A result of Pabion [8] shows that such a strong result is not possible for the additive semigroup.
The roots of contemporary Platonism
Authors: Maddy Penelope
Published: May 2006

Though many working mathematicians embrace a rough and ready form of Platonism, that venerable position has suffered a checkered philosophical career. Indeed the three schools of thought with which most of us began our official philosophizing about mathematics—Intuitionism, Formalism, and Logicism—all stand in fundamental disagreement with Platonism. Nevertheless, various versions of Platonistic thinking survive in contemporary philosophical circles. The aim of this paper is to describe these views, and, as my title suggests, to trace their roots.

I'll begin with some preliminary remarks about the big three schools. This seems a reasonable approach to the issues both because most observers are familiar, at least in a general way, with the tenets of Intuitionism, Formalism, and Logicism, and because it is in reaction to these that contemporary Platonism has taken shape.
Coding over a measurable cardinal
Authors: Friedman Sy D.
Published: May 2006

The purpose of this paper is to extend the coding method (see Beller, Jensen and Welch [82]) into the context of large cardinals.

Theorem. Suppose μ is a normal measure on κ in V and 〈 V, A〉 ⊨ ZFC. Then there is a 〈V, A〉-definable forcing for producing a real R such that:

(a) V[R] ⊨ ZFC and A is V[R]-definable with parameter R.

(b) V[R] = L[μ*, R], where μ* is a normal measure on κ in V[R] extending μ.

(c) V ⊨ GCH → is cardinal and cofinality preserving.

Corollary. It is consistent that μ is a normal measure, R ⊆ ω is not set-generic over L[μ] and 0+ ∉ L[μ, R].

Some other corollaries will be discussed in §4 of the paper.

The main difficulty in L[μ]-coding lies in the problem of “stationary restraint”.

As in all coding constructions, conditions will be of the form belonging to an initial segment of the cardinals, where p(γ) is a condition for almost disjoint coding into a subset of γ+. In addition for limit cardinals γ in Domain(p), 〈pγ′∣γ′ < γ〉 serves to code pγ.

An important restriction in coding arguments is that for inaccessible for only a nonstationary set of γ′ < γ. The reason is that otherwise there are conflicts between the restraint imposed by the different and the need to code extensions of pγ below γ.
Descriptive set theory over hyperfinite sets
Authors: Keisler H. Jerome , Kunen Kenneth , Miller Arnold , Leth Steven
Published: May 2006

The separation, uniformization, and other properties of the Borel and projective hierarchies over hyperfinite sets are investigated and compared to the corresponding properties in classical descriptive set theory. The techniques used in this investigation also provide some results about countably determined sets and functions, as well as an improvement of an earlier theorem of Kunen and Miller.
Large resplendent models generated by indiscernibles
Authors: Schmerl James H.
Published: May 2006

The motivation for the results presented here comes from the following two known theorems which concern countable, recursively saturated models of Peano arithmetic.

(1) if is a countable, recursively saturated model of PA, then for each infinite cardinal κ there is a resplendent which has cardinality κ. (See Theorem 10 of [1].)

(2) if is a countable, recursively saturated model of PA, then is generated by a set of indiscernibles. (See [4].)

It will be shown here that (1) and (2) can be amalgamated into a common generalization.

(3) if is a countable, recursively saturated model of PA, then for each infinite cardinal κ there is a resplendent which has cardinality κ and which is generated by a set of indiscernibles.

By way of contrast we will also get recursively saturated models of PA which fail to be resplendent and yet are generated by indiscernibles.

(4) if is a countable, recursively saturated model of PA, then for each uncountable cardinal κ there is a κ-like recursively saturated generated by a set of indiscernibles.

None of (1), (2) or (3) is stated in its most general form. We will make some comments concerning their generalizations. From now on let us fix a finite language L; all structures considered are infinite L-structures unless otherwise indicated.
The equivalence of the disjunction and existence properties for modal arithmetic
Authors: Friedman Harvey , Sheard Michael
Published: May 2006

In a modal system of arithmetic, a theory S has the modal disjunction property if whenever S ⊢ □φ ∨ □ψ, either S ⊢ □φ or S ⊢ □ψ. S has the modal numerical existence property if whenever S ⊢ ∃x □φ(x), there is some natural number n such that S ⊢ □φ(n). Under certain broadly applicable assumptions, these two properties are equivalent.
Undecidable complexity statements in -arithmetic
Authors: Sigal Ron
Published: May 2006

The failure of a large and diverse body of work to settle some of the now-classical questions of computational complexity (notably P =? NP) suggests that they might not, in fact, be resolvable by established proof techniques.

Hartmanis and Hopcroft [HH] raised the issue of independent statements about computational complexity in 1976, constructing, for any consistent r.e. theory T capable of expressing statements about Turing machines, a Turing machine MT such that statements which intuitively express the computational complexity of MT are independent of T. Their technique involves a simple diagonalizing search over the theorems of T. In this paper we prove a constructive version of their independence result in the context of a generalization of a hierarchy of free variable logics defined by Rose [R1]. These logics are based on an axiomatized treatment of an extension by Löb and Wainer [LW] of Grzegorczyk's [G] hierarchy into the transfinite. Associated with each extended Grzegorczyk class (relative to an ordinal notation system S satisfying certain conditions) is the logic -arithmetic.

Free variable logics are interesting from the perspective of theoretical computer science. We may construe the equational definition of functions as a form of programming system. Each -arithmetic, then, has the nice property of containing both a programming system and a logic for stating and proving facts about programs.
Two recursion theoretic characterizations of proof speed-ups
Authors: Royer James S.
Published: May 2006

Smullyan in [Smu61] identified the recursion theoretic essence of incompleteness results such as Gödel's first incompleteness theorem and Rosser's theorem. Smullyan (improving upon [Kle50] and [Kle52]) showed that, for sufficiently complex theories, the collection of provable formulae and the collection of refutable formulae are effectively inseparable—where formulae and their Gödel numbers are identified. This paper gives a similar treatment for proof speed-up. We say that a formal system S1is speedable over another system S0on a set of formulaeAiff, for each recursive functionh, there is a formulaαinAsuch that the length of the shortest proof ofαin S0is larger thanhof the shortest proof ofαin S1. (Here we equate the length of a proof with something like the number of characters making it up,notits number of lines.) We characterize speedability in terms of the inseparability by r.e. sets of the collection of formulae which are provable in S1but unprovable in S0from the collectionA–where again formulae and their Gödel numbers are identified. We provide precise definitions of proof length, speedability and r.e. inseparability below.

We follow the terminology and notation of [Rog87] with borrowings from [Soa87]. Below,ϕis an acceptable numbering of the partial recursive functions [Rog87] andΦa (Blum) complexity measure associated withϕ[Blu67], [DW83].
Meager sets on the hyperfinite time line
Authors: Keisler H. Jerome , Leth Steven C.
Published: May 2006

In this paper we study notions of a “meager subset” of a hyper-finite set. We work within an ω-saturated nonstandard universe and fix a hyperfinite natural number Є *N∖N. We shall consider subsets of the set = {1, 2, …,H}.

By analogy with the meager subsets of the real interval [0, 1], a notion of meager subset of should have the following properties.

1. Finite sets, countable unions of meager sets, subsets of meager sets, and translates of meager sets should be meager.

2. The Baire Category Theorem should hold; that is, should not be meager.

3. The internal analogue of the Cantor set should be meager.

4. The notion of a meager set should be with respect to a natural topology on .

5. There should exist meager subsets of of Loeb measure one.

6. Sierpiński and Lusin sets should have hyperfinite counterparts with properties similar to the classical case.

Property 5 is desirable so that, as with Lebesgue measure and Baire category on [0, 1], the topological and measure-theoretic notions of “large” and “small” sets are incomparable.

Property 6, while not as necessary as the other five, is desirable because of the strong interplay between measure and category in the classical results about Lusin and Sierpinski sets. Our objective is to find notions of meager set which have a relationship to Loeb measure similar to the classical relationship between meager sets and Lebesgue measure.