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
1
vote
0
answers
206
views
Interpretation of model theory in algebraic geometry
I found a paper Some applications of a model theoretic fact to (semi-) algebraic geometry by Lou van den Dries. In this paper, the author uses model theoretical methods to prove the completeness of ...
- 227
9
votes
2
answers
1k
views
Truth in a different universe of sets?
I understand that provability and truth as different concepts.
Provability is syntactic, it only concerns whether the given
sentence can be derived by reiterating the inference rules over a
collection ...
- 5,038
0
votes
0
answers
129
views
Provability predicates
We know that there are provability predicates, that is, predicates derived from the recursive relation "x is a demonstration of y", with which Godel's second incompleteness theorem would not ...
- 265
4
votes
0
answers
281
views
Which countable sets don't drastically change the definable topologies on $\mathbb{R}$?
For $\mathcal{M}$ an expansion of $\mathcal{R}=(\mathbb{R};+,\times)$ and $A\subseteq\mathbb{R}$, let $\tau^\mathcal{M}_A$ be the topology on $\mathbb{R}$ generated by the sets definable in $\mathcal{...
- 20.7k
11
votes
1
answer
665
views
On the classification of second-countable Stone spaces
Let $X$ be a Stone space (i.e. totally disconnected compact Hausdorff). Then the following are equivalent:
$X$ is second countable
$X$ is metrizable
$X$ has countably many clopen subsets
$X$ is an ...
- 62.6k
4
votes
1
answer
486
views
Truth Values of Statements in non-standard models
Excuse me, if the question sounds too naive.
Non-standard models of PA will have statements of non-standard lengths, basically infinite. And it is also true that every statement of a theory will have ...
- 1
3
votes
0
answers
140
views
Lindström's theorem part 2 for non-relativizing logics
By "logic" I mean the definition gotten by removing the relativization property from "regular logic" — see e.g. Ebbinghaus/Flum/Thomas — and adding the condition that for every ...
- 20.7k
8
votes
1
answer
1k
views
Worst of both worlds?
It's well known that $\mathsf{AC}$ implies the existence of non-measurable sets. And it's also true that, if all sets are measurable, then $|\mathbb{R}/\mathbb{Q}| > |\mathbb{R}|$. But is there a ...
- 309
0
votes
0
answers
104
views
Can a definable group of definable automorphisms of a field contain the Frobenius automorphism?
Let $K$ be an infinite definable field of characteristic $p >0$ in a certain theory $T$ with a definable group of definable automorphisms. Can this group contain the Frobenius automorphism?
- 1
2
votes
0
answers
495
views
Gödel's second incompleteness theorem [closed]
Apparently, see Feferman or Wikipedia, in a consistent system there are formulations of consistency that are demonstrable in the system itself while others are not. What distinguishes one from another?...
- 265
6
votes
1
answer
310
views
Original motivations of Fraïssé's amalgamation construction
Roland Fraïssé introduced in the 50's his famous construction of Fraïssé limits, and then Ehud Hrushowski modified it in the early 90's to construct new structures.
The motivations for the latter was ...
- 1,005
11
votes
1
answer
436
views
Are flat functors out of a finite category necessarily finite?
Note: I've originally asked this question on math stack exchange, but I have learnt that this is the better place to ask for research level questions, so I have deleted the original question there.
...
- 113
3
votes
1
answer
99
views
Is the filter generated by $A$-generic sets S1-prime?
Let $\mathfrak U$ be a monster model.
Let $A\subseteq\mathfrak U$ be a small set of parameters.
A set $\mathfrak D\subseteq\mathfrak U^{|x|}$ is $A$-generic if finitely many translations of $\mathfrak ...
2
votes
1
answer
557
views
Logical content of Gauss's Lemma (arithmetic)
In the context where $a$, $b$, $c$ are integers we have $(a \mid bc, a\land b = 1) \Rightarrow a\mid c$. This result is called Gauss's Lemma in French Highschool.
It is well known that (Steve Awodey, ...
- 29
5
votes
0
answers
227
views
Classical first-order model theory via hyperdoctrines
I have been reading this discussion by John Baez and Michael Weiss and I find this approach to model theory using boolean hyper-doctrines very interesting. One of their goal was to arrive at a proof ...
- 3,084
4
votes
0
answers
152
views
Can this theory of dyadic rationals prove that multiplying by three is the same as summing thrice?
(This question arose from a discussion with Jade Vanadium about a theory of dyadic rationals.)
Let $T$ be the 2-sorted FOL theory with sorts $ℕ,ℚ$ and constant-symbols $0,1$ and binary function-...
- 2,848
1
vote
1
answer
216
views
Seeking clarification of ultrapower nonstandard model of arithmetic
I've read that one nonstandard model of arithmetic is:
take $\mathbb{N}^\mathbb{N}$, the set of countably infinite sequences of natural numbers
take a quotent that gives the ultrapower: identify ...
- 1,278
4
votes
1
answer
202
views
If a theory has many mutually non-embeddable countable models can it have a countable $\omega$-saturated model?
A theory can have $2^\omega$-many non-isomorphic countable models but has a countable $\omega$-saturated model. (https://math.stackexchange.com/questions/305602/if-a-theory-has-a-countable-omega-...
- 105
12
votes
1
answer
3k
views
Is there a "halting machine" which halts on itself?
The crux of the halting problem is that there can be no Turing machine $M$ such that $\text{Halt}(M(N))=\neg \text{Halt}(N(N))$ for all Turing machines $N$, since $\text{Halt}(M(M))=\neg \text{Halt}(M(...
- 2,837
2
votes
0
answers
84
views
Do Fagin's zero-one laws hold on stochastic block model?
Let $n$ be a positive integer (the number of vertices), $k$ be a positive integer (the number of communities), $p = (p_1, . . . , p_k)$ be a probability vector on $[k] := \{1, . . . , k\}$ (the prior ...
- 131