11 found
Order:
  1.  47
    Notes on Polynomially Bounded Arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.
    We characterize the collapse of Buss' bounded arithmetic in terms of the provable collapse of the polynomial time hierarchy. We include also some general model-theoretical investigations on fragments of bounded arithmetic.
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark   35 citations  
  2.  84
    Computational Randomness and Lowness.Sebastiaan A. Terwijn & Domenico Zambella - 2001 - Journal of Symbolic Logic 66 (3):1199-1205.
    We prove that there are uncountably many sets that are low for the class of Schnorr random reals. We give a purely recursion theoretic characterization of these sets and show that they all have Turing degree incomparable to 0'. This contrasts with a result of Kučera and Terwijn [5] on sets that are low for the class of Martin-Löf random reals.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   21 citations  
  3.  11
    On the Proofs of Arithmetical Completeness for Interpretability Logic.Domenico Zambella - 1992 - Notre Dame Journal of Formal Logic 33 (4):542-551.
  4.  11
    End Extensions of Models of Linearly Bounded Arithmetic.Domenico Zambella - 1997 - Annals of Pure and Applied Logic 88 (2-3):263-277.
    We show that every model of IΔ0 has an end extension to a model of a theory where log-space computable function are formalizable. We also show the existence of an isomorphism between models of IΔ0 and models of linear arithmetic LA.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  5. A Note on Recursive Models of Set Theories.Domenico Zambella & Antonella Mancini - 2001 - Notre Dame Journal of Formal Logic 42 (2):109-115.
    We construct two recursive models of fragments of set theory. We also show that the fragments of Kripke-Platek set theory that prove -induction for -formulas have no recursive models but the standard model of the hereditarily finite sets.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  6.  10
    Elementary Classes of Finite VC-Dimension.Domenico Zambella - 2015 - Archive for Mathematical Logic 54 (5-6):511-520.
    Let be a saturated model of inaccessible cardinality, and let be arbitrary. Let denote the expansion of with a new predicate for. Write for the collection of subsets such that ≡. We prove that if the VC-dimension of is finite then is externally definable.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  7.  8
    The Real Truth.Stefano Baratella & Domenico Zambella - 2015 - Mathematical Logic Quarterly 61 (1-2):32-44.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  8.  7
    Ramsey’s Coheirs.Eugenio Colla & Domenico Zambella - 2022 - Journal of Symbolic Logic 87 (1):377-391.
    We use the model theoretic notion of coheir to give short proofs of old and new theorems in Ramsey Theory. As an illustration we start from Ramsey's theorem itself. Then we prove Hindman's theorem and the Hales-Jewett theorem. Finally, we prove the two Ramsey theoretic principles that have among their consequences partition theorems due to Carlson and to Gowers.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  9.  31
    Generic Expansions of Countable Models.Silvia Barbina & Domenico Zambella - 2012 - Notre Dame Journal of Formal Logic 53 (4):511-523.
    We compare two different notions of generic expansions of countable saturated structures. One kind of genericity is related to existential closure, and another is defined via topological properties and Baire category theory. The second type of genericity was first formulated by Truss for automorphisms. We work with a later generalization, due to Ivanov, to finite tuples of predicates and functions. Let $N$ be a countable saturated model of some complete theory $T$ , and let $(N,\sigma)$ denote an expansion of $N$ (...)
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark  
  10.  12
    Algebraic Methods and Bounded Formulas.Domenico Zambella - 1997 - Notre Dame Journal of Formal Logic 38 (1):37-48.
    We present some algebraic tools useful to the study of the expressive power of bounded formulas in second-order arithmetic (alternatively, second-order formulas in finite models). The techniques presented here come from Boolean circuit complexity and are adapted to the context of arithmetic. The purpose of this article is to expose them to a public with interests ranging from arithmetic to finite model theory. Our exposition is self-contained.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  11.  4
    Forcing in Finite Structures.Domenico Zambella - 1997 - Mathematical Logic Quarterly 43 (3):401-412.
    We present a simple and completely model-theoretical proof of a strengthening of a theorem of Ajtai: The independence of the pigeonhole principle from IΔ0. With regard to strength, the theorem proved here corresponds to the complexity/proof-theoretical results of [10] and [14], but a different combinatorics is used. Techniques inspired by Razborov [11] replace those derived from Håstad [8]. This leads to a much shorter and very direct construction.
    Direct download  
     
    Export citation  
     
    Bookmark   1 citation