bluuebunny/crossref_metadata_2025 huggingface dataset:
Conservative reduction classes of Krom formulas
Authors: Aanderaa Stål O. , Börger Egon , Lewis Harry R.
Published: May 2006

A Krom formula of pure quantification theory is a formula in conjunctive normal form such that each conjunct is a disjunction of at most two atomic formulas or negations of atomic formulas. Every class of Krom formulas that is determined by the form of their quantifier prefixes and which is known to have an unsolvable decision problem for satisfiability is here shown to be a conservative reduction class. Therefore both the general satisfiability problem, and the problem of satisfiability in finite models, can be effectively reduced from arbitrary formulas to Krom formulas of these several prefix types.
Implicational logics in natural deduction systems
Authors: López-Escobar E.G.K.
Published: May 2006

In 1959 M. Dummett [3] introduced the logic LC obtained by adding the axiom ACpqCqp to the formalization of the intuitionistic prepositional calculus having modus ponens and substitution as its rules of inference. Later on R. A. Bull [1] showed, by quite a roundabout way, that the implicational theses of LC were precisely the theses of the implicational calculus obtained by adding the axiom CCCpqrCCCqprr to the system of positive implication. In 1964 Bull [2] gave another proof, this time using results of Birkhoff concerning subdirectly reducible algebras.

The aim of this short note is to emphasize that the use of Gentzen's natural deduction systems (see Prawitz [4]) allows us to give a much more direct proof.
Ordinal analysis of terms of finite type
Authors: Howard W. A.
Published: May 2006

Sanchis [Sa] and Diller [Di] have introduced an interesting relation between terms for primitive recursive functionals of finite type in order to obtain a computability proof. The method is as follows. First the relation is shown to be well-founded. Then computability of each term is obtained by transfinite induction over the relation.

Their relation is given by various clauses which define the (immediate) successors of a term. Hence, starting with a term H and repeatedly applying the successor relation one generates the tree of H (say). The problem is to prove that the trees are well-founded. In their proofs Sanchis and Diller use the axiom of bar induction. Diller also gives a proof using transfinite induction: each tree is shown to have a length b < φω(0) (the first ω-critical number) and the induction is over ordinals less than or equal to b.

For proof-theoretic purposes it would be desirable to employ a method of proof which is more elementary than the axiom of bar induction and also to obtain a smaller ordinal bound. The purpose of the following is to provide such a method. We show that for a primitive recursive term H of finite type the tree generated by the relation of Sanchis and Diller has length less than ε0. Our method is similar to that used by Tait [Ta] in his theory of infinite terms. The immediately natural metamathematics is elementary intuitionistic analysis with the axiom of choice and transfinite induction over the relevant ordinal notations. We give several versions of the basic list of successor clauses, and for one version we show how to carry out the treatment in Skolem arithmetic (with primitive recursion of lowest type).
On a problem of MacDowell and Specker
Authors: Nadel Mark
Published: May 2006

