Mathematics - Logic Publications (50)

Search

Mathematics - Logic Publications

For $n<\omega$, we say that the $\Pi^1_n$-reflection principle holds at $\kappa$ and write $Refl_n(\kappa)$ if and only if every $\Pi^1_n$-indescribable subset of $\kappa$ has a $\Pi^1_n$-indescribable proper initial segment. The $\Pi^1_n$-reflection principle $Refl_n(\kappa)$ generalizes a certain stationary reflection principle and implies that $\kappa$ is $\Pi^1_n$-indescribable of order $\omega$. We prove that the converse of this implication is consistently false in the case $n=1$. Read More


The Kechris-Pestov-Todorcevic correspondence connects extreme amenability of non-Archimedean Polish groups with Ramsey properties of classes of finite structures. The purpose of the present paper is to recast it as one of the instances of a more general construction, allowing to show that Ramsey-type statements actually appear as natural combinatorial expressions of the existence of fixed points in certain compactifications of groups, and that similar correspondences in fact exist in various dynamical contexts. Read More


We study pivotal decomposition schemes and investigate classes of pivotally decomposable operations. We provide sufficient conditions on pivotal operations that guarantee that the corresponding classes of pivotally decomposable operations are clones, and show that under certain assumptions these conditions are also necessary. In the latter case, the pivotal operation together with the constant operations generate the corresponding clone. Read More


Let $\kappa$ be an infinite cardinal. Then, forcing with $\mathbb{R}(\kappa)$$\times$$\mathbb{R}(\kappa)$ adds a generic filter for $\mathbb{C}(\kappa);$ where $\mathbb{R}(\kappa)$ and $\mathbb{C}(\kappa)$ are the forcing notions for adding $\kappa$-many random reals and adding $\kappa$-many Cohen reals respectively. Read More


We show that the standard approach of minimal invariant sets, which applies Zorn's Lemma and is used to prove fixed point theorems for non-expansive mappings in Banach spaces can be applied without any reference to the full Axiom of Choice when the given Banach space is separable. Our method applies results from classical and effective descriptive set theory. Read More


We study the equivalence classes under $\Delta^1_1$ isomorphism, otherwise effective-Borel isomorphism, between complete separable metric spaces which admit a recursive presentation and we show the existence of strictly increasing and strictly decreasing sequences as well as of infinite antichains under the natural notion of $\Delta^1_1$-reduction, as opposed to the non-effective case, where only two such classes exist, the one of the Baire space and the one of the naturals. A key tool for our study is a mapping $T \mapsto \mathcal{N}^T$ from the space of all trees on the naturals to the class of Polish spaces, for which every recursively presented space is $\Delta^1_1$-isomorphic to some $\mathcal{N}^T$ for a recursive $T$, so that the preceding spaces are representatives for the classes of $\Delta^1_1$-isomorphism. We isolate two large categories of spaces of the type $\mathcal{N}^T$, the Kleene spaces and the Spector-Gandy spaces and we study them extensively. Read More


I show that propositional intuitionistic logic is complete with respect to a corrected version of Dummett's pragmatist justification procedure. In particular, given a pragmatist justification of an argument, I show how to obtain a natural deduction derivation of the conclusion of the argument from, at most, the same assumptions. Read More


We introduce the notion of additive filter and present a new proof of the existence of idempotent ultrafilters on N without any use of Zorn's Lemma, and where one only assumes the Ultrafilter Theorem for the continuum. Read More


We describe the modules in the Ziegler closure of ray and coray tubes in module categories over finite-dimensional algebras. We improve slightly on Krause's result for stable tubes by showing that the inverse limit along a coray in a ray or coray tube is indecomposable, so in particular, the inverse limit along a coray in a stable tube is indecomposable. In order to do all this, we first describe the finitely presented modules over and the Ziegler spectra of iterated one-point extensions of valuation domains. Read More


A compact topological space $X$ is \emph{spectral} if it is sober and the compact open subsets of $X$ form a basis of the topology of $X$, closed under finite intersections. It is well known that the spectrum of an Abelian $\ell$-group with unit -- equivalently, of an MV-algebra -- is spectral. Theorem. Read More


