bluuebunny/crossref_metadata_2025 huggingface dataset:
Simplest normal truth functions
Authors: Nelson Raymond J.
Published: May 2006

In [1] Quine has presented a method for finding the simplest disjunctive normal forms of truth functions. Like the tabular methods of [2] and [3], Quine's method requires expansion of a formula into developed normal form as a preliminary step. This aspect of his method to a certain extent defeats one of the purposes of a mechanical method, which is to secure simplest forms in complicated cases (perhaps by using a digital computer) [4]. In the present paper we develop a method for both disjunctive and conjunctive normal truth functions which is in some respects similar to Quine's but which does not involve prior expansion of a formula into developed normal form. Familiarity with [1] is presupposed.

We use the notations and conventions of [1] with the following exceptions and additions. ‘Φ’ names any formula, ‘Ψ’ any conjunction of literals, and ‘χ’ any disjunction of literals. Any disjunction of conjunctions of literals is a disjunctive normal formula and is designated by ‘ψ’; any conjunction of disjunctions of literals is a conjunctive normal formula and is designated by ‘X’. Note that we do not make use of Quine's notion of fundamental formulas. A formula Ψ occurring in a disjunctive normal formula ψ, provided it is a disjunct of ψ, is a clause; similarly for χ. We use ‘≠” for logical equivalence of formulas and ‘=’ for identity of formulas to within the order of literals in clauses and the order of clauses in normal formulas.
Recursive well-orderings
Authors: Spector Clifford
Published: May 2006

Cantor's second ordinal number class is perhaps the simplest example of a set of mathematical objects which cannot all be named in one language. In this paper we shall investigate a system of names for a segment of the first and second number classes in relation to decision problems. The system, except for one minor difference, is the one studied by Markwald in [12]. In our system ordinals are named by natural numbers from a set W via recursive well-orderings of subsets of the natural numbers.

The decision problems will be related to the hyperarithmetical hierarchy of Davis [2], [3] and Kleene [8]. This hierarchy is indexed by ordinal notations from Kleene's system S3 [4], [6], [9], in which ordinals are named by natural numbers from a set O, partially well-ordered ([12] p. 138) by a relation a≤Ob; O and ≤O are defined inductively by applications of the successor and limit operations. As results of this investigation, we shall (i) answer negatively Markwald's question [12] Theorem 12 whether his set “W” is arithmetical by showing that it is not even hyperarithmetical, (ii) obtain a new proof of the main result of Kleene [10] that every predicate expressible in both the one-function-quantifier forms of [8] is recursive in Hα for some aεO, (iii) answer affirmatively the question raised by Davis [2], [3] whether all the Church-Kleene constructive ordinals are uniqueness ordinals, and (iv) solve the function-quantifier analog of Post's problem [15]. Strong use will be made of the well-orderings that can be constructed from one-function-quantifier predicates as in [9].
Nicht konstruktiv beweisbare Sätze der Analysis
Authors: Specker Ernst
Published: May 2006

Nach allgemeiner Ueberzeugung können gewisse Sätze der Analysis nicht konstruktiv bewiesen werden. Man denke etwa an den folgenden Satz: Eine monotone und beschränkte Folge a(n) von rationalen Zahlen konvergiert, d.h. es gibt eine solche ganzzahlige Funktion k(m), daß

Unter einem konstruktiven Beweis dieses Satzes hätte man etwa die Angabe eines Verfahrens zu verstehen, das gestattet, die Funktion k(m) auf Grand der Folge a(n) rekursiv zu definieren. Wenn ein solcher Beweis vorläge, wäre insbesondere gezeigt, daß es zu einer rekursiv definierten Folge a(n) mit den verlangten Eigenschaften stets eine rekursiv definierbare Konvergenzfunktion k(m) gibt.

Es soil nun im folgenden von einigen grundlegenden Sätzen der reellen Analysis gezeigt werden, daß sie nicht konstruktiv bewiesen werden können—konstruktiv in dem Sinn, der eben angedeutet wurde. Wir stützen uns dabei auf die Begriffe der rekursiven und der berechenbaren Funktion; rekursive und berechenbare Funktionen sind zahlentheoretische Funktionen. Unter einer rekursiven Funktion möge vorläufig eine primitiv rekursive Funktion verstanden werden (vgl. etwa D. Hilbert und P. Bernays [3], S.286); berechenbar meint berechenbar im Sinne von A. Church [1], S. C. Kleene [4], A. M. Turing [6]. Der Begriff der “konstruktiv definierten Funktion” wird durch die Bestimmung als “rekursive Funktion” eher eng, durch die Bestimmung als “berechenbare Funktion” eher weit gefaßt.

Definition I. Eine Folge rationaler Zahlen Φ(n) heißt rekursiv,(berechenbar), wenn es solche rekursiven (berechenbaren) Funktionen ϕ{n), ψ(n) und χ(n) gibt, daß χ(n) ≧1 und

.

Definition II. Eine Folge Φ(n) von rationalen Zahlen heißt rekursiv (berechenbar) konvergent, wenn es eine solche rekursive (berechenbare) Funktion v(m) gibt, daß

Wir werden zeigen (Satz I): Es gibt eine rekursive, monotone und beschränkte Folge rationaler Zahlen, die nicht berechenbar konvergiert. Bei unserer Auffassungsweise ist darin enthalten, daß der zu Beginn erwähnte Satz nicht konstruktiv bewiesen werden kann.
A test for the equality of truth-tables
Authors: Kalicki Jan
Published: May 2006

