Proceedings of the 11th Asian Logic Conference

The following sections are included:

• PREFACE

• ORGANIZING COMMITTEES

• CONTENTS

In this note we show that a set is provably in the fragment IΣ_n of arithmetic iff it is IΣ_n-provably in the class D_α of α-r.e. sets in the Ershov hierarchy for an α <_ε0 ω_1+n, where <_ε0 denotes a standard ε₀-ordering.

In the Appendix it is shown that a limit existence rule (LimR) due to Beklemishev and Visser becomes stronger when the number of nested applications of the inference rule grows.

We describe the major result on categoricity in L_ω1,ω, placing it in the context of more general work in abstract elementary classes. In particular, we illustrate the role of higher dimensional amalgamations and sketch the role of a weak extension of ZFC in the proof. We expound the translation of the problem to studying atomic models of first order theories. We provide a simple example of the failure of amalgamation for a complete sentence of L_ω1,ω. We prove some basic results on the absoluteness of various concepts in the model theory of L_ω1,ω and publicize the problem of absoluteness of ℵ1-categoricity in this context. Stemming from this analysis, we prove Theorem: The class of countable models whose automorphism groups admit a complete left invariant metric is but not .

The following sections are included:

• Introduction

• K-trivial sets and NCR₁

• Incomplete r.e. degrees and NCR₁

• References

We survey what is known about limitwise monotonic functions and sets and discuss their applications in effective algebra and computable model theory. Additionally, we characterize the computably enumerable degrees that are totally limitwise monotonic, show the support strictly increasing 0′-limitwise monotonic sets on ℚ do not capture the sets with computable strong η-representations, and study the limitwise monotonic spectra of a set.

We prove that the equivalence of pure states of a separable C*-algebra is either smooth or it continuously reduces [0,1]^ℕ/ℓ₂ and it therefore cannot be classified by countable structures. The latter was independently proved by Kerr–Li–Pichot by using different methods. We also give some remarks on a 1967 problem of Dixmier.

This paper summarises previous work on automatic families. It then investigates a natural size measure for members of an automatic family: the size of a member language in the family is defined as the length of its smallest index. This measure satisfies various properties similar to those of Kolmogorov complexity; in particular the size of a language depends only up to a constant on the underlying automatic family. This family of size measures is extended to a measure on all regular sets. This extension is given by the maximum number of states visited in some run of the minimal deterministic finite automaton recognising the language. Furthermore, a characterisation is given regarding when a class of languages is a subclass of an automatic family.

Sanjay Jain and Frank Stephan are supported in part by NUS grant numbers R252-000-308-112 and R146-000-114-112.

We begin a search for degree-theoretic properties that might be used to separate Ramsey's Theorem for pairs from its stable version in the Reverse Mathematical sense. This paper introduces the notion of c-cappability and shows that this property cannot be used to obtain such a separation when combined with 2-CEA-ness.

In [1] (Proc. ALC 10), we study the following property (*) of an oracle X. (*) "For every positive integer r, X is r-generic in the sense of Dowd (1992, Inf. Comput.)" (that is, for each r, the forcing complexity of the r-query tautologies with respect to X is bounded by a polynomial; this property is different from r-genericity of arithmetical forcing). In [1], we show that if X is Schnorr random then X has the property (*), and that the property (*) is conserved through a certain type of p-time bounded-truth-table reduction. In the current article, we show (1) and (2) below. (1) There exists a primitive recursive oracle X that has the property (*); (2) Every Turing degree contains an oracle X that has the property (*). The results (1) and (2) are extensions of results in [2] (Suzuki, 2002, Inf. Comput.) about 1-genericity in the sense of Dowd. (2) is an affirmative solution to Problem 4 in [2].

Let be a countable first order language. Let A be a Σ₁ admissible set such that and the cardinality of A is ω₁. Let be a set of sentences such that < A, T > is Σ₁ admissible. T is consistent iff no contradiction can be derived from T via a deduction in A. T is complete iff for each sentence , either or . An n-type p of T is a consistent, complete set of formulas of arity ≤ n such that < A, p > is Σ₁ admissible; ST is the set of all types of T.

Say T is degenerate iff T has a countable, ω-homogeneous model that realizes every type in ST.

A typical instance of type-completeness is: if , then there is a such that and .

T is type-admissible iff is Σ₁ admissible for each coherent pair of types.

Mild stability (Section 6) implies type-completeness and type-admissibilty.

Main Result: If T is consistent, complete, type-complete, type-admissible, and not degenerate, then T has a model of size ω₁.

The following sections are included:

• Some Presuppositions for a Naïve Metaphysical Conception of Modality and de re Constructions

• A Syntactic Treatment of de re Constructions

• The Underlying System IQ: A System of Universally Free Logic with Rigid Designators

• A Quantified Modal System with Rigid Designators: A Natural Modal System IQS5

• A Modal System with Names as Constant Quantifiers

• References

The following sections are included:

• AUTHOR INDEX