Classifying resolving subcategories over a Cohen–Macaulay local ring

Let R be a Cohen–Macaulay local ring. Denote by mod R the category of finitely generated R-modules. In this paper, we consider the classification problem of resolving subcategories of mod R in terms of specialization-closed subsets of Spec R. We give a classification of the resolving subcategories closed under tensor products and transposes. Under restrictive hypotheses, we also give better classification results.     

Proximity Frames and Regularization

It is well known that the category KHaus of compact Hausdorff spaces is dually equivalent to the category KRFrm of compact regular frames. By de Vries duality, KHaus is also dually equivalent to the category DeV of de Vries algebras, and so DeV is equivalent to KRFrm, where the latter equivalence can be described constructively through Booleanization. Our purpose here is to lift this circle of equivalences and dual equivalences to the setting of stably compact spaces. The dual equivalence of KHaus and KRFrm has a well-known generalization to a dual equivalence of the categories StKSp of stably compact spaces and StKFrm of stably compact frames. Here we give a common generalization of de Vries algebras and stably compact frames we call proximity frames. For the category PrFrm of proximity frames we introduce the notion of regularization that extends that of Booleanization. This yields the category RPrFrm of regular proximity frames. We show there are equivalences and dual equivalences among PrFrm, its subcategories StKFrm and RPrFrm, and StKSp. Restricting to the compact Hausdorff setting, the equivalences and dual equivalences among StKFrm, RPrFrm, and StKSp yield the known ones among KRFrm, DeV, and KHaus. The restriction of PrFrm to this setting provides a new category StrInc whose objects are frames with strong inclusions and whose morphisms and composition are generalizations of those in DeV. Both KRFrm and DeV are subcategories of StrInc that are equivalent to StrInc. For a compact Hausdorff space X, the category StrInc not only contains both the frame of open sets of X and the de Vries algebra of regular open sets of X, these two objects are isomorphic in StrInc, with the second being the regularization of the first. The restrictions of these categories are considered also in the setting of spectral spaces, Stone spaces, and extremally disconnected spaces.     

A Topologist’s View of Chu Spaces

For a symmetric monoidal-closed category $\mathcal{X}$ and any object K, the category of K-Chu spaces is small-topological over $\mathcal{X}$ and small cotopological over $\mathcal{X}^{{{\text{op}}}}$ . Its full subcategory of $\mathcal{M}$ -extensive K-Chu spaces is topological over $\mathcal{X}$ when $\mathcal{X}$ is $\mathcal{M}$ -complete, for any morphism class $\mathcal{M}$ . Often this subcategory may be presented as a full coreflective subcategory of Diers’ category of affine K-spaces. Hence, in addition to their roots in the theory of pairs of topological vector spaces (Barr) and their connections with linear logic (Seely), the Dialectica categories (Hyland, de Paiva), and with the study of event structures for modeling concurrent processes (Pratt), Chu spaces seem to have a less explored link with algebraic geometry. We use the Zariski closure operator to describe the objects of the *-autonomous category of $\mathcal{M}$ -extensive and $\mathcal{M}$ -coextensive K-Chu spaces in terms of Zariski separation and to identify its important subcategory of complete objects.     

Unitary SK1 of semiramified graded and valued division algebras

We prove formulas for SK₁(E, τ), which is the unitary SK₁ for a graded division algebra E finite-dimensional and semiramified over its center T with respect to a unitary involution τ on E. Every such formula yields a corresponding formula for SK₁(D, ρ) where D is a division algebra tame and semiramified over a Henselian valued field and ρ is a unitary involution on D. For example, it is shown that if ${\sf{E} \sim \sf{I}_0 \otimes_{\sf{T}_0}\sf{N}}$ where I ₀ is a central simple T ₀-algebra split by N ₀ and N is decomposably semiramified with ${\sf{N}_0 \cong L_1\otimes_{\sf{T}_0} L_2}$ with L ₁, L ₂ fields each cyclic Galois over T ₀, then $${\rm SK}_1(\sf{E}, \tau) \,\cong\ {\rm Br}(({L_1}\otimes_{\sf{T}_0} {L_2})/\sf{T}_0;\sf{T}_0^\tau)\big/ \left[{\rm Br}({L_1}/\sf{T}_0;\sf{T}_0^\tau)\cdot {\rm Br}({L_2}/\sf{T}_0;\sf{T}_0^\tau) \cdot \langle[\sf{I}_0]\rangle\right].$$      

