bluuebunny/crossref_metadata_2025 huggingface dataset:
Subgroups of small index in infinite symmetric groups. II
Authors: Shelah Saharon , Thomas Simon
Published: May 2006

Throughout this paper κ denotes an infinite cardinal, S = Sym(κ) and G is a subgroup of S. We shall be seeking the subgroups G with [S: G] < 2κ. In [2], the following result was proved.

Theorem 1. If [S: G] ≤ κthen there exists a subset Δ of k such that ∣Δ∣ < k and S(Δ) ≤ G.

Here S(Δ) = Sym(K/⊿) is the pointwise stabilizer of Δ in S.

However, the converse of Theorem 1 is not true. For if cf(κ) ≤ ∣Δ∣ < κ, then [S: S(Δ)] ≥ κcf(κ) > κ. This suggests that a substantially sharpened version of Theorem 1 may be true.

Question 1 [2]. Is it provable in ZFC, or even in ZFC with GCH, that if [S: G] ≤ κ then there is a subset Δ of κ such that ∣Δ∣ < cf(κ) and S(Δ) ≤ G?

At least two of the authors of [2] made a serious attempt to answer the above question positively. In §3, we shall see that they were essentially trying to prove that measurable cardinals do not exist.

The following result, due independently to Semmes [5] and Neumann [2], suggests a second way in which Theorem 1 might be improved.

Theorem 2. If k = ℵ0andthen there is a finite subset Δ of k such thatS(Δ) ≤ G.

Question 2 [2]. Is it provable in ZFC that if [S: G] < 2κ then there is a subset Δ of κ such that ∣Δ∣ < κ and S(Δ) < G?

This question will be answered negatively in §4.
Generalizations of the one-dimensional version of the Kruskal-Friedman theorems
Authors: Gordeev L.
Published: May 2006

The paper [Schütte + Simpson] deals with the following one-dimensional case of Friedman's extension (see in [Simpson 1]) of Kruskal's theorem ([Kruskal]). Given a natural number n, let Sn+1 be the set of all finite sequences of natural numbers <n + 1. If s1 = (a0,…,ak) ∈Sn+1 and s2 = (b0,…,bm) ∈Sn + 1, then a strictly monotone function f: {0,…, k} → {0,…, m} is called an embedding of s1 into s2 if the following two assertions are satisfied:

1) ai, = bf(i), for all i < k;

2) if f(i) < j < f(i + 1) then bj > bf(i+1), for all i < k, j < m.

Then for every infinite sequence s1, s2,…,sk,… of elements of Sn + 1 there exist indices i < j and an embedding of si into Sj. That is, Sn+1 forms a well-quasi-ordering (wqo) with respect to embeddability. For each n, this statement W(Sn+1) is provable in the standard second order conservative extension of Peano arithmetic. On the other hand, the proof-theoretic strength of the statements W(Sn+1) grows so fast that this formal theory cannot prove the limit statement ∀nW(Sn+1). The appropriate first order -versions of these combinatory statements preserve their proof-theoretic strength, so that actually one can speak in terms of provability in Peano arithmetic. These are the main conclusions from [Schütte + Simpson].

We wish to extend this into the transfinite. That is, we take an arbitrary countable ordinal τ > 0 instead of n + 1 and try to obtain an analogous “strong” combinatory statement about finite sequences of ordinals < τ.
Complementation in the Turing degrees
Authors: Slaman Theodore A. , Steel John R.
Published: May 2006

Posner [6] has shown, by a nonuniform proof, that every degree has a complement below 0′. We show that a 1-generic complement for each set of degree between 0 and 0′ can be found uniformly. Moreover, the methods just as easily can be used to produce a complement whose jump has the degree of any real recursively enumerable in and above ∅′. In the second half of the paper, we show that the complementation of the degrees below 0′ does not extend to all recursively enumerable degrees. Namely, there is a pair of recursively enumerable degrees a above b such that no degree strictly below a joins b above a. (This result is independently due to S. B. Cooper.) We end with some open problems.
Binary relational structures having only countably many nonisomorphic substructures
Authors: Macpherson Dugald , Schmerl James H.
Published: May 2006

For a structure let φ() be the number of nonisomorphic, countably infinite substructures of . The problem considered here, suggested by M. Pouzet, is that of characterizing those countable for which φ() ≤ ℵ0. In this paper we will deal exclusively with structures in a finite, binary relational language L. The characterization of those L-structures for which φ() ≤ ℵ0 (which turns out to be equivalent to ) is given in Theorem 3. It is the culmination of a three-step process. The first step, resulting in Theorem 1, shows that for a countable stable L-structure , φ() ≤ ℵ0 iff is cellular. (See Definition 0.1.) In the second step we consider linearly ordered sets = (A, ≤ ℵ0), and characterize in Theorem 2 the order types of those for which φ() ≤ ℵ0. Finally, in Theorem 3, we amalgamate Theorems 1 and 2 to get the classification of all countable L-structures for which φ() ≤ ℵ0.
Model-theoretic properties characterizing Peano arithmetic
Authors: Kaye Richard
Published: May 2006

Let= {0,1, +,·,<} be the usual first-order language of arithmetic. We show that Peano arithmetic is the least first-order-theory containingIΔ0+ exp such that every complete extensionTof it has a countable modelKsatisfying

(i)Khas no proper elementary substructures, and

