Mathematics - Logic Publications (50)

Search

Mathematics - Logic Publications

We study the complexity of the isomorphism relation for various classes of closed subgroups of the group of permutations of the natural numbers. We use the setting of Borel reducibility between equivalence relations on Polish spaces. For profinite, locally compact, and Roelcke precompact groups, we show that the complexity is the same as the one of countable graph isomorphism. Read More


In this article, we give a full description of the Wadge degrees of Borel functions from $\omega^\omega$ to a better quasi ordering $\mathcal{Q}$. More precisely, for any countable ordinal $\xi$, we show that the Wadge degrees of $\mathbf{\Delta}^0_{1+\xi}$-measurable functions $\omega^\omega\to\mathcal{Q}$ can be represented by countable joins of the $\xi$-th transfinite nests of $\mathcal{Q}$-labeled well-founded trees. Read More


In order to understand the structure of the "typical" element of an automorphism group, one has to study how large the conjugacy classes of the group are. When typical is meant in the sense of Baire category, a complete description of the size of the conjugacy classes has been given by Kechris and Rosendal. Following Dougherty and Mycielski we investigate the measure theoretic dual of this problem, using Christensen's notion of Haar null sets. Read More


We propose foundations for a synthetic theory of $(\infty,1)$-categories within homotopy type theory. First we develop a simplicial type theory within a new three-layered type theory with shapes, whose contexts are extended by polytopes within directed cubes, which can be abstracted over using "extension types" that generalize the path-types of cubical type theory. The simplices are then used to probe the internal categorical structures of types, allowing us to define Segal types, in which binary composites exist uniquely up to homotopy, and Rezk types, in which the categorical isomorphisms are additionally equivalent to the type-theoretic identities -- a "local univalence" condition. Read More


It is proved that the category $\mathbb{EM}$ of extended multisets is dually equivalent to the category $\mathbb{CHMV}$ of compact Hausdorff MV-algebras with continuous homomorphisms, which is in turn equivalent to the category of complete and completely distributive MV-algebras with homomorphisms that reflect principal maximal ideals. Read More


We continue the analysis of definably compact groups definable in a real closed field $\mathcal{R}$. In [3], we proved that for every definably compact definably connected semialgebraic group $G$ over $\mathcal{R}$ there are a connected $R$-algebraic group $H$, a definable injective map $\phi$ from a generic definable neighborhood of the identity of $G$ into the group $H\left(R\right)$ of $R$-points of $H$ such that $\phi$ acts as a group homomorphism inside its domain. The above result and our study of locally definable covering homomorphisms for locally definable groups combine to prove that if such group $G$ is in addition abelian, then its o-minimal universal covering group $\widetilde{G}$ is definably isomorphic, as a locally definable group, to a connected open locally definable subgroup of the o-minimal universal covering group $\widetilde{H\left(R\right)^{0}}$ of the group $H\left(R\right)^{0}$ for some connected $R$-algebraic group $H$. Read More


Formulae of the Lambek calculus are constructed using three binary connectives, multiplication and two divisions. We extend it using a unary connective, positive Kleene iteration. For this new operation, following its natural interpretation, we present two lines of calculi. Read More


We give some background on uniform pro-p groups and the model theory of profinite NIP groups. Read More


*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. Read More


For a group $G$, we define the notion of a $G$-kernel and show that the properties of $G$-kernels are closely related with the existence of a model companion of the theory of Galois actions of $G$. Using Bass-Serre theory, we show that this model companion exists for virtually free groups generalizing the existing results about free groups and finite groups. We show that the new theories we obtain are not simple and not even NTP$_2$. Read More


Modal description logics feature modalities that capture dependence of knowledge on parameters such as time, place, or the information state of agents. E.g. Read More


We explore a general method based on trees of elementary submodels in order to present highly simplified proofs to numerous results in infinite combinatorics. While countable elementary submodels have been employed in such settings already, we significantly broaden this framework by developing the corresponding technique for countably closed models of size continuum. The applications range from various theorems on paradoxical decompositions of the plane, to coloring sparse set systems, results on graph chromatic number and constructions from point-set topology. Read More