We prove the consistency of ZF+DC+"there are no mad families"+"there exists a non-meager filter on $\omega$" relative to ZFC, answering a question of Neeman and Norwood. We also introduce a weaker version of madness, and we strengthen the result from [HwSh:1090] by showing that no such families exist in our model. Read More


We prove that in the Cohen extension adding $\aleph_3$ generic reals to a model of $ZFC+CH$ containing a simplified $(\omega_1,2)$-morass, gap-2 morass-definable $\eta_1$-orderings with cardinality $\aleph_3$ are order-isomorphic. Hence it is consistent that the $2^{\aleph_0}=\aleph_3$ and that morass-definable $\eta_1$-orderings with cardinality of the continuum are order-isomorphic. We prove that there are ultrapowers of $\mathbb{R}$ over $\omega$ that are gap-2 morass-definable. Read More


An introduction and survey of homotopy type theory in honor of W.W. Tait. Read More


When a linear order has an order preserving surjection onto each of its suborders we say that it is strongly surjective. We prove that the set of countable strongly surjective linear orders is complete for the class of sets which are the union of an analytic and a coanalytic set. Using hypotheses beyond ZFC, we prove the existence of uncountable strongly surjective orders. Read More


By a well-known result of Shepherdson, models of the theory IOpen (a first order arithmetic containing the scheme of induction for all quantifier free formulas) are exactly all the discretely ordered semirings that are integer parts of their real closures. In this paper we prove several analogous results that provide algebraic equivalents to various fragments of IOpen. Read More


We prove that no uncountable Polish group can admit a system of generators whose associated length function satisfies the following conditions: (i) if $0 < k < \omega$, then $lg(x) \leq lg(x^k)$; (ii) if $lg(y) < k < \omega$ and $x^k = y$, then $x = e$. In particular, the automorphism group of a countable structure cannot be an uncountable right-angled Artin group. This generalizes results from [3] and [5], where this is proved for free and free Abelian uncountable groups. Read More


Given a set $A\subseteq\mathbb{N}$, we consider the relationship between stability of the structure $(\mathbb{Z},+,0,A)$ and sparsity assumptions on the set $A$. We first show that a strong enough sparsity assumption on $A$ yields stability of $(\mathbb{Z},+,0,A)$. Specifically, if there is a function $f:A\longrightarrow\mathbb{R}^+$ such that $\text{sup}_{a\in A}|a-f(a)|<\infty$ and $\{\frac{s}{t}:s,t\in f(A),~t\leq s\}$ is closed and discrete, then $(\mathbb{Z},+,0,A)$ is superstable (of $U$-rank $\omega$ if $A$ is infinite). Read More


The algebra of embeddings at the I3 level has been deeply analyzed, but nothing is known algebra-wise for embeddings above I3. In this paper it is introduced an operation for embeddings at the level of I0 and above, and it is proven that they generate an LD-algebra that can be quite different from the I3 one. Read More


We present a unified categorical treatment of completeness theorems for several classical and intuitionistic infinitary logics with a proposed axiomatization. This provides new completeness theorems and subsumes previous ones by G\"odel, Kripke, Beth, Karp, Joyal, Makkai and Fourman/Grayson. As an application we prove, using large cardinals assumptions, the disjunction and existence properties for infinitary intuitionistic first-order logics. Read More


We investigate (2,1):1 structures, which consist of a countable set $A$ together with a function $f: A \to A$ such that for every element $x$ in $A$, $f$ maps either exactly one element or exactly two elements of $A$ to $x$. These structures extend the notions of injection structures, 2:1 structures, and (2,0):1 structures studied by Cenzer, Harizanov, and Remmel, all of which can be thought of as infinite directed graphs. We look at various computability-theoretic properties of (2,1):1 structures, most notably that of computable categoricity. Read More


This paper proves the approximate intermediate value theorem, constructively and from notably weak hypotheses: from pointwise rather than uniform continuity, without assuming that reals are presented with rational approximants, and without using countable choice. The theorem is that if a pointwise continuous function has both a negative and a positive value, then it has values arbitrarily close to 0. The proof builds on the usual classical proof by bisection, which repeatedly selects the left or right half of an interval; the algorithm here selects an interval of half the size in a continuous way, interpolating between those two possibilities. Read More


