• ### $\aleph_1$ and the modal $\mu$-calculus(1704.03772)

Oct. 3, 2019 cs.LO, math.LO
For a regular cardinal $\kappa$, a formula of the modal $\mu$-calculus is $\kappa$-continuous in a variable x if, on every model, its interpretation as a unary function of x is monotone and preserves unions of $\kappa$-directed sets. We define the fragment $C_{\aleph_1}(x)$ of the modal $\mu$-calculus and prove that all the formulas in this fragment are $\aleph_1$-continuous. For each formula $\phi(x)$ of the modal $\mu$-calculus, we construct a formula $\psi(x) \in C_{\aleph_1 }(x)$ such that $\phi(x)$ is $\kappa$-continuous, for some $\kappa$, if and only if $\phi(x)$ is equivalent to $\psi(x)$. Consequently, we prove that (i) the problem whether a formula is $\kappa$-continuous for some $\kappa$ is decidable, (ii) up to equivalence, there are only two fragments determined by continuity at some regular cardinal: the fragment $C_{\aleph_0}(x)$ studied by Fontaine and the fragment $C_{\aleph_1}(x)$. We apply our considerations to the problem of characterizing closure ordinals of formulas of the modal $\mu$-calculus. An ordinal $\alpha$ is the closure ordinal of a formula $\phi(x)$ if its interpretation on every model converges to its least fixed-point in at most $\alpha$ steps and if there is a model where the convergence occurs exactly in $\alpha$ steps. We prove that $\omega_1$, the least uncountable ordinal, is such a closure ordinal. Moreover we prove that closure ordinals are closed under ordinal sum. Thus, any formal expression built from 0, 1, $\omega$, $\omega_1$ by using the binary operator symbol + gives rise to a closure ordinal.
• ### Tameness from two successive good frames(1707.09008)

March 25, 2019 math.LO
We show, assuming a mild set-theoretic hypothesis, that if an abstract elementary class (AEC) has a superstable-like forking notion for models of cardinality $\lambda$ and a superstable-like forking notion for models of cardinality $\lambda^+$, then orbital types over models of cardinality $\lambda^+$ are determined by their restrictions to submodels of cardinality $\lambda$. By a superstable-like forking notion, we mean here a good frame, a central concept of Shelah's book on AECs. It is known that locality of orbital types together with the existence of a superstable-like notion for models of cardinality $\lambda$ implies the existence of a superstable-like notion for models of cardinality $\lambda^+$, but here we prove the converse. An immediate consequence is that forking in $\lambda^+$ can be described in terms of forking in $\lambda$.
• ### Game characterizations and lower cones in the Weihrauch degrees(1511.03693)

Aug. 5, 2019 cs.LO, math.LO
We introduce a parametrized version of the Wadge game for functions and show that each lower cone in the Weihrauch degrees is characterized by such a game. These parametrized Wadge games subsume the original Wadge game, the eraser and backtrack games as well as Semmes's tree games. In particular, we propose that the lower cones in the Weihrauch degrees are the answer to Andretta's question on which classes of functions admit game characterizations. We then discuss some applications of such parametrized Wadge games. Using machinery from Weihrauch reducibility theory, we introduce games characterizing every (transfinite) level of the Baire hierarchy via an iteration of a pruning derivative on countably branching trees.
• ### Modalities in homotopy type theory(1706.07526)

Nov. 11, 2019 math.CT, cs.LO, math.LO
Univalent homotopy type theory (HoTT) may be seen as a language for the category of $\infty$-groupoids. It is being developed as a new foundation for mathematics and as an internal language for (elementary) higher toposes. We develop the theory of factorization systems, reflective subuniverses, and modalities in homotopy type theory, including their construction using a "localization" higher inductive type. This produces in particular the ($n$-connected, $n$-truncated) factorization system as well as internal presentations of subtoposes, through lex modalities. We also develop the semantics of these constructions.
• ### Obstructions to lifting abelian subalgebras of corona algebras(1611.06272)

