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
6
votes
1
answer
299
views
When can interpretations be "optimized"?
To make this more readable, I've put some definitions/conventions at the end of this question.
I'm interested in when a given interpretation isn't "missing any information." Specifically, ...
3
votes
0
answers
96
views
Decidability of theory of modules over a ring of finite representation type
I have read from Mike Prest's model theory for modules (London lecture note series) chapter 17 that a Ring of finite representation type has a decidable theory of modules. Here decidability was ...
5
votes
1
answer
196
views
When is an elementary subclass reflective?
Consider an elementary class, $K$, of some $\mathcal{L}$-theory, $T$ equipped with the usual $\mathcal{L}$-structure homomorphisms. (Not elementary embeddings, which elementary classes are more ...
10
votes
1
answer
246
views
Can we always "sharpen" interpretations?
For the purposes of this question, a $T$-interpretation with arity $n$ will be a tuple $\Phi=(\delta,\eta,F)$ where
$\delta$ and $\eta$ are individual formulas of arity $n$ and $2n$ respectively,
$T$...
4
votes
1
answer
142
views
Source on equality-free second-order logic (nontrivially construed)
Throughout I'm only interested in the standard semantics for second-order logic, and all structures/languages are relational for simplicity.
If defined naively, second-order logic without equality is ...
7
votes
1
answer
444
views
Are no infinite subsets of the set of all propositional atoms definable in this structure, even with parameters?
I asked this on Math Stack Exchange, but apparently no one paid attention to it. So, I am asking it again, filling in the background necessary to understand it.
Consider a countably infinite set $P$ ...
2
votes
1
answer
89
views
Why every $\Sigma_1^1(\mathrm{mon})$ sentence true of $\omega$ is also true of $\omega+\zeta$?
A $\Sigma_1^1(\mathrm{mon})$ sentence means an existential monadic second-order sentence,
$\omega=\langle\mathbb{N},<\rangle$, and $\zeta=\langle\mathbb{Z},<\rangle$.
Why every $\Sigma_1^1(\...
7
votes
1
answer
336
views
How hard is it to get "absolutely" no amorphous sets?
A beautiful and surprising (to me at least) result around the axiom of choice is that, while full $\mathsf{AC}$ is preserved by forcing, a model of $\mathsf{ZF}$ + "There are no amorphous sets&...
3
votes
1
answer
258
views
What is an axiomatization of the equality-free theory of antisymmetric relations?
An antisymmetric relation is defined as a binary relation $R$ on a set $S$ such that $(xRy \land yRx) \rightarrow x=y$, for all $x,y$ in $S$. Certainly, they can't be defined in first-order logic ...
6
votes
1
answer
271
views
The algebraic structure of a line in a (Tarski) plane
By a Tarski plane (resp. plane) I understand a mathematical structure $(X,B,\equiv)$ consisting of a set $X$, a ternary betweenness relation $B\subseteq X^3$ and the 4-ary congruence relation ${\equiv}...
7
votes
1
answer
225
views
What is known about first order logic of $\mathbb{N}$ with + and a unary predicate?
In "Weak Second-Order Arithmetic and Finite Automata", Büchi claims that the first order theory of $\mathbb{N}$ with + and a predicate for recognizing powers of 2 ($Pw_2$) is expressively ...
5
votes
0
answers
117
views
Can the equational theory of commutative rings be "unpacked" from the equational theory of exponentiation?
Below, I'll use "$\approx$" for the equality symbol in an equation, as opposed to "actual" equality.
Suppose $\mathcal{V}$ is a variety (in the sense of universal algebra) in the ...
0
votes
0
answers
58
views
First-order logics expressively equivalent to the computable languages
There is a really nice theorem that the subsets of $(\Sigma^*, =_{el}, \preceq, (S_a)_{a \in \Sigma})$ definable in first-order logic are exactly the regular sets.
Where:
$\Sigma^*$ is the set of ...
0
votes
0
answers
105
views
Is there a clear inconsistency with this general assertion about n-internalizations of external bijections?
Define: $j^1[x]= j(x) \\ j^{n+1}[x] = \{j^n[y]: y \in x\} \\ j^{-n}[x] = \{y : j^n[y] \in x\}$
Define:
$n=1,2,3,...\\ _n\mathsf{Forth}_j(S)=\{j^n[x] : x \in S\} \\ _n\mathsf{Back}_j(S)=\{j^{-n}[x] : ...
1
vote
1
answer
142
views
Can we have such an infinite descending sequence of functions with prior ones inside their successors?
Let $M$ be some non-well-founded model of $\sf ZF$, can we have a sequence $(S_n)_{n \in \mathbb N}$ of nonempty sets in $M$, where each $S_n \subset \mathcal P(S_{n+1})$; and such that there exists ...
1
vote
0
answers
159
views
Can we have a proper class of infinitely descending infinite ordinals?
Working in $\sf ZF-Reg.$, can we have a transitive model $M$ of $\sf ZF$ such that there exists a proper class (i.e. a subset of $M$ that is not an element of $M$) of infinitely descending infinite ...
8
votes
0
answers
164
views
Does determinacy imply unravellability for the Borel sets (over a weak base theory)?
As far as I know, the only way we currently know how to prove Borel determinacy in $\mathsf{ZFC}$ is to go through unravelability (a rather technical property whose definition can be found in Martin's ...
7
votes
0
answers
304
views
Is there a "nice" inner model for $\mathsf{ZF}$ + a Dedekind-finite infinite set of reals?
Below, given a formula $\varphi$ which $\mathsf{ZF}$ proves defines a set of reals and an inner model $W$, I'll write "$\varphi^W$" and "$L(\varphi^W)$" for "$\{x:W\models\...
5
votes
0
answers
180
views
"Very $L$-like" models, part 1: large cardinals
(The original version of this question was much narrower and less natural; but see the edit history if interested.)
Say that a good logic is a regular logic $\mathcal{L}$ containing $\mathsf{FOL}$ ...
2
votes
1
answer
196
views
Minor Lefschetz principle
I once read (I think) the following equivalent formulation of the Minor Lefschetz principle:
If an elementary sentence holds for one algebraically closed field,
then it holds for every algebraically ...
9
votes
0
answers
265
views
Is “simplicity is elementary” still hard? (Felgner’s 1990 theorem on simple groups, and subsequent work)
I came across a reference in this MathOverflow answer to an intriguing result of Ulrich Felgner [1]: among finite non-Abelian groups, the property of being simple is first-order definable. According ...
4
votes
0
answers
283
views
Is this "finite-ish combinatorics" reflection principle consistent?
This question is an attempt to chisel away at this earlier question of mine, which in retrospect may be rather intractable. Throughout, we work in $\mathsf{ZF}$.
Briefly (see the linked question for ...
6
votes
0
answers
217
views
The number of countable models with determinacy
Throughout, work in $\mathsf{ZF+DC+AD_\mathbb{R}}$.
Given a theory $T$, let $[T]$ be the set of isomorphism types of models of $T$ with domain $\subseteq\omega$. This question is an outgrowth of this ...
8
votes
1
answer
354
views
On the strength of higher-logic analogues of $\mathsf{ZFC}$ + Montague's Reflection Principle
Throughout, I work in $\mathsf{MK}$ in order to be able to conveniently quantify over logics; if one prefers, we can restrict attention to (say) $\Sigma_{17}$-definable logics and work in $\mathsf{ZFC}...
6
votes
0
answers
257
views
Are there applications of model theory to category theory?
There seems to be a decent amount of literature connecting category theory and model theory. (See for instance the paper Classifying Spaces and the Lascar Group). But for the most part, it seems to be ...
20
votes
1
answer
677
views
Model-completeness of real exponential fields
Let $\mathbb R$ denote the ordered field of the reals (in a language with $+$, $\cdot$, and possibly $<$, $0$, $1$, or $-$; these are all existentially definable in terms of $+$ and $\cdot$ alone).
...
5
votes
1
answer
197
views
Upwards-fragility of inaccessibles (again)
Although self-contained, this question is a follow-up to this earlier one. Also, thanks to Fedor Pakhomov for fixing a trivial early version of this question!
Work in $\mathsf{ZFC}$ + "There is a ...
5
votes
1
answer
172
views
Fragility of large cardinals with respect to transitive end extensions
To motivate things, let me start with a special case of the question I'm interested in. Let $\mathsf{In}(x)\equiv$ "$x$ is an inaccessible cardinal."
Question 1: Is it consistent with the ...
5
votes
0
answers
241
views
How strong is this "modal definability principle"?
Throughout, we work in the class theory $\mathsf{MK}$ (although I'm open to tweaking this), "logic" means "set-sized logic whose semantics is definable over $V$," and "$\...
6
votes
1
answer
159
views
Are ordered and unordered pairing functions "definably equivalent?"
This question is basically a lift to MO of a part of an old MSE question. That question asked, roughly, for the model-theoretic relationship between ordered and unordered pairing functions. To keep ...
4
votes
0
answers
156
views
Invariant Spaces of Hypergraphs
The following arose from a question in model theory (specifically in the model theory of modules).
Fix an arity $k$. Let $[\mathbb{Q}]^k$ denote the set of all subsets of $\mathbb{Q}$ of cardinality $...
4
votes
1
answer
121
views
Logical generators of groups and $\mathrm{Aut}$-bases
An element $s$ of a group $G$ is a logical generator of $G$ iff every element of $G$ can be defined in the first order language of groups with $s$ as a parameter. In this case we may call $G$ a ...
9
votes
1
answer
718
views
Is a complex algebraic set with a Zariski dense subset of algebraic points already defined over the algebraic numbers?
This is a cross-post! For the original post on SE (9 upvotes, no answer) see:
https://math.stackexchange.com/questions/4475853/is-a-complex-algebraic-set-with-a-zariski-dense-subset-of-algebraic-...
5
votes
1
answer
370
views
Does the main theorem of elimination theory with $\mathbb{Z}$-coefficients imply that projective varieties are complete?
I have a question concerning the completeness of projective varieties.
Let $k$ be an algebraically closed field. By the "main theorem of elimination theory" I mean the following result:
Let $...
0
votes
1
answer
149
views
Can we have all classes that can be partitioned into non-singleton finite sets, be sets?
Working in a suitable extension of $\sf ZF-Reg.$, can we have a transitive model $M$ of $\sf ZF-Reg.$ such that for every set in $M$ there is a partition on it in $M$ all compartments of which are non-...
6
votes
1
answer
236
views
Can there be no complexity bound on the definable elementary $V\rightarrow M$?
This starts with a vaguely-recalled result (which may be false!): that if $\mathcal{U}$ is a measure on the least measurable cardinal $\kappa$, then every elementary $j: L[\mathcal{U}]\rightarrow M$ ...
3
votes
1
answer
238
views
Is there a maximal fragment of FOL with "no negation at all?"
Say that a logic $\mathcal{L}$ is nowhere-negative iff for every $\mathcal{L}$-theory $T$ there is a structure $\mathfrak{A}$ such that $$\mathit{Th}_\mathcal{L}(\mathfrak{A})=\mathit{Ded}_\mathcal{L}(...
19
votes
1
answer
1k
views
Is the theory of a partial order bi-interpretable with the theory of a pre-order?
A partial order relation $\leq$ on a set $A$ is a binary relation that is reflexive, transitive, and antisymmetric.
A preorder relation $\unlhd$ (also sometimes known as a quasi order or pseudo order) ...
7
votes
1
answer
465
views
Is there any theory of "étale cohomology" with algebraic coefficients?
For simplicity, I will restrict attention to untwisted coefficients.
Let $k$ be a finite field of characteristic $p$, and $\ell\ne p$ prime. Can one define a cohomology theory with $\mathbb{Q}_\ell^{\...
19
votes
0
answers
554
views
What algebraic properties are preserved by $\mathbb{N}\leadsto\beta\mathbb{N}$?
Given a binary operation $\star$ on $\mathbb{N}$, we can naturally extend $\star$ to a semicontinuous operation $\widehat{\star}$ on the set $\beta\mathbb{N}$ of ultrafilters on $\mathbb{N}$ as ...
7
votes
1
answer
406
views
Is the equational theory of this "orthocentrish" algebra finitely based?
Let $\mathcal{A}$ be the algebra (in the sense of universal algebra) whose underlying set is the four-element set $\{a,b,c,d\}$ and whose structure consists just of the ternary operation $F$ defined ...
1
vote
1
answer
197
views
An extension of Woodin's star axiom
In the proof that Martin's maximum implies (*), the introduction gives the following theorem:
Assume there is a proper class of Woodin cardinals. Then, the following are equivalent:
$(^*)$
For any $\...
1
vote
1
answer
200
views
Minimal models in strong set theories - pt. 2
This is a follow-up to this question.
So, as Noah elucidated (thanks Noah!), whenever $T$ is r.e., $M(T) < \sigma$ ($\sigma$ is the least stable ordinal, i.e. $L_\sigma\prec_{\Sigma_1}L$).
In ...
12
votes
3
answers
848
views
Is there a simple instance of intransitivity for implicit definability?
This question continues the theme of some recent questions on implicit definability.
A relation $R$ is implicitly definable in a first-order structure $M$ if there is a property $\varphi(\dot R)$, ...
22
votes
1
answer
1k
views
Is the set of primes implicitly definable from successor?
An earlier question by Joel David Hamkins asked whether multiplication is implicitly definable in the structure $(\mathbb{N},S)$ of the naturals with successor. Here $R$ is implicitly definable if ...
44
votes
2
answers
4k
views
Is multiplication implicitly definable from successor?
A relation $R$ is implicitly definable in a structure $M$ if there is a formula $\varphi(\dot R)$ in the first-order language of $M$ expanded to include relation $R$, such that $M\models\varphi(\dot R)...
4
votes
0
answers
143
views
Is the orthocenter "(roughly) equationally finitely-based"?
Let $T$ be the "almost everywhere" equational theory of the orthocenter function, "tweaked appropriately" to avoid partiality issues (see this earlier question of mine for details)....
6
votes
0
answers
81
views
Is there an unstable NSOP theory in which all invariant types are coheirs?
There are some first-order theories $T$ with the property that for any $M \models T$, the only $M$-invariant global types are those that are coheirs over $M$ (i.e., finitely satisfiable in $M$). Two ...
6
votes
1
answer
391
views
Joyal arithmetic universes and the Box operator
Last month @godelian, alias Christian Espíndola, in a FOM post has mentioned Joyal's proof of Godel's second incompleteness via the so-called Arithmetic Universes, introduced by Joyal around 1973, ...
2
votes
1
answer
227
views
Example of a bounded imperfect PAC field that is not separably closed
How do you construct a bounded (meaning there are only finitely many separable finite extensions of any given degree) imperfect pseudo-algebraically closed field that is not separably closed? I assume ...