bluuebunny/crossref_metadata_2025 huggingface dataset:
On carnap and popper probability functions
Authors: Leblanc Hugues , van Fraassen Bas C.
Published: May 2006

With PC understood to be the propositional calculus of [3], call a binary function Pr from the wffs of PC to the reals a Carnap (probability) function if it meets requirements A1—A5 in Table I (with ‘⊢…’ short in A3—A4 for ‘… is a tautology’), and call the function a Popper (probability) function if it meets requirements Bl—B6 there:

Leblanc established in [3] that every Carnap function is a Popper one, and he tendered proof of the converse. As reported by Stalnaker in [5], the proof unfortunately was incomplete, a mishap due to Leblanc's abbreviating ‘Pr(A, ∼ A) = 1’ as ‘⊢ A’ when Pr is a Popper function. Borrowing from [4], Leblanc did show, as Harper notes in [2, footnote 17], that

(1) If Pr is a Popper function and A is a tautology, then Pr(A, ∼ A) = 1. He did not, however, show that

(2) If Pr is a Popper function and Pr(A, ∼ A) = 1, then A is a tautology.

Nor could he have done so: (2) is false, as the simplest of counterexamples shows. Denied (2), Leblanc had no hope of proving that every Popper function is a Carnap one: of a Popper function Pr it is easily ascertained that Pr meets requirement A4 if and only if Pr(A, ∼ A) = 1 just in case A is a tautology.
Flipping properties in arithmetic
Authors: Kirby L. A. S.
Published: May 2006

Flipping properties were introduced in set theory by Abramson, Harrington, Kleinberg and Zwicker [1]. Here we consider them in the context of arithmetic and link them with combinatorial properties of initial segments of nonstandard models studied in [3]. As a corollary we obtain independence resutls involving flipping properties.

We follow the notation of the author and Paris in [3] and [2], and assume some knowledge of [3]. M will denote a countable nonstandard model of P (Peano arithmetic) and I will be a proper initial segment of M. We denote by N the standard model or the standard part of M. X ↑ I will mean that X is unbounded in I. If X ⊆ M is coded in M and M ≺ K, let X(K) be the subset of K coded in K by the element which codes X in M. So X(K) ⋂ M = X.

Recall that M ≺IK (K is an I-extension of M) if M ≺ K and for some c∈K,

In [3] regular and strong initial segments are defined, and among other things it is shown that I is regular if and only if there exists an I-extension of M.
The model of set theory generated by countably many generic reals
Authors: Blass Andreas
Published: May 2006

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

Let p be an odd prime. A method is described which given a structure M of finite similarity type produces a nilpotent group of class 2 and exponent p which is in the same stability class as M.

Theorem. There are nilpotent groups of class 2 and exponent p in all stability classes.

Theorem. The problem of characterizing a stability class is equivalent to characterizing the (nilpotent, class 2, exponent p) groups in that class.
Hyper-torre isols
Authors: Ellentuck Erik
Published: May 2006

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

A minimal pair of recursively enumerable (r.e.) degrees is a pair of degrees a, b of nonrecursive r.e. sets with the property that if c ≤ a and c ≤ b then c = 0. Lachlan [2] and Yates [4] independently proved the existence of minimal pairs. It was natural to ask whether for an arbitrary nonzero r.e. degree c there is a minimal pair a, b with a ≤ c and b ≤ c. In 1971 Lachlan and Ladner proved that a minimal pair below c cannot be obtained in a uniformly effective way from c for r.e. c ≠ 0. but the result was never published. More recently Cooper [1] showed that if c is r.e. and c′ = 0″ then there is a minimal pair below c.

In this paper we prove two results:

Theorem 1. There exists a nonzero r.e. degree with no minimal pair below it.

Theorem 2. There exists a nonzero r.e. degree c such that, if d is r.e. and 0 < d ≤ c, then there is a minimal pair below d.

The second theorem is a straightforward variation on the original minimal pair construction, but the proof of the first theorem has some novel features. After some preliminaries in §1, the first theorem is proved in §2 and the second in §3.

I am grateful to Richard Ladner who collaborated with me during the first phase of work on this paper as witnessed by our joint abstract [3]. The many discussions we had about the construction required in Theorem 1 were of great help to me.
Proper classes
Authors: Maddy Penelope
Published: May 2006

The modern problem of infinity was first raised by Aristotle who held (at least on the popular interpretation) that infinite sets exist potentially (i.e. one more number can always be counted, one more division can always be made in a line segment) but not actually (i.e. the numbers or divisions cannot all exist at one time). In fact, Aristotle not only held that completed infinities never actually exist, but also that they are impossible, that is, that the assumption that they do exist leads to contradictions. To see this, consider Aristotle's view that mathematical entities depend for their existence on the existence of primary substance in which they inhere, coupled with his view that there can be no infinite body. From these it follows that if there were actual completed infinities, infinite bodies would both exist and not exist. The details here are not so important as the idea that if a completed infinite is assumed to exist a contradiction follows.