Let T extend the theory P of Peano arithmetic, and suppose . Form from a model , in analogy to the way in which the ordered ring of integers is formed from the standard model of arithmetic. Let P′ and T′ be the corresponding analogues of P and T respectively. Now consider the group . In [5] MacDowell and Specker set out to determine the structure of such groups. (The precise statement in [5] refers to the ring of integers rather than the ordered ring. However, as pointed out to us by J. Knight, since Lagrange's Theorem that a positive integer is the sum of four squares is provable in the analogue of P′ for rings (see, for example, the proof in [7, p. 102]), the set of positive elements is definable in the ring, and consequently, so is the ordering. Thus, for the present purpose it makes no difference which of the two structures is used. Of course, one needs the ordering to discuss end extensions, as considered in [5]. On the other hand, one should be aware that in Pr′ one cannot define an ordering, where the theory Pr′ is the theory of the group of integers with distinguished element 1, 〈Z, +, 1〉. The constant 1 is needed so that divisibility mod n can be expressed. We will return to this point later.) In §1 we shall outline the results in this direction obtained in [5].

Lipshitz and Nadel, unaware that a similar question had been posed and investigated in [5] (though, of course aware that [5] contained the celebrated results on end extensions) set out to characterize those models 〈A, +〉 of Pr = Presburger Arithmetic (the complete theory of 〈ω, +〉) which can be expanded to models 〈A, +, ·, 0, 1, ≤〉 of P. They were able to give a complete characterization for countable models 〈A, +〉 in [4], which we describe in §2.
Kleene index sets and functional m-degrees
Authors: Mohrherr Jeanleah
Published: May 2006

A many-one degree is functional if it contains the index set of some class of partial recursive functions but does not contain an index set of a class of r.e. sets. We give a natural embedding of the r.e. m-degrees into the functional degrees of 0′. There are many functional degrees in 0′ in the sense that every partial-order can be embedded. By generalizing, we show there are many functional degrees in every complete Turing degree.

There is a natural tie between the studies of index sets and partial-many-one reducibility. Every partial-many-one degree contains one or two index sets.
Independence results for class forms of the axiom of choice
Authors: Howard Paul E. , Rubin Arthur L. , Rubin Jean E.
Published: May 2006

Let NBG be von Neumann-Bemays-Gödel set theory without the axiom of choice and let NBGA be the modification which allows atoms. In this paper we consider some of the well-known class or global forms of the wellordering theorem, the axiom of choice, and maximal principles which are known to be equivalent in NBG and show they are not equivalent in NBGA.
α-Degrees of maximal α-r.e. sets
Authors: Leggett Anne
Published: May 2006

Martin [10] has computed the degrees of several classes of ω-r.e. sets. Lachlan [3] and Shoenfield [14] have obtained some additional results. For most of the examples, a class of r.e. sets is given by a property that is first-order definable over the lattice of ω-r.e. sets. Then the set of degrees of sets in this class is computed. The only sets of nonzero degrees which arise from the known examples are the following: ϕ, {a∣a is ω-r.e. and a ≠ 0}, {a∣a is ω-r.e. and a′ = 0″}, and {a∣a is ω-r.e. and a″ > 0″} (see [14]).

There have been some results in this direction for α an arbitrary admissible ordinal. Sacks [13] has shown that every nonzero α-r.e. α-degree contains a regular α-r.e. set. Thus regularity does not separate the α-r.e. α-degrees. Simpson [18] has several theorems which give information about the kinds of α-r.e. sets a given α-degree can contain. The classes of α-r.e. sets considered do separate the α-r.e. α-degrees into two nonempty pieces for some α's, but they are not necessarily given by properties which are definable over the lattice of α-r.e. sets. Using some definability results of Lerman [6], we shall make some comments about the definability of these classes of sets.
Recursively saturated nonstandard models of arithmetic
Authors: Smoryński C.
Published: May 2006

Through the ability of arithmetic to partially define truth and the ability of infinite integers to simulate limit processes, nonstandard models of arithmetic automatically have a certain amount of saturation: Any encodable partial type whose formulae all fall into the domain of applicability of a truth definition must, by finite satisfiability and Overspill, be nonstandard-finitely satisfiable—whence realized. This fact was first exploited by A. Robinson, who in Robinson [1963] cited the unrealizability in a given model of a certain encodable partial type to prove Tarski's Theorem on the Undefinability of Truth. A decade later, H. Friedman brought this phenomenon to the public's attention by using it to establish impressive embeddability criteria for countable nonstandard models of arithmetic. Subsequently, Wilkie considered models expandable to “strong theories” and, among such models, complemented Friedman's embeddability criteria with elementary embeddability and isomorphism criteria. Oddly enough, the fact that some kind of saturation property was being employed was not explicitly acknowledged in any of this work.

It is in the unpublished dissertation of Wilmers that these submerged saturation properties first surfaced. [As I have only seen accounts of it (most notably Murawski [1976/1977]) and not the dissertation itself, what I have to say about it will not quite be accurate. (Indeed, the referee has refuted, without providing alternate information, every conjecture I have made about the contents of this thesis.)
Patterns of projecta
Authors: Krawczyk Adam
Published: May 2006

Roughly speaking, a pattern is a finite sequence coding the set of natural numbers n for which the Σn+1 projectum is less than the Σn projectum for a given admissible ordinal. We prove that for each pattern there exists an ordinal realizing it. Several results on the orderings of patterns are given. We conclude the paper with remarks on Δn projecta. The main technique, used throughout the paper, is Jensen's Uniformisation Theorem.
An example concerning Scott heights
Authors: Makkai M.
Published: May 2006

Unless otherwise stated, every structure in this paper is countable in a countable, actually recursive language and every formula is one of .

The definition of the so-called canonical Scott-sentence of a structure M, CSS(M) (compare Nadel [8]), is based on the ordinal invariant called the Scott-height of M, denoted SH(M) (compare Makkai [5]). To describe SH(M), let “b ≡αα”, for finite tuples of equal lengths b and a of elements of M and any ordinal α, stand for “b and a satisfy (in M) the same formulas of quantifier-rank ≤ α” (for the quantifier rank of a formula, see e.g., Barwise [1]); also, let “b ∼ a” mean that there is an automorphism of M mapping b to a. With a fixed M, and a in M, sh(a) (or shM(a)) denotes the least ordinal α such that for all b in M, b ≡αa implies b ∼ a. SH(M) is the least ordinal α such that for all a and b in M, b ≡αa implies b ∼ a; hence SH(M) = sup{sh(a): a in M}.
Algebraic independence
Authors: Knight Julia F.
Published: May 2006

This paper is concerned with algebraic independence in structures that are relatively simple for their size. It is shown that for κ a limit cardinal, if a structure of power at least κ is ∞ω-equivalent to a structure of power less than κ, then must contain an infinite set of algebraically independent elements. The same method of proof yields the fact that if σ is an Lω1ω-sentence (not necessarily complete) and σ has a model of power ℵω then some model of σ contains an infinite algebraically independent set.

All structures are assumed to be of countable similarity type. Letters , etc. will be used to denote either a structure or the universe of the structure. If X ⊆ , the algebraic closure of X (in ), denoted by Cl(X), is the union of all finite sets that are weakly definable (in ) by Lωω-formulas with parameters from X. A set S is algebraically independent if for each a in S, a ∉ Cl(S – {a}). An algebraically independent set is sometimes called a “free” set (in [3] and [4], for example).

It is known (see [5]) that any structure of power ℵn must have a set of n algebraically independent elements, and there are structures of power ℵn with no independent set of size n + 1. In power ℵω every structure will have arbitrarily large finite algebraically independent sets. However, it is consistent with ZFC that some models of power ℵω do not have any infinite algebraically independent set. Devlin [4] showed that if V = L, then for any cardinal κ, if every structure of power κ has an infinite algebraically independent set, then κ has a certain large cardinal property that ℵω can never possess.
Wtt-degrees and T-degrees of r.e. sets
Authors: Stob Michael
Published: May 2006

We use some simple facts about the wtt-degrees of r.e. sets together with a construction to answer some questions concerning the join and meet operators in the r.e. degrees. The construction is that of an r.e. Turing degree a with just one wtt-degree in a such that a is the join of a minimal pair of r.e. degrees. We hope to illustrate the usefulness of studying the stronger reducibility orderings of r.e. sets for providing information about Turing reducibility.
A remark on Africk's paper on Scott's interpolation theorem for Lω1ω
Authors: Motohashi Nobuyoshi
Published: May 2006

In order to prove that the Scott's interpolation theorem fails in Lω1ω, H. Africk proved the following lemma in [1]. (See [1] for notations.)

Africk's Lemma. Suppose that and . Then every -sentence in Lω1ω is equivalent to a sentence of the form and a sentence of the form , where Ai,j, Bi,j, are Fj-sentences and there are only countable distinct Ai,j or Bi,j together.

But this lemma is false as is shown in the following: Suppose that Z = {0,1}, Fj = {Pk,j}k⊂ω and . Let A be the sentence ⋀k⊂ω(∀xPk,0(x) ∨ ∀xPk,1(x)). If Africk's Lemma is true, then there are countably many Fj-sentences , such that A is equivalent to Since is countable, there are only countably many distinct pairs (Ai,0, Ai,1). So, we get a countable set {(Bi,0, Bi,1)}i⊂ω, such that A is equivalent to ⋁ik⊂ω(Bk,0 ∧ Bk,1). Since Bk,0 ∧ Bk,1 → ∀xPk,0(x) ∨ ∀xPk,1 is l-valid(i.e. valid in all first-order structures of cardinality 1) for every k ϵ ω, we have that either Bk,0 → ∀xPk,0(x) is 1-valid or Bk,0 → ∀xPk,1(x) is 1-valid. Let I be the set of all the k ϵ ω such that Bk,0 → ∀xPk,0(x) is 1-valid and the first-order structure defined by , , if k ϵ I and , if k ∉ I.
First-order topological axioms
Authors: Kopperman R. D.
Published: May 2006

We exhibit a finite list of first-order axioms which may be used to define topological spaces. For most separation axioms we discover a first-order equivalent statement.
Some facts about Kurt Gödel
Authors: Wang Hao
Published: May 2006

The text of this article was done together with Gödel in 1976 to 1977 and was approved by him at that time. The footnotes and section headings have been added much later.

Gödel was born on April 28, 1906 at Brno (or Brünn in German), Czechoslovakia (at that time part of the Austro-Hungarian Monarchy). After completing secondary school there, he went, in 1924, to Vienna to study physics at the University. His interest in precision led him from physics to mathematics and to mathematical logic. He enjoyed much the lectures by Furtwangler on number theory and developed an interest in this subject which was, for example, relevant to his application of the Chinese remainder theorem in expressing primitive recursive functions in terms of addition and multiplication. In 1926 he transferred to mathematics and coincidentally became a member of the M. Schlick circle. However, he has never been a positivist, but accepted only some of their theses even at that time. Later on, he moved further and further away from them. He completed his formal studies at the University before the summer of 1929. He also attended during this period philosophical lectures by Heinrich Gomperz whose father was famous in Greek philosophy.

At about this time he read the first edition of Hilbert-Ackermann (1928) in which the completeness of the (restricted) predicate calculus was formulated and posed as an open problem. Gödel settled this problem and wrote up the result as his doctoral dissertation which was finished and approved in the autumn of 1929. The degree was granted on February 6, 1930. A somewhat revised version of the dissertation was published in 1930 in the Monatshefte.
On a combinatorial principle of Hajnal and Komjáth
Authors: Velleman Dan
Published: May 2006

In their paper [3], Hajnal and Komjáth define the following combinatorial principle:

Definition 1.1. Suppose κ is an infinite cardinal and n < ω. Then Hn(κ) is the statement: There is a function F: [κ]n → [[κ]ω]≤ω such that

(a) ∀A ∈[κ]n ∀Y ∈ F(A)(Y ⊆ min (A)), and

(b) .

Hn(κ) is related to a more general principle introduced by Hajnal and Nagy in [4]. For applications of these principles to free sets for set mappings and Ramsey games we refer the reader to [3] and [4].

In [3] Hajnal and Komjáth prove the consistency of ZFC + GCH + ∀n ∈ ω(Hn + 1(ωn + 1)), relative to an ω-Mahlo cardinal. They conjecture that L is a model of this theory, and suggest that the proof might require higher gap morasses. The first few cases of this conjecture are known to be true; it is easy to see that if CH holds then H1 (ω1) is true, and Laver proved that V = L implies H2(ω2). In this paper we go one step further and prove V = L → H3(ω3). Unfortunately our methods do not appear to give Hn (ωn) for n ≥ 4.

Most of our notation is standard. If X is any set and κ is a cardinal number then [X]κ is the set of subsets of X with cardinality κ, and [X]≤κ is the set of subsets of X with cardinality ≤ κ. If X is a set of ordinals then tp(X) is the order type of X.
Recursion in Kolmogorov's R-operator and the ordinal σ3
Authors: John Thomas
Published: May 2006

The theory of objects recursive in functions of higher types was developed originally by Kleene [Kl 1,2]. The sets of objects of finite types are defined by Kleene as follows:

T0 = ω = the set of nonnegative integers,

and, for all i ∈ ω,

Ti+1 = Tiω = the set of total functions from Ti to ω.

In order to study and classify the functions recursive in Kolmogorov's R-operator, it is necessary to discuss recursion in partial functions of higher types. Accordingly, we define the partial objects of higher finite types by

and, for all i ∈ ω,

= the set of partial functions from Ti to ω.

In addition to considering the partial functions from Ti to ω, the “hereditary partial” functions also have to be considered. For example, Hinman has studied objects of type 2 which act on partial functions from ω to ω. In case of dealing with a function F which has partial functions in its domain, we usually require that F be consistent, i.e. if F(f) is defined and g is an object of the same type as f, defined at least at all points where f is defined (in short, g extends f—notation: g ⊇ f), then F(g) is defined and is equal to F(f). Now we can define the higher type partial objects which are consistent by

and, for all i ∈ ω,

= the set of consistent partial functions from to ω.
Weak partition relations and measurability
Authors: Spector Mitchell
Published: May 2006

The concept of "partition relation" has proven to be extremely important in the development of the theory of large cardinals. This is due in good part to the fact that the ordinal numbers which appear as parameters in partition relations provide a natural way to define a detailed hierarchy of the corresponding large cardinal axioms. In particular, the study of cardinals satisfying Ramsey-Erdös-style partition relations has yielded a great number of very interesting large cardinal axioms which lie in strength strictly between inaccessibility and measurability. It is the purpose of this paper to show that this phenomenon does not occur if we use infinite exponent partition relations; no such partition relation has consistency strength strictly between inaccessibility and measurability. We also give a complete determination of which infinite exponent partition relations hold, assuming that there is no inner model of set theory with a measurable cardinal.

Our notation is standard. If F is a function and x is a set, then F″x denotes the range of F on x. If X is a set of ordinals and α is an ordinal, then [X]α is the collection of all subsets of X of order type α. We identify a member of [X]α with a strictly increasing function from α to X. If p ∈ [X]α and q ∈ [α]β, then the composition of p with q, which we denote pq, is a member of [X]β.
Decision problems concerning properties of finite sets of equations
Authors: Kalfa Cornelia
Published: May 2006

In this paper a general method of proving the undecidability of a property P, for finite sets Σ of equations of a countable algebraic language, is presented. The method is subsequently applied to establish the undecidability of the following properties, in almost all nontrivial such languages:

1. The first-order theory generated by the infinite models of Σ is complete.

2. The first-order theory generated by the infinite models of Σ is model-complete.

3. Σ has the joint-embedding property.

4. The first-order theory generated by the models of Σ with more than one element has the joint-embedding property.

5. The first-order theory generated by the infinite models of Σ has the joint-embedding property.

A countable algebraic language ℒ is a first-order language with equality, with countably many nonlogical symbols but without relation symbols, ℒ is trivial if it has at most one operation symbol, and this is of rank one. Otherwise, ℒ is nontrivial. An ℒ-equation is a sentence of the form , where φ and ψ are ℒ-terms. The set of ℒ-equations is denoted by Eqℒ. A set of sentences is said to have the joint-embedding property if any two models of it are embeddable in a third model of it.

If P is a property of sets of ℒ-equations, the decision problem of P for finite sets of ℒ-equations is the problem of the existence or not of an algorithm for deciding whether, given a finite Σ ⊂ Eqℒ, Σ has P or not.
Splitting properties of r.e. sets and degrees
Authors: Downey R. G. , Welch L. V.
Published: May 2006

A pair of r.e. sets A1, A2 are said to split an r.e. set A (written A1 Δ A2 = A) if A1 ∩ A2 = ∅ and A1 ∪ A2 = A. In the literature there are various results asserting certain splitting properties hold for all r.e. sets. For example Sacks' splitting theorem (cf. [So]) asserts that an r.e. nonrecursive set A may be split into a pair of Turing incomparable r.e. sets A1, A2, and Lachlan's splitting theorem [La5] asserts that A may be split into a pair of r.e. sets A1, A2 for which there exists an r.e. set B with B ⊕ A1, B ⊕ A2 <TA and with the infinum of the Turing degrees of B ⊕ A1 and B ⊕ A2 existing in the upper semilattice of r.e. degrees.

Two of the earliest observations establishing that splitting properties possessed by some r.e. sets are not possessed by others, are Lachlan's nondiamond theorem [La1] (and so, in particular, no complete r.e. set can be split nontrivially with degree theoretic inf 0) and the Yates-Lachlan construction of a minimal pair (a pair of nonzero r.e. degrees with inf 0). Other examples of this phenomenon, which are not obtained by interpreting degree theoretic results in the r.e. sets, are Lachlan's construction of nonmitotic r.e. sets [La2] (sets which cannot be split into a pair of r.e. sets of the same degree) and, later, Ladner's [Ld1, 2] and Ingrassia's [In] analysis of their degrees.
Distributive ideals and partition relations
Authors: Johnson C. A.
Published: May 2006

It is a theorem of Rowbottom [12] that ifκis measurable andIis a normal prime ideal onκ, then for eachλ<κ,

In this paper a natural structural property of ideals, distributivity, is considered and shown to be related to this and other ideal theoretic partition relations.

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

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

We give a new elementary proof of the comparison theorem relating and ; the proof does not use Skolem theories.

By the same method we prove:

a) , for suitable classes of sentences;

b) proves the consistency of , for finite k, and hence is stronger than .