In this paper the symbolism, definitions and results of my two papers, namely A test for the existence of tautologies according to many-valued truth-tables (hereafter referred to as ET) and Note on truth-tables (hereafter referred to as TT) will be presupposed.

The problem whether two arbitrary truth-tables with finite number of elements are equal or not was reduced in TT to the question of equality of two identical tables in which different elements have been designated. However, no general method for testing the equality of truth-tables was given there, although some cases were discussed for which such a method is available. In the present paper we shall describe a general method using the considerations of ET and TT.
A derivation of number theory from ancestral theory
Authors: Myhill John
Published: May 2006

Martin has shown that the notions of ancestral and class-inclusion are sufficient to develop the theory of natural numbers in a system containing variables of only one type.

The purpose of the present paper is to show that an analogous construction is possible in a system containing, beyond the quantificational level, only the ancestral and the ordered pair.

The formulae of our system comprise quantificational schemata and anything which can be obtained therefrom by writing pairs (e.g. (x; y), ((x; y); (x; (y; y))) etc.) for free variables, or by writing ancestral abstracts (e.g. (*xyFxy) etc.) for schematic letters, or both.

The ancestral abstract (*xyFxy) means what is usually meant by ; and the formula (*xyFxy)zw answers to Martin's (zw; xy)(Fxy).

The system presupposes a non-simple applied functional calculus of the first order, with a rule of substitution for predicate letters; over and above this it has three axioms for the ancestral and two for the ordered pair.
Coherence and the axioms of confirmation
Authors: Shimony Abner
Published: May 2006

It has been pointed out by Carnap that ‘probability’ is an equivocal term, which is used currently in two senses: (i) the degree to which it is rational to believe a hypothesis h on specified evidence e, and (ii) the relative frequency (in an indefinitely long run) of one property of events or things with respect to another. This paper is concerned only with the first of these two senses, which will be referred to as ‘the concept of confirmation,’ in order to avoid equivocation.

We may distinguish a quantitative and a comparative concept of confirmation. The general form of statements involving the former is

The degree of confirmation of the proposition h, given the proposition

e as evidence, is r (where r is a real number between 0 and 1).

In this paper the notation for a statement of this form is

The general form of statements involving the comparative concept is The proposition h is equally or less confirmed on e than is the proposition h′ on e′,

which may be symbolized as

The following abbreviations will also be used in discussing comparative confirmation:

The former of these two abbreviations means intuitively

The proposition h is less confirmed on evidence e than h′ is on e′. The latter means

The proposition h is confirmed on evidence e to the same degree that h′ is on e′.
Formal development of ordinal number theory
Authors: Orey Steven
Published: May 2006

In this paper we shall develop a theory of ordinal numbers for the system ML, [6]. Since NF, [2], is a sub-system of ML one could let the ordinal arithmetic developed in [9] serve also as the ordinal arithmetic of ML. However, it was shown in [9] that the ordinal numbers of [9], NO, do not have all the usual properties of ordinal numbers and that theorems contradicting basic results of “intuitive ordinal arithmetic” can be proved.

In particular it will be a theorem in our development of ordinal numbers that, for any ordinal number α, the set of all smaller ordinal numbers ordered by ≤ has ordinal number α; this result does not hold for the ordinals of [9] (see [9], XII.3.15). It will also be an easy consequence of our definition of ordinal number that proofs by induction over the ordinal numbers are permitted for arbitrary statements of ML; proofs by induction over NO can be carried through only for stratified statements with no unrestricted class variables.

The class we shall take as the class of ordinal numbers, to be designated by ‘ORN’, will turn out to be a proper subclass of NO. This is because in ML there are two natural ways of defining the concept of well ordering. Sets which are well ordered in the sense of [9] we shall callweakly well ordered; sets which satisfy a certain more stringent condition will be calledstrongly well ordered. NO is the set of order types of weakly well ordered sets, while ORN is the class of order types of strongly well ordered sets. Basic properties of weakly and strongly well ordered sets are developed in Section 2.
Corrections to two papers on modal logic
Authors: Fitch Frederic B.
Published: May 2006

The two following papers are in need of certain corrections: Modal functions in two-valued logic and Note on modal functions. I became aware of the need for these corrections while comparing these earlier papers of mine with J. C. C. McKinsey's paper, On the syntactical construction of systems of modal logic.

The first of the two papers should be corrected in such a way that the system of two-valued logic there employed becomes “complete” in the sense that either p or ∼ p is in Τ for every Κ-symbol Τ. This could be achieved by use of an additional axiom that postulates the required completeness. (I mistakenly supposed that the original set of axioms guaranteed this completeness.)
Concatenation as a basis for arithmetic
Authors: Quine W. V.
Published: May 2006

General syntax, the formal part of the general theory of signs, has as its basic operation the operation of concatenation, expressed by the connective ‘⌢’ and understood as follows : where x and y are any expressions, x⌢y is the expression formed by writing the expression x immediately followed by the expression y. E.g., where ‘alpha’ and ‘beta’ are understood as names of the respective signs ‘α’ and ‘β’, the syntactical expression ‘alpha⌢beta’ is a name of the expression ‘αβ’.