(ii) wheneverL≻Kis a countable elementary extension there isandsuch that.

Other model-theoretic conditions similar to (i) and (ii) are also discussed and shown to characterize Peano arithmetic.
Small stable groups and generics
Authors: Wagner Frank O.
Published: May 2006

We define an ℜ-group to be a stable group with the property that a generic element (for any definable transitive group action) can only be algebraic over a generic. We then derive some corollaries for ℜ-groups and fields, and prove a decomposition theorem and a field theorem. As a nonsuperstable example, we prove that small stable groups are ℜ-groups.
Stationary subsets of [ℵω]<ωn
Authors: Liu Kecheng
Published: May 2006

In this paper, assuming large cardinals, we prove the consistency of the following:

Let n ∈ ω and k1, k2 ≤ n. Let f: ω → {k1, k2} be such that for all n1 < n2 ∈ f−1{k1},n2 − n1 ≥ 4. Then the set

is stationary in

The above is equivalent to the statement that for any structure on on ℵω, there is ≺ A such that ∣∣ = ωn and for all m > n, cf( ∩ ωm) = ωf(m).
A very discontinuous Borel function
Authors: Steprāns Juris
Published: May 2006

It is shown to be consistent that the reals are covered by ℵ1, meagre sets yet there is a Baire class 1 function which cannot be covered by fewer than ℵ2, continuous functions. A new cardinal invariant is introduced which corresponds to the least number of continuous functions required to cover a given function. This is characterized combinatorially. A forcing notion similar to, but not equivalent to, superperfect forcing is introduced.
The Bass-Milnor-Serre theorem for nonstandard models in Peano arithmetic
Authors: Khelif Anatole
Published: May 2006

The aim of this paper is to extend the Bass-Milnor-Serre theorem to the nonstandard rings associated with nonstandard models of Peano arithmetic, in brief to Peano rings.

First, we recall the classical setting. Let k be an algebraïc number field, and let θ be its ring of integers. Let n be an integer ≥ 3, and let G be the group Sln(θ) of (n, n) matrices of determinant 1 with coefficients in θ.

The profinite topology in G is the topology having as fundamental system of open subgroups the subgroups of finite index.

Congruence subgroups of finite index of G are the kernels of the maps Sln(θ) → Sln(θ/I) for which all ideals I of θ are of finite index. By taking these subgroups as a fundamental system of open subgroups, one obtains the congruence topology on G. Every open set for this topology is open in the profinite topology.

We denote by Ḡ (resp., Ĝ) the completion of G for the congruence (resp., profinite) topology.

The Bass-Milnor-Serre theorem [1] consists of the two following statements:

(A) If k admits a real embedding, then we have an exact sequence

That is, Ĝ and Ḡ are isomorphic.

(B) If k is totally imaginary, then one has an exact sequence

where μ(k)is the group of the roots of unity of k.
On a topological construction of Juhasz and Shelah
Authors: Velleman Dan
Published: May 2006

In [2], Juhasz and Shelah use a forcing argument to show that it is consistent with GCH that there is a 0-dimensional T2 topological space X of cardinality ℵ3 such that every partition of the triples of X into countably many pieces has a nondiscrete (in the topology) homogeneous set. In this paper we will show how to construct such a space using a simplified (ω2, 1)-morass with certain additional structure added to it. The additional structure will be a slight strengthening of a built-in ◊ sequence, analogous to the strengthening of ordinary ◊k to ◊S for a stationary set S ⊆ k.

Suppose 〈〈θα∣ ∝ ≤ ω2〉, 〈∝β∣α < β ≤ ω2〉〉 is a neat simplified (ω2, 1)-morass (see [3]). Let ℒ be a language with countably many symbols of all types, and suppose that for each α < ω2, α is an ℒ-structure with universe θα. The sequence 〈α∣α < ω2 is called a built-in ◊ sequence for the morass if for every ℒ-structure with universe ω3 there is some α < ω2 and some f ∈αω2 such that f(α) ≺ , where f(α) is the ℒ-structure isomorphic to α under the isomorphism f. We can strengthen this slightly by assuming that α is only defined for α ∈ S, for some stationary set S ⊆ ω2. We will then say that is a built-in ◊ sequence on levels in S if for every ℒ-structure with universe ω3 there is some α ∈ S and some f ∈ αω2 such that f(α) ≺ .
Torre models in the isols
Authors: Barback Joseph
Published: May 2006

In [14] J. Hirschfeld established the close connection of models of the true AE sentences of Peano Arithmetic and homomorphic images of the semiring of recursive functions. This fragment of Arithmetic includes most of the familiar results of classical number theory. There are two nice ways that such models appear in the isols. One way was introduced by A. Nerode in [20] and is referred to in the literature as Nerode Semirings. The other way is called a tame model. It is very similar to a Nerode Semiring and was introduced in [6]. The model theoretic properties of Nerode Semirings and tame models have been widely studied by T. G. McLaughlin ([16], [17], and [18]).

In this paper we introduce a new variety of tame model called a torre model. It has as a generator an infinite regressive isol with a nice structural property relative to recursively enumerable sets and their extensions to the isols. What is then obtained is a nonstandard model in the isols of the fragment of Peano Arithmetic with the following property: Let T be a torre model. Let f be any recursive function, and let fΛ be its extension to the isols. If there is an isol A with fΛ(A) ϵ T, then there is also an isol B ϵ T with fΛ(B) = fΛ(A).
Strong ultrapowers and long core models
Authors: Cummings James
Published: May 2006

