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
7 votes
0 answers
281 views

Is there a natural logic in which equality has this weird behavior?

Below, by "logic" I mean "regular logic without equality;" see Badia/Caicedo/Noguera, Maximality of logic without identity. Given a logic $\mathcal{L}$, a structure $\mathfrak{M}$, ...
Noah Schweber's user avatar
9 votes
1 answer
290 views

Equational theory of the orthocenter

Previously asked at MSE: Briefly speaking, I'm looking for a description of the equational theory of the orthocenter function, $\mathsf{orth}$. By $\mathsf{orth}$ I mean the (partial) function sending ...
Noah Schweber's user avatar
7 votes
1 answer
248 views

Algebraic proof that the monoid ring of a torsion-free monoid is reduced

In what follows, I say that a monoid $M$ is torsion-free if the $n$-th power map is injective for all $n \geq 1$. I have a proof of the following result: Claim: if $M$ is a torsion-free commutative ...
Béranger Seguin's user avatar
4 votes
1 answer
152 views

Is there a minimal first-order model that has IP theory?

I'm hoping to (prove that one cannot) find an infinite first-order $\mathcal{M}$ that is: Minimal (All definable subsets of $\mathcal{M}$ are finite or cofinite) IP (has the independence property) ...
Calliope Ryan-Smith's user avatar
5 votes
1 answer
215 views

Does second-order logic satisfy Craig interpolation for second-order languages?

(For simplicity, all languages are relational.) In analogy with first-order languages, say that a second-order language is a set of relation symbols of two kinds: first-order relation symbols and ...
Noah Schweber's user avatar
5 votes
0 answers
115 views

Existence of invariant valuations

