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
9 votes
1 answer
316 views

Logics detecting their own equivalence notions, take two: $\mathcal{L}_{\omega_2,\omega}$

This question is a follow-up to another question of mine, with different language - see the link below. Say that an infinite regular cardinal $\kappa$ is Fraissean iff the logic $\mathcal{L}_{\kappa,\...
Noah Schweber's user avatar
4 votes
2 answers
273 views

Quantifier elimination in $S^1$

Does quantifier elimination (by cylindrical decomposition) work for systems of polynomial equations and inequalities where some or all of the variables are complex numbers of unit modulus, rather than ...
H A Helfgott's user avatar
  • 19.3k
12 votes
1 answer
580 views

Can $\mathcal{L}_{\omega_1,\omega}$ detect $\mathcal{L}_{\omega_1,\omega}$-equivalence?

Roughly speaking, say that a logic $\mathcal{L}$ is self-equivalence-defining (SED) iff for each finite signature $\Sigma$ there is a larger signature $\Sigma'\supseteq\Sigma\sqcup\{A,B\}$ with $A,B$ ...
Noah Schweber's user avatar
4 votes
1 answer
412 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 ...
Léreau's user avatar
  • 211
3 votes
0 answers
119 views

Question on the model completeness of the real field expanded by restricted Pfaffian functions

Currently I'm reading "Model completeness results for expansions of the ordered field of real numbers by restricted Pfaffian functions and the exponential function" by Wilkie, and I do not ...
Bytegear's user avatar
  • 123
3 votes
1 answer
336 views

Dehornoy's proof that the application of two elementary embeddings is an elementary embedding

What is meant by the statement and the proof of Lemma 3.2 in Chapter XII of Dehornoy's book Braids and Self-Distributivity? That lemma states "Assume that $j_1$ and $j_2$ are elementary ...
kdog's user avatar
  • 245
3 votes
0 answers
182 views

A restricted form of the inner model hypothesis

Previously asked and bountied at MSE, with slight difference. To keep things relatively simple I'm presenting a somewhat-butchered version of the IMH; for more details, see S.-D. Friedman, Internal ...
Noah Schweber's user avatar
5 votes
1 answer
247 views

Can the forcing-absolute fragment of SOL have a strong Lowenheim-Skolem property?

Previously asked and bountied at MSE: Let $\mathsf{SOL_{abs}}$ be the "forcing-absolute" fragment of second-order logic - that is, the set of second-order formulas $\varphi$ such that for ...
Noah Schweber's user avatar
5 votes
1 answer
244 views

Does there always exist a categorical extension of $ZFC_2$ with no set models?

$ZFC_2$, i.e. second-order Zermelo-Fraenkel set theory with Choice, has only one proper class model upto isomorphism, namely $V$. But it may or may not also have set models. If $V$ has no ...
Keshav Srinivasan's user avatar
5 votes
1 answer
553 views

Can there be no "surprisingly averageable" second-order sentences?

Say that a second-order sentence $\varphi$ is averageable iff there exists some infinite cardinal $\kappa$ and some nonprincipal ultrafilter $\mathcal{U}$ on $\kappa$ such that for every $\kappa$-...
Noah Schweber's user avatar
6 votes
1 answer
371 views

Poset of automorphism groups of variants of a structure

Say that two structures $\mathfrak{A},\mathfrak{B}$ in possibly different finite languages are parametrically equivalent - and write "$\mathfrak{A}\approx\mathfrak{B}$" - iff they have the ...
Noah Schweber's user avatar
8 votes
1 answer
386 views

Does "agreement on cardinalities" imply second-order elementary substructurehood?

Say that a logic $\mathcal{L}$ satisfies the weak test property iff for all $\mathfrak{A}\subseteq\mathfrak{B}$ we have $(1)\implies(2)$ below: For each $\mathcal{L}$-formula $\varphi$ with ...
Noah Schweber's user avatar
3 votes
0 answers
129 views

Equivalence of category of internal groups and the category of groups

Is the category of internal groups in set equivalent to the category of groups or isomorphic to it or are they just equal? When we define an internal group in Set since the product is unique only up ...
amir homayoun Nejah's user avatar
6 votes
1 answer
218 views

Sharp Craig interpolation theorem for $L_{\omega_1 \omega}$

I’d like to know if a sharp version of Craig’s interpolation theorem for $L_{\omega_1 \omega}$ is already known or exists in the literature. By a “sharp” version of this theorem, I mean something like ...
Rachael Alvir's user avatar
10 votes
0 answers
319 views

Extending models of topological set theory

$\mathsf{GPK_\infty^+}$ is an alternative set theory in which we have comprehension for formulas which are positive in a certain sense; see the SEP article for more detail (or this MO post, which ...
Noah Schweber's user avatar
17 votes
0 answers
1k views

Non-rigid ultrapowers in $\mathsf{ZFC}$?

Originally asked and bountied at MSE: Question: Can $\mathsf{ZFC}$ prove that for every countably infinite structure $\mathcal{A}$ in a countable language there is an ultrafilter $\mathcal{U}$ on $\...
Noah Schweber's user avatar
3 votes
0 answers
208 views

Comparing classes of possible ultraproducts

This is tangentially related to this recent question of mine. Given nonprincipal ultrafilters $\mathcal{U},\mathcal{V}$ on sets $X,Y$, say $\mathcal{U}\sqsubseteq\mathcal{V}$ iff every finite ...
Noah Schweber's user avatar
7 votes
1 answer
354 views

Compatibility of Łośian phenomena in second-order logic

(Throughout, all ultrafilters are nonprincipal.) Given a property $P$ - really, a sentence in some appropriate logic - say that a ultrafilter $\mathcal{U}$ on a cardinal $\kappa$ averages $P$ iff for ...
Noah Schweber's user avatar
5 votes
1 answer
163 views

Possible values of "Kripke rank" for formulae in IPL

Fix a (countable) set $\mathcal{P}$ of atomic propositional variables. Recall a Kripke model $\mathcal{K}$ for intuitionistic propositional logic (IPL) consists of: A preorder $(W,\leq)$ For each $w \...
Jordan Mitchell Barrett's user avatar
2 votes
1 answer
147 views

Is adding all sentences true of terms in skolemized theory conservative?

Suppose I have a (incomplete) theory $T$ (e.g. PA) which I skolemize to get a theory $T_S$ in the expanded language. I now build $T'$ by adding to $T_S$ any sentence $(\forall x)\phi(x)$ where I can ...
Peter Gerdes's user avatar
  • 2,551
7 votes
0 answers
279 views

Generic behavior of "polynomialish" models of $\mathsf{Q}$

(This question was originally asked and bountied at MSE - with different notation, some more explicit arguments, and topology in place of forcing.) Suppose $\mathcal{R}=(R_i)_{i\in\mathbb{N}}$ is a ...
Noah Schweber's user avatar
3 votes
0 answers
175 views

Can we interpret ZFC in GEM?

I have long held similar views as put forth here. As professor Hamkins points out though, $(M,\subseteq)$ is insufficient to model most of mathematics. However, this is unsatisfactory to me, as this ...
tox123's user avatar
  • 416
7 votes
0 answers
151 views

Is there a complete characterization of hyperimaginaries in $\mathsf{DLO}$?

Recall that in a first-order theory $T$, a hyperimaginary is an equivalence class of some type-definable equivalence relation $E(x,y)$ (with $x$ a possibly infinite tuple of parameters). The $E$-...
James Hanson's user avatar
  • 10.3k
8 votes
1 answer
339 views

Are these theories of real and complex number biinterpretable?

Let $T_R$ be the first-order theory of real closed fields. This is precisely the theory over the language $\{0,1,+,\times\}$ such that the theorems are the formulas that hold in $\Bbb R$. It can be ...
Oscar Cunningham's user avatar
1 vote
1 answer
252 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 ...
Noah Schweber's user avatar
5 votes
0 answers
286 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 ...
Corey Bacal Switzer's user avatar
5 votes
0 answers
156 views

Axiomatizability of image of functor

Let $\sigma$ and $\tau$ be first-order languages and let $S$ resp. $T$ be theories (sets of sentences) for $\sigma$ resp. for $\tau$ ($S$ and $T$ possibly empty). Let $\mathcal C$ resp. $\mathcal D$ ...
Daniel W.'s user avatar
  • 365
5 votes
1 answer
665 views

Quantifier elimination for abelian groups

In the Wikipedia article (https://en.wikipedia.org/wiki/Quantifier_elimination#cite_note-4) it is said that every abelian group has quantifier elimination property and a long old paper of W. Szmielew ...
Sh.M1972's user avatar
  • 2,183
6 votes
1 answer
357 views

Failure of "directedness" for second-order logic?

Say that a logic $\mathcal{L}$ is directed iff whenever $\mathfrak{A}\equiv_\mathcal{L}\mathfrak{B}$ there is some $\mathfrak{C}$ with $\mathcal{L}$-elementary substructures $\mathfrak{A}'\...
Noah Schweber's user avatar
4 votes
1 answer
129 views

Do almost-point-transitive algebras generate almost-point-transitive varieties?

Say that an algebra $\mathfrak{A}$ (in the sense of universal algebra) is point-transitive iff for every $a,b\in\mathfrak{A}$ there is a $\pi\in Aut(\mathfrak{A})$ with $\pi(a)=b$. While genuinely ...
Noah Schweber's user avatar
7 votes
1 answer
262 views

Is $\mathbb{Q}$ "equivalent" to a structure with transitive automorphism group action?

Say that structures $\mathfrak{A},\mathfrak{B}$ with the same underlying set are parametrically equivalent iff every primitive relation/function in one is definable (with parameters) in the other. For ...
Noah Schweber's user avatar
18 votes
1 answer
1k views

A topological version of the Lowenheim-Skolem number

This is a continuation of an MSE question which received a partial answer (see below). Given a topological space $\mathcal{X}$, let $C(\mathcal{X})$ be the ring of real-valued continuous functions on $...
Noah Schweber's user avatar
12 votes
2 answers
900 views

Is this definability principle consistent?

(Below I'm thinking only about computably axiomatizable set theories extending $\mathsf{ZFC}$ which are arithmetically, or at least $\Sigma^0_1$-, sound.) Say that a theory $T$ is omniscient iff $T$ ...
Noah Schweber's user avatar
0 votes
1 answer
121 views

An infinite Leibnizian structure in a finite language with precisely $n$ definable elements

This question was inspired by Joel David Hamkins's excellent question on Leibnizian structures with no definable elements. Let $n$ be a positive integer. Is there an infinite structure in a finite ...
user107952's user avatar
  • 2,063
9 votes
1 answer
396 views

On a result by Rubin on elementary equivalence of homeomorphism groups and homeomorphisms of the underlying spaces

In the known paper On the reconstruction of topological spaces from their group of homeomorphisms by Matatyahu Rubin several deep reconstruction theorems of the form "if $X$ and $Y$ are ...
Alessandro Codenotti's user avatar
2 votes
0 answers
98 views

Name for the theory of words with equal length, prefix, successors

I've worked with this theory for a while, but I've never been quite sure what to call it: $$(\Sigma^*, =_{el}, \preceq, (S_a)_{a \in \Sigma})$$ Where $\Sigma^*$ is the set of finite words on finite ...
TomKern's user avatar
  • 429
7 votes
0 answers
293 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 ...
Noah Schweber's user avatar
2 votes
1 answer
140 views

Is there a lower bound on the size of a supertransitive model of ZFC?

In a posting to mathstackexchange I've alluded to the concept of supertransitive model. Now $M$ is a supertransitive model of a set $Q$ of first order sentences, denoted by $M \models^{sptr} Q$, is ...
Zuhair Al-Johar's user avatar
25 votes
2 answers
1k views

Detecting uncountable cardinals in $(\mathbb{R};+,\times,\mathbb{N})$

For a structure $\mathcal{X}=(X;...)$, say that a cardinal $\kappa$ is $\mathcal{X}$-detectable iff there is some sentence $\varphi$ in the language of $\mathcal{X}$ together with a fresh unary ...
Noah Schweber's user avatar
0 votes
0 answers
73 views

Binary relational structures in which all binary relations are equivalence relations

I’m interested in (finite) binary relational structures (i.e. relational structures with only unary and binary relations) in which all binary relations are equivalence relations. Is there a name for ...
Victor's user avatar
  • 655
9 votes
1 answer
453 views

Are there ill-founded "maximally wide" models of $\mathsf{ZFC}$?

Throughout assume $\mathsf{ZFC}$ + "There is a proper class of inaccessible cardinals." I'm also happy to strengthen the large cardinal hypothesis if that would help. Say that a model $M\...
Noah Schweber's user avatar
4 votes
1 answer
189 views

Sizes of "nearly amorphous" models

Say that a structure $\mathcal{M}$ is amorphic iff for every finite $\overline{a}\in\mathcal{M}$ and bi-infinite $X\subseteq\mathcal{M}$ there is some automorphism $\alpha\in Aut(\mathcal{M})$ fixing $...
Noah Schweber's user avatar
38 votes
3 answers
3k views

Can one show that the real field is not interpretable in the complex field without the axiom of choice?

We all know that the complex field structure $\langle\mathbb{C},+,\cdot,0,1\rangle$ is interpretable in the real field $\langle\mathbb{R},+,\cdot,0,1\rangle$, by encoding $a+bi$ with the real-number ...
Joel David Hamkins's user avatar
4 votes
0 answers
207 views

Model theory and dynamical system (open problems)

I am curious about the open problems which are between model theory and dynamical system. I mean the open problems that are interesting for both groups and there are some evidences showing there might ...
Alex Israel's user avatar
2 votes
1 answer
217 views

Second-order strong minimality and amorphousness, take 2

Recently I asked a question about whether a second-order analogue of strong minimality could correspond to amorphous satisfiability (= having a model whose underlying set cannot be partitioned into ...
Noah Schweber's user avatar
7 votes
2 answers
662 views

Can second-order logic identify "amorphous satisfiability"?

Recall that a set is amorphous iff it is infinite but has no partition into two infinite subsets. I'm interested in the possible structure (in the sense of model theory) which an amorphous set can ...
Noah Schweber's user avatar
2 votes
0 answers
209 views

When is a $\Sigma_n$ Skolem hull a proper submodel?

For $M$ an amenable structure and $X \subset M$, the $\Sigma_n$ Skolem hull of $X$ is a $\Sigma_n$-elementary submodel of $M$. That is, as presentend in Devlin, Constructibility, pp. 85-88, for $h_n$ ...
Johan's user avatar
  • 501
6 votes
1 answer
149 views

a filter of subsets intersecting the cartesian power of each infinite subset

Is the following filter known in set theory, and does it have a name ? For $k=1$ it is the filter of cofinite subsets. Fix a natural number $k$ and a linear order $I$. Define a filter on the set of ...
user254885's user avatar
4 votes
0 answers
102 views

Computably saturated Skolem hulls of Morley sequences in $\mathsf{PA}$

Recall that a model $M$ of a first-order theory $T$ (in a computable language $\mathcal{L}$) is computably saturated if for every finite tuple $\bar{a} \in M$ and every computable partial type $\Sigma(...
James Hanson's user avatar
  • 10.3k
20 votes
1 answer
1k views

Does sine interact equationally with addition alone?

$\DeclareMathOperator\Eq{Eq}\DeclareMathOperator\Th{Th}$Originally asked at MSE without success: For a structure $\mathcal{A}$ whose signature only contains function and constant symbols, let $\Eq(\...
Noah Schweber's user avatar

1
4 5
6
7 8
25