# Questions tagged [model-theory]

Model theory is the branch of mathematical logic which deals with the connection between a formal language and its interpretations, or models.

892
questions

**6**

votes

**1**answer

148 views

### Models with fixed cardinality of non-Lebesgue measurable sets

In the usual $\mathsf{ZFC}$, we know that there are $2^\mathfrak{c}$ many subsets of $\mathbb{R}$ that are not (Lebesgue) measurable. On the other hand, the Solovay model also provides us a model of $\...

**8**

votes

**0**answers

174 views

### Definable constructions in o-minimal geometry

Recently I've been working with o-minimal expansions of $(\mathbb{R},\times,+)$, and I want to work "internally" to the language of o-minimal sets instead of working with "definable ...

**7**

votes

**0**answers

85 views

### Reduced power of an ordered field

Suppose $K$ is an ordered field, $X$ is any set, and $F$ is a filter over $X$. Let $G$ be the reduced power of $K$ by $F$. That is, we take all functions from $X$ to $K$, then take equivalence ...

**9**

votes

**1**answer

269 views

### Do saturated models require choice?

Let $T$ be a first-order theory, and suppose we want to build a saturated model $\mathbb U$ of $T$. That is, we want a model $\mathbb U$ of cardinality bigger than $|T|$, saturated in its own ...

**6**

votes

**1**answer

164 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} = \...

**6**

votes

**1**answer

238 views

### Groups with three conjugacy classes that define an ordering

Consider the following property for a group $(\mathcal{G},\cdot,1)$:
There are exactly three conjugacy classes $\{1\}$, $\mathcal{C}_1$, $\mathcal{C}_2$ in $\mathcal{G}$, and we have $\mathcal{C}_1 \...

**2**

votes

**1**answer

245 views

### Question in Vaught's paper

On page 307 of Vaught's paper "Denumerable models of complete theories", theorem 2.1.2 states that there is a denumerable model $\frak{A}$ of $T$ such that if, for each $j\in \omega, \:P_j$ ...

**10**

votes

**3**answers

344 views

### Comparing the existing formulations of universal algebra and their levels of generality

I am a newcomer to universal algebra and I just read this (very good, IMO) book on the topic:
Adámek, J., Rosický, J., & Vitale, E. M. (2010). Algebraic theories: a categorical introduction to ...

**6**

votes

**0**answers

283 views

### Proof of Tennenbaum's Theorem by McCarty

Tennenbaum's Theorem in its usual form states that for any countable non-standard model $M$ of PA there is no way to code the elements of $M$ as natural numbers such that either the addition or ...

**3**

votes

**1**answer

207 views

### Candidate “AEC-yielding” fragments of bad logics