In his paper [7] Steel asked whether there can exist a normal measure U on a cardinal κ such that

We use Reverse Easton forcing to show that this is consistent from a P2κ hypermeasure; we also show that the result is sharp, using the core model for nonoverlapping coherent extender sequences.

The proof uses forcing technology due to Woodin.

In this section we collect some facts that are useful in the forcing constructions of the next section. None of them are due to us, and we are unsure to whom they should be attributed for the most part. We give sketchy proofs; the reader who wants to see more details is referred to [2].
Extending the Curry-Howard interpretation to linear, relevant and other resource logics
Authors: Gabbay Dov M. , de Queiroz Ruy J. G. B.
Published: May 2006

The so-called Curry-Howard interpretation (Curry [1934], Curry and Feys [1958], Howard [1969], Tait [1965]) is known to provide a rather neat term-functional account of intuitionistic implication. Could one refine the interpretation to obtain an almost as good account of other neighbouring implications, including the so-called ‘resource’ implications (e.g. linear, relevant, etc.)?

We answer this question positively by demonstrating that just by working with side conditions on the rule of assertability conditions for the connective representing implication (‘→’) one can characterise those ‘resource’ logics. The idea stems from the realisation that whereas the elimination rule for conditionals (of which implication is a particular case) remains virtually unchanged no matter what kind of conditional one has (i.e. linear, relevant, intuitionistic, classical, etc., all have modus ponens), the corresponding introduction rule carries an element of vagueness which can be explored in the characterisation of several sorts of conditionals. The rule of →-introduction is classified as an ‘improper’ inference rule, to use a terminology from Prawitz [1965]. Now, the so-called improper rules leave room for manoeuvre as to how a particular logic can be obtained just by imposing conditions on the discharge of assumptions that would correspond to the particular logical discipline one is adopting (linear, relevant, ticket entailment, intuitionistic, classical, etc.). The side conditions can be ‘naturally’ imposed, given that a degree of ‘vagueness’ is introduced by the presentation of those improper inference rules, such as the rule of →-introduction:

which says: starting from assumption ‘A’, and arriving at ‘B’ via an unspecified number of steps, one can discharge the assumption and conclude that ‘A’ implies ‘B’.
The Härtig quantifier: a survey
Authors: Herre Heinrich , Krynicki Michał , Pinus Alexandr , Väänänen Jouko
Published: May 2006

A fundamental notion in a large part of mathematics is the notion of equicardinality. The language with Härtig quantifier is, roughly speaking, a first-order language in which the notion of equicardinality is expressible. Thus this language, denoted byLI, is in some sense very natural and has in consequence special interest. Properties ofLIare studied in many papers. In [BF, Chapter VI] there is a short survey of some known results aboutLI. We feel that a more extensive exposition of these results is needed.

The aim of this paper is to give an overview of the present knowledge about the languageLIand list a selection of open problems concerning it.

After the Introduction (§1), in §§2 and 3 we give the fundamental results aboutLI. In §4 the known model-theoretic properties are discussed. The next section is devoted to properties of mathematical theories inLI. In §6 the spectra of sentences ofLIare discussed, and §7 is devoted to properties ofLIwhich depend on set-theoretic assumptions. The paper finishes with a list of open problem and an extensive bibliography. The bibliography contains not only papers we refer to but also all papers known to us containing results about the language with Härtig quantifier.

Contents. §1. Introduction. §2. Preliminaries. §3. Basic results. §4. Model-theoretic properties ofLI. §5. Decidability of theories withI. §6. Spectra ofLI-sentences. §7. Independence results. §8. What is not yet known aboutLI. Bibliography.
Interpreting groups in ω-categorical structures
Authors: Macpherson Dugald
Published: May 2006

It is shown lhat no infinite group is interpretable in any structure which is homogeneous in a finite relational language. Related questions are discussed for other ω-categorical structures.
The combinatorics of combinatorial coding by a real
Authors: Shelah Saharon , Stanley Lee J.
Published: May 2006

We lay the combinatorial foundations for [5] by setting up and proving the essential properties of the coding apparatus for singular cardinals. We also prove another result concerning the coding apparatus for inaccessible cardinals.
Scott incomplete Boolean ultrapowers of the real line
Authors: Ozawa Masanao
Published: May 2006

An ordered field is said to be Scott complete iff it is complete with respect to its uniform structure. Zakon has asked whether nonstandard real lines are Scott complete. We prove in ZFC that for any complete Boolean algebra B which is not (ω, 2)-distributive there is an ultrafilter of B such that the Boolean ultrapower of the real line modulo is not Scott complete. We also show how forcing in set theory gives rise to examples of Boolean ultrapowers of the real line which are not Scott complete.
Requirement systems
Authors: Knight Julia F.
Published: May 2006

Methods for carrying out transfinitely nested priority constructions have been developed by Harrington [7] and by Ash [2, 1, 3, 4]. Ash's method has different versions, with later ones becoming simpler. Lemmp and Lerman [11] have also developed a method, for finitely nested constructions. Ash formulated abstractly the object of a nested priority construction, and he proved a metatheorem for what he called “α-systems”, listing conditions which guarantee the success of the construction. Harrington's method of “workers”, at least in its original, informal state, seems more flexible than Ash's α-systems.