If F is a type-definable family of commensurable subsets, subgroups or sub-vector spaces in a metric structure, then there is an invariant subset, subgroup or sub-vector space commensurable with F. This in particular applies to type-definable or hyper-definable objects in a classical first-order structure. Read More


We construct a \emph{single} $\mathcal{L}_{\omega_1,\omega}$-sentence $\psi$ that codes Kurepa trees to prove the consistency of the following: (1) The spectrum of $\psi$ is consistently equal to $[\aleph_0,\aleph_{\omega_1}]$ and also consistently equal to $[\aleph_0,2^{\aleph_1})$, where $2^{\aleph_1}$ is weakly inaccessible. (2) The amalgamation spectrum of $\psi$ is consistently equal to $[\aleph_1,\aleph_{\omega_1}]$ and $[\aleph_1,2^{\aleph_1})$, where again $2^{\aleph_1}$ is weakly inaccessible. This is the first example of an $\mathcal{L}_{\omega_1,\omega}$--sentence whose spectrum and amalgamation spectrum are consistently both right-open and right-closed. Read More


A problem of Glasner, now known as Glasner's problem, asks whether every minimally almost periodic, monothetic, Polish groups is extremely amenable. The purpose of this short note is to observe that a positive answer is obtained under the additional assumption that the universal minimal flow is metrizable. Read More


This text was published in the book "Penser les math{\'e}matiques: s\'eminaire de philosophie et math\'ematiques de l'\'Ecole normale sup\'erieure (J. Dieudonn\'e, M. Loi, R. Read More


New Foundations ($\mathrm{NF}$) is a set theory obtained from naive set theory by putting a stratification constraint on the comprehension schema; for example, it proves that there is a universal set $V$. $\mathrm{NFU}$ ($\mathrm{NF}$ with atoms) is known to be consistent through its close connection with models of conventional set theory that admit automorphisms. A first-order theory, $\mathrm{ML}_\mathrm{CAT}$, in the language of categories is introduced and proved to be equiconsistent to $\mathrm{NF}$ (analogous results are obtained for intuitionistic and classical $\mathrm{NF}$ with and without atoms). Read More


Two structures A and B are n-equivalent if player II has a winning strategy in the n-move Ehrenfeucht-Fraisse game on A and B. We extend earlier results about n-equivalence for finite coloured linear orders, describing an algorithm for reducing to canonical form under 2-equivalence, and concentrating on the cases of 2 and 3 moves. Read More


Most interesting proofs in mathematics contain an inductive argument which requires an extension of the LK-calculus to formalize. The most commonly used calculi for induction contain a separate rule or axiom which reduces the valid proof theoretic properties of the calculus. To the best of our knowledge, there are no such calculi which allow cut-elimination to a normal form with the subformula property, i. Read More


It is shown that the complex field equipped with the "approximate exponential map", defined up to ambiguity from a small group, is quasiminimal: every automorphism-invariant subset of the field is countable or co-countable. If the ambiguity is taken to be from a subfield analogous to a field of constants then the resulting "blurred exponential field" is isomorphic to the result of an equivalent blurring of Zilber's exponential field, and to a suitable reduct of a differentially closed field. These results are progress towards Zilber's conjecture that the complex exponential field itself is quasiminimal. Read More


I explore two separate topics: the concept of jointness for set-theoretic guessing principles, and the notion of grounded forcing axioms. A family of guessing sequences is said to be joint if all of its members can guess any given family of targets independently and simultaneously. I primarily investigate jointness in the case of various kinds of Laver diamonds. Read More


In this paper, we analyze and compare three of the many algebraic structures that have been used for modeling dependent type theories: categories with families, split type-categories, and representable maps of presheaves. We study these in the setting of univalent foundations, where the relationships between them can be stated more transparently. We also introduce relative universes, generalizing the preceding notions. Read More