In this paper we propose a semantics in which the truth value of a formula is a pair of elements in a complete Boolean algebra. Through the semantics we can unify largely two proofs of cut-eliminability (Hauptsatz) in classical second order logic calculus, one is due to Takahashi-Prawitz and the other by Maehara. Read More


We continue the investigation of analytic spaces from the perspective of computable structure theory. We show that if $p \geq 1$ is a computable real, and if $\Omega$ is a nonzero, non-atomic, and separable measure space, then every computable presentation of $L^p(\Omega)$ is computably linearly isometric to the standard computable presentation of $L^p[0,1]$; in particular, $L^p[0,1]$ is computably categorical. We also show that there is a measure space $\Omega$ that does not have a computable presentation even though $L^p(\Omega)$ does for every computable real $p \geq 1$. Read More


In quantum logic there is well-known arbitrariness in choosing a binary operation for conditional. Currently, we have at least three candidates, called the Sasaki conditional, the contrapositive Sasaki conditional, and the relevance conditional. A fundamental problem is to show how the form of the conditional follows from an analysis of operational concepts in quantum theory. Read More


Assuming the existence of a Mahlo cardinal, we produce a generic extension of G\"{o}del's constructible universe $L$, in which the transfer principles $(\aleph_2, \aleph_0) \to (\aleph_3, \aleph_1)$ and $(\aleph_3, \aleph_1) \to (\aleph_2, \aleph_0)$ fail simultaneously. The result answers a question of Silver from 1971. We also extend our result to higher gaps. Read More


In this paper we investigate a connection between the growth rates of certain classes of finite structures and a generalization of $\text{VC}$-dimension called $\text{VC}_{\ell}$-dimension. Let $\mathcal{L}$ be a finite relational language with maximum arity $r$. A hereditary $\mathcal{L}$-property is a class of finite $\mathcal{L}$-structures closed under isomorphism and substructures. Read More


The main purpose of this paper is to study $e$-separable spaces, originally introduced by Kurepa as $K_0'$ spaces; a space $X$ is $e$-separable iff $X$ has a dense set which is the union of countably many closed discrete sets. We primarily focus on the behaviour of $e$-separable spaces under products and the cardinal invariants that are naturally related to $e$-separable spaces. Our main results show that the statement "the product of at most $\mathfrak c$ many $e$-separable spaces is $e$-separable" depends on the existence of certain large cardinals and hence independent of ZFC. Read More


We discuss such Maltsev conditions that consist of just one linear equation, we call them loop conditions. To every such condition can be assigned a graph. We provide a classification of conditions with undirected graphs. Read More


The TTE approach to Computable Analysis is the study of so-called representations (encodings for continuous objects such as reals, functions, and sets) with respect to the notions of computability they induce. A rich variety of such representations had been devised over the past decades, particularly regarding closed subsets of Euclidean space plus subclasses thereof (like compact subsets). In addition, they had been compared and classified with respect to both non-uniform computability of single sets and uniform computability of operators on sets. Read More


We define and study semilattices and lattices for $E$-closed families of theories. Properties of these semilattices and lattices are investigated. It is shown that lattices for families of theories with least generating sets are distributive. Read More


We define the notions of relative $e$-spectra, with respect to $E$-operators, relative closures, and relative generating sets. We study properties connected with relative $e$-spectra and relative generating sets. Read More


We consider and characterize classes of finite and countably categorical structures and their theories preserved under $E$-operators and $P$-operators. We describe $e$-spectra and families of finite cardinalities for structures belonging to closures with respect to $E$-operators and $P$-operators. Read More


We generalise M. M. Skriganov's notion of weak admissibility for lattices to include standard lattices occurring in Diophantine approximation and algebraic number theory, and we prove estimates for the number of lattice points in sets such as aligned boxes. Read More


We construct a universal action of a countable locally finite group on a separable metric space by isometries. This single action contains all actions of all countable locally finite groups on all separable metric spaces as subactions. The main ingredient is an amalgamation of actions by isometries. Read More


This short introduction to category theory is for readers with relatively little mathematical background. At its heart is the concept of a universal property, important throughout mathematics. After a chapter introducing the basic definitions, separate chapters present three ways of expressing universal properties: via adjoint functors, representable functors, and limits. Read More


In this paper, we correct some errors in [21]. We define a new realizability semantics for the simply typed $\lambda\mu$-calculus. We show that if a term is typable, then it inhabits the interpretation of its type. Read More