Previously asked and bountied on MSE without success:
Given a logic $\mathcal{L}$ and a signature $\Sigma$, let the $\Sigma$-system of $\mathcal{L}$ be the pair $Sys_\Sigma(\mathcal{L})=(Struc(\Sigma),...

**8**

votes

**1**answer

580 views

### What is the theory of the random poset?

$\DeclareMathOperator\Th{Th}$The random poset is the Fraisse limit of the class of finite posets, just like the random graph is the Fraisse limit of the class of finite graphs? That is, the random ...

**1**

vote

**0**answers

26 views

### Axiomatizable classes in second and higher-order logics

I asked this on math stack exchange, but there were no answers. I want to know, are there more axiomatizable classes as you increase the order of the logic. So, for example, are there classes of ...

**12**

votes

**1**answer

520 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 ...

**4**

votes

**1**answer

239 views

### Compactness number for a fragment of second-order logic

Previously asked and bountied without response at MSE.
This question is a companion to this one, about a tame(?) fragment of second-order logic with the standard semantics, $\mathsf{SOL}$, motivated ...

**6**

votes

**0**answers

121 views

### Which first-order theories admit a compact-like superstructure?

Positive set theory is an approach to rectifying Russel's paradox by restricting the syntactic form of formulas for which we allow comprehension. It can be motivated by the construction of certain ...

**8**

votes

**0**answers

193 views

### How many steps does it take to “Tarski-Vaughtify” second-order logic?

Given a regular logic $\mathcal{L}$, let $\preccurlyeq_\mathcal{L}$ be the usual elementary submodelhood relation for $\mathcal{L}$. There is also a separate submodelhood relation coming from the ...

**4**

votes

**0**answers

184 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 ...

**2**

votes

**0**answers

106 views

### Are partial elements necessary in boolean-valued models?

It seems to me that there is a difference in the treatment of "partial" elements in boolean-valued models in set theory vs topos theory: in set theory, one usually only considers "...

**5**

votes

**0**answers

85 views

### How hard can it be to extract SOP from an unstable NIP theory?

A very fundamental result of Shelah in neostability theory is the fact that any unstable NIP theory has an instance of the strict order property, a formula $\varphi(x,y)$ (with $x$ and $y$ possibly ...

**5**

votes

**1**answer

169 views

### Boolean valued models in a general setting

It is well known that Boolean valued models play significant roles for set-theoretic purposes. But how well-studied are Boolean valued models in a more general setting, as models for random first-...

**6**

votes

**1**answer

249 views

### Is $\mathsf{ZFC+V=L}$ consistently $\omega$-complete?

This was previously asked and bountied on MSE:
For brevity, let $T$ be $\mathsf{ZFC+V=L}$.
Say that an extension of $\mathsf{ZFC}$ is $\omega$-complete iff it has exactly one $\omega$-model up to ...

**14**

votes

**2**answers

493 views

### How special is first-order $\mathsf{PA}$?

This is a modified version of a question which was asked and bountied at MSE without success.
Below, "$\mathsf{PA}$" refers to first-order Peano arithmetic.
There are various "...

**5**

votes

**1**answer

137 views

### Can a nonstandard model of $\mathsf{PA}$ be “$\Delta^1_1$-well-ordered?”

This was asked and bountied at MSE with no response:
My question is the following:
Is there a nonstandard model $\mathcal{M}\models\mathsf{PA}$ such that $\mathcal{M}$ has no $\Delta^1_1$-with-...

**5**

votes

**0**answers

76 views

### Is there an NSOP theory with FFSOP?

After talking to a couple of people, I have been unable to determine whether this is even known.
Recall that a first-order theory $T$ has the strict order property or SOP if there is a formula $\...

**10**

votes

**3**answers

672 views

### Is there a semantics for intuitionistic logic that is meta-theoretically “self-hosting”?

One can study the standard semantics of classical propositional logic within classical logic set theory, so we can say that the semantics of classical logic is meta-theoretically "self-hosting&...

**5**

votes

**0**answers

87 views

### How many parameters are needed to define strongly minimal sets in $\aleph_0$-categorical, $\aleph_0$-stable theories?

There's a well-known result of Cherlin, Harrington, and Lachlan that gives a very precise structural understanding of $\aleph_0$-categorical, $\aleph_0$-stable theories. One thing in particular is ...

**9**

votes

**2**answers

356 views

### Varieties where every algebra is projective?

Is it possible to classify all varieties (in the sense of universal algebra) where every algebra is projective?
Several years ago I asked a similar question, with "free" in place of "...

**7**

votes

**1**answer

207 views

### Paris-Harrington principles parametrized by functions $f:\mathbb N \to \mathbb N$

Recall that the Paris-Harrington Principle, $\mathsf{PH}$, is the statement that for each $e, r, k < \omega$ there is an $N < \omega$ so that given any coloring $c:[N]^e \to r$ there is an $H \...

**4**

votes

**1**answer

237 views

### What is the lowest complexity definition of $\mathbb{Z}$ in an infinite algebraic extension of $\mathbb{Q}$?

In 2009, Jochen Koenigsmann showed that $\mathbb{Z}$ is universally definable in the field $\mathbb{Q}$. And in 2012, Jennifer Park proved a result which implies that $\mathbb{Z}$ is $\exists\forall$-...

**22**

votes

**6**answers

1k views

### Is this theory the complete theory of the real ordered field?

We know that the real ordered field can be characterized up to isomorphism as a complete ordered field. However this is a second order characterization. That raises the following question. Consider ...

**8**

votes

**1**answer

213 views

### What is the lowest complexity definition of $\mathbb{Z}$ in an infinite extension of $\mathbb{Q}$

In 2009, Jochen Koenigsmann showed that $\mathbb{Z}$ is universally definable in the field $\mathbb{Q}$. And in 2012, Jennifer Park proved a result which implies that $\mathbb{Z}$ is $\exists\forall$-...

**19**

votes

**5**answers

2k views

### Is there a metamathematical $V$?

As with many of you, I've been following Peter Scholze's recent question about universes with great interest. In ring theory, we don't often have to deal with proper classes, but they occasionally ...

**2**

votes

**0**answers

71 views

### When are classes with prescribed reducts “pseudo”-elementary?

Let $\mathsf{Set}$ be the class of all sets and let $\mathcal{L}$ be a first-order language. Let $M \subseteq \mathsf{Set}$ be a set of $\mathcal{L}$-structures and let $$\mathfrak{Th}_{\in}(M) = \\ \{...

**0**

votes

**0**answers

129 views

### What are the handy, go-to methods of proving consistency of a proof system?

Suppose you face a proof system portraying some notion or knowledge that you haven't encountered, or others haven't studied before. What would be your first attempts to examine the consistency of the ...

**7**

votes

**1**answer

112 views

### Is there a pseudofinite group with a quantifier-free instance of the order property?

Recall that a group $G$ is pseudofinite if every first-order sentence $\varphi$ (in the language of groups) satisfied in $G$ is also satisfied in some finite group. Also recall that an instance of the ...

**10**

votes

**1**answer

297 views

### Is $\mathbb{Z}$ universally definable in any number fields other than $\mathbb{Q}$?

In 2009, Jochen Koenigsmann showed that $\mathbb{Z}$ is universally definable in the field $\mathbb{Q}$. My question is, are there any other number fields in which $\mathbb{Z}$ is universally ...

**10**

votes

**0**answers

284 views

### Definability up to isomorphism versus definability of an isomorphic copy

Question: Is it provable in ZFC that every structure that is ordinal definable up to isomorphism has an ordinal definable isomorphic copy? If not, what are some counterexamples? All structures are ...

**7**

votes

**1**answer

295 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 ...

**8**

votes

**1**answer

281 views

### Intuition behind Boolean-valued models of set theory

$\DeclareMathOperator\Card{Card}$The book Forcing Eine Einführung in die Mathematik der Unabhängigkeitsbeweise by Hoffmann provides an intuition behind boolean valued models of set theory which I will ...

**6**

votes

**0**answers

151 views

### Reference requestion: theorem guaranteeing self-embeddings of expansions of $\mathit{Ord}$

This is an attempt to locate a theorem I vaguely remember but cannot find (which arose in the context of Consistency of non-trivial elementary embedding $j : \mathit{Ord} \to \mathit{Ord}$ and ...

**9**

votes

**0**answers

255 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 ...

**6**

votes

**0**answers

136 views

### Does the random graph interpret the random directed graph?

The random graph is the Fraisse limit of the class of finite graphs, the random directed graph is the Fraisse limit of the class of directed graphs, a directed graph is just a set with a binary ...

**0**

votes

**1**answer

213 views

### How do “Galois-type” and “saturation” for AECs generalize “type” and “saturation” in first-order model theory?

As I'm not allowed to ask a new question due to limit reached matter,
I still want to EDIT this one as communicated with @Alex Kruckman
in the comments below. I would like to understand the ...

**3**

votes

**1**answer

390 views

### Forcing, a technical detail

In the snippet below from Shelah's book P&I Forcing,
in the definition 5.2(2)
I do not follow why in this sentence [naturally extended to include $N\prec (H(\mu^\dagger),\epsilon),\mu\in N$] $N$ ...

**8**

votes

**1**answer

342 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 ...

**1**

vote

**0**answers

79 views

### Indiscernible sequences in o-minimal structures

Is there an explicit characterisation of indiscernible sequences in o-minimal structures ? Say for expansions of the reals or $R_{an}$ ?
Is there a characterisation of o-minimality in terms of ...

**4**

votes

**1**answer

247 views

### Is there a complete characterization of ordered fields without definable proper subfields?

$\mathbb{Q}$ has no proper subfields. As a result, all ordered fields elementarily equivalent to $\mathbb{Q}$ have no proper subfields which are first-order definable without parameters. And by the ...

**4**

votes

**1**answer

161 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. ...

**3**

votes

**1**answer

88 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 ...

**6**

votes

**1**answer

187 views

### Is the hereditary version of this weak finiteness notion nontrivial?

Say that a set $X$ is $\Pi^1_1$-pseudofinite if every first-order sentence $\varphi$ with a model with underlying set $X$ has a finite model. The existence of infinite $\Pi^1_1$-pseudofinite sets is ...