Mathematics - Logic Publications (50)

Search

Mathematics - Logic Publications

We introduce a generalization of the Cantor-Dedekind continuum with explicit infinitesimals. These infinitesimals are used as numbers obeying the same basic rules as the other elements of the generalized continuum, in accordance with Leibniz's original intuition, but with an important difference: their product is null, as the Dutch theologian Bernard Nieuwentijt sustained, against Leibniz's opinion. The starting-point is the concept of shadow, and from it we define indiscernibility (the central concept) and monad. Read More


A first order theory T is said to be "tight" if for any two deductively closed extensions U and V of T (both of which are formulated in the language of T), U and V are bi-interpretable iff U = V. By a theorem of Visser, PA (Peano Arithmetic) is tight. Here we show that Z_2 (second order arithmetic), ZF (Zermelo-Fraenkel set theory), and KM (Kelley-Morse theory of classes) are also tight theories. Read More


We show that every countable Borel equivalence relation structurable by $n$-dimensional contractible simplicial complexes embeds into one which is structurable by such complexes with the further property that each vertex belongs to at most $M_n := 2^{n-1}(n^2+3n+2)-2$ edges; this generalizes a result of Jackson-Kechris-Louveau in the case $n = 1$. The proof is based on that of a classical result of Whitehead on countable CW-complexes. Read More


We introduce split principles and show that their negations provide simple combinatorial characterizations of large cardinal properties. As examples, we show how inaccessiblity, weak compactness, subtlety, almost ineffability and ineffability can be characterized. Two-cardinal versions of these principles allow us to characterize when the two-cardinal versions of these properties hold: when $\kappa$ is almost $\lambda$-ineffable, $\lambda$-ineffable, and we can also characterize mild ineffability by a slightly modified version of the principle. Read More


A computable structure $\mathcal{A}$ is decidable if, given a formula $\varphi(\bar{x})$ of elementary first-order logic, and a tuple $\bar{a} \in \mathcal{A}$, we have a decision procedure to decide whether $\varphi$ holds of $\bar{a}$. We show that there is no reasonable classification of the decidably presentable structures. Formally, we show that the index set of the computable structures with decidable presentations is $\Sigma^1_1$-complete. Read More


The class of abelian $p$-groups are an example of some very interesting phenomena in computable structure theory. We will give an elementary first-order theory $T_p$ whose models are each bi-interpretable with the disjoint union of an abelian $p$-group and a pure set (and so that every abelian $p$-group is bi-interpretable with a model of $T_p$) using computable infinitary formulas. This answers a question of Knight by giving an example of an elementary first-order theory of "Ulm type": Any two models, low for $\omega_1^{CK}$, and with the same computable infinitary theory, are isomorphic. Read More


