Mathematics - Logic Publications (50)


Mathematics - Logic Publications

We extend Solovay's theorem about definable subsets of the Baire space to the generalized Baire space ${}^\lambda\lambda$, where $\lambda$ is an uncountable cardinal with $\lambda^{<\lambda}=\lambda$. In the first main theorem, we show that that the perfect set property for all subsets of ${}^{\lambda}\lambda$ that are definable from elements of ${}^\lambda\mathrm{Ord}$ is consistent relative to the existence of an inaccessible cardinal above $\lambda$. In the second main theorem, we introduce a Banach-Mazur type game of length $\lambda$ and show that the determinacy of this game, for all subsets of ${}^\lambda\lambda$ that are definable from elements of ${}^\lambda\mathrm{Ord}$ as winning conditions, is consistent relative to the existence of an inaccessible cardinal above $\lambda$. Read More

If $(X,d)$ is a Polish metric space of dimension $0$, then by Wadge's lemma, no more than two Borel subsets of $X$ can be incomparable with respect to continuous reducibility. In contrast, our main result shows that for any metric space $(X,d)$ of positive dimension, there are uncountably many Borel subsets of $(X,d)$ that are pairwise incomparable with respect to continuous reducibility. The reducibility that is given by the collection of continuous functions on a topological space $(X,\tau)$ is called the \emph{Wadge quasi-order} for $(X,\tau)$. Read More

In the seminal work "Pomset logic: A noncommutative extension of classical linear logic" Retor\'e introduced Pomset logic, an extension of linear logic with a self-dual noncommutative connective. Pomset logic is defined by means of proof-nets, later a deep inference system BV was designed for this extension, but equivalence of system has not been proven up to now. As for a sequent calculus formulation, it has not been known for either of these logics, and there are convincing arguments that such a sequent calculus in the usual sense simply does not exist for them. Read More

It is known that semigroups are Ramsey algebras. This paper is an attempt to understand the role associativity plays in a binary system being a Ramsey algebra. Specifically, we show that the nonassociative Moufang loop of octonions is not a Ramsey algebra. Read More

We consider graph Turing machines, a model of parallel computation on a graph, in which each vertex is only capable of performing one of a finite number of operations. This model of computation is a natural generalization of several well-studied notions of computation, including ordinary Turing machines, cellular automata, and parallel graph dynamical systems. We analyze the power of computations that can take place in this model, both in terms of the degrees of computability of the functions that can be computed, and the time and space resources needed to carry out these computations. Read More

