Proceedings of the 13th Asian Logic Conference

The following sections are included:

• Preface
• Organizing committees
• Contents

We present an analogy between cardinal characteristics from set theory and highness properties from computability theory, which specify a sense in which a Turing oracle is computationally strong. While this analogy was first studied explicitly by Rupprecht (Effective correspondents to cardinal characteristics in Cichoń's diagram, PhD thesis, University of Michigan, 2010), many prior results can be viewed from this perspective. After a comprehensive survey of the analogy for characteristics from Cichoń's diagram, we extend it to Kurtz randomness and the analogue of the Specker-Eda number.

Let φ be an acceptable programming system/numbering of the partial computable functions: ℕ = {0, 1, 2,…} → ℕ, where, for p ∈ ℕ, φ_p is the partial computable function computed by program p of the φ-system and W_p = domain(φ_p). W_p is, then, the computably enumerable (c.e.) set accepted by p.

The first author taught in a class a recursion theorem proof employing a pair of cases that, for each q, {x | φ_x = φ_q} is not computably enumerable. The particular pair of cases employed was: domain(φ_q) is infinite vs. finite — incidentally, by Rice's Theorem, a non-constructive disjunction. Some student asked why the proof involved an analysis by cases. The answer given straightaway to the student was that his teacher didn't know how else to do it.

The present paper provides, among other things, a better answer: any proof that, for each q, {x | φ_x = φ_q} is not c.e. provably must involve some such non-constructiveness. Furthermore, completely characterized are all the possible such pairs of (index set based) cases that will work.

Along the way, relevantly explored are uniform lifts of the concept completely productive (abbr: c-productive) sets to sequences of sets.

The c-productive sets are the effectively non-c.e. sets.

A set sequence S_q, q ∈ ℕ, is said to be uniformly c-productive if there is a computable f so that, for all q, x, f(q, x) is a counterexample to S_q = W_x.

Relevance: a completely constructive proof that each S_q is not c.e. would entail the S_qs forming a uniformly c-productive sequence.

Relevantly shown, then, is that the sequence {x | φ_x = φ_q}, q ∈ ℕ is not uniformly c-productive — and this even though, of course, the set {〈q, x〉 | φ_x = φ_q} is c-productive.

For some results we provide upper and/or lower bounds for them as to position in the Arithmetical Hierarchy of the Law of Excluded Middle needed in addition to Heyting Arithmetic.

Results are also obtained for similar problems, including for run-time bounded programming systems and other subrecursive systems.

Proof methods include recursion theorems.

We construct a pair of c.e. sets A ≡_wtt ∅^′ and B ≡_T ∅^′ whose truth table degrees form a minimal pair.

In the context of recursion-theoretic inductive inference, a partial learner identifies an r.e. language L if and only if it outputs one index e of the language L infinitely often and outputs all other indices only finitely often. Osherson, Stob and Weinstein showed in 1986 that there is a partial learner that succeeds to learn every r.e. language under this learning criterion. Therefore, subsequent investigations refined the question to what happens if the partial learner has to satisfy additional constraints like consistency, conservativeness, confidence and reliability. The present paper gives an overview of recent investigations on this topic.

Let T be a stable theory. It was shown in Ref. 5 that one can define the notions of homology groups attached to a stationary type of T. It was also shown that if T fails to have an amalgamation property called 3-uniqueness, then for some stationary type p the homology group H₂(p) has to be a nontrivial abelian profinite group. The goal of this paper is to show that for any abelian profinite group G there is a stable (in fact, categorical) theory and a stationary type p such that H₂(p) ≅ G.

We introduce some questions and results related to stability class and model completeness of ab initio generic structures. Then we give a characterization for the model completeness of generic structures.

Generic structures constructed from a certain kind of amalgamation classes are shown to have a model complete countably categorical theory.

This paper generalizes the categorical relationship among the topological systems, topological spaces and frames as shown by Vickers. Here similar relationship among fuzzy topological systems (on fuzzy sets), fuzzy topological spaces (on fuzzy sets) and frames has been obtained. Connections of this categorical study with future development of logics are indicated.

This paper describes an axiomatic theory BT with operations and infinitely many types for sets intended for formalising constructive mathematics. In addition to previously known metamathematical properties of BT, we introduce a realizability for BT and use it to prove its existence property. Due to a predicative comprehension axiom, sets in BT can be interpreted recursively as external terms. This method is used in constructing the realizability and a countable set-theoretical model for BT. The latter can be applied to establish further metamathematical properties of the theory BT.

This paper deals with goal-directed unbounded coalitional games (GUCGs), in which each player is assigned a propositional formula as her goal. Players in a game may form coalitions for their own interests. The end condition of a game is reached if those players whose goals are satisfied can cooperate to prevent other players from reaching their goals. We study various solution concepts of GUCGs and their computational complexity.

Extensions of Visser's basic propositional logic (BPL) are explored. We present the lattice of extensions of BPL: the lattice of superbasic logics. From a uniform perspective, we establish logical properties of superbasic logics, including strong completeness, finite model property, disjunction property, Post completeness, and two constant property. Moreover, the embedding of superbasic logics into normal modal logics by Gödel-McKinsey-Tarski style translations is revisited.

This is a survey paper on some recent developments in the study of higher degree theory, the theory of degree structure of generalized degrees at uncountable cardinals, in particular at those with countable cofinality.

The study of generalized degree notions, known as α-recursion theory, was initiated by Sacks in the early 70s. But the early works were mainly from recursion theoretical perspective, and the results are mostly limited to Gödel's constructive universe. Some recent works (see Refs. 1,2) in set theory indicate that there is a profound connection between the complexity of degree structures at singular cardinals of countable cofinality and the large cardinal properties at the vicinity. This paper shall exam degree structures cross through L-like models for various mild large cardinals, or under large cardinal assumptions, by which hopefully a new line of research will be depicted.

In Refs. 2 and 3, Greenberg, Montalbán and Slaman investigated both hyperarithmetic and constructibility degree spectra of countable structures. Inspired by their results, we push them to a more general setting by investigating degree spectra of equivalence relations.