This negative attitude towards completed infinities flourished for centuries. By the mid-1500's, the German mathematician Stifel (who apparently also invented Pascal's triangle) was moved to condemn irrational numbers simply by their association with the completed infinite:

… just as an infinite number is not a number, so an irrational number is not a true number, but lies hidden in a kind of cloud of infinity.

About a hundred years later, Galileo further discredited the completed infinite by pointing out that line segments of different lengths can be brought into one-to-one correspondence by projection, as can the natural numbers and the perfect squares by assigning each number to its square.
The existence of countable totally nonconstructive extensions of the countable atomless Boolean algebra
Authors: Madison E. W.
Published: May 2006

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

A natural way of studying the computability of an algebraic structure or process is to apply some of the theory of the recursive functions to the algebra under consideration through the manufacture of appropriate coordinate systems from the natural numbers. An algebraic structureA= (A;σ1,…,σk) iscomputableif it possesses a recursive coordinate system in the following precise sense: associated toAthere is a pair (α, Ω) consisting of a recursive set of natural numbersΩand a surjectionα:Ω→Aso that (i) the relation defined onΩbyn≡αmiffα(n) =α(m) inAis recursive, and (ii) each of the operations ofAmay be effectively followed inΩ, that is, for each (say)r-ary operationσonAthere is anrargument recursive functiononΩwhich commutes the diagram

whereinαrisr-foldα× … ×α.

This concept of a computable algebraic system is the independent technical idea of M.O.Rabin [18] and A.I.Mal'cev [14]. From these first papers one may learn of the strength and elegance of the general method of coordinatising; note-worthy for us is the fact that computability is a finiteness condition of algebra—an isomorphism invariant possessed of all finite algebraic systems—and that it serves to set upon an algebraic foundation the combinatorial idea that a system can be combinatorially presented and have effectively decidable term or word problem.
Dimension theory and homogeneity for elementary extensions of a model
Authors: Pillay Anand
Published: May 2006

We take a fixed countable model M0, and we look at the structure of and number of its countable elementary extensions (up to isomorphism over M0). Assuming that S(M0) is countable, we prove that if N is a weakly minimal extension of , and if then there is an elementary embedding of N into M over M0), then N is homogeneous over M0. Moreover the condition that ∣S(M0)∣ = ℵ0 cannot be removed. Under the hypothesis that M0 contains no infinite set of tuples ordered by a formula, we prove that M0 has infinitely many countable elementary extensions up to isomorphism over M0. A preliminary result is that all types over M0 are definable, and moreover is definable over M0 if and only if is definable over M0 (forking symmetry). We also introduce a notion of relative homogeneity, and show that a large class of elementary extensions of M0 are relatively homogeneous over M0 (under the assumptions that M0 has no order and S(M0) is countable).

I will now discuss the background to and motivation behind the results in this paper, and also the place of this paper relative to other conjectures and investigations. To simplify notation let T denote the complete diagram of M0. First, our result that if M0 has no order then T has infinitely many countable models is related to the following conjecture: any theory with a finite number (more than one) of countable models is unstable.
Extremely undecidable sentences
Authors: Boolos George
Published: May 2006

Let ‘ϕ’, ‘χ’, and ‘ψ’ be variables ranging over functions from the sentence letters P0, P1, … Pn, … of (propositional) modal logic to sentences of P(eano) Arithmetic), and for each sentence A of modal logic, inductively define Aϕ by

[and similarly for other nonmodal propositional connectives]; and

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

The results in this paper were motivated by the following result due to R. Solovay.

Theorem 1 (Solovay). Let M be a nonstandard model of Peano's first order axioms P and let I ⊂e M (i.e. ϕ ≠ ⊂ M and I is closed under < and successor). Then for each of the functions we can define J ⊆e I in ‹M, I› such that J is closed under that function. (∣x∣ denotes [log2(x)].)

Proof. Just notice that the cuts defined by

are successively closed under

In view of Theorem 1, the following question was raised by R. Solovay: Can we define J ⊆ I in ‹M, I› such that J is closed under exponentiation? In Theorem 2 we show that the answer is “no”. Theorem 3 is based on Theorem 2 and extends the technique to cuts which are models of subsystems of P.

To prove both theorems we shall need an estimate due to R. Parikh (see [1], especially the proof of Theorem 2.2a). For the sake of completeness, and also to introduce some notation we shall sketch Parikh's estimate in the next section. At all times we shall give the easiest estimates which still work rather than the sharpest ones.
Some recent developments in higher recursion theory
Authors: Friedman Sy D.
Published: May 2006

In recent years higher recursion theory has experienced a deep interaction with other areas of logic, particularly set theory (fine structure, forcing, and combinatorics) and infinitary model theory. In this paper we wish to illustrate this interaction by surveying the progress that has been made in two areas: the global theory of the κ-degrees and the study of closure ordinals.
The τ-theory for free groups is undecidable
Authors: Lo Libo
Published: May 2006

In this paper we give short proofs to the undecidability of the τ-theory for free groups and other relevant theories.
Closure properties of almost-finiteness classes in recursive function theory
Authors: Rolletschek Heinrich
Published: May 2006

