All Questions
Tagged with computability-theory model-theory
67 questions
11
votes
0
answers
234
views
+50
Is there a decidable theory of arithmetic with a non-collapsing quantifier hierarchy?
This question is very close to this old MSE question of mine, which is still unanswered.
Is there an (ideally reasonably-natural!) expansion of the structure $(\mathbb{N};+)$ in a finite language ...
- 21.2k
3
votes
0
answers
153
views
What is known about the word problem on free algebraic models?
Consider the fragment of first-order logic with equality and universal quantification as the only logical symbols; we call this logic the logic of universal algebra. I am interested in languages $\...
1
vote
0
answers
40
views
Can a positive elementary inductive definition refer to its own stage comparison relation?
This is a cross-post of a question from cstheory.SE
Moschovakis' stage comparison theorem says that the stage comparison relation associated with any positive elementary induction is itself definable ...
- 211
6
votes
0
answers
263
views
Decidably clarifying ordinals
For a computable$^*$ ordinal $\alpha$ (viewed as an $\{<\}$-structure), say that a first-order sentence $\sigma$ in a relational language $\Sigma\supseteq \{<\}$ decidably clarifies $\alpha$ iff ...
- 21.2k
2
votes
0
answers
235
views
Is there a computable model of HoTT?
Among the various models of homotopy type theory (simplicial sets, cubical sets, etc.), is there a computable one?
Can the negative follow from the Gödel-Rosser incompleteness theorem?
If there is no ...
user507115
1
vote
1
answer
558
views
Natural Numbers
Let $L$ be a countable language and $M$ be a model of $L^N$ (the realization of $L$ in the natural numbers $N$) in which every recursive unary relation is expressible. Show that $M$ is not recursive.
- 265
3
votes
0
answers
143
views
Lindström's theorem part 2 for non-relativizing logics
By "logic" I mean the definition gotten by removing the relativization property from "regular logic" — see e.g. Ebbinghaus/Flum/Thomas — and adding the condition that for every ...
- 21.2k
3
votes
0
answers
99
views
Comparing computable structures via Kleene and Skolem
Below, by "structure" I mean "computable structure in a finite language with domain $\omega$," and by "sentence" I mean "finitary first-order sentence containing no ...
- 21.2k
0
votes
0
answers
181
views
Can a model of "true computation" exist? What would be its consequences?
Analogous to the model of True Arithmetic, the model of "True Computation" is defined to be the set of all true first-order statements about Turing machines i.e. answers to elementary ...
10
votes
2
answers
470
views
Is the set of permissible numbers of models of various cardinalities computable?
This question arose in the comments to this question.
Let $X$ be the set of pairs $(m,k)$ such that there is some (consistent complete countable first-order) theory $T$ with exactly $m$ models of size ...
- 21.2k
7
votes
0
answers
110
views
How tightly are decidability and "induction-completeness" linked?
It is known that there are a number of expansions of the structure $\mathfrak{N}:=(\mathbb{N};+)$ which are decidable (= have computable theories); one such example is the expansion by a predicate ...
- 21.2k
6
votes
0
answers
124
views
An analogue of Scott sentences in the (mostly) computable realm?
Below, "structure" means "computable structure in a computable language." In particular, we do distinguish between isomorphic copies of the same structure.
Let $\mathcal{L}_{\...
- 21.2k
5
votes
1
answer
487
views
How to solve this exercise about large countable ordinals?
In this note (Notes on Higher Type ITTM-recursion, 2021) written by Philip Welch, I'm trying to solve exercise 3.5(i), but I don't know how to solve it.
The problem is: assume that $L_{\gamma_0}<_{...
- 1,490
6
votes
2
answers
298
views
Is the usual enumeration of $\mathsf{PA}$ "minimal for consistency strength"?
This question is about a technical imprecision which is easily avoidable but whose details I'd like to understand better. When we refer to "the consistency strength of $\mathsf{PA}$" (say) ...
- 21.2k
6
votes
1
answer
571
views
Parameter-free effective cardinals
In the paper "Effective cardinals and determinacy in third order arithmetic" by Juan Aguilera, effective cardinals is defined.
I'm curious about its little variation, parameter-free ...
- 1,490
0
votes
0
answers
66
views
First-order logics expressively equivalent to the computable languages
There is a really nice theorem that the subsets of $(\Sigma^*, =_{el}, \preceq, (S_a)_{a \in \Sigma})$ definable in first-order logic are exactly the regular sets.
Where:
$\Sigma^*$ is the set of ...
- 429
6
votes
1
answer
227
views
How often are forcing extensions of countable computably saturated models of $\mathsf{ZFC}$ computably saturated?
Recall that given a finite language $\mathcal{L}$, we say that an $\mathcal{L}$-structure is computably saturated (or recursively saturated) if for any computable set $\Sigma(\bar{x},y)$ of $\mathcal{...
- 12.5k
6
votes
0
answers
207
views
Fragments of infinitary logic with a weak definability property
For a countable admissible ordinal $\alpha$, let $\mathcal{L}_\alpha=\mathcal{L}_{\infty,\omega}\cap L_\alpha$ and let $\equiv_\alpha$ be the corresponding elementary equivalence relation. Say that ...
- 21.2k
4
votes
1
answer
439
views
Alternative proof of Tennenbaum's theorem
The standard proof of Tennenbaums's theorem uses the existence of recursively enumerable inseparable sets and is presented e.g. in Kaye [1, 2], Smith [3].
In the following, $\mathcal{M}$ will always ...
- 211
1
vote
1
answer
260
views
Natural strong logic with Barwise compactness property
Throughout, by "logic" I mean regular logic (in the sense of Ebbinghaus–Flum–Thomas) whose sentences are coded by elements of $\mathsf{HC}$. Say that $\mathcal{L}$ is Barwise compact iff ...
- 21.2k
5
votes
0
answers
317
views
$\Sigma_n$-complete sets in the Levy hierarchy
Recall that a set $A \subseteq \mathbb N$ is (many-one, Turing) $\Sigma_n$-complete if it's $\Sigma_n$ and any other $\Sigma_n$ set (many-one, Turing) reduces to it. This definition actually makes ...
- 1,882
7
votes
0
answers
304
views
Which countable ordinals are "Barwise compact" for $\mathcal{L}_{\infty,\omega_1}$?
Barwise compactness says (as a special case) that whenever $\alpha$ is countable and admissible, $T\subseteq\mathcal{L}_{\infty,\omega}\cap L_\alpha$ is $\alpha$-c.e., and every subset of $T$ which is ...
- 21.2k
6
votes
2
answers
277
views
Are there structures in a finite signature that are recursively categorically axiomatizable in SOL but not finitely categorically axiomatizable?
Recall that a structure $\mathcal{M} = \langle M, I^\sigma_M \rangle$ in a signature $\sigma$ is categorically axiomatized by a second-order theory $T$ when, for any $\sigma$-structure $\mathcal{N} = \...
- 1,155
4
votes
0
answers
197
views
Are there any 1-decidable algebraic extensions of $\mathbb{Q}$ which are not decidable?
A model $M$ is decidable if the set of all first-order formulas which are true in $M$ is a recursive set. And a model is $1$-decidable if the set of all existential formulas which are true in $M$ is ...
- 4,597
8
votes
1
answer
514
views
How big is the least non-$\Sigma^1_1$-pointwise-definable ordinal?
There's a large countable ordinal which has cropped up (as a lower bound!) in a computable structure theory problem I'm playing with. At present I don't really understand how big it is, and I'm ...
- 21.2k
9
votes
0
answers
279
views
What logic characterizes relative intrinsic complexity in set recursion?
Short version: Is there an analogue of the Ash-Knight-Manasse-Slaman/Chisholm theorem for $E$-recursion?
Long version: I'm interested in "$E$-recursive structure theory," but it's not ...
- 21.2k
9
votes
1
answer
495
views
Can two versions of $\omega_1^{CK}(\mathsf{Ord})$ ever coincide?
The goal of this question is to fill in the gap in this old answer of mine.
For a transitive set $M$, thought of as an $\{\in\}$-structure, we define the following ordinals (this is not the notation ...
- 21.2k
4
votes
1
answer
202
views
Is there a "listable" structure of computable dimension $\omega$?
Say that a (countable, computable-language) structure $\mathfrak{A}$ has computable dimension $\omega$ iff there are infinitely many computable copies of $\mathfrak{A}$ up to computable isomorphism. ...
- 21.2k
3
votes
1
answer
139
views
Does "productive = dimension $\omega$" for computable structures?
In analogy with the terminology for sets, say that a (countable, computable language) structure $\mathfrak{A}$ is productive if there is a computable way to properly expand any computable list of ...
- 21.2k
5
votes
0
answers
246
views
Does $\mathsf{Q}$ have any interesting provably recursive functions?
This question was asked and bountied at MSE without success.
For an appropriate theory $T$, say that an $n$-ary $T$-provably recursive function is a $\Sigma_1$ formula $\varphi$ with $n+1$ free ...
- 21.2k
6
votes
0
answers
249
views
Number of models vs. complexity for SOL theories
This was previously asked at MSE without success.
Suppose $T$ is a complete first-order theory with continuum-many countable models up to isomorphism. We define two sets of Turing degrees associated ...
- 21.2k
3
votes
1
answer
716
views
Turing machines with all runs decidable
$\DeclareMathOperator\Comp{\mathit{Comp}}
\DeclareMathOperator\succ{\mathit{succ}}$Let $(\Phi_e)_{e\in\omega}$ be your favorite enumeration of Turing machines. For $e,n\in\omega$ there is a structure $...
- 21.2k
8
votes
1
answer
365
views
The lattice of analogues of Robinson's $Q$
This question was asked and bountied at MSE without response.
Call a sentence $\varphi$ in the language of arithmetic $Q$-like iff $\mathbb{N}\models\varphi$ and $\{\varphi\}$ is essentially ...
- 21.2k
11
votes
2
answers
920
views
Where did this presentation of Gödel's theorem appear?
This question was asked and bountied at MSE, with no response.
Many years ago I ran into the following proof of Gödel's first incompleteness theorem
(here $T$ is an "appropriate" theory of ...
- 21.2k
21
votes
0
answers
919
views
"Compactness for computability" - does it ever happen?
Throughout, "computable structure" means "first-order structure in a computable language with domain $\omega$ whose atomic diagram is computable."
Say that a computable structure $...
- 21.2k
4
votes
1
answer
206
views
Algorithmically deciding existence of finite limits in a category
Given $\Sigma$ a consistent finite first order theory in vocabulary $L$, one can consider the category of its models $\mathcal{M}(\Sigma)$, its objects are the models of $\Sigma$ and arrows are ...
- 173
7
votes
1
answer
596
views
Can an uncountable model of Peano Arithmetic be recursive?
Can an uncountable model of Peano Arithmetic be recursive?
What does it mean for an uncountable model to be recursive? Well, we represent the elements of the model using real numbers instead of ...
- 6,353
9
votes
1
answer
517
views
Axiomatizable $\exists \forall$ theory
I have been thinking the following problem proposed by my friends for a long time.
Let $\mathcal{L}$ be the first-order language of theory of rings and let $K$ be the class of algebraic number ...
- 151
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
17
votes
1
answer
720
views
Would an oracle for Rayo's function let you compute a model of $(V, \in)$?
Working in Kelly-morse set theory, let $R$ be an oracle that can compute Rayo's function. Can $R$ compute a countable model $M = (\mathbb N,\in_M)$ that is elementary equivalent to $(V, \in)$?
- 6,353
3
votes
0
answers
98
views
Reducibilities: Muchnik versus Medvedev-mod-parameters
By "structure," I mean "countable first-order structure in a computable language." And I'm comfortable with whatever set-theoretic hypotheses make things most interesting, should such things be ...
- 21.2k
5
votes
1
answer
286
views
Is there an oracle that can compute something iff it is computable in every countable model that is equivalent to $(V, \in)$?
Let us work in Kelly-morse set theory, so we can talk about $V$. For some model $M=(\mathbb N, \in_M)$ that is elementary equivalent $(V, \in)$, we can have an oracle that corresponds to $(\mathbb N, \...
- 6,353
3
votes
0
answers
615
views
Non-standard Turing machines
Turing machines can be encoded as natural numbers. In particular, one can (say, by using the binary representation of a computer program) find a bijection between natural numbers and Turing machines. ...
- 31
3
votes
0
answers
137
views
Moving between first and second order models using recursion
It seems that there are times when parts of the second order model of a certain structure can be determined to a significant degree using the first order model of the structure and recursion. For ...
- 10.1k
8
votes
1
answer
542
views
What is the Turing degree associated with an ultrafilter $U$?
I asked Turing degree of a turing machine with access to an (arbitrary) nonstandard integer, not thinking about the possiblity that this could depend on the model used. The question was not formulated ...
- 6,353
5
votes
3
answers
847
views
Turing degree of a turing machine with access to an (arbitrary) nonstandard integer
Let us consider Turing machines (or other Turing-complete model of computation) that, in addition to their regular input, are given some integer $H$, where $H$ is positive nonstandard. This means, in ...
- 6,353
3
votes
0
answers
179
views
How to show that the set of universal sentences with infinite models is a decidable set?
I was looking for an example for a a non- complete set of formulas (not finite) that might be decidable and I found the following statement:
Given a recursive language $L$ the set $\{ \phi \ | \ \phi$...
6
votes
1
answer
914
views
The set of largest numbers definable by formulas in different lengths
Let $n=\phi(l)$ to be the largest number definable by a first order arithmetic formula $f(x)$ having length at most $l$. By "$n$ is definable by formula $f(x)$" I mean $\mathcal{N}\vDash f(a)$ iff $a=...
- 2,619
6
votes
0
answers
132
views
Recursive enumeration of totally categorical structures
A theorem of Hrushovski [1] says that every totally categorical theory admits a finite axiomatization which may include certain "infinity axioms", called a quasi-finite axiomatization. In particular, ...
- 618
5
votes
2
answers
472
views
Consistent sentences with no arithmetically definable models
I've seen a construction of a sentence of first order logic that is consistent, but has no models with underlying set $\mathbb{N}$ and recursive functions and relations. Do there also exist consistent ...
- 2,130