On Borel almost disjoint families

There is a close correspondence between uncountable almost disjoint families of subsets of $\omega $ and Aleksandrov–Urysohn compacta (in short, AU-compacta)—separable, uncountable compact spaces whose second derived set is a singleton. We shall show in particular, that AU-compacta embeddable in the space of first Baire class functions on the Cantor set $2^\omega $ , with the pointwise topology, are exactly the ones determined by almost disjoint families that are Borel sets in $2^\omega $ , and they are also distinguished among AU-compacta by the property that the cylindrical $\sigma $ -algebras of their function spaces are standard measurable spaces. Although the first condition implies the third one for arbitrary separable compact space, it is an open problem, whether the reverse implication is always true.     

Phase transitions of iterated Higman-style well-partial-orderings

We elaborate Weiermann-style phase transitions for well-partial-orderings (wpo) determined by iterated finite sequences under Higman-Friedman style embedding with Gordeev’s symmetric gap condition. For every d-times iterated wpo ${\left({\rm S}\text{\textsc{eq}}^{d}, \trianglelefteq _{d}\right)}$ in question, d >? 1, we fix a natural extension of Peano Arithmetic, ${T \supseteq \sf{PA}}$ , that proves the corresponding second-order sentence ${\sf{WPO}\left({\rm S}{\textsc{eq}}^{d}, \trianglelefteq _{d}\right) }$ . Having this we consider the following parametrized first-order slow well-partial-ordering sentence ${\sf{SWP}\left({\rm S}\text{\textsc{eq}}^{d}, \trianglelefteq _{d}, r\right):}$ $$\left( \forall K > 0 \right) \left( \exists M > 0\right) \left( \forall x_{0},\ldots ,x_{M}\in {\rm S}\text{\textsc{eq}}^{d}\right)$$ $$\left( \left( \forall i\leq M\right) \left( \left| x_{i}\right| < K + r \left\lceil \log _{d} \left( i+1\right) \right\rceil \right)\rightarrow \left( \exists i < j \leq M \right) \left(x_{i} \trianglelefteq _{d} x_{j}\right) \right)$$ for a natural additive Seq ^d -norm |·| and r ranging over EFA-provably computable positive reals, where EFA is an abbreviation for IΔ ₀?+?exp. We show that the following basic phase transition clauses hold with respect to ${T = \Pi_{1}^{0}\sf{CA}_{ < \varphi ^{_{\left( d-1\right) }} \left(0\right) }}$ and the threshold point1.

1. If r <? 1 then ${\sf{SWP}\left({\rm S}\text{\textsc{eq}}^{d}, \trianglelefteq _{d},r \right) }$ is provable in T.

1. If ${r > 1}$ then ${\sf{SWP}\left({\rm S}\text{\textsc{eq}}^{d}, \trianglelefteq _{d},r \right) }$ is not provable in T.

Moreover, by the well-known proof theoretic equivalences we can just as well replace T by PA or ACA ₀ and ${\Delta _{1}^{1}\sf{CA}}$ , if d =? 2 and d =? 3, respectively.In the limit case d → ∞ we replaceEFA-provably computable reals r by EFA-provably computable functions ${f: \mathbb{N} \rightarrow \mathbb{R}_{+}}$ and prove analogous theorems. (In the sequel we denote by ${\mathbb{R}_{+}}$ the set of EFA-provably computable positive reals). In the basic case T?=? PA we strengthen the basic phase transition result by adding the following static threshold clause

1. ${\sf{SWP}\left({\rm S}\text{\textsc{eq}}^{2}, \trianglelefteq _{2}, 1\right)}$ is still provable in T = PA (actually in EFA).

Furthermore we prove the following dynamic threshold clauses which, loosely speaking are obtained by replacing the static threshold t by slowly growing functions 1 _α given by ${1_{\alpha }\left( i\right)\,{:=}\,1+\frac{1}{H_{\alpha }^{-1}\left(i\right) }, H_{\alpha}}$ being the familiar fast growing Hardy function and ${H_{\alpha }^{-1}\left( i\right)\,{:=}\,\rm min \left\{ j \mid H_{\alpha } \left ( j\right) \geq i \right\}}$ the corresponding slowly growing inversion.