a) and b) answer a question of Feferman and Sieg.
Theories with finitely many models
Authors: Thomas Simon
Published: May 2006

If L is a first order language and n is a natural number, then Ln is the set of formulas which only make use of the variables x1,…,xn. While every finite structure is determined up to isomorphism by its theory in L, the same is no longer true in Ln. This simple observation is the source of a number of intriguing questions. For example, Poizat [2] has asked whether a complete theory in Ln which has at least two nonisomorphic finite models must necessarily also have an infinite one. The purpose of this paper is to present some counterexamples to this conjecture.

Theorem. For each n ≤ 3 there are complete theories in L2n−2andL2n−1having exactly n + 1 models.

In our notation and definitions, we follow Poizat [2]. To test structures for elementary equivalence in Ln, we shall use the modified Ehrenfeucht-Fraïssé games of Immerman [1]. For convenience, we repeat his definition here.

Suppose that L is a purely relational language, each of the relations having arity at most n. Let and ℬ be two structures for L. Define the Ln game on and ℬ as follows. There are two players, I and II, and there are n pairs of counters a1, b1, …, an, bn. On each move, player I picks up any of the counters and places it on an element of the appropriate structure.
Recursive categoricity and persistence
Authors: Millar Terrence
Published: May 2006

This paper is concerned with recursive structures and the persistance of an effective notion of categoricity. The terminology and notational conventions are standard. We will devote the rest of this paragraph to a cursory review of some of the assumed conventions. If θ is a formula, then θk denotes θ if k is zero, and ¬θ if k is one. If A is a sequence with domain a subset of ω, then A∣n denotes the sequence obtained by restricting the domain of A to n. For an effective first order language L, let {ci∣i<ω} be distinct new constants, and let {θi∣i<ω} be an effective enumeration of all sentences in the language L ∪ {ci∣j<ω}. An infinite L-structure is recursive iff it has universe ω and the set is recursive, where cn is interpreted by n. In general we say that a set of formulas is recursive if the set of its indices with respect to an enumeration such as above is recursive. The ∃-diagram of a structure is recursive if the structure is recursive and the set and θi is an existential sentence} is also recursive. The definition of “the ∀∃-diagram of is recursive” is similar.
The inclusion-exclusion principle for finitely many isolated sets
Authors: Dekker J. C. E.
Published: May 2006