March 22, 2019 math.OA, math.LO
Let $A$ be a non-commutative, non-unital $\mathrm{C}^\ast$-algebra. Given a set of commuting positive elements in the corona algebra $Q(A)$, we study some obstructions to the existence of a commutative lifting of such set to the multiplier algebra $M(A)$. Our focus are the obstructions caused by the size of the collection we want to lift. It is known that no obstacles show up when lifting a countable family of commuting projections, or of pairwise orthogonal positive elements. However, this is not the case for larger collections. We prove in fact that for every primitive, non-unital, $\sigma$-unital $\mathrm{C}^\ast$-algebra $A$, there exists an uncountable set of pairwise orthogonal positive elements in $Q(A)$ such that no uncountable subset of it can be lifted to a set of commuting elements of $M(A)$. Moreover, the positive elements in $Q(A)$ can be chosen to be projections if $A$ has real rank zero.
• ### When is scalar multiplication decidable?(1505.08055)

March 21, 2019 math.LO
Let $K$ be a subfield of $\mathbb{R}$. The theory of $\mathbb{R}$ viewed as an ordered $K$-vector space and expanded by a predicate for $\mathbb{Z}$ is decidable if and only if $K$ is a real quadratic field.
• ### Compactness in MV-Topologies: Tychonoff Theorem and Stone-Cech Compactification(1608.02923)

March 20, 2019 math.LO
In this paper, we discuss some questions about compactness in MV-topological spaces. More precisely, we first present a Tychonoff theorem for such a class of fuzzy topological spaces and some consequence of this result, among which, for example, the existence of products in the category of Stone MV-spaces and, consequently, of coproducts in the one of limit cut complete MV-algebras. Then we show that our Tychonoff theorem is equivalent, in ZF, to the Axiom of Choice, classical Tychonoff theorem, and Lowen's analogous result for lattice-valued fuzzy topology. Last, we show an extension of the Stone-Cech compactification functor to the category of MV-topological spaces, and we discuss its relationship with previous works on compactification for fuzzy topological spaces.
• ### Initial Semantics for Reduction Rules(1212.5668)

March 20, 2019 cs.LO, math.LO
We give an algebraic characterization of the syntax and operational semantics of a class of simply-typed languages, such as the language PCF: we characterize simply-typed syntax with variable binding and equipped with reduction rules via a universal property, namely as the initial object of some category of models. For this purpose, we employ techniques developed in two previous works: in the first work we model syntactic translations between languages over different sets of types as initial morphisms in a category of models. In the second work we characterize untyped syntax with reduction rules as initial object in a category of models. In the present work, we combine the techniques used earlier in order to characterize simply-typed syntax with reduction rules as initial object in a category. The universal property yields an operator which allows to specify translations---that are semantically faithful by construction---between languages over possibly different sets of types. As an example, we upgrade a translation from PCF to the untyped lambda calculus, given in previous work, to account for reduction in the source and target. Specifically, we specify a reduction semantics in the source and target language through suitable rules. By equipping the untyped lambda calculus with the structure of a model of PCF, initiality yields a translation from PCF to the lambda calculus, that is faithful with respect to the reduction semantics specified by the rules. This paper is an extended version of an article published in the proceedings of WoLLIC 2012.
• ### The definability of $\mathbb{E}$ in self-iterable mice(1412.0085)

March 19, 2019 math.LO
Let $M$ be a fine structural mouse and let $F\in M$ be such that $M\models$$F$ is a total extender'' and $(M||\mathrm{lh}(F),F)$ is a premouse. We show that it follows that $F\in\mathbb{E}^M$, where $\mathbb{E}^M$ is the extender sequence of $M$. We also prove generalizations of this fact. Let $M$ be a premouse with no largest cardinal and let $\Sigma$ be a sufficient iteration strategy for $M$. We prove that if $M$ knows enough of $\Sigma\upharpoonright M$ then $\mathbb{E}^M$ is definable over the universe $\lfloor M\rfloor$ of $M$, so if also $\lfloor M\rfloor\models\mathrm{ZFC}$ then $\lfloor M\rfloor\models$$V=\mathrm{HOD}$''. We show that this result applies in particular to $M=M_{\mathrm{nt}}|\lambda$, where $M_{\mathrm{nt}}$ is the least non-tame mouse and $\lambda$ is any limit cardinal of $M_{\mathrm{nt}}$. We also show that there is no iterable bicephalus $(N,E,F)$ for which $E$ is type $2$ and $F$ is type $1$ or $3$. As a corollary, we deduce a uniqueness property for maximal $L[\mathbb{E}]$ constructions computed in iterable background universes.
• ### Souslin quasi-orders and bi-embeddability of uncountable structures(1609.09292)