1. If ${\alpha < \varepsilon _{0}}$ , then ${\sf{SWP}\left({\rm S}\text{\textsc{eq}}^{2}, \trianglelefteq _{2}, 1_{\alpha}\right)}$ is provable in T = PA.

1. ${\sf{SWP}\left( {\rm S}\text{\textsc{eq}}^{2}, \trianglelefteq _{2},1_{\varepsilon _{0}}\right)}$ is not provable in T = PA.

We conjecture that this pattern is characteristic for all ${T\supseteq \sf{PA}}$ under consideration and their proof-theoretical ordinals o (T ), instead of ${\varepsilon _{0}}$ .     

E-local pseudovarieties

Generalizing a property of the pseudovariety of all aperiodic semigroups observed by Tilson, we call E -local a pseudovariety V which satisfies the following property: for a finite semigroup, the subsemigroup generated by its idempotents belongs to V if and only if so do the subsemigroups generated by the idempotents in each of its regular $\mathcal{D}$ -classes. In this paper, we present several sufficient or necessary conditions for a pseudovariety to be E-local or for a pseudoidentity to define an E-local pseudovariety. We also determine several examples of the smallest E-local pseudovariety containing a given pseudovariety.     

A note on da Costa-Doria “exotic formalizations”

We analyze N. C. A. da Costa and F. A. Doria’s “exotic formalization” of the conjecture P = NP [3–7]. For any standard axiomatic PA extension T and any number-theoretic sentence ${\varphi }$ , we let ${\varphi ^{\star} := \varphi \vee \lnot \mathsf{Con}\left( \mathsf{T}\right)}$ and prove the following “exotic” inferences 1–3. 1. ${\mathsf{T}+\varphi ^{\star}}$ is consistent, if so is T, 2. ${\mathsf{T}+\varphi}$ is consistent, provided that ${\mathsf{T}+\varphi ^{\star}}$ is ω-consistent, 3. ${\mathsf{T}+\varphi}$ is consistent, provided that T is consistent and has the same provably total recursive functions as ${\mathsf{T}+\left( \varphi \leftrightarrow \varphi ^{\star }\right) }$ . Furthermore we show that 1–3 continue to hold for ${\varphi ^{\star} := \varphi _{S} :=\varphi \vee \lnot S}$ , where ${S=\forall x\exists yR\left( x,y\right)}$ is any ${\Pi _{2}^{0}}$ sentence satisfying: 4. ${\left( \forall n\in \omega \right) \left( \mathsf{T}\vdash S_{x}\left[ \underline{n}\right] \right) }$ , 5. ${\mathsf{Con}\left( \mathsf{T}\right) \Rightarrow \mathsf{T}\nvdash S}$ . We observe that if ${\varphi :=\left[ \mathsf{P}=\mathsf{NP}\right] }$ and ${S:= \left[\digamma total\right] }$ , where ${\digamma=\digamma _{\mathsf{T}}}$ is da Costa-Doria “exotic” function with respect to T, then 4, 5 are satisfied for most familiar (presumably) consistent T in question, while ${\varphi _{S}}$ becomes equivalent to da Costa-Doria “exotic formalization” ${\left[ \mathsf{P}=\mathsf{NP}\right]^{\digamma}}$ . Moreover, the corresponding “exotic” inferences 1–3 generalize analogous da Costa-Doria results. Hence these “exotic” inferences are universal for all number-theoretic sentences and not characteristic to the conjecture P = NP. Nor do they infer relative consistency of P = NP (see Conclusion 15 in the text).     

On the conservativity of the axiom of choice over set theory

We show that for various set theories T including ZF, T + AC is conservative over T for sentences of the form ${\forall x \exists ! y}$ A(x, y) where A(x, y) is a ??₀ formula.     

Extracting BB′IW Inhabitants of Simple Types From Proofs in the Sequent Calculus {LT_\to^{t}} for Implicational Ticket Entailment

The decidability of the logic of pure ticket entailment means that the problem of inhabitation of simple types by combinators over the base { B, B′, I, W } is decidable too. Type-assignment systems are often formulated as natural deduction systems. However, our decision procedure for this logic, which we presented in earlier papers, relies on two sequent calculi and it does not yield directly a combinator for a theorem of ${T_\to}$ . Here we describe an algorithm to extract an inhabitant from a sequent calculus proof—without translating the proof into another proof system.     