In this paper we will investigate closure properties of the class of immune sets and of other, more restricted classes of sets of natural numbers under union and similar operations. Our main theorem states that there exists a hyperhyperimmune set A such that A join A is not hyperhyperimmune. We will prove this result in §3. The remaining questions about closure properties are all much easier and will be answered in §2.

We consider the closure properties which are given in the following

Definition. Let bea. class of subsets of N.

(i) is closed under join, if A join B ∈ whenever A ∈ and B ∈ .

(ii) is closed under self-join, if A join A ∈ whenever A ∈ .

(iii) is closed under union, if A ⋃ B ∈ whenever A ∈ and B ∈ .

(iv) is closed under cartesian product, if A × B ∈ whenever A ∈ and B ∈ .

(v) is closed under cartesian self-product, if A × A ∈ whenever A ∈ .

The almost-finiteness classes we consider are the following:

1 = {X∣X is immune};

2 = {X∣ simple};

3 = {X∣X is hyperimmune};

4 = {X∣ is hypersimple};

5 = {X∣X is strongly hyperimmune};

6 = {X∣ is strongly hypersimple};

7 = {X∣X is hyperhyperimmune};

8 = {X∣X is strongly hyperhyperimmune};

9 = {X∣ is hyperhypersimple};

10 = {X∣X is dense immune};

11 = {X∣ is dense simple}.

The definitions are all contained in Rogers [4, Chapter 12] and/or in Robinson [3]. In addition we could consider the class of -strongly hyperimmune sets and classes defined by lim-properties; see Rogers [4, pp. 243–244]. For other classes, however, such as the class of cohesive sets, the questions become trivial.

Our aim is to establish the table on the next page.
A model of peano arithmetic with no elementary end extension
Authors: Mills George
Published: May 2006

We construct a model of Peano arithmetic in an uncountable language which has no elementary end extension. This answers a question of Gaifman and contrasts with the well-known theorem of MacDowell and Specker which states that every model of Peano arithmetic in a countable language has an elementary end extension. The construction employs forcing in a nonstandard model.
Groupes stables, avec types génériques réguliers
Authors: Poizat Bruno
Published: May 2006

Cet article ne contient rien de révolutionnaire, et son auteur a conscience du risque qu'il court de le voir dépassé, lors de sa parution, par des travaux plus profonds. Il a pensé qu'il n'était pas inutile de publier, faute de mieux, les résultats simples auxquels il est parvenu (le lecteur lui saura gré de ce caractère reposant), en espérant qu'il passeront à la postérité sous forme d'exercices dans les manuels futurs où les petits enfants apprendront la théorie des modèles.

Il s'agit de groupes stables; on sait depuis longtemps que la stabilité de la théorie d'un groupe impose des “conditions de chaîne” sur ses sous-groupes définissables : l'exploitation de ce phénomène, de nature bien algébrique, qui est brièvement exposé dans la première section de cet article, a fait le bonheur d'une génération de théoriciens des modèles. Un autre phénomène, plus subtil, semble ne pas avoir épuisé sa substance : c'est celui, dont l'apparition remonte aux travaux de B. Zilber, qui est décrit dans [7] sous le nom de “types de strate maximum”, et dans [2] sous le nom de “large sets”; la deuxième section lui est consacrée: elle a été écrite dans le désir de montrer l'équivalence de ces deux approches, et aussi par repentir de n'avoir pas suffisament éclairé ses motivations dans [7]. Ce souci d'unification a eu une influence, que j'espère salutaire, sur le vocabulaire: je parle ici de “types génériques” et d'“ensembles (ou de formules) génériques”. Ces termes, ainsi que celui de “composante connexe”, sont empruntés au langage de la géométrie: un groupe algébrique, étant définissable dans la théorie d'un corps algébriquement clos, est stable, et ses “types génériques” sont les “points génériques” des géomètres.
Countable models of multidimensional ℵ0-stable theories
Authors: Bouscaren Elisabeth
Published: May 2006

The notations and the definitions used here are identical to those in [B.L.]. We also assume that the reader is familiar with the properties of the Rudin-Keisler order on types [L.].

Let T denote an ℵ0-stable countable theory. The main result in [B.L.] is: All countable models of T are almost homogeneous if and only if T satisfies

(*) For all models M of T and all ā ∈ M, if p ∈ S1(ā) is strongly regular multidimensional, then Dim(p; M) ≥ ℵ0.

In this paper we investigate the case of a theory T which does not satisfy condition (*) and, under certain additional assumptions, we construct nonisomorphic and non-almost-homogeneous countable models. The same type of construction has been used before to show that if T is multidimensional, then for all α ≥ 1, T has at least nonisomorphic models of cardinality ℵα [La.], [Sh.]. As a corollary of our main theorem (Theorem 6) and of the previous result in [B.L.], we prove Vaught's Conjecture (and, in fact, Martin's Strong Conjecture) for theories T with αT finite.

Although we are here interested in countable models, we can also note that our construction proves that theories satisfying the assumptions in Theorem 6 have at least nonisomorphic models of cardinality ℵα.
Model companions of distributive p-algebras
Authors: Schmid Jürg
Published: May 2006