We introduce and develop the notion of *displayed categories*. A displayed category over a category C is equivalent to `a category C 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. Read More


In this paper we provided an explicit construction for the left adjoint of the forgetful functor from the category of Heyting algebras to that of Hilbert algebras. This functor factorizes through the free implicative semilattice extension of a Hilbert algebra of Celani and Jansana [On the free implicative semilattice extension of a Hilbert algebra}. Mathematical Logic Quarterly 58, 3 (2012), 188--207]. Read More


We simplify a criterion (due to Ibarluc\'ia and the author) which characterizes dynamical simplices, that is, sets $K$ of probability measures on a Cantor space $X$ for which there exists a minimal homeomorphism of $X$ whose set of invariant measures coincides with $K$. We then point out that this criterion is related to Fra\"iss\'e theory, and use that connection to provide a new proof of Downarowicz' theorem stating that any Choquet simplex is affinely homeomorphic to a dynamical simplex. The construction enables us to prove that there exist minimal homeomorphisms of a Cantor space which are speedup equivalent but not orbit equivalent, answering a question of D. Read More


This paper enlarges classical syllogistic logic with assertions having to do with comparisons between the sizes of sets. So it concerns a logical system whose sentences are of the following forms: {\sf All $x$ are $y$} and {\sf Some $x$ are $y$}, {\sf There are at least as many $x$ as $y$}, and {\sf There are more $x$ than $y$}. Here $x$ and $y$ range over subsets (not elements) of a given \emph{infinite} set. Read More


We prove that for any choice of parameters $k,t,\lambda$ the class of all finite ordered designs with parameters $k,t,\lambda$ is a Ramsey class. Read More


Using a modification of the invariant Jensen forcing, we define a model of ZFC, in which, for a given $n\ge3$, there exists a lightface $\varPi^1_n$ set of reals, which is a ${\mathsf E}_0$ equivalence class, hence a countable set, and which does not contain any OD element, while every non-empty countable $\varSigma^1_n$ set of reals is necessarily constructible, hence contains only OD reals. Read More


The paper is devoted to an algebraic interpretation of Kuznetsov's theorem which states the assertoric equipollence of intuitionistic and proof-intuitionistic propositional calculi. Given a Heyting algebra, we define an enrichable Heyting algebra, in which the former algebra is embedded, moreover, we show that both algebras generate one and the same variety of Heyting algebras. This algebraic result is equivalent to the Kuznetsov theorem. Read More


We show that the first order theory of the lattice of open sets in some natural topological spaces is $m$-equivalent to second order arithmetic. We also show that for many natural computable metric spaces and computable domains the first order theory of the lattice of effectively open sets is undecidable. Moreover, for several important spaces (e. Read More


Our aim is to solve a quite old question on the difference between expandability and compact expandability. Toward this, we further investigate the logic of countable cofinality. Read More


An edited version is given of the text of G\"odel's unpublished manuscript of the notes for a course in basic logic he delivered at the University of Notre Dame in 1939. G\"odel's notes deal with what is today considered as important logical problems par excellence, completeness, decidability, independence of axioms, and with natural deduction too, which was all still a novelty at the time the course was delivered. Full of regards towards beginners, the notes are not excessively formalistic. Read More


We complement the characterization of the graph products of cyclic groups $G(\Gamma, \mathfrak{p})$ admitting a Polish group topology of [9] with the following result. Let $G = G(\Gamma, \mathfrak{p})$, then the following are equivalent: (i) there is a metric on $\Gamma$ which induces a separable topology in which $E_{\Gamma}$ is closed; (ii) $G(\Gamma, \mathfrak{p})$ is embeddable into a Polish group; (iii) $G(\Gamma, \mathfrak{p})$ is embeddable into a non-Archimedean Polish group. We also construct left-invariant separable group ultrametrics for $G = G(\Gamma, \mathfrak{p})$ and $\Gamma$ a closed graph on the Baire space, which is of independent interest. Read More


In this paper, a new algebraic structure is defined, which is a new MV-algebra that has a product operation, we will call it MVW-rig (Multivalued-weak rig). This structure is defined with universal algebra axioms, it is presented with a good amount of natural examples in the MV-algebra environment and the first results having to do with ideal, quotients, homomorphisms and subdirect product are established. In particular, its prime spectrum is studied, that with the co-Zariski topology it is compact. Read More


We show that every free amalgamation class of finite structures with relations and (symmetric) partial functions is a Ramsey class when enriched by a free linear ordering of vertices. This is a common strengthening of the Ne\v{s}et\v{r}il-R\"odl Theorem and the second and third authors' Ramsey theorem for finite models (that is, structures with both relations and functions). We also find subclasses with the ordering property. Read More


We study the density function of measurable subsets of the Cantor space. Among other things, we identify a universal set $\mathcal{U}$ for $\Sigma^{1}_{1}$ subsets of $( 0 ; 1 )$ in terms of the density function; specifically $\mathcal{U}$ is the set of all pairs $( K , r )$ with $K$ compact and $r \in ( 0 ; 1 )$ being the density of some point with respect to $K$. This result yields that the set of all $K$ such that the range of its density function is $S \cup \{ 0 , 1 \}$, for some fixed uncountable analytic set $S \subseteq ( 0 ; 1 )$, is $\Pi^{1}_{2}$-complete. Read More


We state the Ramsey property of classes of ordered structures with closures and given local properties. This generalises many old and new results: the Ne\v{s}et\v{r}il-R\"{o}dl Theorem, the author's Ramsey lift of bowtie-free graphs as well as the Ramsey Theorem for Finite Models (i.e. Read More


We give strengthened versions of the Herwig-Lascar and Hodkinson-Otto extension theorems for partial automorphisms of finite relational structures. Such strengthening yields several combinatorial and group-theoretic consequences. We obtain a "coherent" form of EPPA for free amalgamation classes over a finite relational language. Read More


In order to understand the structure of the "typical" element of a homeomorphism group, one has to study how large the conjugacy classes of the group are. When typical means generic in the sense of Baire category, this is well understood, see e.g. Read More


We give a complete characterization of the graph products of cyclic groups admitting a Polish group topology, and show that they are all realizable as the group of automorphisms of a countable structure. In particular, we characterize the right-angled Coxeter groups (resp. Artin groups) admitting a Polish group topology. Read More


We establish the consistency of the failure of the diamond principle on a cardinal $\kappa$ which satisfies a strong simultaneous reflection property. The result is based on an analysis of Radin forcing, and further leads to a characterization of weak compactness of $\kappa$ in a Radin generic extension. Read More


We show that the $\omega$-categorical existentially closed universal bowtie-free graph of Cherlin-Shelah-Shi admits generic automorphisms in the sense of Truss. Moreover, we show that this graph is not finitely homogenisable. Read More


A Boolean algebra carries a strictly positive exhaustive submeasure if and only if it has a sequential topology that is uniformly Frechet. Read More


We present a necessary and sufficient condition for a Boolean algebra to carry a finitely additive measure. Read More


A Boolean $\sigma$-algebra $B$ is a measure algebra if and only if it is weakly distributive and uniformly concentrated. Read More


James Earl Baumgartner (March 23, 1943 - December 28, 2011) came of age mathematically during the emergence of forcing as a fundamental technique of set theory, and his seminal research changed the way set theory is done. He made fundamental contributions to the development of forcing, to our understanding of uncountable orders, to the partition calculus, and to large cardinals and their ideals. He promulgated the use of logic such as absoluteness and elementary submodels to solve problems in set theory, he applied his knowledge of set theory to a variety of areas in collaboration with other mathematicians, and he encouraged a community of mathematicians with engaging survey talks, enthusiastic discussions of open problems, and friendly mathematical conversations. Read More


We show how Leibnitz.s indiscernibility principle and Gentzen's original work lead to extensions of the sequent calculus to first order logic with equality and investigate the cut elimination property. Furthermore we discuss and improve the nonlengthening property of Lifshitz and Orevkov. Read More


We give a new axiomatization of the N-pseudospace, studied in [2] (Tent(2014)) and [1] (Baudisch,Martin-Pizarro,Ziegler(2014)) based on the zigzags introduced in [2]. We also present a more detailed account of the characterization of forking given in [2]. Read More


Can a positive function on R have zero Lebesgue integral? It depends on how much choice one has. Keywords: Lebesgue integral; Zermelo--Fraenkel theory; Feferman-Levy model Read More


Limits on the number of satisfying assignments for CNS instances with n variables and m clauses are derived from various inequalities. Some bounds can be calculated in polynomial time, sharper bounds demand information about the distribution of the number of unsatisfied clauses. Quite generally, the number of satisfying assignments involve variance and mean of this distribution. Read More