Provability logic and the completeness principle

The logic $\mathsf{iGLC}$ is the intuitionistic version of Löb's Logic plus the completeness principle $A\to \square A$. In this paper, we prove an arithmetical completeness theorems for $\mathsf{iGLC}$ for theories equipped with two provability predicates □ and △ that prove the schemes $A\to △A$ and $\square △S\to \square S$ for $S\in {\mathrm{\Sigma }}_1$. We provide two salient instances of the theorem. In the first, □ is fast provability and △ is ordinary provability and, in the second, □ is ordinary provability and △ is slow provability.Using the second instance, we reprove a theorem previously obtained by Mohammad Ardeshir and Mojtaba Mojtahedi [1] determining the ${\mathrm{\Sigma }}_1$-provability logic of Heyting Arithmetic.     

Finite computable dimension and degrees of categoricity

We first give an example of a rigid structure of computable dimension 2 such that the unique isomorphism between two non-computably isomorphic computable copies has Turing degree strictly below ${\mathbf{0}}^{″}$, and not above ${\mathbf{0}}^{\prime }$. This gives a first example of a computable structure with a degree of categoricity that does not belong to an interval of the form $[{\mathbf{0}}^{(\alpha )},{\mathbf{0}}^{(\alpha +1)}]$ for any computable ordinal α. We then extend the technique to produce a rigid structure of computable dimension 3 such that if ${\mathbf{d}}_0$, ${\mathbf{d}}_1$, and ${\mathbf{d}}_2$ are the degrees of isomorphisms between distinct representatives of the three computable equivalence classes, then each ${\mathbf{d}}_i<{\mathbf{d}}_0\oplus {\mathbf{d}}_1\oplus {\mathbf{d}}_2$. The resulting structure is an example of a structure that has a degree of categoricity, but not strongly.     

On modal logics arising from scattered locally compact Hausdorff spaces

For a topological space X, let $\mathsf{L}(X)$ be the modal logic of X where □ is interpreted as interior (and hence ◇ as closure) in X. It was shown in [3] that the modal logics S4, S4.1, S4.2, S4.1.2, S4.Grz, ${\mathsf{S4}.\mathsf{Grz}}_n$ ($n\ge 1$), and their intersections arise as $\mathsf{L}(X)$ for some Stone space X. We give an example of a scattered Stone space whose logic is not such an intersection. This gives an affirmative answer to [3, Question 6.2]. On the other hand, we show that a scattered Stone space that is in addition hereditarily paracompact does not give rise to a new logic; namely we show that the logic of such a space is either S4.Grz or ${\mathsf{S4}.\mathsf{Grz}}_n$ for some $n\ge 1$. In fact, we prove this result for any scattered locally compact open hereditarily collectionwise normal and open hereditarily strongly zero-dimensional space.     

The Σ1-provability logic of HA

In this paper we introduce a modal theory ${\mathsf{iH}}_{\sigma }$ which is sound and complete for arithmetical ${\mathrm{\Sigma }}_1$-interpretations in $\mathsf{HA}$, in other words, we will show that ${\mathsf{iH}}_{\sigma }$ is the ${\mathrm{\Sigma }}_1$-provability logic of $\mathsf{HA}$. Moreover we will show that ${\mathsf{iH}}_{\sigma }$ is decidable. As a by-product of these results, we show that $\mathsf{HA}+\square \perp$ has de Jongh property.     

The strength of compactness in Computability Theory and Nonstandard Analysis

Compactness is one of the core notions of analysis: it connects local properties to global ones and makes limits well-behaved. We study the computational properties of the compactness of Cantor space $2^{\mathbb{N}}$ for uncountable covers. The most basic question is: how hard is it to compute a finite sub-cover from such a cover of $2^{\mathbb{N}}$? Another natural question is: how hard is it to compute a sequence that covers $2^{\mathbb{N}}$ minus a measure zero set from such a cover? The special and weak fan functionals respectively compute such finite sub-covers and sequences. In this paper, we establish the connection between these new fan functionals on one hand, and various well-known comprehension axioms on the other hand, including arithmetical comprehension, transfinite recursion, and the Suslin functional. In the spirit of Reverse Mathematics, we also analyse the logical strength of compactness in Nonstandard Analysis. Perhaps surprisingly, the results in the latter mirror (often perfectly) the computational properties of the special and weak fan functionals. In particular, we show that compactness (nonstandard or otherwise) readily brings us to the outer edges of Reverse Mathematics (namely ${\mathrm{\Pi }}_2^1{\text{-}\mathsf{\text{CA}}}_0$), and even into Schweber's higher-order framework (namely ${\mathrm{\Sigma }}_1^2$-separation).     

Linearity and classification of ZpZp2-linear generalized Hadamard codes