Twisted split category algebras as quasi-hereditary algebras

We show that if C is a finite split category, k is a field of characteristic 0, and α is a 2-cocycle of C with values in k  ^× , then the twisted category algebra k _α C is quasi-hereditary.     

A characterization of the Grassmann embedding of H(q), with q even

In this note, we characterize the Grassmann embedding of H(q), q even, as the unique full embedding of H(q) in PG(12, q) for which each ideal line of H(q) is contained in a plane. In particular, we show that no such embedding exists for H(q), with q odd. As a corollary, we can classify all full polarized embeddings of H(q) in PG(12, q) with the property that the lines through any point are contained in a solid; they necessarily are Grassmann embeddings of H(q), with q even.     

Admissible closures of polynomial time computable arithmetic

We propose two admissible closures ${\mathbb{A}({\sf PTCA})}$ and ${\mathbb{A}({\sf PHCA})}$ of Ferreira??s system PTCA of polynomial time computable arithmetic and of full bounded arithmetic (or polynomial hierarchy computable arithmetic) PHCA. The main results obtained are: (i) ${\mathbb{A}({\sf PTCA})}$ is conservative over PTCA with respect to ${\forall\exists\Sigma^b_1}$ sentences, and (ii) ${\mathbb{A}({\sf PHCA})}$ is conservative over full bounded arithmetic PHCA for ${\forall\exists\Sigma^b_{\infty}}$ sentences. This yields that (i) the ${\Sigma^b_1}$ definable functions of ${\mathbb{A}({\sf PTCA})}$ are the polytime functions, and (ii) the ${\Sigma^b_{\infty}}$ definable functions of ${\mathbb{A}({\sf PHCA})}$ are the functions in the polynomial time hierarchy.     

Semiconic idempotent residuated structures

An idempotent residuated po-monoid is semiconic if it is a subdirect product of algebras in which the monoid identity is comparable with all other elements. It is proved that the quasivariety SCIP of all semiconic idempotent commutative residuated po-monoids is locally finite. The lattice-ordered members of this class form avariety SCIL, which is not locally finite, but it is proved that SCIL has the finite embeddability property (FEP). More generally, for every relative subvariety K of SCIP, the lattice-ordered members of K have the FEP. This gives a unified explanation of the strong finite model property for a range of logical systems. It is also proved that SCIL has continuously many semisimple subvarieties, and that the involutive algebras in SCIL are subdirect products of chains.     

Enriched Logical Connections

In the setting of enriched category theory, we describe dual adjunctions of the form $L\dashv R:{\mathsf{Spa}}^{op} \longrightarrow{\mathsf{Alg}}$ between the dual of the category Spa of “spaces” and the category Alg of “algebras” that arise from a schizophrenic object Ω, which is both an “algebra” and a “space”. We call such adjunctions logical connections. We prove that the exact nature of Ω is that of a module that allows to lift optimally the structure of a “space” and an “algebra” to certain diagrams. Our approach allows to give a unified framework known from logical connections over the category of sets and analyzed, e.g., by Hans Porst and Walter Tholen, with future applications of logical connections in coalgebraic logic and elsewhere, where typically, both the category of “spaces” and the category of “algebras” consist of “structured presheaves”.     

On predicate provability logics and binumerations of fragments of Peano arithmetic

