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,228
questions
1
vote
0
answers
39
views
Comparing semiring of formulas and Lindenbaum algebra
This is motivationally related to an earlier question of mine.
Given a first-order theory $T$, let $\widehat{D}(T)$ be the semiring defined as follows:
Elements of $\widehat{D}(T)$ are equivalence ...
- 20.7k
3
votes
1
answer
125
views
Can we see quantifier elimination by comparing semirings?
This question came up while reading the paper Hales, What is motivic measure?. Broadly speaking, I'm interested in which ideas from motivic measure make sense in arbitrary first-order theories (or ...
- 20.7k
20
votes
1
answer
802
views
Is there a minimal (least?) countably saturated real-closed field?
I heard from a reputable mathematician that ZFC proves that there is a minimal countably saturated real-closed field. I have several questions about this.
Is there a soft model-theoretic construction ...
- 230k
3
votes
1
answer
299
views
Chevalley's theorem on valuation spectra
In the paper On Valuation Spectra (Section 2, Page 176), Huber and Knebusch asserted that: if the ring map $A\to B$ is finitely presented then the associated map of valuation spectra $\mathrm{Spv}(B)\...
- 255
2
votes
0
answers
127
views
On "necessary connectives" in a structure
Given a clone $\mathcal{C}$ over $\{\top,\perp\}$, let $\mathsf{FOL}^\mathcal{C}$ be the version of first-order logic with connectives from $\mathcal{C}$ in place of the usual Booleans. Given a clone $...
- 20.7k
8
votes
1
answer
183
views
Mostowski's absoluteness theorem and proving that theories extending $0^\#$ have incomparable minimal transitive models
This question says that the theory ZFC + $0^\#$ has incomparable minimal transitive models. It proves this as follows (my emphasis):
[F]or every c.e. $T⊢\text{ZFC\P}+0^\#$ having a model $M$ with $On^...
- 1,047
3
votes
0
answers
93
views
Are "equi-expressivity" relations always congruences on Post's lattice?
Given a clone $\mathcal{C}$ over the set $\{\top,\perp\}$, let $\mathsf{FOL}^\mathcal{C}$ be the version of first-order logic with (symbols corresponding to) elements of $\mathcal{C}$ replacing the ...
- 20.7k
-3
votes
1
answer
325
views
Two equivalent statements about formulas projected onto an Ultrafilter
Question 1:
In the same language, let $ X $ be a nonempty set, and let $ \{ (\forall x_{x(i)} f(i)) \ | \ i \in X \} $ be a set of formulas. We use $ x(i) $ to denote the index of the variable on ...
- 47
5
votes
0
answers
174
views
Whence compactness of automorphism quantifiers?
The following question arose while trying to read Shelah's papers Models with second-order properties I-V. For simplicity, I'm assuming a much stronger theory here than Shelah: throughout, we work in $...
- 20.7k
8
votes
0
answers
134
views
Is there a substructure-preservation result for FOL in finite model theory?
It's well-known$^*$ that the Los-Tarski theorem ("Every substructure-preserved sentence is equivalent to a $\forall^*$-sentence") fails for $\mathsf{FOL}$ in the finite setting: we can find ...
- 20.7k
8
votes
0
answers
148
views
Which sentences are "strategically preserved"?
Below, everything is first-order.
Say that a sentence $\varphi$ is strategically preserved iff player 2 has a winning strategy in the following game:
Players 1 and 2 alternately build a sequence of ...
- 20.7k
2
votes
0
answers
204
views
Is there a computable model of HoTT?
Among the various models of homotopy type theory (simplicial sets, cubical sets, etc.), is there a computable one?
Can the negative follow from the Gödel-Rosser incompleteness theorem?
If there is no ...
user507115
17
votes
6
answers
2k
views
Book recommendation introduction to model theory
Next semester I will be teaching model theory to master students. The course is designed to be "soft", with no ambition of getting to the very hardcore stuff. Currently, this is the syllabus....
- 8,475
4
votes
0
answers
110
views
Is there an abstract logic satisfying the Löwenhein-Skolem property for single sentences but not for countable sets of sentences?
An abstract logic satisfies the LS property for single sentences if each satisfiable sentence has a countable model. Similarly, the LS property for countable sets of sentences holds if every ...
- 2,407
5
votes
1
answer
193
views
What is the theory of computably saturated models of ZFC with an *externally well-founded* predicate?
For any model of $M$ of ZFC, we can extend it to a model $M_{ew}$ with an "externally well-founded" predicate $ew$. For $x \in M$, We say that $M_{ew} \vDash ew(x)$ when there is no infinite ...
- 6,298
1
vote
0
answers
98
views
Effortless automated proofs for "simple" formulae?
From small cases to all of them. This is in the spirit of 15 theorem see https://en.wikipedia.org/wiki/15_and_290_theorems
EXAMPLE : Suppose you have the following problem: P(a)
For any fixed non ...
- 1,306
7
votes
1
answer
170
views
Is Presburger arithmetic in stronger logics still complete?
Originally asked at MSE:
Let $\Sigma=\{+,<,0,1\}$ be the usual language of Presburger arithmetic. Given a "reasonable" logic $\mathcal{L}$, let $\mathbb{Pres}(\mathcal{L})$ be the $\...
- 20.7k
3
votes
0
answers
121
views
Comparing two fragments of SOL with the downward Lowenheim-Skolem property
For $S$ a set of (parameter-free) second-order formulas and $\mathfrak{A},\mathfrak{B}$ structures, write $\mathfrak{A}\trianglelefteq^S\mathfrak{B}$ iff $\mathfrak{A}$ is a substructure of $\mathfrak{...
- 20.7k
4
votes
1
answer
172
views
Can we have external automorphisms over intersectional models?
Is the following inconsistent:
By "intersectional" set I mean a set having the intersectional set of every nonempty subset of it, being an element of it.
$\forall S \subset M: S\neq \...
- 10.2k
4
votes
0
answers
159
views
In finite model theory, is "invariant FOL with $\varepsilon$-operator" unavoidably second-order?
Throughout, all structures are finite.
Say that a class of finite structures $\mathbb{K}$ is $\mathsf{FOL}_\varepsilon^\text{inv}$-elementary iff it is the class of finite models of a sentence in the ...
- 20.7k
1
vote
1
answer
551
views
Natural Numbers
Let $L$ be a countable language and $M$ be a model of $L^N$ (the realization of $L$ in the natural numbers $N$) in which every recursive unary relation is expressible. Show that $M$ is not recursive.
- 265
13
votes
1
answer
2k
views
Are some interesting mathematical statements minimal?
Gödel's set $\mathrm{L}$, of constructible sets, decides many interesting mathematical statements, as the Continuum hypothesis and the Axiom of Choice.
Are some interesting mathematical questions, ...
- 3,480
5
votes
1
answer
534
views
The "first-order theory of the second-order theory of $\mathrm{ZFC}$"
$\newcommand\ZFC{\mathrm{ZFC}}\DeclareMathOperator\Con{Con}$It is often interesting to look at the theory of all first-order statements that are true in some second-order theory, giving us things like ...
- 4,857
4
votes
1
answer
324
views
Expressiveness in arithmetic
Let $\mathcal{S}$ be a formal system for arithmetic (e.g. $P$ or $PA$), $f:N^q\rightarrow N^p$ a function of $N^q$ on $N^ p$ and $\alpha(\mathbf{x})$ a formula of $\mathcal{S}$ with $p$ free variables....
- 265
10
votes
1
answer
199
views
Is $(\mathbb R_{\mathrm{an}}, (x\mapsto x^r)_{r\in\mathbb R})$ still the largest known polynomially bounded o-minimal structure so far?
From Chris Miller's paper in 1995, the structure $(\mathbb R_{\mathrm{an}}, (x\mapsto x^r)_{r\in\mathbb R})$,is the largest known polynomially bounded o-minimal structure as of that time. I wonder if ...
- 321
8
votes
0
answers
131
views
What is this quotient of the free product?
Previously asked at MSE. The construction here can generalize to arbitrary algebras (in the sense of universal algebra) in the same signature with the only needed tweak being the replacement of "...
- 20.7k
21
votes
1
answer
1k
views
Are the real numbers isomorphic to a nontrivial ultraproduct of fields?
Let $K_1, K_2, \dots$ be a countable sequence of fields, and let $\prod_{\mathcal F} K_i$ be the ultraproduct with respect to some nonprincipal ultrafilter $\mathcal F$.
Question: Can there be a field ...
- 62.6k
1
vote
0
answers
68
views
Finitely presentable groups are residually finite if and only if they are universally pseudofinite
Suppose $G$ is finitely presentable. Then residual finiteness of $G$ is equivalent to $G$ satisfying the universal theory of finite groups (equivalently, to every existential statement true in $G$ ...
- 1,248
6
votes
0
answers
222
views
Do maximal compact logics exist?
By "logic" I mean regular logic in the sense of abstract model theory (see e.g. the last section of Ebbinghaus/Flum/Thomas' book). My question is simple:
Is there a logic $\mathcal{L}$ ...
- 20.7k
1
vote
1
answer
187
views
Gödel coding and the function $z(x)$
The function $z(x)$ that associates to each formula $\alpha$ of $P$ its Gödel number $z(\alpha)$ is external to the system. How then can expressions in which $z(x)$ be involved be expressed in $P$? ...
- 265