In [10, 9], there are finite and transfinite versions of a metatheorem for workers. The statements are complicated, and these metatheorems have not proved to be very useful. The present paper gives a new transfinite metatheorem. The statement is considerably simpler than the one in [9], although not so simple as that in [3]. The new metatheorem grew, in part, out of an effort to find a new proof of Ash's metatheorem. The new metatheorem yields the one in [3], and it seems more flexible. A different generalization of Ash's metatheorem will be given in [5].

Ash's metatheorem is easier to use than the one in the present paper, and the result in [3] is certainly the one to use wherever it applies. Here we give one application of the new metatheorem which does not seem to follow from the result in [3]. This is a theorem on models “representing” a given Scott set, which implies one half of a recent result of Solovay [18], on Turing degrees of models of particular completions of Peano arithmetic (PA).
Canonical seeds and Prikry trees
Authors: Hamkins Joel David
Published: May 2006

Applying the seed concept to Prikry tree forcing ℙμ, I investigate how well ℙμ preserves the maximality property of ordinary Prikry forcing and prove that ℙμ, Prikry sequences are maximal exactly when μ admits no non-canonical seeds via a finite iteration. In particular, I conclude that if μ is a strongly normal supercompactness measure, then ℙμ Prikry sequences are maximal, thereby proving, for a large class of measures, a conjecture of W. Hugh Woodin's.
On the complexity of propositional quantification in intuitionistic logic
Authors: Kremer Philip
Published: May 2006

We define a propositionally quantified intuitionistic logic Hπ+ by a natural extension of Kripke's semantics for propositional intuitionistic logic. We then show that Hπ+ is recursively isomorphic to full second order classical logic. Hπ+ is the intuitionistic analogue of the modal systems S5π+, S4π+, S4.2π+, K4π+, Tπ+, Kπ+ and Bπ+, studied by Fine.
Finitary sketches
Authors: Adámek J. , Johnstone P. T. , Makowsky J. A. , Rosický J.
Published: May 2006

Finitary sketches, i.e., sketches with finite-limit and finite-colimit specifications, are proved to be as strong as geometric sketches, i.e., sketches with finite-limit and arbitrary colimit specifications. Categories sketchable by such sketches are fully characterized in the infinitary first-order logic: they are axiomatizable by σ-coherent theories, i.e., basic theories using finite conjunctions, countable disjunctions, and finite quantifications. The latter result is absolute; the equivalence of geometric and finitary sketches requires (in fact, is equivalent to) the non-existence of measurable cardinals.
Compact bracket abstraction in combinatory logic
Authors: Broda Sabine , Damas Luís
Published: May 2006

Translations from Lambda calculi into combinatory logics can be used to avoid some implementational problems of the former systems. However, this scheme can only be efficient if the translation produces short output with a small number of combinators, in order to reduce the time and transient storage space spent during reduction of combinatory terms. In this paper we present a combinatory system and an abstraction algorithm, based on the original bracket abstraction operator of Schönfinkel [9]. The algorithm introduces at most one combinator for each abstraction in the initial Lambda term. This avoids explosive term growth during successive abstractions and makes the system suitable for practical applications. We prove the correctness of the algorithm and establish some relations between the combinatory system and the Lambda calculus.
A new deconstructive logic: linear logic
Authors: Danos Vincent , Joinet Jean-Baptiste , Schellinx Harold
Published: May 2006

The main concern of this paper is the design of a noetherian and confluent normalization for LK2 (that is, classical second order predicate logic presented as a sequent calculus).

The method we present is powerful: since it allows us to recover as fragments formalisms as seemingly different as Girard's LC and Parigot's λμ, FD ([10, 12, 32, 36]), delineates other viable systems as well, and gives means to extend the Krivine/Leivant paradigm of ‘programming-with-proofs’ ([26, 27]) to classical logic; it is painless: since we reduce strong normalization and confluence to the same properties for linear logic (for non-additive proof nets, to be precise) using appropriate embeddings (so-called decorations); it is unifying: it organizes known solutions in a simple pattern that makes apparent the how and why of their making.

A comparison of our method to that of embedding LK into LJ (intuitionistic sequent calculus) brings to the fore the latter's defects for these ‘deconstructive purposes’.
Lower bounds for resolution and cutting plane proofs and monotone computations
Authors: Pudlák Pavel
Published: May 2006

We prove an exponential lower bound on the length of cutting plane proofs. The proof uses an extension of a lower bound for monotone circuits to circuits which compute with real numbers and use nondecreasing functions as gates. The latter result is of independent interest, since, in particular, it implies an exponential lower bound for some arithmetic circuits.
Defining relevant implication in a propositionally quantified S4
Authors: Kremer Philip
Published: May 2006

R. K. Meyer once gave precise form to the question of whether relevant implication can be defined in any modal system, and his answer was ‘no’. In the present paper, we extend S4, first with propositional quantifiers, to the system S4π+; and then with definite propositional descriptions, to the system S4π+ip. We show that relevant implication can in some sense be defined in the modal system S4π+ip, although it cannot be defined in S4π+.
Amalgamations preserving ℵ1-categoricity
Authors: Pillay Anand , Tsuboi Akito
Published: May 2006

