All Questions
Tagged with decidability model-theory
21 questions
3
votes
0
answers
99
views
Decidability of theory of modules over a ring of finite representation type
I have read from Mike Prest's model theory for modules (London lecture note series) chapter 17 that a Ring of finite representation type has a decidable theory of modules. Here decidability was ...
- 31
7
votes
1
answer
261
views
What is known about first order logic of $\mathbb{N}$ with + and a unary predicate?
In "Weak Second-Order Arithmetic and Finite Automata", Büchi claims that the first order theory of $\mathbb{N}$ with + and a predicate for recognizing powers of 2 ($Pw_2$) is expressively ...
- 429
4
votes
2
answers
769
views
Tarski's original proof of quantifier elimination in algebraically closed fields
I am currently helping teach a course about foundations of mathematics, which has thus far focused mostly on propositional and first-order logic. As part of the course, the students are each required ...
- 721
5
votes
2
answers
286
views
Quantifier elimination in $S^1$
Does quantifier elimination (by cylindrical decomposition) work for systems of polynomial equations and inequalities where some or all of the variables are complex numbers of unit modulus, rather than ...
- 20.2k
12
votes
1
answer
1k
views
Testing whether $e^x+ax^2+bx+c$ has a zero
What is the simple test with exponential polynomials to determine whether
$$f(x)=e^x+ax^2+bx+c$$ has a positive zero?
This was prompted by the question about discriminants here. We have an ineffective ...
user44143
12
votes
2
answers
560
views
Decidability of a first-order theory of hyperreals
The theory of real closed fields is decidable. The hyperreals satisfy that theory, so we can interpret statements in the theory of real closed fields as being about hyperreals.
If we add a unary ...
- 6,353
0
votes
1
answer
139
views
Linear programming with exponential inequalities and rational variables
If we are given a set of real linear inequalities then using elimination theory or just linear programming we can decide. If the program also has inequalities of form $2^x\leq g$ in addition to linear ...
- 1,826
7
votes
1
answer
272
views
Is $\mathbb{F}_{p}(t)^{h}$ an elementary substructure of/existentially closed in $\mathbb{F}_{p}((t))$?
It is a well-known fact that the Henselization of the function field $\mathbb{F}_{p}(t)$ in regard to the $t$-adic valuation is $\mathbb{F}_{p}(t)^{alg} \cap \mathbb{F}_{p}((t))$, so of course $\...
- 311
6
votes
1
answer
286
views
Example of applying real quantifier elimination algorithm for polynomials
Sorry if any of this is unclear, or doesn't make much sense, I'm still trying to figure it out, a practical example such as this would likely help me understand better than anything else. I have read ...
- 61
2
votes
0
answers
218
views
The elementary theory of finite commutative rings
I have wondered the decidability of elementary theory of finite commutative rings. Since we know that the elementary theory of finite fields is decidable shown by J.Ax (The Elementary Theory of Finite ...
- 151
6
votes
1
answer
281
views
Deciding isomorphism between graphs which interpret in the pure set
I am interested in the following decision problem:
Given descriptions of two graphs $G,H$ which interpret in the pure set $\mathbb N=(\{0,1,2,\ldots\},=)$, decide whether $G$ and $H$ are isomorphic....
- 618
16
votes
1
answer
600
views
Is this theory decidable?
It is well-known that both Presburger arithmetic (by contrast with Peano arithmetic) and Tarski geometry are decidable. I was in the shower this morning and wondered whether there exists an elegant ...
- 12.4k
0
votes
0
answers
197
views
Is the positive existential theory undecidable?
Could you tell if the positive existential theory of $\mathbb{C}[e^{\mu x} \mid \mu \in \mathbb{C}]$ is undecidable in the language $\{+, \cdot , \frac{d}{dx} , 0, 1, e^x\}$ ?
How can we prove the (...
- 309
6
votes
1
answer
485
views
Show that the positive existential theory is undecidable
To show that the positive existential theory of $\mathbb{C}[t, e^{\lambda t} \mid \lambda \in \mathbb{C}]$ in the language $\{+, \cdot , ' , 0 , 1, t\}$ is undecidable we have to prove the following: $...
- 309
15
votes
2
answers
1k
views
Decidability of decidability
The questions I'm going to ask are non formal because they concern decidability of decidability, and I couldn't find any references on that after some quick searches. I hope that this thread is still "...
- 438
5
votes
1
answer
522
views
Quantifier elimination vs decidability
Quantifier elimination is used as a technique to get decidability (e.g. $Th( \mathbb{N}, +)$ ) of theories, but typically one has to go over to some expansion. Are there examples of theories which are ...
1
vote
0
answers
87
views
unique types and decidability
Suppose $\mathcal{M}$ is an infinite structure which has the property that every type that is realised is realised uniquely. Also assume that every element of $\mathcal{M}$ is definable but there is ...
37
votes
4
answers
2k
views
Is the field of constructible numbers known to be decidable?
By the field of constructible numbers I mean the union of all finite towers of real quadratic extensions beginning with $\mathbb{Q}$. By decidable I mean the set of first order truths in this field, ...
- 11.1k
13
votes
1
answer
5k
views
Is the first-order theory (with =) of real numbers with addition and multiplication complete and decidable?
Due to Andreas Blass's answer to my question "Is the feasibility of a system of nonlinear, non-convex equations (inequalities) decidable?", i have now investigated real closed fields (RCF), because i ...
- 165
9
votes
2
answers
886
views
Are there standard examples of stable theories that are undecidable?
What is known about decidability of various first order theories studied in stable model theory, geometric model theory, o-minimality? For example, is there a natural example of an undecidable first ...
- 1,299
60
votes
6
answers
7k
views
Has decidability got something to do with primes?
Note: I have modified the question to make it clearer and more relevant. That makes some of references to the old version no longer hold. I hope the victims won't be furious over this.
Motivation:
...
- 2,824