Proceedings of the 12th Asian Logic Conference

The following sections are included:

• Preface

• Contents

We study infinite sequences whose initial segment complexity is invariant under effective insertions of blocks of zeros in-between their digits. Surprisingly, such resolute sequences may have nontrivial initial segment complexity. In fact, we show that they occur in many well known classes from computability theory, e.g. in every jump class and every high degree. Moreover there are degrees which consist entirely of resolute sequences, while there are degrees which do not contain any. Finally we establish connections with the contiguous c.e. degrees, the ultracompressible sequences, the anti-complex sequences thus demonstrating that this class is an interesting superclass of the sequences with trivial initial segment complexity.

We apply the techniques of computable model theory to the distance function of a graph. This task leads us to adapt the definitions of several truth-table reducibilities so that they apply to functions as well as to sets. We prove as-sorted theorems about the new reducibilities and especially about functions which have nonincreasing computable approximations (i.e., functions that are appoximable from above). Finally, we show that the spectrum of the distance function of a computable graph can consist of an arbitrary single 1-btt degree which is approximable from above, or of all such 1-btt degrees at once, or of the 1-btt degrees of exactly those functions approximable from above in at most n steps.

Carnap's 1946 semantics for S5 modal logic depends on the claim that α is true iff α is L-true, i.e., valid. I investigate some problems with this definition, and then consider the relation between this early attempt, and work in the late 1950s by Kanger, Hintikka and Kripke, which led to the development of the current possible-worlds semantics for modal logic. Finally I look at J.C.C. McKinsey's ‘syntactical’ account of validity for a modal logic between S4 and S5.

Posner and Robinson [4] proved that if S ⊆ ω is non-computable, then there, exists a G ⊆ ω such that S ⊕ G ≥_T G′. Shore and Slaman [7] extended this result to all n ∈ ω, by showing that if S ⋠ θ⁽ⁿ⁻¹⁾ then there exists a G such that S ⊕ G ≥_T G⁽ⁿ⁾. Their argument employs Kumabe-Slaman forcing, and so the set they obtain, unlike that of the Posner-Robinson theorem, is not generic for Cohen forcing in any way. We answer the question of whether this is a necessary complication by showing that for all n ≥ 1, the set G of the Shore-Slaman theorem cannot be chosen to be even weakly 2-generic. Our result applies to several other effective forcing notions commonly used in computability theory, and we also prove that the set G cannot be chosen to be 2-random.

Claims emphasizing the supposed freedom of mathematics (e.g. those by Cantor and Hilbert) are considered. A challenge by Frege to such claims is also analyzed and sustained.

If is a relativizable notion of randomness, we say that van Lambalgen's theorem holds for if for all A, B ∈ 2^ω, we have if and only if . Van Lambalgen proved that this holds for Martin-Löf randomness. We show that van Lambalgen's theorem fails for Demuth randomness, but holds for the partial relativization Demuth_BLR.

We investigate faithful unitary representations for Polishable ideals, or more generally abelian Polish groups. We give various characterizations for the existence of such representations. The main technical result is to show that the density ideal does not admit any faithful unitary representations.

We discuss some basic geometry of sets definable in the Urysohn sphere using only finitely many parameters and briefly remark on the case of arbitrary definable sets. Then we discuss definable functions in the Urysohn sphere satisfying a special syntactic property.

McKinsey–Tarski (1944), Shehtman (1999), and Lucero-Bryan (2011) proved completeness theorems for modal logics with modalities □, □ and ∀, and [∂] and ∀, respectively, with topological semantics over the real numbers. We give short proofs of these results using lexicographic sums of linear orders.

The following sections are included:

• Introduction

• Requirements and basic strategy

• Construction

• Verification

• References