Strictly positive logics recently attracted attention both in the description logic and in the provability logic communities for their combination of efficiency and sufficient expressivity. The language of Reflection Calculus RC consists of implications between formulas built up from propositional variables and constant `true' using only conjunction and diamond modalities which are interpreted in Peano arithmetic as restricted uniform reflection principles. We extend the language of RC by another series of modalities representing the operators associating with a given arithmetical theory T its fragment axiomatized by all theorems of T of arithmetical complexity $\Pi^0_n$, for all n>0. Read More

In 2014, Pila and Tsimerman gave a proof of the Ax-Schanuel conjecture for the $j$-function and, with Mok, have recently announced a proof of its generalization to any (pure) Shimura variety. We refer to this generalization as the hyperbolic Ax-Schanuel conjecture. In this article, we seek to generalize the ideas of Habegger and Pila to show that, under a number of arithmetic hypotheses, the hyperbolic Ax-Schanuel conjecture can faciltate an extension of the Pila-Zannier strategy to the Zilber-Pink conjecture for Shimura varieties. Read More

Here we define the notion of residually null sets, a $\sigma$-ideal of subsets of a Polish space which contains the meager sets and, in some contexts, generalizes the notion of universally null. From this $\sigma$-ideal we realize a $\sigma$-algebra of sets which is consistently a strict extension of the Baire property algebra. We then uncover a generalization to Pettis' Theorem which furnishes a new automatic continuity result. Read More

In this short note, using results of Bourgain, Fremlin, and Talagrand \cite{BFT}, we show that for a countable structure $M$ and a formula $\phi(x,y)$ the following are equivalent: (i) $\phi(x,y)$ has NIP on $M$ (see Definition~\ref{NIP-formula} below). (ii) For every net $(a_i)_{i\in I}$ of elements of $M$ and a saturated elementary extension $M^*$ of $M$, if $tp_\phi(a_i/M^*)\to p'$, then the type $p'$ is Baire 1 definable over $M$. This implies, as it is well known, that if $\phi$ is NIP then every global $M$-invariant $\phi$-type is Baire 1 definable over $M$. Read More

Yorioka [J. Symbolic Logic 67(4):1373-1384, 2002] introduced a class of ideals (parametrized by reals) on the Cantor space to prove that the relation between the size of the continuum and the cofinality of the strong measure zero ideal on the real line cannot be decided in ZFC. We construct a matrix iteration of ccc posets to force that, for many ideals in that class, their associated cardinal invariants (i. Read More

We study definably compact definably connected groups definable in a sufficiently saturated real closed field $R$. We introduce the notion of group-generic point for $\bigvee$-definable groups and show the existence of group-generic points for definably compact groups definable in a sufficiently saturated o-minimal expansion of a real closed field. We use this notion along with some properties of generic sets to prove that for every definably compact definably connected group $G$ definable in $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. Read More

In this paper, we prove first-order definability of the ground ring of integers, inside a polynomial ring with coefficients in a reduced indecomposable (commutative, unital) ring, provided the definability of a suitable subset of the constants. This extends a result, that has long been known to hold for integral domains (Robinson, 1952, Denef 1978) to a wider class of coefficient rings. We also provide an example of such a coefficient ring, which is not a domain, for which the requirement of having a definable subset is actually met. Read More

Every transformation monoid comes equipped with a canonical topology-the topology of pointwise convergence. For some structures, the topology of the endomorphism monoid can be reconstructed from its underlying abstract monoid. This phenomenon is called automatic homeomorphicity. Read More

We study an infinite countable iteration of the natural product between ordinals. We present an "effective" way to compute this countable natural product; in the non trivial cases, the result depends only on the natural sum of the degrees of the factors, where the degree of a nonzero ordinal is the largest exponent in its Cantor normal form representation. Thus we are able to lift former results about infinitary sums to infinitary products. Read More

Recent results of Hindman, Leader and Strauss and of Fern\'andez-Bret\'on and Rinot showed that natural versions of Hindman's Theorem fail {\em for all} uncontable cardinals. On the other hand, Komj\'ath proved a result in the positive direction, showing that {\em there are} arbitrarily large abelian groups satisfying {\em some} Hindman-type property. In this note we show how a family of natural Hindman-type theorems for uncountable cardinals can be obtained by adapting some recent results of the author from their original countable setting. Read More

We show that the class of finite groups with n automorphisms has the amalgamation property for every n. Consequently, the automorphism group of Philip Hall's universal locally finite group has ample generics, that is, it admits comeager diagonal conjugacy classes in all dimensions. Read More

We are concerned with two separation theorems about analytic sets by Dyck and Preiss, the former involves the positively-defined subsets of the Cantor space and the latter the Borel-convex subsets of finite dimensional Banach spaces. We show by introducing the corresponding separation trees that both of these results admit a constructive proof. This enables us to give the uniform version of the separation theorems, and derive as corollaries the results, which are analogous to the fundamental fact "HYP is effectively bi-analytic" provided by the Souslin-Kleene Theorem. Read More

We identify multirole logic as a new form of logic in which conjunction/disjunction is interpreted as an ultrafilter on the power set of some underlying set (of roles) and the notion of negation is generalized to endomorphisms on this underlying set. We formalize both multirole logic (MRL) and linear multirole logic (LMRL) as natural generalizations of classical logic (CL) and classical linear logic (CLL), respectively, and also present a filter-based interpretation for intuitionism in multirole logic. Among various meta-properties established for MRL and LMRL, we obtain one named multiparty cut-elimination stating that every cut involving one or more sequents (as a generalization of a (binary) cut involving exactly two sequents) can be eliminated, thus extending the celebrated result of cut-elimination by Gentzen. Read More

In Alm-Hirsch-Maddux (2016), relation algebras $\mathfrak{L}(q,n)$ were defined that generalize Roger Lyndon's relation algebras from projective lines, so that $\mathfrak{L}(q,0)$ is a Lyndon algebra. In that paper, it was shown that if $q>2304n^2+1$, $\mathfrak{L}(q,n)$ is representable, and if $q<2n$, $\mathfrak{L}(q,n)$ is not representable. In the present paper, we reduced this gap by proving that if $q\geq n(\log n)^{1+\varepsilon}$, $\mathfrak{L}(q,n)$ is representable. Read More

We further investigate a divisibility relation on the set $\beta N$ of ultrafilters on the set of natural numbers. We single out prime ultrafilters (divisible only by 1 and themselves) and establish a hierarchy in which a position of every ultrafilter depends on the set of prime ultrafilters it is divisible by. We also construct ultrafilters with many immediate successors in this hierarchy and find positions of products of ultrafilters. Read More

Since it was realized that the Curry-Howard isomorphism can be extended to the case of classical logic as well, several calculi has appeared as candidates for the encodings of proofs in classical logic. One of them was the $\lambda\mu$-calculus of Parigot ([19]). In this paper, following the reasoning of Xi presented for the $\l$-calculus ([27]), we give an upper bound for the lengths of reductions in the $\lambda\mu$-calculus extended with two more simplification rules: the $\rho$- and $\theta$-rules. Read More

These are notes of a series of talks about motivic integration I gave on the M\"unster Model Theory Month. Readers are assumed to have some basic knowledge of model theory and of valued fields. The notes are closest to the Cluckers-Loeser style of motivic integration, though mostly they are about doing p-adic integration uniformly in all $\mathbb{Q}_p$. Read More

As mathematical induction is applied to prove statements on natural numbers, {\it continuous induction} (or, {\it real induction}) is a tool to prove some statements in real analysis.(Although, this comparison is somehow an overstatement.) Here, we first consider it on densely ordered abelian groups to prove Heine-Borel theorem (every closed and bounded interval is compact with respect to order topology) in those structures. Read More

We use countable metric spaces to code Polish metric spaces and evaluate the complexity of some statements about these codes and of some relations that can be determined by the codes. Also, we propose a coding for continuous functions between Polish metric spaces. Read More

This note is a commentary on the model-theoretic interpretation of Grothendieck's double limit characterization of weak relative compactness. Read More

We introduce the Dichotomy Property, a new property of some languages in Set Computable Theory, in order to explore the expressivity of some languages which are extensions of MLS. By-product we prove undecidability of MLS extended with not ordered cartesian product and disjoint unary union operators. Read More

We introduce a combinatorial criterion for verifying whether a formula is not the conjunction of an equation and a co-equation. Using this, we give a transparent proof for the nonequationality of the free group, which was originally proved by Sela. Furthermore, we extend this result to arbitrary free products of groups (except $\mathbb{Z}_2*\mathbb{Z}_2$), providing an abundance of new stable nonequational theories. Read More

This note contains additions to the paper 'Clustered cell decomposition in P-minimal structures' (arXiv:1612.02683). We discuss a question which was raised in that paper, on the order of clustered cells. Read More

A metric algebra is a metric variant of the notion of $\Sigma$-algebra, first introduced in universal algebra to deal with algebras equipped with metric structures such as normed vector spaces. In this paper, we showed metric versions of the variety theorem, which characterizes strict varieties (classes of metric algebras defined by metric equations) and continuous varieties (classes defined by a continuous family of basic quantitative inferences) by means of closure properties. To this aim, we introduce the notion of congruential pseudometric on a metric algebra, which corresponds to congruence in classical universal algebra, and we investigate its structure. Read More

We develop first-order logic and some extensions for incomplete information scenarios and consider related complexity issues. Read More

We study upper bounds, approximations, and limits for functions of motivic exponential class, uniformly in non-Archimedean local fields whose characteristic is $0$ or sufficiently large. Our results together form a flexible framework for doing analysis over local fields in a field-independent way. As corollaries, we obtain many new transfer principles, for example, for local constancy, continuity, and existence of various kinds of limits. Read More

In this short note, we mimic the proof of the simplicity of the theory ACFA of generic difference fields in order to provide a criterion, valid for certain theories of pure fields and fields equipped with operators, which shows that a complete theory is simple whenever its definable and algebraic closures are controlled by an underlying stable theory. Read More

In this paper we study selected argument forms involving counterfactuals and indicative conditionals under uncertainty. We selected argument forms to explore whether people with an Eastern cultural background reason differently about conditionals compared to Westerners, because of the differences in the location of negations. In a 2x2 between-participants design, 63 Japanese university students were allocated to four groups, crossing indicative conditionals and counterfactuals, and each presented in two random task orders. Read More

We present a formal measure of argument strength, which combines the ideas that conclusions of strong arguments are (i) highly probable and (ii) their uncertainty is relatively precise. Likewise, arguments are weak when their conclusion probability is low or when it is highly imprecise. We show how the proposed measure provides a new model of the Ellsberg paradox. Read More

This is an introduction to type theory, synthetic topology, and homotopy type theory from a category-theoretic and topological point of view, written as a chapter for the book "New Spaces for Mathematics and Physics" (ed. Gabriel Catren and Mathieu Anel). Read More

We present a description of the (non-modular) commutator, inspired by that of Kearnes in~\cite[p.~930]{MR1358491}, that provides a simple recipe for computing the commutator. Read More

Every real is computable from a Martin-Loef random real. This well known result in algorithmic randomness was proved by Kucera and Gacs. In this survey article we discuss various approaches to the problem of coding an arbitrary real into a Martin-Loef random real,and also describe new results concerning optimal methods of coding. Read More

We investigate the structure of fixed point sets of self-embeddings of models of arithmetic. In particular, given a countable nonstandard model M of a modest fragment of Peano arithimetic, we provide complete characterizations of (a) the initial segments of M that can be realized as the longest initial segment of fixed points of a nontrivial self-embedding of M onto a proper initial segment of M; and (b) the initial segments of M that can be realized as the fixed point set of some nontrivial self-embedding of M onto a proper initial segement of M. Moreover, we demonstrate the the standard cut is strong in M iff there is a self-embedding of M onto a proper initial segment of itself that moves every element that is not definable in M by an existential formula. Read More

Iterated reflection principles have been employed extensively to unfold epistemic commitments that are incurred by accepting a mathematical theory. Recently this has been applied to theories of truth. The idea is to start with a collection of Tarski-biconditionals and arrive by finitely iterated reflection at strong compositional truth theories. Read More

Graph polynomials are graph parameters invariant under graph isomorphisms which take values in a polynomial ring with a fixed finite number of indeterminates. We study graph polynomials from a model theoretic point of view. In this paper we distinguish between the graph theoretic (semantic) and the algebraic (syntactic) meaning of graph polynomials. Read More

Bi-Intuitionistic Stable Tense Logics (BIST Logics) are tense logics with a Kripke semantics where worlds in a frame are equipped with a pre-order as well as with an accessibility relation which is 'stable' with respect to this pre-order. BIST logics are extensions of a logic, BiSKt, which arose in the semantic context of hypergraphs, since a special case of the pre-order can represent the incidence structure of a hypergraph. In this paper we provide, for the first time, a Hilbert-style axiomatisation of BISKt and prove the strong completeness of BiSKt. Read More

We prove that after adding a Silver real no ultrafilter from the ground model can be extended to a P-point, and this remains to be the case in any further extension which has the Sacks property. We conclude that there are no P-points in the Silver model. In particular, it is possible to construct a model without P-points by iterating Borel partial orders. Read More

We show that \'Ecalle's transseries and their variants (LE and EL-series) can be interpreted as functions from positive infinite surreal numbers to surreal numbers. The same holds for a much larger class of formal series, here called omega-series. Omega-series are the smallest subfield of the surreal numbers containing the reals, the ordinal omega, and closed under the exp and log functions and all possible infinite sums. Read More

We show there is a closed (in fact effectively closed, i.e., $\Pi^0_1$) eventually different family (working in ZF or less). Read More

Authors: Frank Wagner1
Affiliations: 1ICJ

There is no bad group of Morley rank 2n+1 with an abelian Borel subgroup of Morley rank n. In particular, there is no bad group of Morley rank 3 (O. Fr{\'e}con). Read More

Cost functions provide a framework for constructions of sets Turing below the halting problem that are close to computable. We carry out a systematic study of cost functions. We relate their algebraic properties to their expressive strength. Read More

This year's logic blog contains a variety of results, some of them available only here. Highlights include the resolution of the Gamma question by Monin, and a number of entries on topological group theory and its connection to logic. There's also a new proof by Yu of Harrington's 1978 result that a Pi-11 set of hyperdegrees with a perfect subset contains an upper cone. Read More

The class of uniformly computable real functions with respect to a small subrecursive class of operators computes the elementary functions of calculus, restricted to compact subsets of their domains. The class of conditionally computable real functions with respect to the same class of operators is a proper extension of the class of uniformly computable real functions and it computes the elementary functions of calculus on their whole domains. The definition of both classes relies on certain transformations of infinitistic names of real numbers. Read More

We investigate a theory of models equipped which an action of a fixed group G. We show that under the assumption of stability of the basic theory (and few other assumptions) the arising model companion of the theory of models equipped with an action of G is simple and eliminates quantifiers up to some existential formulas - similar to ACFA. Moreover, it codes finite sets and allows geometric elimination of imaginaries, but not always weak elimination of imaginaries. Read More