Tarski and Hermes have presented axioms for concatenation, and definitions of derivative syntactical concepts. Hermes has also related concatenation theory to the arithmetic of natural numbers, constructing a model of the latter within the former. Conversely, Gödel's proof of the impossibility of a complete consistent systematization of arithmetic depended on constructing a model of concatenation theory within arithmetic.
Zusammenhang der mehrfachen und transfiniten Rekursionen
Authors: Péter Rózsa
Published: May 2006

Es ist bekannt, daβ man aus den Funktionen 0 und n + 1 ausgehend, die in der elementaren Zahlentheorie benutzten Funktionen durch eine endliche Kette von Substitutionen und “primitiven Rekursionen” der Form

(α(a1, …, ar) und β(n, a1, …, ar, ar+1) bereits eingeführte Funktionen) definieren kann. Aber die “mehrfache Rekursion”, wobei die Rekursion gleichzeitig nach mehreren Variablen läuft, führt aus der so entstehenden Klasse der “primitiv-rekursiven Funktionen” hinaus. Die sogenannten “mehrfachen”, und zwar “k-rekursiven” Funktionen (zu welchen als Spezialfall auch die primitiv-rekursiven Funktionen gehören) lassen sich von gewissen Ausgangsfunktionen ausgehend durch eine endliche Kette von Substitutionen und “k-fachen Rekursionen” (wobei die Rekursion gleichzeitig nach k Variablen läuft) einer gewissen Normalform aufbauen. Die k + 1-fache Rekursion führt für ein jedes k aus der Klasse der k-rekursiven Funktionen hinaus. Das kann mit Hilfe des Diagonalverfahrens bewiesen werden. Das Diagonalverfahren auf sämtliche mehrfach-rekursive Funktionen angewandt (auch wenn man sich auf Funktionen von einer gegebenen Variablenanzahl beschränkt) würde als Beispiel einer nicht mehrfachrekursiven Funktion eine Funktion ergeben, bei der es vom ersten Argument abhängt, wievielstellig die Funktion ist.

Man sagt allgemein, daβ eine Funktion durch irgendeine Rekursion definiert wird, wenn ihr Wert an gewissen Anfangsstellen angegeben, und an einer anderen Stelle aus Werten aufgebaut wird, welche die Funktion an vorherigen Stellen angenommen hat. Es kann aber verschieden vorgeschrieben werden, welche Stellen als Vorgänger einer gegebenen Stelle zu betrachten sind.
Set-theoretic foundations for logic
Authors: Quine W. V.
Published: May 2006

1. Introduction. In his set theory Zermelo uses the variables “x”, “y”, etc. for the representation of “things” generally. Among these things he includes sets, or, as I shall say henceforth, classes. He adopts the connective “ϵ” of membership as his sole special primitive; thus the elementary formulae of his system are describable simply as expressions of the form “xϵy”, with any thing-variables ”x”, “y”, “z”, etc. supplanting “x” and “y”. The postulates of his system are so fashioned as to avoid the logical paradoxes without use of the theory of types. One of the postulates, the so-called Aussonderungsaxiom, may be stated in familiar logical notation as

where is understood as any statement about y which is definite in a certain sense which Zermelo introduces informally for the purpose. Skolem has pointed out that it is adequate here to construe “definite” statements as embracing just the elementary formulae and all formulae thence constructible by the truth functions and by quantification with respect to thing-variables. A second of Zermelo's postulates is the principle of extensionality; this asserts that mutually inclusive classes are identical, i.e. are members of just the same classes. There are further postulates which provide for the existence of the null class, the class of all subclasses of any given class, the class of all members of members of any given class, the unit class of any given thing, and the class whose sole members are any two given things. Finally the multiplicative axiom (Auswahlprinzip) and the axiom of infinity are adopted.
An undecidable problem in the algebra of truth-tables
Authors: Kalicki Jan
Published: May 2006

In a previous paper I have described a decision method for testing whether or not two arbitrary finite truth-tables are “equal”, i.e., determine the same set of tautologies. The same problem for the case of infinite truth-tables remained open.

In the present note we shall show that the answer to the problem in the case of infinite truth-tables is negative; in fact we shall prove that there exists neither a decision method for testing the equality of arbitrary truth-tables, nor even one for testing the equality of what we call “recursive” truth-tables.

The terminology of Kalicki [3] will be used; for brevity's sake the discussion involving the notions of recursiveness and recursive enumerability uses the informal terminology and mode of argumentation employed by Post in [9].
The theory of classes A modification of von Neumann's system
Authors: Robinson Raphael M.
Published: May 2006

1. The theory of classes presented in this paper is a simplification of that presented by J. von Neumann in his paper Die Axiomatisierung der Mengenlehre. However, this paper is written so that it can be read independently of von Neumann's. The principal modifications of his system are the following.

(1) The idea of ordered pair is defined in terms of the other primitive concepts of the system. (See Axiom 4.3 below.)

(2) A much simpler proof of the well-ordering theorem, based on von Neumann's equivalence axiom (Axiom 2.2 below) is given. (More exactly, the theory of ordinal numbers, on which the proof of the well-ordering theorem is based, is simplified—see §8.)

(3) Functions are not assumed to be defined for all arguments. In place of “ = A” we have “is undefined.” This makes possible a constructive interpretation of the system. (See §2.)

