# Tagged Questions

53 views

### Nonstandard models of PA with a decidable order relation.

There this exercise in Models of Peano Arithmetic (Kaye 1991, p.157), which asks to define a recursive binary relation on $\mathbb{N}^2$, such that $M \upharpoonright <$ is isomorphic to ...
56 views

### A Question About Tennebaum's Theorem?

Tennenbaum's theorem proves there are no countable recursive nonstandard models of Peano arithmetic. It is a proof by contradiction. If our countable, nonstandard model is recursive, then, given a ...
135 views

### Tennenbaum's theorem without overspill

While trying to clean up Wikipedia's proof sketch for Tennenbaum's theorem (there is no computable non-standard model of Peano Arithmetic), the following strategy occurred to me. Since it seems to be ...
57 views

### Determining if a theory in first-order logic is decidable

We have a theory in first-order logic which we know that is uncountably categorical, complete but not finitely axiomatisable. We also want to know if it is decidable. But I don't know the procedure ...
66 views

### Possible Turing degrees of countable models of ZFC

Let $M$ be a countable model in a signature $\Sigma$. We assume $\Sigma$ is finite, and (for convenience) has no function or constant symbols. Without loss of generality, we can assume that $M$'s ...
124 views

### Running programs in nonstandard models of PA

I came across the following problem in several places, to paraphrase: Let $T$ be a recursively axiomatizable, consistent extension of PA. Then there exists some $e$ such that the $e'$th program ...
85 views

### Theory vs. Deductive Theory

Looking through some notes on model and computability theory, I noticed that the definition of the term 'theory' changed between them; in particular, the model theory (based on Hodges' text) defined a ...
63 views

### Omitting Types… recursively

I'm working on the following problem at the moment: Let $\mathcal{L} = \{R\}$, where $R$ is a binary relation symbol. Let $T$ be a consistent, decidable $\cal{L}$-theory, and let $p(x)$ be a ...
62 views

### Complexity of index sets in nonprincipal ultrafilters

Let $U$ be a nonprincipal ultrafilter on $\omega$. It can be shown that the set $I = \{e \mid W_e \in U\}$ (where $W_e$ is the $e$th r.e. set in some given enumeration) cannot be $\Delta_2^0$ (in ...
337 views

### Complete theories - dense linear order

There are two things I would like to prove. DLO - Dense linear order is complete, that means that when $\psi$ is a sentence of the language $\{<\}$ then $DLO\vDash\psi$ or $DLO\vDash\neg\psi$ ...
173 views

### Second incompleteness and Model theorey

If we let $T$ be a consistent theory in the language of arithmetic $\mathcal{L}_A$ theory extending Peano Arithmetic — with specified numbering of formulas $\left[\cdot\right]$ and suppose that ...
98 views

### On the Decision Problem for Two-variable First-Order Logic

I have a question concerning the model construction of the $\forall \forall \land \forall \exists$ - Scott sentence on page 6 in this paper: www.cs.rice.edu/~vardi/papers/basl96.ps.gz Why do we ...
A language $L_{\omega_1\omega}$ generalizes an ordinary first-order language by allowing countably long disjunctions. If we take its nonlogical vocabulary to contain just a predicate for the ...