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.
1,203
questions
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,\...
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 ...
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$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$-...
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 ...
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 ...
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 ...
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 ...
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 ...
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 $\...
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 ...
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 ...
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 \...
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 ...
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 ...
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 ...
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$-...
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 ...
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 ...
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 ...
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$ ...
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 ...
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}'\...
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 ...
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 ...
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 $...
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$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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\...
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 $...
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 ...
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 ...
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 ...
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 ...
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$ ...
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 ...
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(...
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(\...