Let Bn, 0 ≤ n ≤ ω, be the equational classes of distributive p-algebras (precise definitions are given in §1). It has been known for some time that the elementary theories Tn of Bn possess model companions ; see, e.g., [6] and [14] and the references given there. However, no axiomatizations of were given, with the exception of n = 0 (Boolean case) and n= 1 (Stonian case). While the first case belongs to the folklore of the subject (see [6], also [11]), the second case presented considerable difficulties (see Schmitt [13]). Schmitt's use of methods characteristic for Stone algebras seems to prevent a ready adaptation of his results to the cases n ≥ 2.

The natural way to get a hold on is to determine the class E(Bn) of existentially complete members of Bn: Since exists, it equals the elementary theory of E(Bn). The present author succeeded [12] in solving the simpler problem of determining the classes A(Bn) of algebraically closed algebras in Bn (exact definitions of A(Bn) and E(Bn) are given in §1) for all 0 > n < ω. A(Bn) is easier to handle since it contains sufficiently many “small” algebras-viz. finite direct products of certain subdirectly irreducibles-in terms of which the members of A(Bn) may be analyzed (in contrast, all members of E(Bn) are infinite and ℵ-homogeneous). As it turns out, A(Bn) is finitely axiomatizable for all n, and comparing the theories of A(B0), A(B1) with the explicitly known theories of E(B0), E(B1)-viz. , , a reasonable conjecture for , 2 ≤ n ≤ ω, is immediate. The main part of this paper is concerned with verifying that the conditions formalized by suffice to describe the algebras in E(Bn) (necessity is easy). This verification rests on the same combinatorial techniques as used in [12] to describe the members of A(Bn).
Measurability and degrees of strong compactness
Authors: Apter Arthur W.
Published: May 2006

We prove, relative to suitable hypotheses, that it is consistent for there to be unboundedly many measurable cardinals each of which possesses a large degree of strong compactness, and that it is consistent to assume that the least measurable is partially strongly compact and that the second measurable is strongly compact. These results partially answer questions of Magidor on the relationship of strong compactness to measurability.
Complexity bounds on proofs
Authors: Hatcher William S. , Hodgson Bernard R.
Published: May 2006

In a recent article in this Journal (see [3]), J.P. Jones states and proves a theorem which purports to give an “absolute epistemological upper bound on the complexity of mathematical proofs” for recursively axiomatizable theories. However, Jones' statement of this result is misleading, and in fact defective, as can be seen by a close analysis of it. Such an analysis is the object of the present note.

The main point is that Jones' “epistemological bound” can in no way be considered a computational bound on the complexity of proofs. Not only is the “proof-theoretic interpretation of the number 243” contained in Jones' article objectionable but, more fundamentally, there is in a strong sense no way one can hope to recover anything like the full force suggested by Jones' original statement of the theorem.

We wish to insist that our comments concern only the difficulties surrounding Jones' Corollary 1 on p. 338 of his article and not his ingenious construction of universal Diophantine representations of r.e. sets presented in the same article.
The noncommutativity of random and generic extensions
Authors: Truss J.K.
Published: May 2006

Throughout, M will denote a transitive model of ZFC. Using the terms “random” and “generic” in the sense of [1], one may ask whether there can exist real numbers x and y such that x is generic over M[y] and y is random over M[x]. We shall see below by an elementary argument that this is not possible, and so, in a crude sense at least, random and generic extensions do not commute. This does not however rule out the possibility of a weaker commutativity. Let B be the complete Boolean algebra (in M) for adjoining a random real followed by a generic real and C be the complete Boolean algebra for adjoining a generic real followed by a random real. Then it still might be the case that B and C are isomorphic. This also fails, though, and we shall prove this by establishing the following combinatorial properties of MB and MC:

but

In addition this will show that C cannot be embedded as a complete subalgebra of B.

The property satisfied by B is reminiscent of calibre ℵ1 [2]. B would have calibre if we could replace “infinite” by “uncountable”, and this occurs if Martin's Axiom holds in M. To obtain the nonisomorphism of B and C in general necessitated looking at the weaker property.
LA(Ⅎ)
Authors: Bruce Kim , Keisler H. J.
Published: May 2006

The language LA(Ⅎ) is formed by adding the quantifier Ⅎx, “few x”, to the infinitary logic LA on an admissible set A. A complete axiomatization is obtained for models whose universe is the set of ordinals of A and where Ⅎx is interpreted as there exist A-finitely many x. For well-behaved A, every consistent sentence has a model with an A-recursive diagram. A principal tool is forcing for LA(Ⅎ).
Variations on ◊
Authors: Devlin Keith J.
Published: May 2006

Various equivalents and weakenings of the combinatorial principle ◊ are considered. The paper contains both absolute results and consistency results. Also included is a new characterisation of the notion of a stationary subset of ω1.
Direct product decomposition of theories of modules
Authors: Garavaglia Steven
Published: May 2006

