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
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}$, ...
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 ...
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 ...
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)
...
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 ...
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 ...
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) \\
\...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 \...
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 $\...
-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 ...
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{...
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 ...
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 ...
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 ...
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 ...
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^...
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 ...
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 ...
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 ...
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_\...
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 ...
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$?
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 ...
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\...
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 ...
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 ...
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). ...
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 ...
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 ...
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; ...
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 ...
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 $\...
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$ ...
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 ...
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 ...
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 "...
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}$-...
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 ...
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)....
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 (...
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 ...