March 18, 2019 math.LO
We provide analogues of the results from [FMR11, CMMR13] in the reference list (which correspond to the case $\kappa = \omega$) for arbitrary $\kappa$-Souslin quasi-orders on any Polish space, for $\kappa$ an infinite cardinal smaller than the cardinality of $\mathbb{R}$. These generalizations yield a variety of results concerning the complexity of the embeddability relation between graphs or lattices of size $\kappa$, the isometric embeddability relation between complete metric spaces of density character $\kappa$, and the linear isometric embeddability relation between (real or complex) Banach spaces of density $\kappa$.
• ### An Abstract Approach to Consequence Relations(1710.00220)

March 17, 2019 math.LO
We generalise the Blok-J\'onsson account of structural consequence relations, later developed by Galatos, Tsinakis and other authors, in such a way as to naturally accommodate multiset consequence. While Blok and J\'onsson admit, in place of sheer formulas, a wider range of syntactic units to be manipulated in deductions (including sequents or equations), these objects are invariably aggregated via set-theoretical union. Our approach is more general in that non-idempotent forms of premiss and conclusion aggregation, including multiset sum and fuzzy set union, are considered. In their abstract form, thus, deductive relations are defined as additional compatible preorderings over certain partially ordered monoids. We investigate these relations using categorical methods, and provide analogues of the main results obtained in the general theory of consequence relations. Then we focus on the driving example of multiset deductive relations, providing variations of the methods of matrix semantics and Hilbert systems in Abstract Algebraic Logic.
• ### Formal Holomorphic Embeddings Between $\mathcal{BSD}$-Models(1708.00089)

July 25, 2019 math.LO, math.CV
It is studied the classification problem for formal holomorphic embeddings between Shilov Boundaries of Bounded Symmetric Domains of First Type.
• ### Model-theoretic Characterizations of Large Cardinals(1708.07561)

March 15, 2019 math.LO
We consider compactness characterizations of large cardinals. Based on results of Benda \cite{b-sccomp}, we study compactness for omitting types in various logics. In $\bL_{\kappa, \kappa}$, this allows us to characterize any large cardinal defined in terms of normal ultrafilters, and we also analyze second-order and sort logic. In particular, we give a compactness for omitting types characterization of huge cardinals, which have consistency strength beyond Vop\v{e}nka's Principle.
• ### On the strongest three-valued paraconsistent logic contained in classical logic(1702.03414)

March 14, 2019 cs.LO, math.LO
LP$^{\supset,\mathsf{F}}$ is a three-valued paraconsistent propositional logic which is essentially the same as J3. It has most properties that have been proposed as desirable properties of a reasonable paraconsistent propositional logic. However, it follows easily from already published results that there are exactly 8192 different three-valued paraconsistent propositional logics that have the properties concerned. In this note, properties concerning the logical equivalence relation of a logic are used to distinguish LP$^{\supset,\mathsf{F}}$ from the others. As one of the bonuses of focussing on the logical equivalence relation, it is found that only 32 of the 8192 logics have a logical equivalence relation that satisfies the identity, annihilation, idempotent, and commutative laws for conjunction and disjunction.
• ### Reconstructing the topology on monoids and polymorphism clones of reducts of the rationals(1606.09531)

March 12, 2019 math.LO
We extend results from an earlier paper giving reconstruction results for the endomorphism monoid of the rational numbers under the strict and reflexive relations to the first order reducts of the rationals and the corresponding polymorphism clones. We also give some similar results about the coloured rationals.
• ### Model Theory for a Compact Cardinal(1303.5247)