Beth model is one of the tools in intuitionistic proof theory. Van Dalen constructed a Beth model for intuitionistic analysis with choice sequences. Bernini and Wendel investigated intuitionistic theories with many types of choice sequences, n-functionals, and their relation with classical type theory. In this paper we construct a Beth model for a basic intuitionistic theory with many types of functionals using recursive approach to define nodes in the Beth model. This model is a tool for justifying consistency of intuitionistic principles for functionals of high types. The principles that hold in our Beth model can be added to the initial basic theory in order to develop it into a relatively strong intuitionistic theory, where a significant part of classical type theory can be interpreted, with the purpose of contributing to the programme of justifying classical mathematics from the intuitionistic point of view. In this paper we show that Kripke's schema for n-functionals and standard axioms for lawless n-functionals hold in our Beth model.

Partition functions and graph polynomials have found many applications in combinatorics, physics, biology and even the mathematics of finance. Studying their complexity poses some problems. To capture the complexity of their combinatorial nature, the Turing model of computation and Valiant's notion of counting complexity classes seem most natural. To capture the algebraic and numeric nature of partition functions as real or complex valued functions, the Blum-Shub-Smale (BSS) model of computation seems more natural. As a result many papers use a naive hybrid approach in discussing their complexity or restrict their considerations to sub-fields of ℂ which can be coded in a way to allow dealing with Turing computability.

In this paper we propose a unified natural framework for the study of computability and complexity of partition functions and graph polynomials and show how classical results can be cast in this framework.

It is shown that the relevant logic R is complete with respect to square-increasing, commutative, integral relation algebras. This contrasts with the representable case, where completeness is known to fail.

We correct Miyabe's proof of van Lambalgen's theorem for truth-table Schnorr randomness (which we will call uniformly relative Schnorr randomness). An immediate corollary is one direction of van Lambalgen's theorem for Schnorr randomness. It has been claimed in the literature that this corollary (and the analogous result for computable randomness) is a “straightforward modification of the proof of van Lambalgen's theorem.” This is not so, and we point out why. We also point out an error in Miyabe's proof of van Lambalgen's theorem for truth-table reducible randomness (which we will call uniformly relative computable randomness). While we do not fix the error, we do prove a weaker version of van Lambalgen's theorem where each half is computably random uniformly relative to the other. We also argue that uniform relativization is the correct relativization for all randomness notions.

We explore the computational strength of the hyperimmune-free Turing degrees. In particular we investigate how the property of being dominated by recursive functions interacts with classical computability notions such as the jump operator, relativization and effectively closed sets.

The computational complexity of a set will be calibrated by the amount of changes needed for any of its computable approximations. Firstly, we study Martin-Löf random sets, where we quantify the changes of initial segments. Secondly, we look at c.e. sets, where we quantify the overall amount of changes by obedience to cost functions. Finally, we combine the two settings. The discussions lead to three basic principles on how complexity and changes relate.

Using recent work on the algebraic structure of topological full groups of minimal subshifts, we prove that the isomorphism relation on the space of infinite finitely generated simple amenable groups is not smooth. As an application, we deduce that there does not exist an isomorphism-invariant Borel map which selects a just-infinite quotient of each infinite finitely generated group.

I propose a class of TW-models for epistemic logic, Kripke's models in character with reexivity as the only constraint on the required accessibility relation amongst states, which will satisfy the main theses of Timothy Williamson's knowledge first epistemology. I introduce a function δ from the set S of states to the power set of formulae of the language in use, referred to as ipk-function to signify Williamso's notion of ‘the agent's being in a position to know a proposition in a state’. The semantic rules for the modal operators (for ‘knowing’) and (for ‘believing’) will be stipulated, respectively. The proposed semantic rules not only illuminate Williamson's thesis of understanding the justification of belief in terms of knowledge but also illustrate that to construct models for an epistemic logic with both knowledge-operator and belief-operator , we need not posit two distinct accessibility relations for and respectively. Moreover, TW-models will invalidate a list of problematic formulae/rules of inference, which are taken as the characterization of the problem of logical omniscience. Finally, I add to the original language one extra operator (corresponding to the ipk-function in that , meaning ‘the agent being actually in a position to know φ’, is true in a state α if and only if φ ∈ τ(α)), so that the derivability-power of the problematic formulae/rules of inference can be retained in the desired epistemic logic system by corresponding modified formulae.