A nonnegative integer is called a number, a collection of numbers a set and a collection of sets a class. We write ε for the set of all numbers, o for the empty set, N(α) for the cardinality of α, ⊂ for inclusion and ⊂+ for proper inclusion. Let α, β1,…, βk be subsets of some set υ. Then α′ stands for υ−α and β1 … βk for β1 ∩ … ∩ βk. For subsets α1, …, αr of υ we write:

Note that α0 = υ, hence s0 = N(υ). If the set υ is finite, the classical inclusion-exclusion principle (abbreviated IEP) states

In this paper we generalize (a) and(b) to the case where α1, …, αr are subsets of some countable but isolated set υ. Then the role of the cardinality N(α) of the set α is played by the RET (recursive equivalence type) Req α of α. These generalizations of (a) and (b) are proved in §3. Since they involve recursive distinctness, this notion is discussed in §2. In §4 we consider a natural extension of “the sum of the elements of a finite set σ” to the case where σ is countable. §5 deals with valuations, i.e., certain mappings μ from classes of isolated sets into the collection Λ of all isols which permit us to further generalize IEP by substituting μ(α) for Req α.
Model companions for finitely generated universal Horn classes
Authors: Burris Stanley
Published: May 2006

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

In 1949 Nelson [5] proposed a constructive logic in which falsity is conceived in a fashion analogous to that for intuitionistic truth. The predicate calculus N (for strong negation) was characterized by the usual axioms and rules for positive intuitionistic connectives (see Kleene [4, p. 82, la–7 and 9–12]), with the additional axiom schemata for strong negation: A ⊃ (¬A ⊃ B),