This paper is mainly concerned with describing complete theories of modules by decomposing them (up to elementary equivalence) into direct products of simpler modules. In §1, I give a decomposition theorem which works for arbitrary direct product theories T. Given such a T, I define T-indecomposable structures and show that every model of T is elementarily equivalent to a direct product of T-indecomposable models of T. In §2, I show that if R is a commutative ring then every R-module is elementarily equivalent to ΠMM where M ranges over the maximal ideals of R and M is the localization of at M. This is applied to prove that if R is a commutative von Neumann regular ring and TR is the theory of R-modules then the TR-indecomposables are precisely the cyclic modules of the form R/M where M is a maximal ideal. In §3, I use the decomposition established in §2 to characterize the ω1-categorical and ω-stable modules over a countable commutative von Neumann regular ring and the superstable modules over a commutative von Neumann regular ring of arbitrary cardinality. In the process, I also prove several general characterizations of ω-stable and superstable modules; e.g., if R is any countable ring, then an R-moduIe is ω-stable if and only if every R-module elementarily equivalent to it is equationally compact.
Recursive isomorphism types of recursive Boolean algebras
Authors: Remmel J. B.
Published: May 2006

A Boolean algebra is recursive if B is a recursive subset of the natural numbers N and the operations ∧ (meet), ∨ (join), and ¬ (complement) are partial recursive. Given two Boolean algebras and , we write if is isomorphic to and if is recursively isomorphic to , that is, if there is a partial recursive function f: B1 → B2 which is an isomorphism from to . will denote the set of atoms of and () will denote the ideal generated by the atoms of .

One of the main questions which motivated this paper is “To what extent does the classical isomorphism type of a recursive Boolean algebra restrict the possible recursion theoretic properties of ?” For example, it is easy to see that must be co-r.e. (i.e., N − is an r.e. set), but can be immune, not immune, cohesive, etc? It follows from a result of Goncharov [4] that there exist classical isomorphism types which contain recursive Boolean algebras but do not contain any recursive Boolean algebras such that is recursive. Thus the classical isomorphism can restrict the possible Turing degrees of , but what is the extent of this restriction? Another main question is “What is the recursion theoretic relationship between and () in a recursive Boolean algebra?” In our attempt to answer these questions, we were led to a wide variety of recursive isomorphism types which are contained in the classical isomorphism type of any recursive Boolean algebra with an infinite set of atoms.
Fibered categories and the foundations of naive category theory
Authors: Bénabou Jean
Published: May 2006

Any attempt to give “foundations”, for category theory or any domain in mathematics, could have two objectives, of course related.

(0.1)Noncontradiction: Namely, to provide a formal frame rich enough so that all the actual activity in the domain can be carried out within this frame, and consistent, or at least relatively consistent with a well-established and “safe” theory, e.g. Zermelo-Frankel (ZF).

(0.2)Adequacy, in the following, nontechnical sense:

(i) The basic notions must be simple enough to make transparent the syntactic structures involved.

(ii) The translation between the formal language and the usual language must be, or very quickly become, obvious. This implies in particular that the terminology and notations in the formal system should be identical, or very similar, to the current ones. Although this may seem minor, it is in fact very important.

(iii) “Foundations” can only be “foundations of a given domain at a given moment”, therefore the frame should be easily adaptable to extensions or generalizations of the domain, and, even better, in view of (i), it should suggest how to find meaningful generalizations.

(iv) Sometimes (ii) and (iii) can be incompatible because the current notations are not adapted to a more general situation. A compromise is then necessary. Usually when the tradition is very strong (ii) is predominant, but this causes some incoherence for the notations in the more general case (e.g. the notationf(x) for the value of a functionfatxobliges one, in category theory, to denote the composition of arrows (f, g) →g∘f, and all attempts to change this notation have, so far, failed).
Categorical semantics for higher order polymorphic lambda calculus
Authors: Seely R. A. G.
Published: May 2006

A categorical structure suitable for interpreting polymorphic lambda calculus (PLC) is defined, providing an algebraic semantics for PLC which is sound and complete. In fact, there is an equivalence between the theories and the categories. Also presented is a definitional extension of PLC including “subtypes”, for example, equality subtypes, together with a construction providing models of the extended language, and a context for Girard's extension of the Dialectica interpretation.
Omitting types and the real line
Authors: Newelski Ludomir
Published: May 2006

We investigate some relations between omitting types of a countable theory and some notions defined in terms of the real line, such as for example the ideal of meager subsets ofR. We also try to express connections between the logical structure of a theory and the existence of its countable models omitting certain families of types.

It is well known that assuming MA we can omit <nonisolated types. But MA is rather a strong axiom. We prove that in order to be able to omit <nonisolated types it is sufficient to assume that the real line cannot be covered by less thanmeager sets; and this is in fact the weakest possible condition. It is worth pointing out that by means of forcing we can easily obtain the model of ZFC in whichRcannot be covered by <meager sets. It suffices to add to the ground modelCohen generic reals.