2. We wish first to give a rough picture of the system which we are trying to construct. Suppose that we have the idea “class,” but no material from which to construct classes. Nevertheless, we can construct the class 0 having no elements. And then the class 1 having 0 as its only element. And then the classes {1}, and {0, 1}, etc., using always the previously constructed classes as elements. To extend this method to infinite classes, we must give rules telling what elements are to be included. Since the nature of the rules which we can use is not altogether clear, we try to formalize the whole system; that is, to set up a system of axioms which seems to characterize this system of classes. Now in this set of axioms we find it necessary to use the idea of function (in the “Axiom of Replacement”).
On the relative consistency of set theory
Authors: Orey Steven
Published: May 2006

We present a method for demonstrating the consistency of von Neuman-Gödel set theory Σ (or Zermelo set theory Σ′) relative to various other formal set theories. When a model for a logic L1is constructed, there are two other logics involved: L2, the system which contains the model, and L3, the metalogic in which the argument that L2contains a model for L1is carried out. These three systems need not of course all be distinct. In [2] L1is Σ strengthened by the axiom ∨ = L, L2is Σ, and L3is unformalized. In the present paper L1will be either Σ or Σ′. The basic idea for proving the relative consistency of L1with respect to some other system L2is to construct in L2a model for L1similar to the model constructed in [2]. Since L2may be some kind of type theory, the function corresponding to Gödel's function F must be modified in a suitable manner. In verifying the relativized versions of axioms of L1in L2, we shall have to overcome certain special problems depending on the system L2and not met with in [2]. Except for the remarks at the end of Section 2, we shall not consider the question of formalizing L3, i.e. we use intuitive logic as our metalogic.

In Section 1 we illustrate the method by demonstrating the consistency of Σ relative to the system ML″ obtained by adding E of [4] as an axiom to ML′ of [4]. We use the notation and results of [4] and [7].

Section 2 discusses the use of certain other systems for L2. It will be noted that the systems used for L2are always slightly strengthened versions of well known systems ([5], [6], and the simple theory of types); it is of course to be hoped that modifications may be discovered which would make the method work in the original, unstrengthened systems, or that the relative consistency of the strengthened systems with respect to the original systems can be established.
On completely recursively enumerable classes and their key arrays
Authors: Rice H. G.
Published: May 2006

The two results of this paper (a theorem and an example) are applications of a device described in section 1. Our notation is that of [4], with which we assume familiarity. It may be worth while to mention in particular the function Φ(n, x) which recursively enumerates the partial recursive functions of one variable, the Cantor enumerating functions J(x, y), K(x), L(x), and the classes F and Q of r.e. (recursively enumerable) and finite sets respectively.

It is possible to “give” a finite set in a way which conveys the maximum amount of information; this may be called “giving explicitly”, and it requires that in addition to an effective enumeration or decision procedure for the set we give its cardinal number. It is sometimes desired to enumerate effectively an infinite class of finite sets, each given explicitly (e.g., [4] p. 360, or Dekker [1] p. 497), and we suggest here a device for doing this.

We set up an effective one-to-one correspondence between the finite sets of non-negative integers and these integers themselves: the integer , corresponds to the set αi, = {a1, a2, …, an} and inversely. α0 is the empty set. Clearly i can be effectively computed from the elements of αi and its cardinal number.
Non-null implication
Authors: Nelson David
Published: May 2006

An implication A ⊃ B is said to be null in case A is false in all instances. This note describes several formal systems for first-order predicate logic and arithmetic in which null implications do not occur. In fact, the most restrictive systems avoid the occurrences of any formulas which represent null predicates. The precise sense of this avoidance is explained below.

An intuitionistic negation is a statement of the form A ⊃ F where F is a contradiction. The absence of null implications among true statements entails the absence of intuitionistic negations, and hence systems described here might be called negationless intuitionistic systems.
Decidability and undecidability of extensions of second (first) order theory of (generalized) successor
Authors: Elgot Calvin C. , Rabin Michael O.
Published: May 2006

We study certain first and second order theories which are semantically defined as the sets of all sentences true in certain given structures. Let be a structure where A is a non-empty set, λ is an ordinal, and Pα is an n(α)-ary relation or function4 on A. With we associate a language L appropriate for which may be a first or higher order calculus. L has an n(α)-place predicate or function constant P for each α < λ. We shall study three types of languages: (1) first-order calculi with equality; (2) second-order monadic calculi which contain monadic predicate (set) variables ranging over subsets of A; (3) restricted (weak) second-order calculi which contain monadic predicate variables ranging over finite subsets of A.
Systems of predicative analysis, II: Representations of ordinals
Authors: Feferman Solomon
Published: May 2006

The eventual purpose of this paper is to provide certain specific representations of ordinals and develop their basic properties as needed for the proofs of the results announced in [3]. Since the choice of these representations is really intelligible only if the general principles involved are made explicit, we devote the first half of this paper (§§1 and 2) to such questions. The entire treatment is self-contained.
Natural well-orderings
Authors: Isles David
Published: May 2006

There seem to be at least two approaches to the problem of generating notations for ordinals: the papers of Bachmann [2], Gerber [5], Feferman [3], and Isles [6] provide examples of one and those of Ackermann [1], Takeuti [10], Kino [7], Schütte [9], and Pfeiffer [8] the other. In both of these the normal forms produced can be regarded as being finite trees “based on” some ordinal π.
Hierarchies of Computable groups and the word problem
Authors: Cannonito Frank B.
Published: May 2006