Nelson's paper showed that N may be interpreted with concepts for constructive truth (P-realizability) and falsity (N-realizability). The paper also gave mappings between the intuitionistic and strong negation systems of arithmetic.

These mappings are easily adapted to pure predicate calculus. One shows that intuitionistic predicate calculus I is a subsystem of N by reading the intuitionistic negation of A as A ⊃ B & ¬B in N. It is possible to map N into a subsystem of I using the definition of A′ in [5, p. 19] changing only the definition of (¬A)′ for atomic A to A ⊃ B & ¬B.
Simplified morasses
Authors: Velleman Dan
Published: May 2006

We define a structure which is much simpler than a morass, but whose existence is equivalent to the existence of a morass.
Which set existence axioms are needed to prove the Cauchy/Peano theorem for ordinary differential equations?
Authors: Simpson Stephen G.
Published: May 2006

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

Problems of computing probabilities of statements about large, finite structures have become an important subject area of finite combinatorics. Within the last two decades many researchers have turned their attention to such problems and have developed a variety of methods for dealing with them. Applications of these ideas include nonconstructive existence proofs for graphs with certain properties by showing the properties occur with nonzero probabilities (for examples see Erdös and Spencer [ES] and Bollobás [Bo]), and determination of average running times for sorting algorithms by computing asymptotic probabilities of statements about permutations (see Knuth [Kn]). Two types of techniques recur in solutions to such problems: probabilistic techniques, such as those used by Erdös and Spencer [ES], and classical assymptotic techniques, such as those surveyed by Bender [Be] and de Bruijn [Br]. Studying this body of techniques, one notices that characteristics of these problems suggest certain methods of solution, in much the same way that the form of an integrand may suggest certain substitutions. The question arises, then, as to whether there is a systematic way to approach these problems: is there an algorithm for computing asymptotic probabilities? I will show that the answer is “no”—for any reasonable formulation, the problem of computing asymptotic probabilities is undecidable.