Given a field $K$, one can enrich it via a valuation, an automorphism or both structures at the same time in a compatible way. In all of these three cases, the model theory is well-understood (under ...
Simone Ramello's user avatar
3 votes
0 answers
133 views

Why are the sharps of sets of big ordinals not in $\mathcal{P}(\omega)$?

In his talk A Condensed History of Condensation, Welch presents the following recursive sharp function, that is total when all sharps exist: \begin{align*} \# \colon ON &\to \mathcal{P}(ON) \\ \...
Martín S's user avatar
  • 421
11 votes
1 answer
608 views

Are there quantifiers that require multiple "steps" to define?

(Below I conflate quantifiers and quantifier symbols in a couple places for readability; I can change that if that actually makes things less readable.) For the purposes of this question, an $n$-ary ...
Noah Schweber's user avatar
6 votes
0 answers
350 views

How much "finitary combinatorics" can be emulated by an infinite Dedekind-finite set?

Throughout, we work in $\mathsf{ZF}$. Let $[n]=\{1,...,n\}$. Given a set $X$ and a first-order sentence $\varphi$, let $M_X(\varphi)$ be the set of isomorphism types of models of $\varphi$ with ...
Noah Schweber's user avatar
2 votes
0 answers
238 views

Pairs vs. two pieces: is the usual proof model-theoretically-optimal?

(For clarity, I'll use $R,S$ for binary relation symbols and $A,B$ for actual binary relations.) There is an equality between the numbers (up to isomorphism in the appropriate sense) of partitions of ...
Noah Schweber's user avatar
10 votes
3 answers
893 views

Why can we assume a ctm of ZFC exists in forcing

Following Kunen's book, it makes clear that countable transitive models (ctm) exist only for a finite list of axioms of ZFC. So, why can we assume a ctm of the whole ZFC axioms exists and use it as ...
Guest's user avatar
  • 101
6 votes
1 answer
267 views

A "negative" standard system

For $\mathcal{M}$ a (countable) nonstandard model of $\mathsf{PA}$, let $\mathsf{SS}(\mathcal{M})$ be the set of sets of natural numbers coded by elements of $\mathcal{M}$. There are various ways to ...
Noah Schweber's user avatar
9 votes
0 answers
250 views

Can "$\exists\mathcal{X}(R\cong C(\mathcal{X}))$" be expressed in "large" infinitary second-order logic?

Originally asked and bountied at MSE without success: Say that a ring $R$ is spatial iff there is some topological space $\mathcal{X}$ such that $R\cong C(\mathcal{X})$, where $C(\mathcal{X})$ is the ...
Noah Schweber's user avatar
10 votes
1 answer
294 views

How hard must "no high-degree irreducibles" proofs be?

Let $\mathsf{RCF}$ be the usual theory of real closed fields and for $n>2$ let $\theta_n$ be the sentence "No degree-$n$ polynomial is irreducible." Since $\mathsf{RCF}$ is complete, for ...
Noah Schweber's user avatar
5 votes
1 answer
183 views

Persistent finite axiomatizability, relational edition

Say that a finitely axiomatizable first-order theory $T$ (in a finite language $\Sigma$) is persistently finitely axiomatizable iff the set $T_{\mathsf{w/o=}}$ of equality-free $T$-theorems is ...
Noah Schweber's user avatar
5 votes
1 answer
239 views

Free algebras from model theory perspective

Let $\mathbb{V}$ be a non-trivial variety of algebras, and let $F_S\in\mathbb{V}$ be a free algebra on a set $S$. I want to know what is known about the model theory of $F_S$; I know these objects are ...
arunpatel's user avatar
1 vote
0 answers
73 views

Proof of the Local Deduction Theorem, for one of many logics

I'm looking for a proof of the Local Deduction Theorem for any one of many logics. That is, a proof of the statement: $\Sigma \cup \{\phi\} \models \psi$ iff for some positive $n,$ $\Sigma \models \...
Martín S's user avatar
  • 421
2 votes
1 answer
85 views

An exercise in fuzzy logics built from a t-norm [closed]

Consider the following t-norm: $$ a * b = \begin{cases} 2ab, &\quad\text{if }a, b\le1/2\\ \min\{a, b\} &\quad\text{otherwise} \end{cases} $$ We build from it the $\...
Martín S's user avatar
  • 421
-5 votes
1 answer
228 views

Are equinumerous size preserving models of a theory isomorphic?

If by a size preserving model we mean any bijection between any two elements of it is an element of it. Then: is it a thoerem of $\sf ZFC$ that for any theory $T$ any two equinumerous size preserving ...
Zuhair Al-Johar's user avatar
6 votes
1 answer
197 views

How often are forcing extensions of countable computably saturated models of $\mathsf{ZFC}$ computably saturated?

Recall that given a finite language $\mathcal{L}$, we say that an $\mathcal{L}$-structure is computably saturated (or recursively saturated) if for any computable set $\Sigma(\bar{x},y)$ of $\mathcal{...
James Hanson's user avatar
  • 10.3k
4 votes
2 answers
541 views

Tarski's original proof of quantifier elimination in algebraically closed fields

I am currently helping teach a course about foundations of mathematics, which has thus far focused mostly on propositional and first-order logic. As part of the course, the students are each required ...
Martin Skilleter's user avatar
2 votes
0 answers
178 views

Generalized models of set theory

The forcing method can be viewed as building a Boolean-valued model of set theory. Some generalizations include Heyting algebra/sheaf/lattice-valued model. However, it seems these generalizations are ...
Kushi's user avatar
  • 227
3 votes
1 answer
285 views

Why does the second smallest worldly cardinal believe the smallest worldly cardinal is worldly?

It is known that the property of being a worldly cardinal is not absolute (a cardinal $\kappa$ is worldly iff $V_{\kappa} \vDash \textsf{ZFC}$). See here and here for more. This said, it is the case ...
aidangallagher4's user avatar
6 votes
0 answers
204 views

Fragments of infinitary logic with a weak definability property

For a countable admissible ordinal $\alpha$, let $\mathcal{L}_\alpha=\mathcal{L}_{\infty,\omega}\cap L_\alpha$ and let $\equiv_\alpha$ be the corresponding elementary equivalence relation. Say that ...
Noah Schweber's user avatar
6 votes
0 answers
98 views

Does stable embeddedness improve two-cardinal behavior?

Let $T$ be a first-order theory with two designated unary predicates $P$ and $Q$. We'll say that $P$ is bounded over $Q$ if for every $\kappa$, there is a $\lambda$ such that if $M \models T$ and $|Q^...
James Hanson's user avatar
  • 10.3k
9 votes
1 answer
265 views

Transfinitely iterating the Levi-Civita, Hahn or Puiseux constructions

This question was originally asked at MSE but seems too advanced, so I'm reposting it here. In short, the idea is that many constructions for non-Archimedean fields can naturally be iterated, in some ...
Mike Battaglia's user avatar
11 votes
1 answer
401 views

Is there a finitely axiomatizable class of structures whose equality-free theory is not finitely axiomatizable?

This was originally an MSE question, but I was told to ask it on MathOverflow. Does there exist a class $C$ of $L$-structures for a finite signature $L$, which is finitely axiomatizable in first-order ...
user107952's user avatar
  • 2,063
6 votes
0 answers
244 views

Failure of Łoś-Tarski preservation theorem for some equality-free logic

A famous Łoś-Tarski preservation theorem is that first-order (FO) sentences that are preserved under substructures (resp. superstructures) are precisely the universal (resp. existential) first-order ...
Bartosz Bednarczyk's user avatar
7 votes
2 answers
463 views

Can countable ordinals start gaps of every order in the constructible universe?

Define "$\alpha$ starts a gap of order $n+1$ and length $\beta$" iff $\mathcal P^n(\omega)\cap (L_{\alpha+\beta}\setminus L_\alpha)=\emptyset\land\forall\gamma\in\alpha: L_\alpha\setminus L_\...
Boris Dimitrov's user avatar
5 votes
0 answers
225 views

Surreal numbers and the ultrafilter lemma

In this question, I asked how to interpret a historical claim made by Conway regarding the potential, if not ideal, use of the surreal numbers for nonstandard analysis. In the comments and answers it ...
Mike Battaglia's user avatar
4 votes
2 answers
285 views

Can local $0^\#$ exists in L?

Assume $0^\#$ exists and there is an inaccessible cardinal. Are there two transitive sets $M,N$ s.t. $M\in N,M\vDash ZF+V=L[0^\#],N\vDash ZF+V=L$?
Reflecting_Ordinal's user avatar
5 votes
0 answers
236 views

Proofs in number theory that involve non-standard models of arithmetic

While reading an introductory text on model theory, I found it interesting that one can reformulate the famous conjectures about twin primes and Mersenne primes in terms of non-standard models of ...
Menander I's user avatar
4 votes
1 answer
193 views

Comparing the first-order theories of different kinds of local rings of a complex variety

Let $X$ be a complex variety containing some point $x$. Then $X$ is naturally a complex-analytic space, and we have an inclusion of rings $\mathbb{C}[X]_x\hookrightarrow\mathbb{C}\{X\}_x\...
Doron Grossman-Naples's user avatar
5 votes
2 answers
229 views

Why does the category of definable sets of $T^\mathrm{eq}$ have coproducts?

For each first-order theory $T$ there is an associated weak syntactic category, sometimes also called "the category of definable sets of $T$" and denoted $\mathrm{Def}(T)$. Also, for each ...
user478652's user avatar
9 votes
2 answers
586 views

A "surnatural numbers" as a largest model of the natural numbers

One characteristic of the surreal numbers is that they are a monster model of the first-order theory of real numbers, according to Joel David Hamkins in this post. Thus they are real-closed, and every ...
Mike Battaglia's user avatar
4 votes
1 answer
169 views

The locale of morphisms vs a morphism to an ultrapower?

I'm fixing some type of structure $\Sigma$ (possibly multi-sorted, with functions symbols and relation symbols, though assuming it single sorted with only relation symbols wouldn't change anything). ...
Simon Henry's user avatar
  • 39.9k
12 votes
1 answer
378 views

Do second-order theories always have irredundant axiomatizations?

It's a standard exercise to show that every countable first-order theory has an irredundant axiomatization. For uncountable first-order theories, the result is much more difficult and was proved by ...
Noah Schweber's user avatar
23 votes
1 answer
446 views

Can a non-standard model $M$ of $\mathsf{ZF}$ contain an internally infinite set that is externally smaller than $\aleph_0^M$?

Cardinalities in non-standard models of $\mathsf{ZF}$ are not generally reflected externally, but certain internal facts about cardinalities are always externally reflected (e.g., any internally ...
James Hanson's user avatar
  • 10.3k
12 votes
0 answers
473 views

Why is it so hard to give examples of differentially closed fields?

The theory of algebraically closed field, say in characteristic zero, and of differentially closed fields (of characteristic zero) have much in common: quantifier elimination and (hence) decidability; ...
Gro-Tsen's user avatar
  • 29.9k
6 votes
0 answers
229 views

Is there a nice(r) counterexample to this strengthening of Tarski's theorem?

Given a regular logic $\mathcal{L}$ and a structure $\mathfrak{A}$ (in a finite relational language $\Sigma$ for simplicity), let $\overline{Th_\mathcal{L}(\mathfrak{A})}$ be the structure defined as ...
Noah Schweber's user avatar
4 votes
0 answers
150 views

How big a "scaffold" does second-order logic need to detect its own equivalence notion?

(Previously asked and bountied at MSE:) Let $\Sigma$ be the language consisting of a single binary relation symbol. Second-order logic can "detect" second-order-elementary-equivalence of $\...
Noah Schweber's user avatar
17 votes
1 answer
605 views

How hard is it to say "not exactly $p$" with a Horn sentence?

EDIT: immediately after bountying the question (whoops ...) I found, while looking for something else entirely, that Sauro Tulipani gave an explicit algorithm for producing a Horn sentence $\varphi_p$ ...
Noah Schweber's user avatar
4 votes
0 answers
171 views

Can SOL characterize its own equivalence notion, without "scaffolding," for graphs?

Consider the following property $(*)_\mathcal{L}$ of a logic $\mathcal{L}$: $(*)_\mathcal{L}:\quad$ There is no $\mathcal{L}$-sentence $\varphi$ such that for all graphs $\mathcal{A},\mathcal{B}$ we ...
Noah Schweber's user avatar
0 votes
1 answer
207 views

Is there a non-standard model of PA computable with infinitary computation?

By the Tennenbaum's theorem, there are no non-standard countable models of Peano Arithmetic that are computable using Turing machines. What about models of infinitary computation like infinite time ...
Jozef Mikušinec's user avatar
10 votes
0 answers
255 views

Classifying cohomology

In his 1973 topos seminar in Buffalo (the tapes are now freely available online!), Grothendieck said: The cohomology of a topos associated to an algebraic structure should be called the "...
LeopSchl's user avatar
  • 133
4 votes
0 answers
279 views

A variant of infinitary equivalence

Let $\Sigma$ be the language consisting of a single binary relation symbol, $R$ (so $\Sigma$-structures are graphs, in the model theory sense). For a logic $\mathcal{L}$, say that an $\mathcal{L}$-...
Noah Schweber's user avatar
6 votes
0 answers
236 views

Existing literature on logics "describing their own equivalence notions"

Say that a regular logic $\mathcal{L}$ is self-equivalence-describing (SED) iff for every finite language $\Sigma$ there is a larger language $\Sigma'$ containing at least $\Sigma$ and two new unary ...
Noah Schweber's user avatar
12 votes
4 answers
3k views

What flavor of set theory is used in model theory?

When I read statements like ‘first order theories can’t control cardinalities of their models’ I wonder, what flavor of set theory is used in a (meta)model theory? (I hope not a naïve set theory, lol)....
tzimie's user avatar
  • 185
12 votes
0 answers
316 views

Sentences preserved under inverse limits

One of the classical theorems of model theory is the Chang-Łos-Suszko preservation theorem that states that the theories formulated in FOL (first order logic) that are preserved under direct limits (...
Ali Enayat's user avatar
5 votes
1 answer
395 views

Height of diamond

Assume $V=L$. Let $\alpha$ be the least ordinal such that there is a $\Diamond_{\omega_1}$-sequence in $L_\alpha$. It's obvious that $\omega_1 < \alpha < \omega_2$. Do we have some better ...
Reflecting_Ordinal's user avatar

1
3 4
5
6 7
25