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.

Filter by
Sorted by
Tagged with
6
votes
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
3answers
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
2answers
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
1answer
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
0answers
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
3answers
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
0answers
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
2answers
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
1answer
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
1answer
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
6answers
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
1answer
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
5answers
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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 ...

1
2 3 4 5
18