We also formulate similar results for omitting pairwise contradictory types. It turns out that from some point of view it is much more difficult to find the family of pairwise contradictory types which cannot be omitted by a model ofT, than to find such a family of possibly noncontradictory types. Moreover, for any two countable theoriesT1,T2without prime models, the existence of a family ofκtypes which cannot be omitted by a model ofT1is equivalent to the existence of such a family forT2. This means that from the point of view of omitting types all theories without prime models are identical. Similar results hold for omitting pairwise contradictory types.
Modules of existentially closed algebras
Authors: Eklof Paul C. , Mez Hans-Christian
Published: May 2006

The underlying modules of existentially closed ⊿-algebras are studied. Among other things, it is proved that they are all elementarily equivalent, and that all of them are existentially closed as modules if and only if ⊿ is regular. It is also proved that every saturated module in the appropriate elementary equivalence class underlies an ex. ⊿-algebra. Applications to some problems in module theory are given. A number of open questions are mentioned.
The reals in core models
Authors: Welch Philip
Published: May 2006

We set = ‹, ≤L, # ›, where is the set of degrees of nonconstructibility for countable sets of countable ordinals. We show how to define inductively over this structure the degrees of such sets of ordinals in Κ, the core model, and the next few core models thereafter, i.e. without reference to mice, premice or measurable cardinals
On Dedekind complete o-minimal structures
Authors: Pillay Anand , Steinhorn Charles
Published: May 2006

For a countable complete o-minimal theory T, we introduce the notion of a sequentially complete model of T. We show that a model of T is sequentially complete if and only if ≺ for some Dedekind complete model . We also prove that if T has a Dedekind complete model of power greater than , then T has Dedekind complete models of arbitrarily large powers. Lastly, we show that a dyadic theory—namely, a theory relative to which every formula is equivalent to a Boolean combination of formulas in two variables—that has some Dedekind complete model has Dedekind complete models in arbitrarily large powers.
Elementary axioms for canonical points of toposes
Authors: McLarty Colin
Published: May 2006

Two elementary extensions of the topos axioms are given, each implying the topos has a local geometric morphism to a category of sets. The stronger one realizes sets as precisely the decidables of the topos, so there is a simple internal description of the range of validity of the law of excluded middle in the topos. It also has a natural geometric meaning. Models of the extensions in Grothendieck toposes are described.
A strongly minimal expansion of (ω, s)
Authors: Marker David
Published: May 2006

We will show that there is a nontrivial strongly minimal expansion of (ω, s), the natural numbers with successor. Pillay and Steinhorn [1] proved that there is no -minimal expansion of (ω, ≤). This result provides an interesting contrast.

The strongly minimal expansion of (ω, s) is very easy to describe. Consider the order-two permutation of ω, π recursively defined by

Let T be Th(ω, s, π, 0).
Strong analogues of Martin's axiom Imply Axiom R
Authors: Beaudoin Robert E.
Published: May 2006

We show that either PFA+ or Martin's maximum implies Fleissner's Axiom R, a reflection principle for stationary subsets of Pℵ(λ). In fact, the “plus version” (for one term denoting a stationary set) of Martin's axiom for countably closed partial orders implies Axiom R.
Conservative extensions of models of set theory and generalizations
Authors: Enayat Ali
Published: May 2006

An attempt to answer the following question gave rise to the results of the present paper. Let be an arbitrary model of set theory. Does there exist an elementary extension of satisfying the two requirements: (1) contains an ordinal exceeding all the ordinals of ; (2) does not enlarge any (hyper) integer of ? Note that a trivial application of the ordinary compactness theorem produces a model satisfying condition (1); and an internal ultrapower modulo an internal ultrafilter produces a model satisfying condition (2) (but not (1), because of the axiom of replacement). Also, such a satisfying both conditions (1) and (2) exists if the external cofinality of the ordinals of is countable, since by [KM], would then have an elementary end extension.

Using a class of models constructed by M. Rubin using in [RS], and already employed in [E1], we prove that our question in general has a negative answer (see Theorem 2.3). This result generalizes the results of M. Kaufmann and the author (appearing respectively in [Ka] and [E1]) concerning models of set theory with no elementary end extensions.

In the course of the proof it was necessary to establish that all conservative extensions (see Definition 2.1) of models of ZF must be cofinal. This is in direct contrast with the case of Peano arithmetic where all conservative extensions are end extensional (as observed by Phillips in [Ph1]). This led the author to introduce two useful weakenings of the notion of a conservative end extension which, as shown by the “completeness” theorems in §3, can exist.
Preservation theorem and relativization theorem for cofinal extensions
Authors: Motohashi Nobuyoshi
Published: May 2006

One of the typical preservation theorems in a first order classical predicate logic with equality L is the following theorem due to J. Łoś [4] and A. Tarski [9] (also cf. [1, p. 139]).

Theorem A (Łoś-Tarski). For any sentences A and B in L, the following two conditions (i) and (ii) are equivalent.

(i) Every extension of any model of A is a model of B.

(ii) The two sentences A ⊃ C and C ⊃ B are provable in L for some existential sentence C in L.