Let L0, L1 and L2 be countable languages with L ∩ L1 = L0. Let M0 be an L0-structure and Mi, an expansion of M0 to an Li,-structure (i = 1,2). We will call an L1 ∪ L2-structure M an amalgamation of M1 and M2 if M∣Li ≅ Mi, (i = 1,2). Let's consider the following problem.

(*) Suppose that both M1 and M2 belong to the class . Can we always find an amalgamation M in ?

Of course the existence of such an amalgamation depends on the class L. Some examples of and the answers are given below.

1. = Countably saturated strongly minimal structures with the DMP In [3], Hrushovski showed that any two strongly minimal theories formulated in totally different languages have a common extension which is still strongly minimal and with the DMP (DMP is the property that states that if a point is sufficiently close to ā, then φ(, ) has the same rank and the same degree as φ(, ā).) His proof essentially shows that if L0 = ∅ then any two countably saturated strongly minimal structures with the DMP have a strongly minimal amalgamation. Also he gave an example that shows the condition L0 = ∅ is necessary.

2. = ℵ1-categorical countable structures. Let M1 be the structure (ℚ, +) and let M2 be the {E, F}-structure defined by: (i) E is an equivalence relation which divides the universe into two infinite classes A and B, (ii) F is a bijection between A and B.
The structure of intrinsic complexity of learning
Authors: Jain Sanjay , Sharma Arun
Published: May 2006

Limiting identification of r.e. indexes for r.e. languages (from a presentation of elements of the language) and limiting identification of programs for computable functions (from a graph of the function) have served as models for investigating the boundaries of learnability. Recently, a new approach to the study of “intrinsic” complexity of identification in the limit has been proposed. This approach, instead of dealing with the resource requirements of the learning algorithm, uses the notion of reducibility from recursion theory to compare and to capture the intuitive difficulty of learning various classes of concepts. Freivalds, Kinber, and Smith have studied this approach for function identification and Jain and Sharma have studied it for language identification.

The present paper explores the structure of these reducibilities in the context of language identification. It is shown that there is an infinite hierarchy of language classes that represent learning problems of increasing difficulty. It is also shown that the language classes in this hierarchy are incomparable, under the reductions introduced, to the collection of pattern languages.

Richness of the structure of intrinsic complexity is demonstrated by proving that any finite, acyclic, directed graph can be embedded in the reducibility structure. However, it is also established that this structure is not dense. The question of embedding any infinite, acyclic, directed graph is open.
An Ulm-type classification theorem for equivalence relations in Solovay model
Authors: Kanovei Vladimir
Published: May 2006

We prove that in the Solovay model, every OD equivalence relation, Ε, over the reals, either admits an OD reduction to the equality relation on the set of all countable (of length < ω1) binary sequences, or continuously embeds Ε0, the Vitali equivalence.

If Ε is a (resp. ) relation then the reduction above can be chosen in the class of all Δ1 (resp. Δ2) functions.

The proofs are based on a topology generated by OD sets.
Wildness implies undecidability for lattices over group rings
Authors: Toffalori Carlo
Published: May 2006

Let G be a finite group. A Z [G]-lattice is a finitely generated Z-torsionfree module over the group ring Z [G]. There is a general conjecture concerning classes of modules over sufficiently recursive rings, and linking wildness and undecidability. Given a finite group G, Z [G] is sufficiently recursive, and our aim here is just to investigate this conjecture for Z [G]-lattices. In this setting, the conjecture says that

if and only if

In particular, we wish to deal here with the direction from the left to the right, so the one assuring that wildness implies undecidability. Of course, before beginning the analysis of this problem, one should agree upon a sharp definition of wildness for lattices. But, for our purposes, one might alternatively accept as a starting point a general classification of wild Z [G]-lattices when G is a finite p-group for some prime p, based on the isomorphism type of G. This is due to several authors and can be found, for instance, in [3]. It says that, when p is a prime and G is a finite p-group, then

if and only if

.

More precisely, the representation type of Z [G]-lattices is finite when G is cyclic of order ≤ p2, tame domestic when G is the Klein group [1], tame non-domestic when G is cyclic of order 8 [11].

So our claim might be stated as follows.
Definability and decidability issues in extensions of the integers with the divisibility predicate
Authors: Cegielski Patrick , Matiyasevich Yuri , Richard Denis
Published: May 2006

Let be a first-order structure; we denote by DEF() the set of all first-order definable relations and functions within . Let π be any one-to-one function from ℕ into the set of prime integers.

Let ∣ and • be respectively the divisibility relation and multiplication as function. We show that the sets DEF(ℕ, π, ∣) and DEF(ℕ, π, •) are equal. However there exists function π such that the set DEF(ℕ, +, ∣), or, equivalently, DEF(ℕ, π, •) is not equal to DEF(ℕ, +, •). Nevertheless, in all cases there is an {π, •}-definable and hence also {π, |}-definable structure over π which is isomorphic to 〈ℕ, +, •〉. Hence theories TH(ℕ, π, ∣) and TH(ℕ, π, •) are undecidable.

The binary relation of equipotence between two positive integers saying that they have equal number of prime divisors is not definable within the divisibility lattice over positive integers. We prove it first by comparing the lower bound of the computational complexity of the additive theory of positive integers and of the upper bound of the computational complexity of the theory of the mentioned lattice.

