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
242 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 ...
user avatar
3 votes
1 answer
53 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 ...
user avatar
3 votes
1 answer
185 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 ...
user avatar
1 vote
0 answers
54 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 \...
user avatar
  • 301
1 vote
1 answer
51 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 $\...
user avatar
  • 301
-5 votes
1 answer
192 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 ...
user avatar
6 votes
1 answer
133 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{...
user avatar
  • 6,354
3 votes
2 answers
258 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 ...
user avatar
2 votes
0 answers
150 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 ...
user avatar
  • 227
3 votes
1 answer
219 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 ...
user avatar
6 votes
0 answers
183 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 ...
user avatar
6 votes
0 answers
75 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^...
user avatar
  • 6,354
2 votes
1 answer
115 views

When does $\Pi_2$-reflection on $X$ fail to imply iterated $\Pi_1$-reflection on $X$?

Let lowercase Greek letters denote ordinals. Recall from Richter and Aczel's "Inductive definitions and reflecting properties of admissible ordinals", for a set of formulae $\Gamma$ and a ...
user avatar
  • 293
8 votes
1 answer
191 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 ...
user avatar
11 votes
1 answer
318 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 ...
user avatar
  • 1,193
5 votes
0 answers
111 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 ...
user avatar
5 votes
1 answer
222 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_\...
user avatar
5 votes
0 answers
185 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 ...
user avatar
4 votes
2 answers
228 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$?
user avatar
5 votes
0 answers
145 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 ...
user avatar
3 votes
1 answer
136 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\...
user avatar
4 votes
2 answers
169 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 ...
user avatar
7 votes
2 answers
389 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 ...
user avatar
4 votes
1 answer
124 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). ...
user avatar
  • 32.2k
12 votes
1 answer
340 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 ...
user avatar
18 votes
0 answers
258 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 ...
user avatar
  • 6,354
12 votes
0 answers
327 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; ...
user avatar
  • 21.7k
6 votes
0 answers
219 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 ...
user avatar
4 votes
0 answers
139 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 $\...
user avatar
17 votes
1 answer
547 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$ ...
user avatar
4 votes
0 answers
169 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 ...
user avatar
0 votes
1 answer
100 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 ...
user avatar
9 votes
0 answers
171 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 "...
user avatar
4 votes
0 answers
257 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}$-...
user avatar
6 votes
0 answers
217 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 ...
user avatar
12 votes
4 answers
2k 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)....
user avatar
  • 185
12 votes
0 answers
303 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 (...
user avatar
  • 14.5k
4 votes
1 answer
234 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 ...
user avatar
6 votes
1 answer
202 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,\...
user avatar
4 votes
2 answers
256 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 ...
user avatar
  • 16.7k
11 votes
1 answer
347 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$ ...
user avatar
3 votes
0 answers
308 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 ...
user avatar
  • 191
3 votes
0 answers
113 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 ...
user avatar
  • 123
3 votes
1 answer
298 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 ...
user avatar
  • 235
3 votes
0 answers
173 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 ...
user avatar
5 votes
1 answer
197 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 ...
user avatar
5 votes
1 answer
199 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 ...
user avatar
4 votes
1 answer
355 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$-...
user avatar
4 votes
1 answer
306 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 ...
user avatar
7 votes
1 answer
334 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 ...
user avatar

1
2 3 4 5
20