The ${\mathbb{Z}}_p{\mathbb{Z}}_{p^2}$-additive codes are subgroups of ${\mathbb{Z}}_p^{{\alpha }_1}\times {\mathbb{Z}}_{p^2}^{{\alpha }_2}$, and can be seen as linear codes over ${\mathbb{Z}}_p$ when ${\alpha }_2=0$, ${\mathbb{Z}}_{p^2}$-additive codes when ${\alpha }_1=0$, or ${\mathbb{Z}}_2{\mathbb{Z}}_4$-additive codes when $p=2$. A ${\mathbb{Z}}_p{\mathbb{Z}}_{p^2}$-linear generalized Hadamard (GH) code is a GH code over ${\mathbb{Z}}_p$ which is the Gray map image of a ${\mathbb{Z}}_p{\mathbb{Z}}_{p^2}$-additive code. Recursive constructions of ${\mathbb{Z}}_p{\mathbb{Z}}_{p^2}$-additive GH codes of type $({\alpha }_1,{\alpha }_2;t_1,t_2)$ with $t_1,t_2\ge 1$ are known. In this paper, we generalize some known results for ${\mathbb{Z}}_p{\mathbb{Z}}_{p^2}$-linear GH codes with $p=2$ to any $p\ge 3$ prime when ${\alpha }_1\ne 0$, and then we compare them with the ones obtained when ${\alpha }_1=0$. First, we show for which types the corresponding ${\mathbb{Z}}_p{\mathbb{Z}}_{p^2}$-linear GH codes are nonlinear over ${\mathbb{Z}}_p$. Then, for these codes, we compute the kernel and its dimension, which allow us to classify them completely. Moreover, by computing the rank of some of these codes, we show that, unlike ${\mathbb{Z}}_4$-linear Hadamard codes, the ${\mathbb{Z}}_{p^2}$-linear GH codes are not included in the family of ${\mathbb{Z}}_p{\mathbb{Z}}_{p^2}$-linear GH codes with ${\alpha }_1\ne 0$ when $p\ge 3$ prime. Indeed, there are some families with infinite nonlinear ${\mathbb{Z}}_p{\mathbb{Z}}_{p^2}$-linear GH codes, where the codes are not equivalent to any ${\mathbb{Z}}_{p^s}$-linear GH code with $s\ge 2$.     

Uniqueness of certain Fourier-Jacobi models over finite fields

In this paper, we prove the uniqueness of certain Fourier-Jacobi models for the split exceptional group ${\mathrm{G}}_2$ over finite fields with odd characteristic. Similar results are also proved for ${\mathrm{Sp}}_4$ and ${\mathrm{U}}_4$.     

On the structure of certain valued fields

In this article, we study the structure of finitely ramified mixed characteristic valued fields. For any two complete discrete valued fields $K_1$ and $K_2$ of mixed characteristic with perfect residue fields, we show that if the n-th residue rings are isomorphic for each $n\ge 1$, then $K_1$ and $K_2$ are isometric and isomorphic. More generally, for $n_1\ge 1$, there is $n_2$ depending only on the ramification indices of $K_1$ and $K_2$ such that any homomorphism from the $n_1$-th residue ring of $K_1$ to the $n_2$-th residue ring of $K_2$ can be lifted to a homomorphism between the valuation rings. Moreover, we get a functor from the category of certain principal Artinian local rings of length n to the category of certain complete discrete valuation rings of mixed characteristic with perfect residue fields, which naturally generalizes the functorial property of unramified complete discrete valuation rings. Our lifting result improves Basarab's relative completeness theorem for finitely ramified henselian valued fields, which solves a question posed by Basarab, in the case of perfect residue fields.     

An altered four circulant construction for self-dual codes from group rings and new extremal binary self-dual codes I

We introduce an altered version of the four circulant construction over group rings for self-dual codes. We consider this construction over the binary field, the rings ${\mathbb{F}}_2+u{\mathbb{F}}_2$ and ${\mathbb{F}}_4+u{\mathbb{F}}_4$; using groups of order 4 and 8. Through these constructions and their extensions, we find binary self-dual codes of lengths 16, 32, 48, 64 and 68, many of which are extremal. In particular, we find forty new extremal binary self-dual codes of length 68, including twelve new codes with $\gamma =5$ in $W_{68,2}$, which is the first instance of such a $\gamma$ value in the literature.     

Construction of extremal Type II Z2k-codes

We give methods for constructing many self-dual ${\mathbb{Z}}_m$-codes and Type II ${\mathbb{Z}}_{2k}$-codes of length 2n starting from a given self-dual ${\mathbb{Z}}_m$-code and Type II ${\mathbb{Z}}_{2k}$-code of length 2n, respectively. As an application, we construct extremal Type II ${\mathbb{Z}}_{2k}$-codes of length 24 for $k=4,5,\dots ,20$ and extremal Type II ${\mathbb{Z}}_{2k}$-codes of length 32 for $k=4,5,\dots ,10$. We also construct new extremal Type II ${\mathbb{Z}}_4$-codes of lengths 56 and 64.