All Questions
Tagged with model-theory computability
64
questions
3
votes
1
answer
62
views
Algorithm for Determining Truth of First-Order Sentences in Complex Numbers
Following my previous question Decidability in Natural Numbers with a Combined Function, I realized that there is a spectrum regarding the hardness of deciding whether a first-order sentence is true ...
- 87
-1
votes
1
answer
90
views
Decidability in Natural Numbers with a Combined Function [closed]
It is well known that there is no algorithm to determine whether a given first-order sentence is true in the structure of natural numbers with both addition and multiplication. In contrast, Presburger ...
- 87
2
votes
0
answers
76
views
Are the models of PA recursively enumerable?
Is there a Turing machine (TM from now on) which lists every model of PA (without the induction axiom schema, so just addition and multiplication)? More specifically, can such a TM list all infinite ...
1
vote
1
answer
121
views
"Non-standard" witnesses to a $\Sigma_1^0$ statement
I'm in the midst of confusion about non-standard integers. It is my understanding that for example, in ZFC the Riemann hypothesis is equivalent to a $\Pi_1^0$ statement $(\forall y) \phi(y)$ where $\...
- 1,645
1
vote
1
answer
97
views
Is the problem of whether there is a computable model of a given first-order sentence recursively enumerable?
Trakhtenbrot's theorem states that given a sentence $\phi$ in a finite vocabulary (M. Viswanathan, "Finite Model Theory", notes, 2018), the problem of whether $\phi$ is satisfied in a finite ...
- 1,311
4
votes
1
answer
87
views
Is there a difference between computable model theory and computable structure theory?
I have the seen the books/notes with both titles and there seems to be quite some overlap, but I'm not sure if people in the field view them as having slightly different focuses.
2
votes
1
answer
80
views
Possible counterexample to $\ulcorner\Delta\urcorner$ is recursive $\iff$ $\mathrm{Th}(\Delta)$ is complete?
I am referring to the notes A Problem Course in Mathematical Logic by Stefan Bilaniuk.
Let $\mathcal{L}_N = \{0,S,+,\cdot,E\}$ denote the language of number theory. Given a set of formulas $\Delta$, ...
- 8,387
1
vote
0
answers
93
views
Let $\pi$ be a $ℍ𝑌𝑃_𝔐$-recursive projection of $ℍ𝑌𝑃_𝔐$ into 𝔐. What does $ℍ𝑌𝑃_{(𝔐, Domain(\pi))}$ contain?
Let $\pi$ be a $ℍ𝑌𝑃_𝔐$-recursive projection of $ℍ𝑌𝑃_𝔐$ into 𝔐 (we know it exists by the classic results of Barwise in Admissible Sets and Structures (II.5.14, V.5.3, and VI.4.11/12)). The ...
- 11
2
votes
0
answers
81
views
A Computable Forcing Argument
I encountered the following problem in Ash&Knight's Computable Structures and the Hyperarithmetical Hierarchy, Theorem 10.9 (slightly rephrased):
TFAE for a computable structure $A$ with a ...
- 1,569
1
vote
2
answers
80
views
Which subsets of $\mathbb{N}$ can be the sizes of finite models?
Let $T$ be a finite first order theory (equivalently a single sentence) in a finite language. It is clear that $\{n\in\mathbb{N}:\exists M, M\models T\land |M|=n\}$ is computable: to see if there is a ...
- 998
2
votes
1
answer
199
views
Why are subclasses of first-order logic with the finite model property decidable? [closed]
The title really says all:
Why are subclasses of first-order logic with the finite model property decidable?
- 73
15
votes
1
answer
206
views
Are the algebraic real numbers an automatic structure?
In the 1950's, Julius Büchi showed that $(\mathbb{N},S,+,0)$ is not merely a decidable structure as Presburger had shown, but an automatic structure, i.e. there is an encoding of the natural numbers (...
- 10.3k
0
votes
1
answer
395
views
Let $W\subseteq\omega$ be an infinite c.e. set. Show that there is an infinite $X\subseteq W$ such that $X$ is computable.
If I can prove that $X$ is c.e. and $\omega \setminus X$ is c.e. then I can prove that $X$ is computable by the theorem "Let $W \subseteq \omega$. Then $W$ is computable iff both $W$ and $\omega \...
user995145
0
votes
0
answers
108
views
Models of PA inside a computationally weaker theory
I have two questions about the computability power of theories, one about models of ${PA}$ and the other about the model theory itself:
Is it possible to create a model of ${PA}$ inside a weaker ...
- 37
5
votes
0
answers
137
views
Can "$\omega_1$-Barwise-ness" be ensured by a first-order theory?
With the Barwise compactness theorem in mind, say that a countable infinite ordinal $\alpha$ is $\omega_1$-Barwise iff whenever $T$ is a $\Sigma_1(L_\alpha)$ set of $\mathcal{L}_{\infty,\color{red}{\...
- 249k