The main theorem of the paper is Theorem 1.6, which says that there is a finitely axiomatizable class in which every first order sentence has an asymptotic probability of 0 or 1—i.e., is almost always true or almost always false in finite structures—but for which the problem of deciding whether a sentence has asymptotic probability 0 or 1 is undecidable. Heretofore, classes known to have such a 0-1 law have had decidable asymptotic probability problems (see Lynch [Ly] for examples and a discussion of previous work in the area).
Kueker's conjecture for superstable theories
Authors: Buechler Steven
Published: May 2006

We prove that if every uncountable model of a first-order theory T is ω-saturated and T is superstable then T is categorical in some infinite power.
A direct proof of the finite developments theorem
Authors: de Vrijer Roel
Published: May 2006

Let M be a term of the type free λ-calculus and let be a set of occurrences of redexes in M. A reduction sequence from M which first contracts a member of and afterwards only residuals of is called a development (of M with respect to ). The finite developments theorem says that developments are always finite.

There are several proofs of this theorem in the literature. A plausible strategy is to define some kind of measure for pairs (M, ), which—if M′ results from M by contracting a redex occurrence in and ′ is the set of residuals of in M′— decreases in passing from (M, ) to (M′, ′). This procedure is followed as a matter of fact in the proofs in Hyland [4] and in Barendregt [1] (both are covered in Klop [5]). If, as in the latter proof, the natural numbers are used as measures, then the measure of (M, ) will actually denote an upper bound of the number of reduction steps in a development of M with respect to .