In [2], S. Feferman obtained a similar preservation theorem for outer extensions. In the following, we assume that L has a fixed binary predicate symbol <. Then Σ-formulas are formulas in L which are constructed from atomic formulas and their negations by applying ∧ (conjunctions), ∨ (disjunctions), ∀x < y (bounded universal quantifications), and ∃ (existential quantifications). An extension of an L-structure is said to be an outer extension of if ⊨ a < b and b ϵ ∣∣ imply a ϵ ∣∣ for any elements a, b in ∣∣.

Theorem B (Feferman). For any sentences A and B in L, the following two conditions (i) and (ii) are equivalent.

(i) Every outer extension of any model of A is a model of B.

(ii) The two sentences A ⊃ C and C ⊃ B are provable in L for some Σ-sentence C in L.
Intuitionistic tense and modal logic
Authors: Ewald W. B.
Published: May 2006

In this article we shall construct intuitionistic analogues to the main systems of classical tense logic. Since each classical modal logic can be gotten from some tense logic by one of the definitions

(i) □ p ≡ p ∧ Gp ∧ Hp, ◇p ≡ p ∨ Fp ∨ Pp; or,

(ii) □ p ≡ p ∧ Gp, ◇p = p ∨ Fp

(see [5]), we shall find that our intuitionistic tense logics give us analogues to the classical modal logics as well.

We shall not here discuss the philosophical issues raised by our logics. Readers interested in the intuitionistic view of time and modality should see [2] for a detailed discussion.

In §2 we define the Kripke models for IKt, the intuitionistic analogue to Lemmon's system Kt. We then prove the completeness and decidability of this system (§§3–5). Finally, we extend our results to other sorts of tense logic and to modal logic.

In the language of IKt, we have: sentence-letters p, q, r, etc.; the (intuitionistic) connectives ∧, ∨, →, ¬; and unary operators P (“it was the case”), F (it will be the case”), H (“it has always been the case”) and G (“it will always be the case”). Formulas are defined inductively: all sentence-letters are formulas; if X is a formula, so are ¬X, PX, FX, HX, and GX; if X and Y are formulas, so are X ∧ Y, X ∨ Y, and X → Y. We shall see that, in contrast to classical tense logic, F and P cannot be defined in terms of G and H.
Why some people are excited by Vaught's conjecture
Authors: Lascar Daniel
Published: May 2006

§I. In 1961, R. L. Vaught ([V]) asked if one could prove, without the continuum hypothesis, that there exists a countable complete theory with exactly ℵ1 isomorphism types of countable models. The following statement is known as Vaught conjecture:

Let T be a countable theory. If T has uncountably many countable models, then T hascountable models.

More than twenty years later, this question is still open. Many papers have been written on the question: see for example [HM], [M1], [M2] and [St]. In the opinion of many people, it is a major problem in model theory.

Of course, I cannot say what Vaught had in mind when he asked the question. I just want to explain here what meaning I personally see to this problem. In particular, I will not speak about the topological Vaught conjecture, which is quite another issue.

I suppose that the first question I shall have to face is the following: “Why on earth are you interested in the number of countable models—particularly since the whole question disappears if we assume the continuum hypothesis?” The answer is simply that I am not interested in the number of countable models, nor in the number of models in any cardinality, as a matter of fact. An explanation is due here; it will be a little technical and it will rest upon two names: Scott (sentences) and Morley (theorem).
Pκλ combinatorics II: The RK ordering beneath a supercompact measure
Authors: Zwicker William S.
Published: May 2006

We characterize some large cardinal properties, such as μ-measurability and P2(κ)-measurability, in terms of ultrafilters, and then explore the Rudin-Keisler (RK) relations between these ultrafilters and supercompact measures on Pκ(2κ). This leads to the characterization of 2κ-supercompactness in terms of a measure on measure sequences, and also to the study of a certain natural subset, Fullκ, of Pκ(2κ) whose elements code measures on cardinals less than κ. The hypothesis that Fullκ is stationary (a weaker assumption than 2κ-supercompactness) is equivalent to a higher order Löwenheim-Skolem property, and settles a question about directed versus chain-type unions on Pκλ.
À l'ouest d'Éden
Authors: Poizat Bruno
Published: May 2006

Le prophète des Crétois, nous le savions depuis longtemps, n'était qu'un menteur; pourtant, à l'aube de ce siècle, quand nous avons voulu traduire nos mathématiques en termes d'ensembles, notre conscience s'est troublée de la découverte de paradoxes.

“Si R est une relation binaire entre éléments d'un ensemble (sic) E, il n'existe pas d'élément a de E, tel que pour tout x de E (a, x) satisfasse R si et seulement si (x, x) ne satisfait pas R.” Voilà un résultat bien banal! Quel est cet assaisonement fondationnel qui a le pouvoir de lui donner une saveur si troublante? C'est, sans doute, qu'il manifeste de façon brutale la contradiction d'un système d'axiomes auquel nous sommes viscéralement attachés, la “théorie des ensembles”, composée de l'axiome d'extensionalité (sans influence sur les paradoxes), et du schéma de compréhension (car nous avons d'excellentes raisons de vouloir rester dans le premier ordre, et d'éviter, à l'encontre de Zermelo, un axiome du second ordre).