March 10, 2019 math.LO
We would like to develop model theory for T, a complete theory in L_{theta,theta}(tau) when theta is a compact cardinal. We already have bare bones stability theory and it seemed we can go no further. Dealing with ultrapowers (and ultraproducts) naturally we restrict ourselves to "D a theta-complete ultrafilter on I, probably (I,theta)-regular". The basic theorems of model theory work and can be generalized (like Los theorem), but can we generalize deeper parts of model theory? The first section tries to sort out what occurs to the notion of stable T for complete L_{theta,theta}-theories T. We generalize several properties of complete first order T, equivalent to being stable (see [Sh:c]) and find out which implications hold and which fail. In particular, can we generalize stability enough to generalize [Sh:c, Ch. VI]? Let us concentrate on saturation in the local sense (types consisting of instances of one formula). We prove that at least we can characterize the T's (of cardinality < theta for simplicity) which are minimal for appropriate cardinal lambda > 2^kappa +|T| in each of the following two senses. One is generalizing Keisler order which measures how saturated are ultrapowers. Another asks: Is there an L_{theta,theta}-theory T_1 supseteq T of cardinality |T| + 2^theta such that for every model M_1 of T_1 of cardinality > lambda, the tau(T)-reduct M of M_1 is lambda^+-saturated. Moreover, the two versions of stable used in the characterization are different.
• ### Semantics of higher inductive types(1705.07088)

March 5, 2019 math.CT, math.LO
Higher inductive types are a class of type-forming rules, introduced to provide basic (and not-so-basic) homotopy-theoretic constructions in a type-theoretic style. They have proven very fruitful for the "synthetic" development of homotopy theory within type theory, as well as in formalizing ordinary set-level mathematics in type theory. In this article, we construct models of a wide range of higher inductive types in a fairly wide range of settings. We introduce the notion of cell monad with parameters: a semantically-defined scheme for specifying homotopically well-behaved notions of structure. We then show that any suitable model category has *weakly stable typal initial algebras* for any cell monad with parameters. When combined with the local universes construction to obtain strict stability, this specializes to give models of specific higher inductive types, including spheres, the torus, pushout types, truncations, the James construction, and general localisations. Our results apply in any sufficiently nice Quillen model category, including any right proper, simplicially locally cartesian closed, simplicial Cisinski model category (such as simplicial sets) and any locally presentable locally cartesian closed category (such as sets) with its trivial model structure. In particular, any locally presentable locally cartesian closed $(\infty,1)$-category is presented by some model category to which our results apply.
• ### Completing graphs to metric spaces(1706.00295)

March 4, 2019 math.CO, math.LO, cs.DM
We prove that certain classes of metrically homogeneous graphs omitting triangles of odd short perimeter as well as triangles of long perimeter have the extension property for partial automorphisms and we describe their Ramsey expansions.
• ### Displayed Categories(1705.04296)

March 4, 2019 math.CT, math.LO
We introduce and develop the notion of *displayed categories*. A displayed category over a category C is equivalent to "a category D and functor F : D --> C", but instead of having a single collection of "objects of D" with a map to the objects of C, the objects are given as a family indexed by objects of C, and similarly for the morphisms. This encapsulates a common way of building categories in practice, by starting with an existing category and adding extra data/properties to the objects and morphisms. The interest of this seemingly trivial reformulation is that various properties of functors are more naturally defined as properties of the corresponding displayed categories. Grothendieck fibrations, for example, when defined as certain functors, use equality on objects in their definition. When defined instead as certain displayed categories, no reference to equality on objects is required. Moreover, almost all examples of fibrations in nature are, in fact, categories whose standard construction can be seen as going via displayed categories. We therefore propose displayed categories as a basis for the development of fibrations in the type-theoretic setting, and similarly for various other notions whose classical definitions involve equality on objects. Besides giving a conceptual clarification of such issues, displayed categories also provide a powerful tool in computer formalisation, unifying and abstracting common constructions and proof techniques of category theory, and enabling modular reasoning about categories of multi-component structures. As such, most of the material of this article has been formalised in Coq over the UniMath library, with the aim of providing a practical library for use in further developments.
• ### Thin Games with Symmetry and Concurrent Hyland-Ong Games(1409.7542)

