A list of arithmetical structures complete with respect to the first-order definability

DOI10.1016/S0304-3975(00)00113-4zbMath0971.03035OpenAlexW2033524652WikidataQ127662677 ScholiaQ127662677MaRDI QIDQ5941257

Ivan Korec

Publication date: 20 August 2001

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(00)00113-4

zbMATH Keywords

arithmetical structureelementary definabilityfirst-order definabilityPascal's triangles modulo \(n\)undecidable theories

Mathematics Subject Classification ID

Binomial coefficients; factorials; (q)-identities (11B65) Decidability (number-theoretic aspects) (11U05) Classical first-order logic (03B10) Decidability of theories and sets of sentences (03B25) Basic properties of first-order languages and structures (03C07)

Related Items

Some new results in monadic second-order arithmetic, Computational complexity of logical theories of one successor and another unary function, A note on definability in fragments of arithmetic with free unary predicates, The theory of ceers computes true arithmetic, The lattice of definability: origins, recent developments, and further directions, DECIDABILITY AND CLASSIFICATION OF THE THEORY OF INTEGERS WITH PRIMES, On arithmetical first-order theories allowing encoding and decoding of lists, Decidability of the theory of the natural integers with the Cantor pairing function and the successor, INTERPRETING ARITHMETIC IN THE FIRST-ORDER THEORY OF ADDITION AND COPRIMALITY OF POLYNOMIAL RINGS

Cites Work

• The elementary theory of the natural lattice is finitely axiomatizable
• Twins problem in formal arithmetic
• Logically defined subsets of \(\mathbb{N}{}^ k\)
• Complexity of logical theories involving coprimality
• The theory of \(\langle \mathbb{N} , +, V_ k, V_ l\rangle\) is undecidable
• The theory of successor with an extra predicate
• Büchi's monadic second order successor arithmetic.
• Presburgerness of predicates regular in two number systems
• On Pascal triangles modulo a prime power
• Theories of generalized Pascal triangles
• Definability, decidability, complexity
• Contribution à l'étude d'une conjecture de théorie des nombres par le codage ZBV. (Contribution to the study of a conjecture of number theory by ZBV coding)
• Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theorems
• Solvability of the theory of integers with addition, order, and multiplication by an arbitrary number
• All arithmetical sets of powers of primes are first-order definable in terms of the successor function and the coprimeness predicate
• The elementary theory of finite fields
• Decidability and undecidability of theories with a predicate for the primes
• Decidability and essential undecidability
• Elementary Properties of Ordered Abelian Groups
• Weak Second‐Order Arithmetic and Finite Automata
• Definability in terms of the successor function and the coprimeness predicate in the set of arbitrary integers
• Answer to a problem raised by J. Robinson: The arithmetic of positive or negative integers is definable from successor and divisibility
• Decision Problems of Finite Automata Design and Related Arithmetics
• An Infinite Product for e
• On the bounded monadic theory of well-ordered structures
• ON CERTAIN EXTENSIONS OF THE ARITHMETIC OF ADDITION OF NATURAL NUMBERS
• A combinatorial approach to the theory of ω-automata
• Notes on Binomial Coefficients Iii-Any Integer Divides Almost All Binomial Coefficients†
• Model-interpretability into trees and applications
• A note on undecidable extensions of monadic second order successor arithmetic
• Completeness Theorems, Incompleteness Theorems and Models of Arithmetic
• Undecidable extensions of Skolem arithmetic
• Undecidable extensions of Büchi arithmetic and Cobham-Semënov Theorem
• More on an undecidability result of Bateman, Jockusch and Woods
• Definability in structures of finite valency
• Definability and decidability issues in extensions of the integers with the divisibility predicate
• Decidability and undecidability of extensions of second (first) order theory of (generalized) successor
• On the base-dependence of sets of numbers recognizable by finite automata
• Definability in the monadic second-order theory of successor
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Uniform tag sequences
• Definability and decision problems in arithmetic
• A reduction in the number of primitive ideas of arithmetic
• On direct products of theories
• Existential Definability in Arithmetic
• Concatenation as a basis for arithmetic
• Decidability of the theory of the natural integers with the Cantor pairing function and the successor
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item