The last section provides a self-contained alternative proof of this latter result based on a decision method linked to an elimination of quantifiers via specific tables.
Fine structure for tame inner models
Authors: Schimmerling E. , Steel J. R.
Published: May 2006

In this paper, we solve the strong uniqueness problem posed in [St2]. That is, we extend the full fine structure theory of [MiSt] to backgrounded models all of whose levels are tame (defined in [St2] and below). As a consequence, more powerful large cardinal properties reflect to fine structural inner models. For example, we get the following extension to [MiSt, Theorem 11.3] and [St2, Theorem 0.3].

Suppose that there is a strong cardinal that is a limit of Woodin cardinals. Then there is a good extender sequence such that

(1) every level of is a sound, tame mouse, and

(2) ⊨ “There is a strong cardinal that is a limit of Woodin cardinals”.

Recall that satisfies GCH if all its levels are sound. Another consequence of our work is the following covering property, an extension to [St1, Theorem 1.4] and [St3, Theorem 1.10].

Suppose that fi is a normal measure on Ω and that all premice are tame. Then Kc, the background certified core model, exists and is a premouse of height Ω. Moreover, for μ-almost every α < Ω.

Ideas similar to those introduced here allow us to extend the fine structure theory of [Sch] to the level of tame mice. The details of this extension shall appear elsewhere. From the extension of [Sch] and Theorem 0.2, new relative consistency results follow. For example, we have the following application.

If there is a cardinal κ such that κ is κ+-strongly compact, then there is a premouse that is not tame.
Did Tarski commit “Tarski's fallacy”?
Authors: Sher G. Y.
Published: May 2006

In his 1936 paper,On the Concept of Logical Consequence, Tarski introduced the celebrated definition oflogical consequence: “The sentenceσfollows logicallyfrom the sentences of the class Γ if and only if every model of the class Γ is also a model of the sentenceσ.” [55, p. 417] This definition, Tarski said, is based on two very basic intuitions, “essential for the proper concept of consequence” [55, p. 415] and reflecting common linguistic usage: “Consider any class Γ of sentences and a sentence which follows from the sentences of this class. From an intuitive standpoint it can never happen that both the class Γ consists only of true sentences and the sentenceσis false. Moreover, … we are concerned here with the concept of logical, i.e.,formal, consequence.” [55, p. 414] Tarski believed his definition of logical consequence captured the intuitive notion: “It seems to me that everyone who understands the content of the above definition must admit that it agrees quite well with common usage. … In particular, it can be proved, on the basis of this definition, that every consequence of true sentences must be true.” [55, p. 417] The formality of Tarskian consequences can also be proven. Tarski's definition of logical consequence had a key role in the development of the model-theoretic semantics of modern logic and has stayed at its center ever since.
Strictly primitive recursive realizability, I
Authors: Damnjanovic Zlatan
Published: May 2006

A realizability notion that employs only primitive recursive functions is defined, and, relative to it, the soundness of the fragment of Heyting Arithmetic (HA) in which induction is restricted to formulae is proved. A dual concept of falsifiability is proposed and an analogous soundness result is established for a further restricted fragment of HA.
Characterising subsets of ω1 constructible from a real
Authors: Welch P. D.
Published: May 2006

A small large cardinal upper bound in V for proving when certain subsets of ω1 (including the universally Baire subsets) are precisely those constructible from a real is given. In the core model we find an exact equivalence in terms of the length of the mouse order; we show that ∀B ⊆ ω1 [B is universally Baire ⇔ B ϵ L[r] for some real r] is preserved under set-sized forcing extensions if and only if there are arbitrarily large “admissibly measurable” cardinals.
T-convexity and tame extensions II
Authors: van den Dries Lou
Published: May 2006

I solve here some problems left open in “T-convexity and Tame Extensions” [9]. Familiarity with [9] is assumed, and I will freely use its notations. In particular,Twill denote a completeo-minimal theory extending RCF, the theory of real closed fields. Let (,V) ⊨Tconvex, let=V/m(V)be the residue field, with residue class mapx↦:V↦, and let υ:→ Γ be the associated valuation. “Definable” will mean “definable with parameters”.The main goal of this article is to determine the structure induced by(,V)on its residue fieldand on its value group Γ. In [9] we expanded the ordered fieldto a model ofTas follows. Take a tame elementary substructure′ ofsuch thatR′ ⊆VandR′maps bijectively ontounder the residue class map, and make this bijection into an isomorphism′ ≌ofT-models. (We showed such′ exists, and that this gives an expansion ofto aT-model that is independent of the choice of′.).
The theory of integer multiplication with order restricted to primes is decidable
Authors: Maurin Françoise
Published: May 2006

We show here that the first order theory of the positive integers equipped with multiplication remains decidable when one adds to the language the usual order restricted to the prime numbers. We see moreover that the complexity of the latter theory is a tower of exponentials, of height O(n).
On o-minimal expansions of Archimedean ordered groups
Authors: Laskowski Michael C. , Steinhorn Charles
Published: May 2006

We study o-minimal expansions of Archimedean totally ordered groups. We first prove that any such expansion must be elementarily embeddable via a unique (provided some nonzero element is 0-definable) elementary embedding into a unique o-minimal expansion of the additive ordered group of real numbers . We then show that a definable function in an o-minimal expansion of enjoys good differentiability properties and use this to prove that an Archimedean real closed field is definable in any nonsemilinear expansion of . Combining these results, we obtain several restrictions on possible o-minimal expansions of arbitrary Archimedean ordered groups and in particular of the rational ordered group.
Storage operators and directed lambda-calculus
Authors: David René , Nour Karim
Published: May 2006

