Is there an "offshoot" of model theory that looks at structures over standard models of arithmetic?

82 Views Asked by At

Is there an "offshoot" of model theory that looks at structures over standard models of arithmetic? Also, what, if anything, do you lose by fixing $\omega$ as the sole cardinal that you're working with (assuming temporarily that we were originally mostly interested in infinite models)?

I was wondering earlier today if we lose anything by restricting model theory to "just" countably infinite structures and came across this question. The answer to which implies that if we're interested in infinite models initially, then, in a certain sense, we can look at just the countably infinite ones to answer questions about whether two theories have the same models.

Then I started wondering about what happens if we pick the standard model of $\mathbb{N}$ or $\mathbb{Z}$ as our carrier.

I'm curious what happens if we take our carrier in our structures to be $\mathbb{N}$ or $\mathbb{Z}$ instead of "just" a set, i.e. we look at only $\models_\mathbb{N}$ or $\models_\mathbb{Z}$.

$$ M \models_{\mathbb{N}} T \;\; \textit{if and only if} \;\; \text{$M \models T$ and $\mathbb{N}$ is the carrier of $M$} \;\;\textit{and likewise for $\mathbb{Z}$} $$

One thing that we can now do is compactly describe structures that happen to be computable. We could have done this anyway without fixing our carrier, but fixing $\mathbb{N}$ seems like an interesting perspective, at least.

If we take the $V_2$ symbol from Büchi arithmetic, then we can construct a dense linear order with a lower bound over $\mathbb{N}$ in the following way:

$$ x \, (\le)\, y \iff V_2(y)\cdot V_2(y) \cdot x \le V_2(x) \cdot V_2(x) \cdot y $$

This is a dense linear order because it is equivalent to comparing the fractions below, which is equivalent to replacing $2$ with $\frac{1}{2}$ in the prime factorization of a number, which hits all the dyadic rationals.

$$ x \,(\le)\, y \iff \frac{x}{V_2^2(x)} \le \frac{y}{V_2^2(y)} \; \textit{as rational numbers} $$

1

There are 1 best solutions below

2
On BEST ANSWER

Looking at a specific carrier structure, as opposed to simply making a choice of cardinality, lets you do two things I can think of:

  • We can talk about how adding a piece of structure to an existing structure changes its behavior. The relevant term here is "expansions" - e.g. which expansions of $(\mathbb{N};+)$ remain decidable?

  • We can talk about how difficult it is to "build" a given structure from the perspective of another structure. This is where topics interpretations (in first-order or some other logic) and computable structure theory (in the specific case of $\mathbb{N}$, or occasionally other "computability-flavored" structures like $L_{\omega_1^{CK}}$) live.


I know much more about the second bulletpoint, so let me mention one foundational result on the topic (being slightly vague in the interest of brevity): the Ash/Knight/Manasse/Slaman/Chisholm theorem, proved by the first four authors as one group and independently the fifth author alone. Suppose I have a countable structure $\mathcal{A}$ and some relation $R$ on $\mathcal{A}$. Consider the following questions:

  • How difficult is $R$ to define within $\mathcal{A}$?

  • If I build an isomorphic copy $\mathcal{B}$ of $\mathcal{A}$ with domain $\mathbb{N}$, what is the computability-theoretic complexity of $\mathcal{B}^R$ (= $\mathcal{B}$'s version of $R$)?

It turns out that these two questions are tightly related. For example, the following are equivalent:

  • For every isomorphic copy $\mathcal{B}$ of $\mathcal{A}$ with domain $\mathbb{N}$, the relation $R^\mathcal{B}$ is computably enumerable.

  • There is a computable infinitary $\Sigma_1$ formula $\varphi$ such that $\varphi^\mathcal{A}=R$, that is, $R$ is computable infinitary $\Sigma_1$ definable over $\mathcal{A}$.

Essentially, infinitary logic - or more accurately, computable infinitary logic appropriately "stratified" - provides a "carrier-set-independent" approach to certain computability-flavored questions.