In the present proof we straightforwardly define for each pair (M, ) a natural number, which can easily be seen to indicate the exact number of reduction steps in a development of maximal length of M with respect to .
Isomorphisms between HEO and HROE, ECF and ICFE
Authors: Bezem Marc
Published: May 2006

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

As is well known, NF is a first-order theory whose language coincides with that of ZF. The nonlogical axioms of the theory are: Extensionality. (x)(y)[(z)(z ∈ x ↔ z ∈ y) → x = y].

Comprehension. (Ex)(y)(y ∈ x ↔ ψ) for every stratified ψ in which x does not occur free (a formula of NF is said to be stratified if it can be turned into a formula of the simple theory of types by adding type indices (natural numbers ≥ 0) to its variables).

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

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

A very fruitful line of research in recent years has been the application of techniques in large cardinals and forcing to the production of models in which certain consequences of the axiom of determinateness (AD) are true or in which certain “AD-like” consequences are true. Numerous results have been published on this subject, among them the papers of Bull and Kleinberg [4], Bull [3], Woodin [15], Mitchell [11], and [1], [2].

Another such model will be constructed in this paper. Specifically, the following theorem is proven.

Theorem 1. Con(ZFC + There are cardinals κ < δ < λ so that κ is a supercompact limit of supercompact cardinals, λ is a measurable cardinal, and δ is λ supercompact) ⇒ Con(ZF + ℵ1 and ℵ2 are Ramsey cardinals + The ℵn for 3 ≤ n ≤ ω are singular cardinals of cofinality ω each of which carries a Rowbottom filter + ℵω + 1 is a Ramsey cardinal + ℵω + 2 is a measurable cardinal).

It is well known that under AD + DC, ℵ2 and ℵ2 are measurable cardinals, the ℵn for 3 ≤ n < ω are singular Jonsson cardinals of cofinality ℵ2, ℵω is a Rowbottom cardinal, and ℵω + 1 and ℵω + 2 are measurable cardinals.

The proof of the above theorem will use the existence of normal ultrafilters which satisfy a certain property (*) (to be defined later) and an automorphism argument which draws upon the techniques developed in [9], [2], and [4] but which shows in addition that certain supercompact Prikry partial orderings are in a strong sense “homogeneous”. Before beginning the proof of the theorem, however, we briefly mention some preliminaries.
Typical ambiguity and the axiom of choice
Authors: Crabbé Marcel
Published: May 2006

E. Specker has proved that the axiom of choice (AC) is false in NF [6]. Since AC is stratified, one can, according to another famous result of Specker [7], prove directly ¬AC in type theory (TT) plus some finite set of ambiguity axioms, i.e. sentences of the form φ ↔ φ+, where φ+ results from φ by adding one to its type indices.

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

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

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