Storage operators have been introduced by J. L. Krivine in [5] they are closed λ-terms which, for a data type, allow one to simulate a “call by value” while using the “call by name” strategy. In this paper, we introduce the directed λ-calculus and show that it has the usual properties of the ordinary λ-calculus. With this calculus we get an equivalent—and simple—definition of the storage operators that allows to show some of their properties:

• the stability of the set of storage operators under the β-equivalence (Theorem 5.1.1);

• the undecidability (and semidecidability) of the problem “is a closed λ-term t a storage operator for a finite set of closed normal λ-terms?” (Theorems 5.2.2 and 5.2.3);

• the existence of storage operators for every finite set of closed normal λ-terms (Theorem 5.4.3);

• the computation time of the “storage operation” (Theorem 5.5.2).
A modal view of linear logic
Authors: Martini Simone , Masini Andrea
Published: May 2006

We present a sequent calculus for the modal logic S4, and building on some relevant features of this system (the absence of contraction rules and the confinement of weakenings into axioms and modal rules) we show how S4 can easily be translated into full prepositional linear logic, extending the Grishin-Ono translation of classical logic into linear logic. The translation introduces linear modalities (exponentials) only in correspondence with S4 modalities. We discuss the complexity of the decision problem for several classes of linear formulas naturally arising from the proposed translations.
Combinatorics on ideals and axiom A
Authors: Sharp James D.
Published: May 2006

Throughout this paper denotes a nonprincipal ultrafilter and ℐ denotes the dual ideal. ℙ(ℐ) is the poset of all partial functions p: ω → 2 such that dom(p) ∈ ℐ. In [2], Grigorieff proved that ω1 is preserved in the corresponding generic extension if and only if is a P-point. Later, when Shelah introduced the notion of a proper poset, many people observed that if is a P-point, then ℙ(ℐ) is proper. One way of proving this is to show that player II has a winning strategy in the game for ℙ(ℐ) (see [3, p. 91].)

The notion of an Axiom A poset was introduced by Baumgartner [1]. If a poset satisfies Axiom A, then player II has a winning strategy in the game for ℙ, and thus, ℙ is proper. Indeed most of the naturally occurring proper posets satisfy Axiom A (e.g., Mathias's poset and Laver's poset). Thus, it is natural to ask whether or not ℙ(ℐ) satisfies Axiom A. The main result of this paper is a negative answer to this question. We will prove this by introducing another game and showing that is a P-point if and only if the corresponding game is undetermined. We will then show that if ℙ(ℐ) satisfied Axiom A, then player II would have a winning strategy in the corresponding game .

We let [X]<ω = {s ⊆ X∣ ∣s∣ < ω}. We let Seq(X) denote the set of finite sequences of elements of X. If s = 〈x0, …, xn〉 ∈ Seq(X) and y ∈ X, then s * 〈y〉 = 〈x0,…,xn,y〉 ∈ Seq(X).
A guide to truth predicates in the modern era
Authors: Sheard Michael
Published: May 2006

A reader coming anew to the recent work on languages which contain their own truth predicates may be perplexed by the simple question of where to begin. A first approach to the literature suggests a field which is alive and busy with investigations heading in many different directions, but there is much less indication of how various pieces fit together. There are at least two sources of this confusion. First, the literature is large and diffuse (as befits a subject which goes back over 2000 years); Visser's survey [33] aptly describes the literature as “vast but scattered, repetitive, and disconnected.” Moreover, recent interest in the field has led to a proliferation of research and publication; it seems that almost any issue of any philosophical logic journal from the mid-1980s contains some article on the topic. The second reason, in part a consequence of the first, is that while a typical article in print usually presents a good internal motivation, with clear reference to its immediate intellectual antecedents, its place in the broader picture may not be so easily discerned. The problem can be especially acute in presentations of axiomatic approaches, because decisions on certain basic questions can lie hidden in the formal and notational details which abound in any axiomatization.

In fact, though, the recent research on methods for handling self-referential truth can be seen as a body of work which is very well structured, one in which a few fundamental decisions suffice to locate any particular approach in its appropriate place on the landscape. My goal is to describe this structure and in particular to stress a few critical forks in the road, which will be the recurring metaphor throughout this paper. I will also pay particular attention to pointing out where the interesting technical and mathematical questions lie.
Actions by the classical Banach spaces
Authors: Hjorth G.
Published: May 2006

The study of continuous group actions is ubiquitous in mathematics, and perhaps the most general kinds of actions for which we can hope to prove theorems in just ZFC are those where a Polish group acts on a Polish space.

For this general class we can find works such as [29] that build on ideas from ergodic theory and examine actions of locally compact groups in both the measure theoretic and topological contexts. On the other hand a text in model theory, such as [12], will typically consider issues bearing on the actions by the symmetric group of all permutations of the integers. More generally [1] shows that the orbit equivalence relations induced by closed subgroups of the infinite symmetric group can be reduced to the isomorphism relation on corresponding classes of countable models.

This paper considers a third category formed by the continuous actions of separable Banach spaces on Polish spaces. These examples cannot be subsumed under the two earlier headings, and it is known from [10] that theBorel cardinalitiesof the quotient spaces that arise from such actions are incomparable with the equivalence relations induced by the symmetric group or any locally compact Polish group action.