Nous croyons en premier lieu que la théorie des ensembles est vraie. C'est un peu délicat de préciser ce qu'on entend par là: quand on formalise l'arithmétique, il n'y a pas de confusion possible sur la structure de référence qu'on veut décrire; mais le modèle naturel, le “modèle standard” de la théorie des ensembles, le connait-on vraiment? L'auteur de ces lignes est incapable d'en décider: cela ne l'empêchera pas de faire appel à l'intuition ensembliste la plus débridée, ce qui montre qu'il n'est pas rebuté par l'incohérence plus que par la contradiction!
On the number of nonisomorphic models of an infinitary theory which has the infinitary order property. Part A
Authors: Grossberg Rami , Shelah Saharon
Published: May 2006

Let κ and λ be infinite cardinals such that λ ≤ λ (we have new information for the case when κ ≤ λ). Let T be a theory in Lκ +, ω of cardinality at most κ, let . Now define

Our main concept in this paper is is a theory in Lκ +, ω of cardinality κ at most, and φ(x, y) ϵ Lκ +, ω}. This concept is interesting because of

Theorem 1. Let T ⊆ Lκ +, ω of cardinality ≤ κ, and. If

then (∀χ > κ)I(χ, T) = 2χ (where I(χ, T) stands for the number of isomorphism types of models of T of cardinality χ).

Many years ago the second author proved that . Here we continue that work by proving

Theorem 2. .

Theorem 3. For everyκ ≤ λwe have.

For some κ or λ we have better bounds than in Theorem 3, and this is proved via a new two cardinal theorem.

Theorem 4. For every T ⊆ Lκ +, ω, and any set of formulas ⊆ Lκ +, ω such thatT ⊇ Lκ +, ω, if T is (, μ)-unstable for μ satisfyingμμ*(λ,κ) = μ then T is-unstable (i.e. for every χ ≥ λ, T is (, χ)-unstable). Moreover, T is Lκ +, ω-unstable.

In the second part of the paper, we show that always in the applications it is possible to replace the function I(χ, T) by the function IE(χ, T), and we give an application of the theorems to Boolean powers.
Some properties of invariant sets
Authors: Byerly Robert E.
Published: May 2006

In [1] two interesting invariance notions were introduced: the notions of a set of godel numbers being invariant to automorphisms of the structures (ω, ·) and (ω, E) respectively. Here, · and E are defined by n · m ≃ φn (m) and nEm if and only if n Є Wm, where {φn} and {Wn} are acceptable enumerations of the partial recursive functions and r.e. sets respectively. In this paper we continue the study of the invariant sets, and especially the invariant r.e. sets, of gödel numbers.

We start off with an easy result which characterizes the Turing degrees containing invariant sets. We then take a closer look at r.e. sets invariant with respect to automorphisms of (ω,E). Using the characterization [1, Theorem 4.2] of such sets, we will derive a somewhat different characterization (which was stated, but not proved, in [1, Proposition 4.4]) and, using it as a tool for constructing invariant sets, prove that the r.e. sets invariant with respect to automorphisms of (ω, E) cannot be effectively enumerated.

We will next discuss representations of r.e. sets invariant with respect to automorphisms of (ω, ·). Although these sets do not have as nice a characterization as the r.e. sets invariant with respect to automorphisms of (ω, E) do, the techniques of [1] can still profitably be used to investigate their structure. In particular, if f is a partial recursive function whose graph is invariant with respect to automorphisms of (ω, ·), then for every a in the domain of f, there is a term t(a) built up from a and · only such that f(a) ≃ t(a). This is an analog to [1, Corollary 4.3]. We will also prove an analog to a result mentioned in the previous paragraph: the r.e. sets invariant with respect to automorphisms of (ω, ·) cannot be effectively enumerated.
On modal systems having arithmetical interpretations
Authors: Avron Arnon
Published: May 2006

We deal here with two modal logics, GL and Grz, that are known to have interesting arithmetical interpretations connected with the notion of provability. GL is the extensiom of K (or K4) by the schema □(□ A → A) → □ A, and Grz is the extension of S4 by □(□(A → □A) →A) → □A. GL is also known to be sound and complete with respect to the class of all Kripke models that are transitive, irreflexive and well founded. Grz bears the same relation to the corresponding reflexive models. We refer the reader to [1] for a full exposition of the subject. (See also [4], [2], [6].)

In §I we develop a sequential calculus for both GL and Grz and give a semantical proof that both systems admit cut-elimination. (Incidentally, this provides an easy proof of the semantical completeness of the two systems.) With respect to GL this yields a correction of an error in [2].

In §II we show that cut-elimination fails for QGL (the extension of GL to a language with quantifiers). We further show that, despite this failure, QGL still has some of GL's interesting properties (e.g., the disjunction property). We also show, using fixed-point techniques, that similar properties obtain if we take as semantics for QGL the arithmetical interpretation extended in the obvious way.

We want to thank Professor H. Gaifman for his help while working on the subject.