The aim of this contribution is to bring together the areas of $p$-adic analysis and nonstandard analysis. We develop a nonstandard measure theory with values in a complete non-Archimedean valued field $K$, e.g. Read More


This paper is devoted to understand groups definable in Presburger arithmetic. We prove the following theorems: Theorem 1. Every group definable in a model of Presburger Arithmetic is abelian- by-finite. Read More


A sceptical examination of the motivations for strong modal plural logics. Read More


Assuming the existence of a strong cardinal $\kappa$ and a measurable cardinal above it, we force a generic extension in which $\kappa$ is a singular strong limit cardinal of any prescribed cofinality, and such that the tree property holds at $\kappa^{++}$. Read More


We introduce a new game-theoretic approach to anti-classification results for orbit equivalence relations. Within this framework, we give a short conceptual proof of Hjorth's turbulence theorem. We also introduce a new dynamical criterion providing an obstruction to classification by orbits of CLI groups. Read More


Let $\Lambda $ be a countably infinite property (T) group, and let $A$ be UHF-algebra of infinite type. We prove that there exists a continuum of pairwise non (weakly) cocycle conjugate, strongly outer actions of $\Lambda $on $A$. The proof consists in assigning, to any second countable abelian pro-$p$ group $G$, a strongly outer action of $\Lambda $ on $A$ whose (weak) cocycle conjugacy class completely remembers the group $G$. Read More


A new $\theta$ arithmetic function is proposed that almost achieves the combined efficiency of the addition, multiplication and successor growth operations. These considerations lead us to conjecture that new boundary-case evasions of the Second Incompleteness Theorem exist, where an axiom system can have a limited-but-real appreciation of a fragment of its own Hilbert consistency. Apart from this conjecture, our new $\theta$ function primitive is interesting in its own right. Read More


We extend the Barvinok-Woods algorithm for enumeration of integer points in projections of polytopes to unbounded polyhedra. For this, we obtain a new structural result on projections of semilinear subsets of the integer lattice. We extend the results to general formulas in Presburger Arithmetic. Read More


How many permutations of the natural numbers are needed so that every conditionally convergent series of real numbers can be rearranged to no longer converge to the same sum? We show that the minimum number of permutations needed for this purpose, which we call the rearrangement number, is uncountable, but whether it equals the cardinal of the continuum is independent of the usual axioms of set theory. We compare the rearrangement number with several natural variants, for example one obtained by requiring the rearranged series to still converge but to a new, finite limit. We also compare the rearrangement number with several well-studied cardinal characteristics of the continuum. Read More


We prove several theorems relating amenability of groups in various categories (discrete, definable, topological, automorphism group) to model-theoretic invariants (quotients by connected components, Lascar Galois group, G-compactness, ... Read More


There exist two conjectures for constraint satisfaction problems (CSPs) of reducts of finitely bounded homogeneous structures: the first one states that tractability of the CSP of such a structure is, when the structure is a model-complete core, equivalent to its polymorphism clone satisfying a certain non-trivial linear identity modulo outer embeddings. The second conjecture, challenging the approach via model-complete cores by reflections, states that tractability is equivalent to the linear identities (without outer embeddings) satisfied by its polymorphisms clone, together with the natural uniformity on it, being non-trivial. We prove that the identities satisfied in the polymorphism clone of a structure allow for conclusions about the orbit growth of its automorphism group, and apply this to show that the two conjectures are equivalent. Read More


In this article, we will show that uncomputability is a relative property not only of oracle Turing machines, but also of subrecursive classes. We will define the concept of a Turing submachine, and a recursive relative version for the Busy Beaver function which we will call Busy Beaver Plus function. Therefore, we will prove that the computable Busy Beaver Plus function defined on any Turing submachine is not computable by any program running on this submachine. Read More


We study and extend the conditions for asociativity on fusion over antielement free $\sigma$-sets to introduce a group to solve $\sigma$-set equations. $\sigma$-sets as a theory of sets and antisets is sumarized and used as a framework to define the main elements of this work. A theorem on Local Asociativity, conmutative groups and solution of one variable fusion equation is presented. Read More


2016Dec

This issue surveys some of the activities in the field since the previous issue, and announces a conference fully dedicated to the topic of selection principles. Read More