One of the first things to be addressed concerns the complexity of these equivalence relations. This question forappears in [1].
Implicational F-structures and implicational relevance logics
Authors: Avron A.
Published: May 2006

We describe a method for obtaining classical logic from intuitionistic logic which does not depend on any proof system, and show that by applying it to the most important implicational relevance logics we get relevance logics with nice semantical and proof-theoretical properties. Semantically all these logics are sound and strongly complete relative to classes of structures in which all elements except one are designated. Proof-theoretically they correspond to cut-free hypersequential Gentzen-type calculi. Another major property of all these logics is that the classical implication can faithfully be translated into them.
A completeness theorem for higher order logics
Authors: Sági Gábor
Published: May 2006

Here we investigate the classes of representable directed cylindric algebras of dimension α introduced by Németi [12]. can be seen in two different ways: first, as an algebraic counterpart of higher order logics and second, as a cylindric algebraic analogue of Quasi-Projective Relation Algebras. We will give a new, “purely cylindric algebraic” proof for the following theorems of Németi: (i) is a finitely axiomatizable variety whenever α ≥ 3 is finite and (ii) one can obtain a strong representation theorem for if one chooses an appropriate (non-well-founded) set theory as foundation of mathematics. These results provide a purely cylindric algebraic solution for the Finitization Problem (in the sense of [11]) in some non-well-founded set theories.
Foundation versus induction in Kripke-Platek set theory
Authors: Zambella Domenico
Published: May 2006

We denote by KP_ the fragment of set-theory containing the axioms of extensionality, pairing, union and foundation as well as the schemas of ∆0-comprehension and ∆0-collection, that is: Kripke-Platek set-theory (KP) with the axiom of foundation in place of the ∈-induction schema. The theory KP is obtained by adding to KP_ the schema of ∈-induction

Using ∈-induction it is possible to prove the existence of the transi tive closure without appealing to the axiom of infinity (see, e.g., [1]). Vice versa, when a theory proves the existence of the transitive closure, some induction is immediately ensured (by foundation and comprehension). This is not true in general: e.g., the whole of Zermelo-Fraenkel set-theory without the axiom of infinity does not prove ∈-induction (in fact, it does not prove the existence of the transitive closure; see, e.g., [3]). Open-induction is the schema of ∈-induction restricted to open formulas. We prove the following theorem.

KP_ proves open-induction.

We reason in a fixed but arbitrary model of KP_ whom we refer to as the model. The language is extended with a name for every set in the model. We call this constants parameters. Let φ(x) be a satisfiable open-formula possibly depending on parameters and with no free variable but x. We show that φ(x) is satisfied by an ∈-minimal set, that is, a set a such that φ(a) and (∀x ∈ a) ¬φ(x). We assume that no ordinal satisfies φ(x), otherwise the existence of a ∈-minimal set follows from foundation and comprehension.
CM-triviality and stable groups
Authors: Wagner Frank O.
Published: May 2006

We define a generalized version of CM-triviality, and show that in the presence of enough regular types, or solubility, a stable CM-trivial group is nilpotent-by-finite. A torsion-free small CM-trivial stable group is abelian and connected. The first result makes use of a generalized version of the analysis of bad groups.
On representation theorems for nonmonotonic consequence relations
Authors: Pérez Ramón Pino , Uzcátegui Carlos
Published: May 2006

One of the main tools in the study of nonmonotonic consequence relations is the representation of such relations in terms of preferential models. In this paper we give an unified and simpler framework to obtain such representation theorems.
On closed unbounded sets consisting of former regulars
Authors: Gitik Moti
Published: May 2006

A method of iteration of Prikry type forcing notions as well as a forcing for adding clubs is presented. It is applied to construct a model with a measurable cardinal containing a club of former regulars, starting with ο(κ) = κ + 1. On the other hand, it is shown that the strength of above is at least

ο(κ) = κ.
Finite algebras of relations are representable on finite sets
Authors: Andréka H. , Hodkinson I. , Németi I.
Published: May 2006

Using a combinatorial theorem of Herwig on extending partial isomorphisms of relational structures, we give a simple proof that certain classes of algebras, including Crs, polyadic Crs, and WA, have the ‘finite base property’ and have decidable universal theories, and that any finite algebra in each class is representable on a finite set.
Deduction theorems within RM and its extensions
Authors: Czelakowski J. , Dziobiak W.
Published: May 2006

In [13], M. Tokarz specified some infinite family of consequence operations among all ones associated with the relevant logic RM or with the extensions of RM and proved that each of them admits a deduction theorem scheme. In this paper, we show that the family is complete in a sense that if C is a consequence operation with CRM ≤ C and C admits a deduction theorem scheme, then C is equal to a consequence operation specified in [13]. In algebraic terms, this means that the only quasivarieties of Sugihara algebras with the relative congruence extension property are the quasivarieties corresponding, via the algebraization process, to the consequence operations specified in [13].
The model-theoretic ordinal analysis of theories of predicative strength
Authors: Avigad Jeremy , Sommer Richard
Published: May 2006

We use model-theoretic methods described in [3] to obtain ordinal analyses of a number of theories of first- and second-order arithmetic, whose proof-theoretic ordinals are less than or equal to Γ0.