In §2 we introduce semi-De Morgan algebras and prove the main theorem, which, roughly speaking, states that certain elements of a semi-De Morgan algebra form a De Morgan algebra. Several applications then follow, including new axiomatizations of distributive pseudocomplemented lattices, Stone algebras and De Morgan algebras.
First order topological structures and theories
Authors: Pillay Anand
Published: May 2006

In this paper we introduce the notion of a first order topological structure, and consider various possible conditions on the complexity of the definable sets in such a structure, drawing several consequences thereof.

Our aim is to develop, for a restricted class of unstable theories, results analogous to those for stable theories. The “material basis” for such an endeavor is the analogy between the field of real numbers and the field of complex numbers, the former being a “nicely behaved” unstable structure and the latter the archetypal stable structure. In this sense we try here to situate our work on o-minimal structures [PS] in a general topological context. Note, however, that the p-adic numbers, and structures definable therein, will also fit into our analysis.

In the remainder of this section we discuss several ways of studying topological structures model-theoretically. Eventually we fix on the notion of a structure in which the topology is “explicitly definable” in the sense of Flum and Ziegler [FZ]. In §2 we introduce the hypothesis that every definable set is a Boolean combination of definable open sets. In §3 we introduce a “dimension rank” on (closed) definable sets. In §4 we consider structures on which this rank is defined, and for which also every definable set has a finite number of definably connected definable components. We show that prime models over sets exist under such conditions.
Injectives in finitely generated universal Horn classes
Authors: Albert Michael H. , Willard Ross
Published: May 2006

Let K be a finite set of finite structures. We give a syntactic characterization of the property: every element of K is injective in ISP(K). We use this result to establish that is injective in ISP() for every two-element algebra .
Open induction and the true theory of rationals
Authors: Adamowicz Zofia
Published: May 2006

In the paper we prove the following theorem:

Theorem. There is a model N of open induction in which the set of primes is bounded and N is such that its field of fractions 〈N*, +, ·, <〉 is elementarily equivalent to 〈Q, +, ·, <〉 (the standard rationals).

We fix an ω1-saturated model 〈M, +, ·, <〉 of PA. Let 〈M*, +, ·, <〉 denote the field of fractions of M. The model N that we are looking for will be a substructure of 〈M*, +, ·, <〉.

If A ⊆ M* then let Ā denote the ring generated by A within M*, Ậ the real closure of A, and A* the field of fractions generated by A. We have

Let J ⊆ M. Then 〈M*, +, ·〉 is a linear space over J*. If x1,…,xk ∈ M*, we shall say that x1,…,xk are J-independent if 〈1, x1,…, xk〉 are J*-independent in the usual sense. As usual, we extend the notion of J-independence to the case of infinite sets.

If A ⊆ M* and X ⊆ A, then we say that X is a J-basis of A if X is a maximal subset of A which is J-independent.
An analytic completeness theorem for logics with probability quantifiers
Authors: Hoover Douglas N.
Published: May 2006

We give a completeness theorem for a logic with probability quantifiers which is equivalent to the logics described in a recent survey paper of Keisler [K]. This result improves on the completeness theorems in [K] in that it works for languages with function symbols and produces a model whose universe is an analytic subset of the real line, and whose relations and functions are Borel relative to this universe.
Monotone but not positive subsets of the Cantor space
Authors: Dougherty Randall
Published: May 2006

A subset of the Cantor space ω2 is called monotone iff it is closed upward under the partial ordering ≤ defined by x ≤ y iff x(n) ≤ y(n) for all n ∈ ω. A set is -positive (-positive) iff it is monotone and -positive set is a countable union of -positive sets; a -positive set is a countable intersection of -positive sets. (See Cenzer [2] for background information on these concepts.) It is clear that any -positive set is and monotone; the converse holds for n ≤ 2 [2] and was conjectured by Dyck to hold for greater n. In this note, we will disprove this conjecture by giving examples of monotone sets (for n ≥ 3) which are not even -positive.

First we note a few isomorphisms. The space (ω2, ≤) is isomorphic to the space (ω2 ≥), so instead of monotone and positive sets we may construct hereditary and negative sets (the analogous notions with “closed upward” replaced by “closed downward”). Also, (ω2, ≤) is isomorphic to ((ω), ⊆), where denotes the power set operator, or to ((S), ⊆) for any countably infinite set S.

In order to remove extraneous notation from the proofs, we state the results in an abstract form (whose generality is deceptive).