Definability and decision problems in arithmetic
From MaRDI portal
Publication:5791204
DOI10.2307/2266510zbMath0034.00801OpenAlexW2015376829WikidataQ59540876 ScholiaQ59540876MaRDI QIDQ5791204
Publication date: 1949
Published in: Journal of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2307/2266510
Related Items
Ordered fields dense in their real closure and definable convex valuations ⋮ Hilbert's tenth problem over function fields of positive characteristic not containing the algebraic closure of a finite field ⋮ Further results on Hilbert's tenth problem ⋮ Uniform first-order definitions in finitely generated fields ⋮ Mathematics by machine ⋮ Fuzzy simplification of non-numeric expressions containing some intervals and/or floating point numbers ⋮ Sparse interpolation over finite fields via low-order roots of unity ⋮ Multivariate sparse interpolation using randomized Kronecker substitutions ⋮ Computing the differential Galois group of a parameterized second-order linear differential equation ⋮ A new deterministic algorithm for sparse multivariate polynomial interpolation ⋮ A fast algorithm for computing the characteristic polynomial of the p-curvature ⋮ Computing necessary integrability conditions for planar parametrized homogeneous potentials ⋮ Improved algorithm for computing separating linear forms for bivariate systems ⋮ Solving higher order linear differential equations having elliptic function coefficients ⋮ Parallel telescoping and parameterized Picard-Vessiot theory ⋮ A generalized Apagodu-Zeilberger algorithm ⋮ The asymptotic analysis of some interpolated nonlinear recurrence relations ⋮ Fast arithmetic for the algebraic closure of finite fields ⋮ On the computation of the topology of plane curves ⋮ Essentially optimal interactive certificates in linear algebra ⋮ Root counts of semi-mixed systems, and an application to counting nash equilibria ⋮ Synthesis of optimal numerical algorithms using real quantifier elimination (case study: square root computation) ⋮ Sub-cubic change of ordering for Gröbner basis ⋮ Sparse Gröbner bases ⋮ The MMO problem ⋮ Factoring linear differential operators in n variables ⋮ Online order basis algorithm and its impact on the block Wiedemann algorithm ⋮ On isomorphisms of modules over non-commutative PID ⋮ Radical solutions of first order autonomous algebraic ordinary differential equations ⋮ Computing low-degree factors of lacunary polynomials ⋮ Maximum likelihood geometry in the presence of data zeros ⋮ Constructing fewer open cells by GCD computation in CAD projection ⋮ An a posteriori certification algorithm for Newton homotopies ⋮ Evaluating parametric holonomic sequences using rectangular splitting ⋮ Equivariant lattice generators and Markov bases ⋮ Sparse polynomial interpolation codes and their decoding beyond half the minimum distance ⋮ Sparse multivariate function recovery with a high error rate in the evaluations ⋮ Bounds for D-finite closure properties ⋮ Powers of tensors and fast matrix multiplication ⋮ Reduction among bracket polynomials ⋮ Formal solutions of a class of Pfaffian systems in two variables ⋮ On the reduction of singularly-perturbed linear differential systems ⋮ High performance implementation of the TFT ⋮ Randomized detection of extraneous factors ⋮ Toric border basis ⋮ On efficient algorithms for computing parametric local cohomology classes associated with semi-quasihomogeneous singularities and standard bases ⋮ Can one design a geometry engine? Can one design a geometry engine? On the (un)decidability of certain affine Euclidean geometries ⋮ Defining the integers in large rings of a number field using one universal quantifier ⋮ Baire Category Theory and Hilbert’s Tenth Problem Inside $$\mathbb {Q}$$ Q ⋮ Some new results in monadic second-order arithmetic ⋮ First-order decidability and definability of integers in infinite algebraic extensions of the rational numbers ⋮ A note on definability in fragments of arithmetic with free unary predicates ⋮ Ehrenfeucht games and ordinal addition ⋮ The Hilbert's-tenth-problem operator ⋮ Automatic Sets of Rational Numbers ⋮ Queries with arithmetical constraints ⋮ On mutual definability of operations on fields ⋮ More on generic dimension groups ⋮ Semi-isolation and the strict order property ⋮ On nonelementarily equivalent pairs of fields ⋮ Quantifier rank for parity of embedded finite models. ⋮ Hilbert's tenth problem for fields of rational functions over finite fields ⋮ On arithmetical first-order theories allowing encoding and decoding of lists ⋮ Hilbert's tenth problem for rings of rational functions ⋮ Computational complexity of sentences over fields ⋮ Termination of polynomial loops ⋮ Extensions of Hilbert’s Tenth Problem: Definability and Decidability in Number Theory ⋮ Polynomial time algorithms for sentences over number fields ⋮ Definability of Frobenius orbits and a result on rational distance sets ⋮ Defining Integers ⋮ Complexity of logical theories involving coprimality ⋮ Self-injective regular algebras and function rings ⋮ The scope of Gödel's first incompleteness theorem ⋮ Computable dimensions of Pappusian and Desarguesian projective planes ⋮ All arithmetical sets of powers of primes are first-order definable in terms of the successor function and the coprimeness predicate ⋮ An existential divisibility lemma for global fields ⋮ Decidable \({\exists}^*{\forall}^*\) first-order fragments of linear rational arithmetic with uninterpreted predicates ⋮ Problemi di decidibilita in logica topologica ⋮ Definability, decidability, complexity ⋮ Universally defining finitely generated subrings of global fields ⋮ When is scalar multiplication decidable? ⋮ Decidability questions for a ring of Laurent polynomials ⋮ On decidability and axiomatizability of some ordered structures ⋮ On mathematical realism and applicability of hyperreals ⋮ Axiomatic (and non-axiomatic) mathematics ⋮ Integrality at a prime for global fields and the perfect closure of global fields of characteristic \(p > 2\) ⋮ Predicate logics of expressively strong theories ⋮ First-order definitions of rational functions and \({\mathcal S}\)-integers over holomorphy rings of algebraic functions of characteristic 0 ⋮ Decidability of certain theories of integers ⋮ A view of computability on term algebras ⋮ Extended order-generic queries ⋮ The Undecidability of Algebraic Rings and Fields ⋮ Uniformly defining \(p\)-Henselian valuations ⋮ A note on Parikh maps, abstract languages, and decision problems ⋮ The compactness of first-order logic:from gödel to lindström ⋮ Definability and decidability in infinite algebraic extensions ⋮ Julia Robinson, in memoriam ⋮ A portrait of Alfred Tarski ⋮ On Dipphantine definability and decidability in some rings of algebraic functions of characteristic 0 ⋮ Computable procedures for fields ⋮ Constructive Game Logic ⋮ The Diophantine Problem for Addition and Divisibility ⋮ A near-optimal algorithm for computing real roots of sparse polynomials ⋮ LLL reducing with the most significant bits ⋮ Covering of surfaces parametrized without projective base points ⋮ Linear independence oracles and applications to rectangular and low rank linear systems ⋮ Faster relaxed multiplication ⋮ Unimodular completion of polynomial matrices ⋮ On Diophantine definability and decidability in some infinite totally real extensions of ℚ ⋮ The Diophantine Problem for Polynomial Rings and Fields of Rational Functions ⋮ HTP-COMPLETE RINGS OF RATIONAL NUMBERS ⋮ NOTES ON THE DPRM PROPERTY FOR LISTABLE STRUCTURES ⋮ Unnamed Item ⋮ Extensions of Hilbert's tenth problem ⋮ ORDER TYPES OF MODELS OF FRAGMENTS OF PEANO ARITHMETIC ⋮ On boolean functions and connected sets ⋮ Answer to a problem raised by J. Robinson: The arithmetic of positive or negative integers is definable from successor and divisibility ⋮ CONNECTEDNESS IN STRUCTURES ON THE REAL NUMBERS: O-MINIMALITY AND UNDECIDABILITY ⋮ Strongly NIP almost real closed fields ⋮ Definability in number fields ⋮ Computation models and function algebras ⋮ DEFINABILITY OF HENSELIAN VALUATIONS BY CONDITIONS ON THE VALUE GROUP ⋮ Undecidability and Definability for the Theory of Global Fields ⋮ Elliptic curves retaining their rank in finite extensions and Hilbert's Tenth Problem for rings of algebraic numbers ⋮ THE DIOPHANTINE PROBLEM FOR ADDITION AND DIVISIBILITY OVER SUBRINGS OF THE RATIONALS ⋮ On the model theory of higher rank arithmetic groups ⋮ INTERLEAVING LOGIC AND COUNTING ⋮ A TOPOLOGICAL APPROACH TO UNDEFINABILITY IN ALGEBRAIC EXTENSIONS OF ⋮ Universally defining Z$\mathbb {Z}$ in Q$\mathbb {Q}$ with 10 quantifiers ⋮ Undecidability, unit groups, and some totally imaginary infinite extensions of ℚ ⋮ As easy as $\mathbb {Q}$: Hilbert’s Tenth Problem for subrings of the rationals and number fields ⋮ The theory of integer multiplication with order restricted to primes is decidable ⋮ Matrix-F5 algorithms over finite-precision complete discrete valuation fields ⋮ Definability and decidability issues in extensions of the integers with the divisibility predicate ⋮ The diophantine problem for addition and divisibility for subrings of rational functions over finite fields ⋮ The recursive sets in certain monadic second order fragments of arithmetic ⋮ $\mathbb \{Q\}$ muni de l’arithmétique faible de Penzin est décidable ⋮ Existential definability with bounds on archimedean valuations ⋮ Decidability of the theory of the natural integers with the Cantor pairing function and the successor ⋮ A list of arithmetical structures complete with respect to the first-order definability ⋮ The prime number theorem is PRA-provable ⋮ INTERPRETING ARITHMETIC IN THE FIRST-ORDER THEORY OF ADDITION AND COPRIMALITY OF POLYNOMIAL RINGS ⋮ Computational complexity of quantifier-free negationless theory of field of rational numbers ⋮ The Woods-Erdős conjecture for polynomial rings ⋮ Decidable fragments of field theories ⋮ Address at the Princeton University Bicentennial Conference on Problems of Mathematics (December 17–19, 1946), By Alfred Tarski ⋮ Quantifier elimination by cylindrical algebraic decomposition based on regular chains ⋮ Logspace computations in graph products ⋮ Tame decompositions and collisions ⋮ Arithmetical definability of field elements ⋮ On direct products of theories ⋮ Some theorems on definability and decidability ⋮ On reduction to a symmetric relation ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Diophantine definability of nonnorms of cyclic extensions of global fields ⋮ An Exact Correspondence of Linear Problems and Randomizing Linear Algorithms ⋮ Undecidable extensions of Skolem arithmetic ⋮ First order irrationality criteria for series ⋮ Variants of Robinson's essentially undecidable theoryR ⋮ Expansions of the real field by discrete subgroups of 𝐺𝑙_{𝑛}(ℂ) ⋮ UNIFORM DEFINABILITY OF INTEGERS IN REDUCED INDECOMPOSABLE POLYNOMIAL RINGS ⋮ A construction of real closed fields ⋮ Some theories associated with algebraically closed fields ⋮ Undecidable Rings ⋮ Defining transcendentals in function fields
Cites Work
This page was built for publication: Definability and decision problems in arithmetic