Solovay proved (Israel J Math 25(3–4):287–304, 1976) that the propositional provability logic of any ∑₂-sound recursively enumerable extension of PA is characterized by the propositional modal logic GL. By contrast, Montagna proved in (Notre Dame J Form Log 25(2):179–189, 1984) that predicate provability logics of Peano arithmetic and Bernays–Gödel set theory are different. Moreover, Artemov proved in (Doklady Akademii Nauk SSSR 290(6):1289–1292, 1986) that the predicate provability logic of a theory essentially depends on the choice of a binumeration of the theory which is used to construct the provability predicate. In this paper, we compare predicate provability logics of I∑ _n ’s. For a binumeration α(x) of a recursive theory T, let PL _α(T) be the predicate provability logic of T defined by α(x). We prove that for any natural numbers i, j such that 0 < i < j, there exists a ∑₁ binumeration α(x) of some recursive axiomatization of I∑ _i such that ${{\sf PL}_\alpha({\rm I \Sigma}_i) \nsupseteq \bigcap_{\beta(x)}{\sf PL}_\beta({\rm I \Sigma}_j)}$ PL α ( I Σ i ) ? ? β ( x ) PL β ( I Σ j ) and ${{\sf PL}_\alpha({\rm I \Sigma}_i) \nsubseteq \bigcup_{\beta(x)}{\sf PL}_\beta({\rm I \Sigma}_j)}$ PL α ( I Σ i ) ? ? β ( x ) PL β ( I Σ j ) , where β(x) ranges over all ∑₁ binumerations of recursive axiomatizations of I∑ _j .     

Group homomorphic encryption: characterizations, impossibility results, and applications

We give a complete characterization both in terms of security and design of all currently existing group homomorphic encryption schemes, i.e., existing encryption schemes with a group homomorphic decryption function such as ElGamal and Paillier. To this end, we formalize and identify the basic underlying structure of all existing schemes and say that such schemes are of shift-type. Then, we construct an abstract scheme that represents all shift-type schemes (i.e., every scheme occurs as an instantiation of the abstract scheme) and prove its IND-CCA1 (resp. IND-CPA) security equivalent to the hardness of an abstract problem called Splitting Oracle-Assisted Subgroup Membership Problem (SOAP) (resp. Subgroup Membership Problem, SMP). Roughly, SOAP asks for solving an SMP instance, i.e., for deciding whether a given ciphertext is an encryption of the neutral element of the ciphertext group, while allowing access to a certain oracle beforehand. Our results allow for contributing to a variety of open problems such as the IND-CCA1 security of Paillier’s scheme, or the use of linear codes in group homomorphic encryption. Furthermore, we design a new cryptosystem which provides features that are unique up to now: Its IND-CPA security is based on the k-linear problem introduced by Shacham, and Hofheinz and Kiltz, while its IND-CCA1 security is based on a new k-problem that we prove to have the same progressive property, namely that if the k-instance is easy in the generic group model, the (k+1)-instance is still hard.     

On the hull-kernel and inverse topologies as frames

We consider some frame-theoretic properties of the hull-kernel and the inverse topologies on the set of minimal prime ideals of an algebraic frame with the finite intersection property on its compact elements. Denote by Alg _do the subcategory of Frm consisting of such frames together with dense onto coherent maps. We construct a functor ${{\sf T} : {\bf Alg}_{\rm do} \rightarrow {\bf Frm}}$ T : Alg do → Frm and a natural transformation ${\tau : {\sf E} \rightarrow {\sf T}}$ τ : E → T , where E is the inclusion functor from Alg _do to Frm.     

Reeb Graphs: Approximation and Persistence

Given a continuous function f:X→? on a topological space X, its level set f ^?1(a) changes continuously as the real value a changes. Consequently, the connected components in the level sets appear, disappear, split and merge. The Reeb graph of f summarizes this information into a graph structure. Previous work on Reeb graph mainly focused on its efficient computation. In this paper, we initiate the study of two important aspects of the Reeb graph, which can facilitate its broader applications in shape and data analysis. The first one is the approximation of the Reeb graph of a function on a smooth compact manifold M without boundary. The approximation is computed from a set of points P sampled from M. By leveraging a relation between the Reeb graph and the so-called vertical homology group, as well as between cycles in M and in a Rips complex constructed from P, we compute the H ₁-homology of the Reeb graph from P. It takes O(nlogn) expected time, where n is the size of the 2-skeleton of the Rips complex. As a by-product, when M is an orientable 2-manifold, we also obtain an efficient near-linear time (expected) algorithm for computing the rank of H ₁(M) from point data. The best-known previous algorithm for this problem takes O(n ³) time for point data. The second aspect concerns the definition and computation of the persistent Reeb graph homology for a sequence of Reeb graphs defined on a filtered space. For a piecewise-linear function defined on a filtration of a simplicial complex K, our algorithm computes all persistent H ₁-homology for the Reeb graphs in $O(n n_{e}^{3})$ time, where n is the size of the 2-skeleton and n _e is the number of edges in K.