We investigate the connections between computability theory and Nonstandard Analysis. In particular, we investigate the two following topics and show that they are intimately related. (T. Read More


We define a notion of residue field domination for valued fields which generalizes stable domination in algebraically closed valued fields. We prove that a real closed valued field is dominated by the sorts internal to the residue field, over the value group, both in the pure field sort and in the geometric sorts. These results characterize forking and \th-forking in real closed valued fields (and also algebraically closed valued fields). Read More


Scott showed that for every countable structure $\mathcal{A}$, there is a sentence of the infinitary logic $\mathcal{L}_{\omega_1\omega}$, called a Scott sentence for $\mathcal{A}$, whose models are exactly the isomorphic copies of $\mathcal{A}$. Thus, the least quantifier complexity of a Scott sentence of a structure is an invariant that measures the complexity "describing" the structure. Knight et al. Read More


The aim of this article is to obtain a characterization of the canonical extension of Boolean homomorphisms via the Stone-\v{C}ech compactification. Read More


We introduce the notion of positive local combinatorial dividing-lines in model theory. We show these are equivalently characterized by indecomposable algebraically trivial Fraisse classes and by complete prime filter classes. We exhibit the relationship between this and collapse-of-indiscernibles dividing-lines. Read More


It is well known that strongly minimal groups are commutative. Whether this is true for various generalisations of strong minimality has been asked in several different settings (see Hyttinen [2002], Maesono [2007], Pillay and Tanovi\'c [2011]). In this note we show that the answer is positive for groups with locally modular homogeneous pregeometries. Read More


A complete first-order theory is equational if every definable set is a Boolean combination of instances of equations, that is, of formulae such that the family of finite intersections of instances has the descending chain condition. Equationality is a strengthening of stability. In this short note, we prove that theory of proper extension of algebraically closed fields of some fixed characteristic is equational. Read More


We show that a reduct of the Zariski structure of an algebraic curve which is not locally modular interprets a field, answering a question of Zilber's. Read More


In the article 'Ordinal Logics and the Characterizations of the Informal Concept of Proof', Georg Kreisel poses the problem of assigning unique notations to recursive ordinals, and additionally suggests that the methods which are developed for its solution will be non-constructive in character. In this paper we develop methods in which various uniqueness results for notations of recursive ordinals can be obtained, and thereafter apply these results to investigate the problems surrounding the hierarchical classification of the computable functions. Read More


Motivated by showing that in ZFC we cannot construct a special Aronszajn tree on some cardinal greater than $\aleph_1$, we produce a model in which the approachability property fails (hence there are no special Aronszajn trees) at all regular cardinals in the interval $[\aleph_2, \aleph_{\omega^2+3}]$ and $\aleph_{\omega^2}$ is strong limit. Read More


We prove a triangulation theorem for semi-algebraic sets over a p-adically closed field, quite similar to its real counterpart. We derive from it several applications like the existence of flexible retractions and splitting for semi-algebraic sets. Read More


In \cite{PalSk}, Palacin and Sklinos show that the structure $(\mathbf{Z},+,0,R)$ is superstable of $U$-rank $\omega$ when $R$ is either the set of powers of some fixed natural number greater or equal to $2$ or a sequence $(r_n)$ of natural numbers such that $r_{n+1}/r_n\to\infty$. In this paper, we generalize this result to the class of sparse sequences (as defined by Sem\"enov) that includes sequences $(r_n)$ given by a recurrence relation for which there exists $\theta>1$ such that $r_n/\theta^n$ has a positive limit and such that the minimal polynomial of $\theta$ is the characteristic polynomial of $(r_n)$. We axiomatize for such sequences the structure $(\mathbf{Z},+,0,R,S)$ and prove quantifier elimination in a reasonable language. Read More


We investigate the extension of Monadic Second Order logic, interpreted over infinite words and trees, with generalized "for almost all" quantifiers interpreted using the notions of Baire category and Lebesgue measure. Read More


Let $G$ be the group $\mathbb{Z}^d$ or the monoid $\mathbb{N}^d$ where $d$ is a positive integer. Let $X$ be a subshift over $G$, i.e. Read More


We introduce axiomatically a Nonarchimedean field E, called the field of the Euclidean numbers, where a transfinite sum is defined that is indicized by ordinal numbers less than the first inaccessible {\Omega}. Thanks to this sum, E becomes a saturated hyperreal field isomorphic to the so called Kiesler field of cardinality {\Omega}, and suitable topologies can be put on E and on {\Omega} \cup {{\Omega}} so as to obtain the transfinite sums as limits of a suitable class of their finite subsums. Moreover there is a natural isomorphic embedding into E of the semiring {\Omega} equipped by the natural sum and product. Read More


Thicket density is a new measure of the complexity of a set system, having the same relationship to stable formulas that VC density has to NIP formulas. It has a dichotomy analogous to the Sauer-Shelah result that has applications in both model theory (to the Erd\H{o}s-Hajnal Property for stable graphs) and computability theory (to the separation between recursion and iteration over a particular structure). Read More


We study NSOP$_{1}$ theories. We define Kim-independence, which generalizes non-forking independence in simple theories and corresponds to non-forking at a generic scale. We show that Kim-independence satisfies a version of Kim's lemma, local character, symmetry, and an independence theorem and that, moreover, these properties individually characterize NSOP$_{1}$ theories. Read More


We show that the closed ordinal Ramsey number $R^{cl}(\omega\cdot 2,3)^2$ is equal to $\omega^3\cdot 2$. Read More


The liar paradox is widely seen as not a serious problem. I try to explain why this view is mistaken. Read More


Working in the framework of Borel reducibility, we study various notions of embeddability between groups. We prove that the embeddability between countable groups, the topological embeddability between (discrete) Polish groups, and the isometric embeddability between separable groups with a bounded bi-invariant complete metric are all invariantly universal analytic quasi-orders. This strengthens some results from [Wil14] and [FLR09]. Read More


We make use of a finite support product of $\omega_1$ clones of the Jensen minimal $\varPi^1_2$ singleton forcing to obtain a model of ZFC in which every non-empty lightface analytically definable set of reals contains a lightface analytically definable real (the full basis theorem), but there is no analytically definable wellordering of the continuum. Read More


We present a novel, perspicuous framework for building iterated ultrapowers. Our framework naturally lends itself to the construction of a certain type of indiscernibles, here dubbed $\textit{tight indiscernibles}$, which are shown to provide smooth proofs of the following results: $\textbf{Theorem.}$ Suppose $\mathcal{M=(}M,. Read More


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


We introduce the forcing model of IZFA (Intuitionistic Zermelo-Fraenkel set theory with Atoms) for every Grothendieck topology and prove that the topos of sheaves on every site is equivalent to the category of 'sets in this forcing model'. Read More


Affine $$\lambda$$-terms are $$\lambda$$-terms in which each bound variable occurs at most once and linear $$\lambda$$-terms are $$\lambda$$-terms in which each bound variables occurs once. and only once. In this paper we count the number of closed affine $$\lambda$$-terms of size $n$, closed linear $$\lambda$$-terms of size $n$, affine $$\beta$$-normal forms of size $n$ and linear $$\beta$$-normal forms of ise $n$, for different ways of measuring the size of $$\lambda$$-terms. Read More


For a complete lattice $L$ and a relational structure $\mathfrak{X}=(X,(R_i)_I)$, we introduce the convolution algebra $L^{\mathfrak{X}}$. This algebra consists of the lattice $L^X$ equipped with an additional $n_i$-ary operation $f_i$ for each $n_i+1$-ary relation $R_i$ of $\mathfrak{X}$. For $\alpha_1,\ldots,\alpha_{n_i}\in L^X$ and $x\in X$ we set $f_i(\alpha_1,\ldots,\alpha_{n_i})(x)=\bigvee\{\alpha_1(x_1)\wedge\cdots\wedge\alpha_{n_i}(x_{n_i}):(x_1,\ldots,x_{n_i},x)\in R_i\}$. Read More


Gao, Jackson, and Seward (see arXiv:1201.0513) proved that every countably infinite group $\Gamma$ admits a nonempty free subshift $X \subseteq \{0,1\}^\Gamma$. Furthermore, a theorem of Seward and Tucker-Drob (see arXiv:1402. Read More


We consider Fra\"iss\'e structures whose objects have finite big Ramsey degree and ask what consequences this has for the dynamics of the automorphism group. Motivated by a theorem of D. Devlin about the partition properties of the rationals, we define the notion of a big Ramsey structure, a single structure which codes the big Ramsey degrees of a given Fra\"iss\'e structure. Read More


Topological Ramsey spaces are spaces which support infinite dimensional Ramsey theory similarly to the Ellentuck space. Each topological Ramsey space is endowed with a partial ordering which can be modified to a $\sigma$-closed `almost reduction' relation analogously to the partial ordering of `mod finite' on $[\omega]^{\omega}$. Such forcings add new ultrafilters satisfying weak partition relations and have complete combinatorics. Read More


We here aim to complete our model-theoretic account of the function field Mordell-Lang conjecture, avoiding appeal to dichotomy theorems for Zariski geometries, where we now consider the general case of semiabelian varieties. The main result is a reduction, using model-theoretic tools, of the semiabelian case to the abelian case. Read More


A set $A$ of integers is called total if there is an algorithm which, given an enumeration of $A$, enumerates the complement of $A$, and called cototal if there is an algorithm which, given an enumeration of the complement of $A$, enumerates $A$. Many variants of totality and cototality have been studied in computability theory. In this note, by an effective forcing construction with strongly infinite dimensional Cantor manifolds, which can be viewed as an effectivization of Zapletal's "half-Cohen" forcing (i. Read More


We show that the enveloping space $X_G$ of a partial action of a Polish group $G$ on a Polish space $X$ is a standard Borel space, that is to say, there is a topology $\tau$ on $X_G$ such that $(X_G, \tau)$ is Polish and the quotient Borel structure on $X_G$ is equal to $Borel(X_G,\tau)$. To prove this result we show a generalization of a theorem of Burgess about Borel selectors for the orbit equivalence relation induced by a group action and also show that some properties of the Vaught's transform are valid for partial actions of groups. Read More


Proof schemata are a variant of LK-proofs able to simulate various induction schemes in first-order logic by adding so called proof links to the standard first-order LK-calculus. Proof links allow proofs to reference proofs thus giving proof schemata a recursive structure. Unfortunately, applying reductive cut- elimination is non-trivial in the presence of proof links. Read More


In their 2015 paper, Mertens and Rolen prove that for a certain level 6 "almost holomorphic" modular function $P$, the degree of $P(\tau)$ over $\mathbb{Q}$ for quadratic $\tau$ is as large as expected, settling a conjecture of Bruinier and Ono. Analogously for level 1 modular functions $f$, we expect $\mathbb{Q}(f(\tau))$ to have similar degree to $\mathbb{Q}(j(\tau))$. In this paper, I show for a wide class of level 1 almost holomorphic modular functions that \[\dfrac{1}{M}[\mathbb{Q}(j(\tau)):\mathbb{Q}]\leq [\mathbb{Q}(f(\tau)):\mathbb{Q}]\leq[\mathbb{Q}(j(\tau)):\mathbb{Q}]\] for all quadratic $\tau$ and some constant $M$. Read More


Let $\mathbb{M}$ be the monster model of a complete first-order theory $T$. If $\mathbb{D}$ is a subset of $\mathbb{M}$, following D. Zambella we consider $e(\mathbb{D})=\{\mathbb{D}^\prime\mid (\mathbb{M},\mathbb{D})\equiv (\mathbb{M},\mathbb{D}^\prime)\}$ and $o(\mathbb{D})=\{\mathbb{D}^\prime\mid (\mathbb{M},\mathbb{D})\cong (\mathbb{M},\mathbb{D}^\prime)\}$. Read More


The existence of least finite support is used throughout the subject of nominal sets. In this paper we give some Brouwerian counterexamples showing that constructively, least finite support does not always exist and in fact can be quite badly behaved. On this basis we reinforce the point that when working constructively with nominal sets the use of least finite support should be avoided. Read More


We show that Keisler's order is not linear, assuming the existence of a supercompact cardinal. Read More


Every crowded space $X$ is ${\omega}$-resolvable in the c.c.c generic extension $V^{Fn(|X|,2})$ of the ground model. Read More


We study pairs $(V, V_1)$ of models of $ZFC$ such that adding $\kappa$-many random reals over $V_1$ adds $\lambda$-many random reals over $V$, for some $\lambda > \kappa.$ Read More


We give a syntactic proof of the assertoric equipollence of the intuitionistic propositional calculus and the proof-intuitionistic calculus KM (Kuznetsov's Theorem). Then, we show that this property is true for a wide class of modal logics on an intuitionistic basis, which includes, e.g. Read More


We consider the covering map $\pi:\mathbb{C}^n\to \mathbb{T}$ of a compact complex torus. Given an algebraic variety $X\subseteq \mathbb{C}^n$ we describe the topological closure of $\pi(X)$ in $\mathbb T$. We obtain a similar description when $\mathbb{T}$ is a real torus and $X\subseteq \mathbb{R}^n$ is a set definable in an o-minimal structure over the reals. Read More


We study to what extent torsion-free (Gromov)-hyperbolic groups are elementarily equivalent to their finite index subgroups. In particular, we prove that a hyperbolic limit group either is a free product of cyclic groups and surface groups, or admits infinitely many subgroups of finite index which are pairwise non elementarily equivalent. Read More


We determine the sets definable in expansions of the ordered real additive group by generalized Cantor sets. Given a natural number $r\geq 3$, we say a set $C$ is a generalized Cantor set in base $r$ if there is a non-empty $K\subseteq\{1,\ldots,r-2\}$ such that $C$ is the set of those numbers in $[0,1]$ that admit a base $r$ expansion omitting the digits in $K$. While it is known that the theory of an expansion of the ordered real additive group by a single generalized Cantor set is decidable, we establish that the theory of an expansion by two generalized Cantor sets in multiplicatively independent bases is undecidable. Read More