The word problem for groups was first formulated by M. Dehn [1], who gave a solution for the fundamental groups of a closed orientable surface of genus g ≧ 2. In the following years solutions were given, for example, for groups with one defining relator [2], free groups, free products of groups with a solvable word problem and, in certain cases, free products of groups with amalgamated subgroups [3], [4], [5]. During the period 1953–1957, it was shown independently by Novikov and Boone that the word problem for groups is recursively undecidable [6], [7]; granting Church's Thesis [8], their work implies that the word problem for groups is effectively undecidable.
Trial and error predicates and the solution to a problem of Mostowski
Authors: Putnam Hilary
Published: May 2006

The purpose of this paper is to present two groups of results which have turned out to have a surprisingly close interconnection. The first two results (Theorems 1 and 2) were inspired by the following question: we know what sets are “decidable” — namely, the recursive sets (according to Church's Thesis). But what happens if we modify the notion of a decision procedure by (1) allowing the procedure to “change its mind” any finite number of times (in terms of Turing Machines: we visualize the machine as being given an integer (or an n-tuple of integers) as input. The machine then “prints out” a finite sequence of “yesses” and “nos”. The last “yes” or “no” is always to be the correct answer.); and (2) we give up the requirement that it be possible to tell (effectively) if the computation has terminated? I.e., if the machine has most recently printed “yes”, then we know that the integer put in as input must be in the set unless the machine is going to change its mind; but we have no procedure for telling whether the machine will change its mind or not.

The sets for which there exist decision procedures in this widened sense are decidable by “empirical” means — for, if we always “posit” that the most recently generated answer is correct, we will make a finite number of mistakes, but we will eventually get the correct answer. (Note, however, that even if we have gotten to the correct answer (the end of the finite sequence) we are never sure that we have the correct answer.)
On a question of G. E. Sacks
Authors: Martin Donald A.
Published: May 2006

In [1], p. 171, Sacks asks (question (Q5)) whether there is a recursively enumerable degree of unsolvability d such that

for all n ≧ 0. Sacks points out that the set of conditions which d must satisfy is not arithmetical. For this reason he suggests that a proof of (Q5) might require some new combinatorial device. The purpose of this note is to show how (Q5) may be proved simply by extending the methods of [l].2
Some nondistributive lattices as initial segments of the degrees of unsolvability
Authors: Lerman Manuel
Published: May 2006

The question, “What do initial segments of the degrees of unsolvability look like?” has interested recursive function theorists for several years. Sacks [4] hypothesized that Sis a finite initial segment of degrees if and only if S is order-isomorphic to a finite initial segment of some upper semilattice with a least element. Lachlan [2] suggested the generalization, S is an initial segment of degrees if S is order-isomorphic to some countable upper semilattice with both least and greatest elements.
On modal logic with propositional quantifiers
Authors: Bull R. A.
Published: May 2006

I am interested in extending modal calculi by adding propositional
quantifiers, given by the rules for quantifier introduction:
provided
that p does not occur free in A.
A universal embedding property of the RETs
Authors: Nerode Anil , Manaster Alfred B.
Published: May 2006

Recursive equivalence types are an effective or recursive analogue of cardinal numbers. They were introduced by Dekker in the early 1950's. The richness of various theories related to the recursive equivalence types is demonstrated in this paper by showing that the theory of any countable relational structure can be embedded in or interpreted in these theories. A more complete summary is presented in the last paragraph of this section.

Let E = {0,1, 2, …} be the natural numbers. If α ⊆ E, β ⊆ E, and there is a 1-1 partial recursive function f such that the image under f of α is β, α and β are called recursively equivalent (see [3]). The recursive equivalence type or RET of α, denoted 〈α〉, is the class of all β recursively equivalent to α. Addition of RETs is defined by 〈α〉 + 〈β〉 = 〈{2x ∣ x ∈ α} ∪ 〈{2x + 1 ∣ x ∈ β}〉. The partial ordering ≤ is defined on the RETs by A ≤ B iff (EC)(A + C = B). An RET, X, is called an isol if X ≠ X + 1 or, equivalently, if no representative of X is recursively equivalent to a proper subset of itself. The isols are thus the recursive analogue of the Dedekind-finite cardinals.
On the cardinality of ultraproduct of finite sets
Authors: Shelah Saharon
Published: May 2006

We shall prove that if is an ultrafilter and λℵ0 = λ. This affirms a conjecture of Keisler.
Functions which remain partial recursive under all similarity transformations
Authors: Shapiro Norman
Published: May 2006

This note will characterize those partial functions which are partial recursive under an arbitrary “renaming” of the integers.

The formal result. Let I be the non-negative integers. For any partial function f on I into I, and for any permutation σ of I, let fσ be the partial function which f becomes when the integers are renamed according to σ. That is, let fσ = σfσ−1 in the sense that fσ(x) is defined whenever σ−1(х) ∊ Dom f.
Remark on a system of bernays
Authors: Myhill John
Published: May 2006

In [1], Bemays gives an axiomatization of set-theory which represents the furthest development to date of the Zermelo-Frankel-Gödel tradition. The purpose of this note is to show that one of his axioms is redundant.

Primitives are ∈, set-abstraction (denoted [x/A(x)]) and the Hilbert selector (denoted σ). Different styles are used for free variables (a, b,c, …) and bound variables (x, y, z, …); both kinds of variables range over both sets and classes. Quantifiers and connectives are classical.
Some undecidable problems involving elementary functions of a real variable
Authors: Richardson Daniel
Published: May 2006

Let E be a set of expressions representing real, single valued, partially defined functions of one real variable. E* will be the set of functions represented by expressions in E.

If A is an expression in E, A(x) is the function denoted by A.

It is assumed that E* contains the identity function and the rational numbers as constant functions and that E* is closed under addition, subtraction, multiplication and composition.
An unsolved problem in the theory of constructive order types
Authors: Hamilton Alan G.
Published: May 2006

In the forthcoming monograph of Crossley [1] the question is raised whether the implication 2 + A = A ⇒ 1 + A = A is true for constructive order types. In this paper a partial answer to this question is given, in that a counterexample is constructed, using, however, not the definition of constructive order type (C.O.T.) given in [1], but an earlier one, namely that in Crossley [2]. The difference is that in [1] only orderings which can be imbedded in a standard dense r.e. ordering R by a partial recursive function are considered. The linear ordering constructed in this paper can be shown not to be such. The problem remains open in the case of orderings imbeddable in R.
Weakly atomic-compact relational structures
Authors: Fuhrken G. , Taylor W.
Published: May 2006

A relational structure is called weakly atomic-compact if and only if every set Σ of atomic formulas (taken from the first-order language of the similarity type of augmented by a possibly uncountable set of additional variables as “unknowns”) is satisfiable in whenever every finite subset of Σ is so satisfiable. This notion (as well as some related ones which will be mentioned in §4) was introduced by J. Mycielski as a generalization to model theory of I. Kaplansky's notion of an algebraically compact Abelian group (cf. [5], [7], [1], [8]).
Some consequences of an infinite-exponent partition relation
Authors: Henle J. M.
Published: May 2006

Beginning with Ramsey's theorem of 1930, combinatorists have been intrigued with the notion of large cardinals satisfying partition relations. Years of research have established the smaller ones, weakly ineffable, Erdös, Jonsson, Rowbottom and Ramsey cardinals to be among the most interesting and important large cardinals in set theory. Recently, cardinals satisfying more powerful infinite-exponent partition relations have been examined with growing interest. This is due not only to their inherent qualities and the fact that they imply the existence of other large cardinals (Kleinberg [2], [3]), but also to the fact that the Axiom of Determinacy (AD) implies the existence of great numbers of such cardinals (Martin [5]).

That these properties are more often than not inconsistent with the full Axiom of Choice (Kleinberg [4]) somewhat increases their charm, for the theorems concerning them tend to be a little odd, and their proofs, circumforaneous. The properties are, as far as anyone knows, however, consistent with Dependent Choice (DC).

Our basic theorem will be the following: If k > ω and k satisfies k→(k)k then the least cardinal δ such that has a δ-additive, uniform ultrafilter. In addition, if ACω is assumed, we will show that δ is greater than ω, and hence a measurable cardinal. This result will be strengthened somewhat when we prove that for any k, δ, if then .
Independent Gödel sentences and independent sets
Authors: Dawes A. M. , Florence J. B.
Published: May 2006

In this paper we investigate some of the recursion-theoretic problems which are suggested by the logical notion of independence.

A set S of natural numbers will be said to be k-independent (respectively, ∞-independent) if, roughly speaking, in every correct system there is a k-element set (respectively, an infinite set) of independent true sentences of the form x ∈ S. S will be said to be effectively independent (respectively, absolutely independent) if given any correct system we can generate an infinite set of independent (respectively, absolutely independent) true sentences of the form x ∈ S.

We prove that

(a) S is absolutely independent ⇔S is effectively independent ⇔S is productive;

(b) for every positive integer k there is a Π1 set which is k-independent but not (k + 1)-independent;

(c) there is a Π1 set which is k-independent for all k but not ∞-independent;

(d) there is a co-simple set which is ∞-independent.

We also give two new proofs of the theorem of Myhill [1] on the existence of an infinite set of Σ1 sentences which are absolutely independent relative to Peano arithmetic. The first proof uses the existence of an absolutely independent Π1 set of natural numbers, and the second uses a modification of the method of Gödel and Rosser.
Saturated ideals
Authors: Kunen Kenneth
Published: May 2006

In this paper, we give consistency proofs for the existence of a κ-saturated ideal on an inaccessible κ, and for the existence of an ω2-saturated ideal on ω1. We also include an historical survey outlining other known results on saturated ideals.

§1. Forcing. We assume that the reader is familiar with the usual techniques in forcing and Boolean-valued models (see Jech [3] or Rosser [11]), so we shall just specify here some of the less standard notation.

“cBa” abbreviates “complete Boolean algebra”.

If P (= ‹P, <›) is a notion of forcing, is the associated cBa. We write VP for .

Notions like κ-closed, κ-complete, etc. always mean < κ. Thus, P is κ-closed iff every decreasing chain of length less than κ has a lower bound, and a Boolean algebra is κ-complete iff sups of subsets of of cardinality less than κ always exist.

If is a cBa, x̌ is the object in representing x in V. In many cases, especially with ordinals, the ̌ is dropped. V̌ is the Boolean-valued class representing V — i.e.,
The model theory of ordered differential fields
Authors: Singer Michael F.
Published: May 2006

In this paper, we show that the theory of ordered differential fields has a model completion. We also show that any real differential field, finitely generated over the rational numbers, is isomorphic to some field of real meromorphic functions. In the last section of this paper, we combine these two results and discuss the problem of deciding if a system of differential equations has real analytic solutions. The author wishes to thank G. Stengle for some stimulating and helpful conversations and for drawing our attention to fields of real meromorphic functions.

§ 1. Real and ordered fields. A real field is a field in which −1 is not a sum of squares. An ordered field is a field F together with a binary relation < which totally orders F and satisfies the two properties: (1) If 0 < x and 0 < y then 0 < xy. (2) If x < y then, for all z in F, x + z < y + z. An element x of an ordered field is positive if x > 0. One can see that the square of any element is positive and that the sum of positive elements is positive. Since −1 is not positive, an ordered field is a real field. Conversely, given a real field F, it is known that one can define an ordering (not necessarily uniquely) on F [2, p. 274]. An ordered field F is a real closed field if: (1) every positive element is a square, and (2) every polynomial of odd degree with coefficients in F has a root in F. For example, the real numbers form a real closed field. Every ordered field can be embedded in a real closed field. It is also known that, in a real closed field K, polynomials satisfy the intermediate value property, i.e. if f(x) ∈ K[x] and a, b ∈ K, a < b, and f(a)f(b) < 0 then there is a c in K such that f(c) = 0.
Existentially complete torsion-free nilpotent groups
Authors: Saracino D.
Published: May 2006

This paper continues the study of existentially complete nilpotent groups initiated in [6]. Following [6], we let Kn denote the theory of groups nilpotent of class ≤ n and let Kn+ denote the theory of torsion-free groups nilpotent of class ≤ n. The principal results of [6] were that for n ≥ 2, neither Kn nor Kn+ has a model companion, and the classes E, F, and G of existentially complete, finitely generic and infinitely generic models of Kn are all distinct. The question of the relationships between these classes in the context of Kn was left open, however, and the proof of their distinctness for Kn+ obviously did not carry over to Kn+, because it made strong use of torsion elements.

In this paper we establish the relationships between E, F, and G for K2+. We show that all three classes are distinct. We also show that there is only one countable finitely generic model, and only one countable infinitely generic model, and that all the countable existentially complete models can be arranged in a sequence N1 ⊆ N2 ⊆ N3 ⊆ … ⊆ Nω, where Z(Nn) is the direct sum of n copies of Q. Another result is that the finite and infinite forcing companions of K2+ differ by an ∀∃∀ sentence. Finally, we show that there exist finitely generic models of K2+ in all infinite cardinalities.
Degrees of classes of RE sets
Authors: Shoenfield J. R.
Published: May 2006

In [3], Martin computed the degrees of certain classes of RE sets. To state the results succinctly, some notation is useful.

If A is a set (of natural numbers), dg(A) is the (Turing) degree of A. If A is a class of sets, dg(A) = {dg(A): A ∈ A). Let M be the class of maximal sets, HHS the class of hyperhypersimple sets, and DS the class of dense simple sets. Martin showed that dg(M), dg(HHS), and dg(DS) are all equal to the set H of RE degrees a such that a′ = 0″.

Let M* be the class of coinfinite RE sets having no superset in M; and define HHS* and DS* similarly. Martin showed that dg(DS*) = H. In [2], Lachlan showed (among other things) that dg(M*)⊆K, where K is the set of RE degrees a such that a″ > 0″. We will show that K ⊆ dg (HHS*). Since maximal sets are hyperhypersimple, this gives dg(M*) = dg (HHS*) = K.

These results suggest a problem. In each case in which dg(A) has been calculated, the set of nonzero degrees in dg(A) is either H or K or the empty set or the set of all nonzero RE degrees. Is this always the case for natural classes A? Natural here might mean that A is invariant under all automorphisms of the lattice of RE sets; or that A is definable in the first-order theory of that lattice; or anything else which seems reasonable.
Strict-Π11 predicates on countable and cofinality ω transitive sets
Authors: Grant Philip W.
Published: May 2006

Throughout the paper A will be a transitive set closed under finite subsets and the formulas in various classes mentioned are allowed to contain parameters from A (or from B in §2).

By use of a refinement of Moschovakis' notion of the game-quantifier [13], [14], [15] we are able to obtain a game-theoretic description of s-Π11 predicates over countable sets which then leads to a classification of positive Σ1 inductive sets.

Similar results are then proved for certain sets of cofinality ω. As a consequence we obtain the compactness results of Green [8], [11], Nyberg [16] and Makkai [12].

The use of games to classify inductive sets was initiated by Moschovakis [13], [14], [15] and has been extended to Q-inductive sets by Aczel [2]. Games were also used in a slightly different setting by Vaught [18] and Makkai [12]. In fact, Vaught's proof of the compactness theorem is very close to our proof in §1 and Makkai's extension to cofinality ω sets uses a result similar to Theorem 3 in §2.

We are indebted to the referee for many helpful suggestions, in particular, for bringing to our attention the related works of Vaught and Makkai cited above.
The use of Kripke's schema as a reduction principle
Authors: van Dalen D.
Published: May 2006

The comprehension principle of second order arithmetic asserts the existence of certain species (sets) corresponding to properties of natural numbers. In the intuitionistic theory of sequences of natural numbers there is an analoguous principle, implicit in Brouwer's writing and explicitly stated by Kripke, which asserts the existence of certain sequences corresponding to statements. The justification of this principle, Kripke's Schema, makes use of the concept of the so-called creative subject. For more information the reader is referred to Troelstra [5].

Kripke's Schema reads

There is a weaker version

The idea to reduce species to sequences via Kripke's schema occurred several years ago (cf. [2, p. 128], [5, p. 104]). In [1] the reduction technique was applied in the construction of a model for HAS.

On second thought, however, I realized that there is a straightforward, simpler way to exploit Kripke's schema, avoiding models altogether. The idea to present this material separately was forced on the author by C. Smorynski.

Consider a second order arithmetic with both species and sequence variables. By KS we have

(for convenience we restrict ourselves in KS to 0-1-sequences). An application of AC-NF gives

Of course ξ is not uniquely determined. This is the key to the reduction of full second order arithmetic, or HAS, to a theory of sequences.

We now introduce a translation τ to eliminate species variables. It is no restriction to suppose that the formulae contain only the sequence variables ξ1, ξ3, ξ5, …

Note that by virtue of the definition of τ the axiom of extensionality is automatically verified after translation. The translation τ eliminates the species variables and leaves formulae without species variables invariant.
A new version of Beth semantics for intuitionistic logic
Authors: Gabbay Dov M.
Published: May 2006

We use the notation of Kripke's paper [1]. Let M = (G, K, R) be a tree structure and D a domain and η a Beth model on M. The truth conditions of the Beth semantics for ∨ and ∃ are (see [1]):

(a) η (A ∨ B, H) = T iff for some B ⊆ K, B bars H and for each H′ ∈ B, either η(A, H′) = T or η(B, H′) = T.

(b) η(∃xA(x), H) = T iff for some B ⊆ K, B bars H and for each H′ ∈ B there exists an a ∈ D such that η(A (a), H′) = T.

Suppose we change the truth definition η to η* by replacing condition (b) by the condition (b*) (well known from the Kripke interpretation):

Call this type of interpretation the new version of Beth semantics. We prove

Theorem 1. Intuitionistic predicate logic is complete for the new version of the Beth semantics.

Since Beth structures are of constant domains, and in the new version of Beth semantics the truth conditions for ∧, →, ∃, ∀, ¬ are the same as for the Kripke interpretation, we get:

Corollary 2. The fragment without disjunction of the logic CD of constant domains (i.e. with the additional schema ∀x(A ∨ B(x))→ A ∨ ∀xB(x), x not free in A) equals the fragment without disjunction of intuitionistice logic.
Constructive set theory
Authors: Myhill John
Published: May 2006

This paper is the third in a series collectively entitled Formal systems of intuitionistic analysis. The first two are [4] and [5] in the bibliography; in them I attempted to codify Brouwer's mathematical practice. In the present paper, which is independent of [4] and [5], I shall do the same for Bishop's book [1]. There is a widespread current impression, due partly to Bishop himself (see [2]) and partly to Goodman and the author (see [3]) that the theory of Gödel functionals, with quantifiers and choice, is the appropriate formalism for [1]. That this is not so is seen as soon as one really tries to formalize the mathematics of [1] in detail. Even so simple a matter as the definition of the partial function 1/x on the nonzero reals is quite a headache, unless one is prepared either to distinguish nonzero reals from reals (a nonzero real being a pair consisting of a real x and an integer n with ∣x∣ > 1/n) or, to take the Dialectica interpretation seriously, by adjoining to the Gödel system an axiom saying that every formula is equivalent to its Dialectica interpretation. (See [1, p. 19], [2, pp. 57–60] respectively for these two methods.) In more advanced mathematics the complexities become intolerable.
α-decompositions of α-spaces
Authors: Fowler Northrup
Published: May 2006

The concept of an α-space was introduced and studied by Dekker in [1] and [2] from which we take our terminology and notation. The reader is assumed to be familiar with their contents. In this paper we are interested in the following conjecture which appears in [2, p. 493]:

(*) S ⊕ C = V and S ∥ C and V an α-space ⇒ both S and C are α-spaces.

It can be simply rephrased as:

(**) The two components of an α-decomposition of an α-space are both α-spaces.

In either form it is relevant to the ideas of α-subspace and α-homomorphism. Dekker [2, T5] has established (*) in the case S (or C) is an isolic α-space. In this paper we will prove (*) in two specific cases, one of which is a generalization of Dekker's result.
The infinite injury priority method
Authors: Soare Robert I.
Published: May 2006

One of the most important and distinctive tools in recursion theory has been the priority method whereby a recursively enumerable (r.e.) set A is constructed by stages to satisfy a sequence of conditions {Rn}n∈ω called requirements. If n < m, requirement Rn is given priority over Rm and action taken for Rm at some stage s may at a later stage t > s be undone for the sake of Rn thereby injuring Rm at stage t. The first priority method was invented by Friedberg [2] and Muchnik [11] to solve Post's problem and is characterized by the fact that each requirement is injured at most finitely often.

Shoenfield [20, Lemma 1], and then independently Sacks [17] and Yates [25] invented a much more powerful method in which a requirement may be injured infinitely often, and the method was applied and refined by Sacks [15], [16], [17], [18], [19] and Yates [25], [26] to obtain many deep results on r.e. sets and their degrees. In spite of numerous simplifications and variations this infinite injury method has never been as well understood as the finite injury method because of its apparently greater complexity.

The purpose of this paper is to reduce the Sacks method to two easily understood lemmas whose proofs are very similar to the finite injury case. Using these lemmas we can derive all the results of Sacks on r.e. degrees, and some by Yates and Robinson as well, in a manner accessible to the nonspecialist. The heart of the method is an ingenious observation of Lachlan [7] which is combined with a further simplification of our own.