March 1, 2019 cs.LO, math.LO
We build a cartesian closed category, called Cho, based on event structures. It allows an interpretation of higher-order stateful concurrent programs that is refined and precise: on the one hand it is conservative with respect to standard Hyland-Ong games when interpreting purely functional programs as innocent strategies, while on the other hand it is much more expressive. The interpretation of programs constructs compositionally a representation of their execution that exhibits causal dependencies and remembers the points of non-deterministic branching.The construction is in two stages. First, we build a compact closed category Tcg. It is a variant of Rideau and Winskel's category CG, with the difference that games and strategies in Tcg are equipped with symmetry to express that certain events are essentially the same. This is analogous to the underlying category of AJM games enriching simple games with an equivalence relations on plays. Building on this category, we construct the cartesian closed category Cho as having as objects the standard arenas of Hyland-Ong games, with strategies, represented by certain events structures, playing on games with symmetry obtained as expanded forms of these arenas.To illustrate and give an operational light on these constructions, we interpret (a close variant of) Idealized Parallel Algol in Cho.
• ### Minimum models of second-order set theories(1709.03955)

Feb. 28, 2019 math.LO
In this article I investigate the phenomenon of minimum models of second-order set theories, focusing on Kelley--Morse set theory $\mathsf{KM}$, G\"odel--Bernays set theory $\mathsf{GB}$, and $\mathsf{GB}$ augmented with the principle of Elementary Transfinite Recursion. The main results are the following. (1) A countable model of $\mathsf{ZFC}$ has a minimum $\mathsf{GBC}$-realization if and only if it admits a parametrically definable global well-order. (2) Countable models of $\mathsf{GBC}$ admit minimal extensions with the same sets. (3) There is no minimum transitive model of $\mathsf{KM}$. (4) There is a minimum $\beta$-model of $\mathsf{GB} + \mathsf{ETR}$. The main question left unanswered by this article is whether there is a minimum transitive model of $\mathsf{GB} + \mathsf{ETR}$.
• ### Weak containment of measure preserving group actions(1611.07921)

April 15, 2019 math.DS, math.LO
We survey recent progress in the theory of weak containment of measure preserving group actions.
• ### Generic norms and metrics on countable abelian groups(1605.06323)

Feb. 27, 2019 math.GN, math.LO, math.GR
For a countable abelian group $G$ we investigate generic properties of the space of all invariant metrics on $G$. We prove that for every such an unbounded group $G$, i.e. group which has elements of arbitrarily high order, there is a dense set of invariant metrics on $G$ which make $G$ isometric to the rational Urysohn space, and a comeager set of invariant metrics such that the completion is isometric to the Urysohn space. This generalizes results of Cameron and Vershik, Niemiec, and the author. Then we prove that for every $G$ such that $G\cong \bigoplus_\mathbb{N} G$ there is a comeager set of invariant metrics on $G$ such that all of them give rise to the same metric group after completion. If moreover $G$ is unbounded, then using a result of Melleray and Tsankov we get that the completion is extremely amenable.
• ### Destructibility of the tree property at $\aleph_{\omega+1}$(1603.05526)

April 29, 2019 math.LO
We construct a model in which the tree property holds in $\aleph_{\omega + 1}$ and it is destructible under $\text{Col}(\omega, \omega_1)$. On the other hand we discuss some cases in which the tree property is indestructible under small or closed forcings.
• ### Non-classification of free Araki-Woods factors and $\tau$-invariants(1708.07496)

Feb. 25, 2019 math.OA, math.LO
We define the standard Borel space of free Araki-Woods factors and prove that their isomorphism relation is not classifiable by countable structures. We also prove that equality of $\tau$-topologies, arising as invariants of type III factors, as well as coycle and outer conjugacy of actions of abelian groups on free product factors are not classifiable by countable structures.