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
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, ...
Noah Schweber's user avatar
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 ...
Yoneda Lemma's user avatar
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 ...
tox123's user avatar
  • 416
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$...
Noah Schweber's user avatar
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 ...
Noah Schweber's user avatar
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$ ...
user107952's user avatar
  • 2,063
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(\...
Guozhen Shen's user avatar
  • 1,288
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&...
Noah Schweber's user avatar
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 ...
user107952's user avatar
  • 2,063
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}...
Taras Banakh's user avatar
  • 40.8k
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 ...
TomKern's user avatar
  • 429
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 ...
Noah Schweber's user avatar
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 ...
TomKern's user avatar
  • 429
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] : ...
Zuhair Al-Johar's user avatar
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 ...
Zuhair Al-Johar's user avatar
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 ...
Zuhair Al-Johar's user avatar
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 ...
Noah Schweber's user avatar
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\...
Noah Schweber's user avatar
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}$ ...
Noah Schweber's user avatar
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 ...
THC's user avatar
  • 4,313
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 ...
Peter LeFanu Lumsdaine's user avatar
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 ...
Noah Schweber's user avatar
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 ...
Noah Schweber's user avatar
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}...
Noah Schweber's user avatar
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 ...
tox123's user avatar
  • 416
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). ...
Emil Jeřábek's user avatar
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 ...
Noah Schweber's user avatar
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 ...
Noah Schweber's user avatar
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 "$\...
Noah Schweber's user avatar
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 ...
Noah Schweber's user avatar
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 $...
Danielle Ulrich's user avatar
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 ...
Sh.M1972's user avatar
  • 2,183
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-...
Luvath's user avatar
  • 145
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 $...
Luvath's user avatar
  • 145
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-...
Zuhair Al-Johar's user avatar
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$ ...
Noah Schweber's user avatar
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}(...
Noah Schweber's user avatar
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) ...
Joel David Hamkins's user avatar
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^{\...
Curious's user avatar
  • 301
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 ...
Noah Schweber's user avatar
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 ...
Noah Schweber's user avatar
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 $\...
Binary198's user avatar
  • 704
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 ...
Binary198's user avatar
  • 704
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)$, ...
Joel David Hamkins's user avatar
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 ...
Geoffrey Irving's user avatar
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)...
Joel David Hamkins's user avatar
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)....
Noah Schweber's user avatar
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 ...
James Hanson's user avatar
  • 10.3k
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, ...
Mirco A. Mannucci's user avatar
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 ...
Florian Felix's user avatar

1 2 3
4
5
25