Movatterモバイル変換

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   40 citations  

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   24 citations  

Direct download(4 more)   Export citation   Bookmark   8 citations  

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   8 citations  

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  

We study a real valued propositional logic with unbounded positive and negative truth values that we call ‐valued logic. Such a logic is semantically equivalent to continuous propositional logic, with a different choice of connectives. After presenting the deduction machinery and the semantics of ‐valued logic, we prove a completeness theorem for finite theories. Then we define unital and Archimedean theories, in accordance with the theory of Riesz spaces. In the unital setting, we prove the equivalence of consistency and satisfiability (...) and an approximated completeness theorem similar to the one that holds for continuous propositional logic. Eventually, among unital theories, we characterize Archimedean theories as those for which strong completeness holds. We also point out that ‐valued logic provides alternative calculi for Łukasiewicz logic and for propositional continuous logic. (shrink)

No categories

Direct download(4 more)   Export citation   Bookmark   1 citation  

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  

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$ (...) to the signature $L_{0}$ which is a model of some universal theory $T_{0}$ . We prove that when all existentially closed models of $T_{0}$ have the same existential theory, $(N,\sigma)$ is Truss generic if and only if $(N,\sigma)$ is an e-atomic model. When $T$ is $\omega$ -categorical and $T_{0}$ has a model companion $T_{\mathrm {mc}}$ , the e-atomic models are simply the atomic models of $T_{\mathrm {mc}}$. (shrink)

Direct download(8 more)   Export citation   Bookmark  

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  

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  

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(2 more)   Export citation   Bookmark   1 citation  

Direct download(7 more)   Export citation   Bookmark   1 citation