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,205
questions
18
votes
2
answers
3k
views
Does the original 1931 proof of Gödel’s incompleteness rely on the completeness theorem, or is it purely syntactic?
Has anybody read each and every line of the English translation of the 1931 Gödel paper (from page 40 to the end)?
I tried once, but the notation is so far from the modern notation, and the setup is ...
- 995
1
vote
1
answer
139
views
Stability theory in the context of $\omega$-stable theories
I'm looking for some references to get me started on stability theory. More specifically, I want to find sources that talk about notions in stability theory, but for $\omega$-stable theories, which ...
- 173
8
votes
0
answers
138
views
How strong is exponentiation with only open induction? (Or: "how low can we go?")
Do the strongest theories currently known to be unconstrained by Tennenbaum's theorem ($IOpen$ and some modest extensions) remain so when augmented with a definition of exponentiation and axiom $\...
- 3,522
2
votes
0
answers
92
views
Counterexamples to the definable (P,Q)-Theorem
Pierre Simon conjectured a model-theoretic definable version of Matoušek’s (p,q) -theorem in NIP theories:
[Conjecture 5.1]: Let T be NIP and M⊨T . Let ϕ(x;d) ∈ L(U) a formula, non-forking over M . ...
- 51
4
votes
0
answers
107
views
What logics do the transfinite length pebble games capture?
See e.g. Libkin, Elements of finite model theory for background on the usual pebble game. Below, all languages are finite and relational, and "$\uparrow$" denotes an expression being ...
- 19.3k
9
votes
1
answer
358
views
Various sizes of models of NBG inside NBG (what does a class-sized model give us?)
Following this question and that one illustrating how induction in NBG can be tricky, I realized I'm also confused about the notion of “model” of NBG. The goal of this confusion is to hopefully lift ...
- 30.2k
2
votes
0
answers
189
views
Some questions about the Hyperuniverse Program
The Hyperuniverse Program, founded by Sy D. Friedman, intends to produce new second-order axioms of set theory which appropriately formalize "the universe is maximal" in one of a few ways. A ...
- 1,298
4
votes
1
answer
261
views
Does every ordinal appearing in a model of ZF appear in a model of ZFC?
To be more precise, suppose that $M$ is a model of ZF, for simplicity (or tactility) a set in some larger model $V$ of ZFC+Con(ZF), and suppose that $M\vDash``\alpha$ is an ordinal$"$. Must there be a ...
- 1,251
13
votes
0
answers
313
views
When does HSP reduce to SPH?
This is actually a poorly camouflaged attempt to use the answers to When is the opposite of the category of algebras of a Lawvere theory extensive? (all very interesting) for the purposes of my ...
- 17.5k
8
votes
1
answer
257
views
Is there a largest o-minimal structure all of whose definable functions are analytic?
In the paper "Quasianalytic Denjoy-Carleman classes and o-minimality" by J.-P. Rolin, P. Speissegger and A. J. Wilkie, it is proven that there is no largest o-minimal structure on the real ...
- 161
0
votes
1
answer
268
views
Need proof on a model being elementarily equivalent but non-isomorphic
For countable models, elementary equivalence is not equivalent to isomorphism.
For example, let $\frak{A}= \omega+\Bbb{Z}*\omega$ and $\frak{B}= \omega+\Bbb{Z}*\omega^*$ ($ω^∗$ is the reverse of $ω$)...
anon
3
votes
0
answers
128
views
Is there an ordered algebra analogue of the HSP theorem?
For an algebraic signature (= set of function symbols) $\Sigma$, say that an ordered $\Sigma$-algebra is a pair $\mathfrak{A}=(\mathcal{A};\le)$ where $\mathcal{A}$ is a $\Sigma$-algebra in the sense ...
- 19.3k
2
votes
0
answers
73
views
Question related to number of distinct forcing extensions of a countable model
A bit of context: the below question is motivated by roughly the following scenario: we have some countable model $\mathcal{M}$, and want to “count” the number of functions/sets $f$ such that $\...
- 111
1
vote
0
answers
143
views
Is this approximation to infinitary equivalence coarse on countable structures?
This question is a kind of dual to this earlier one. Note that if we replace $\mathsf{FOL}$ with $\mathcal{L}_{\omega_1,\omega}$, things trivialize since we can use the theory $\{\varphi^A\...
- 19.3k
3
votes
1
answer
148
views
Is having a Frobenius pair first-order expressible in the language of groups?
I am trying to figure out whether or not the following property is first-order expressible in the language of groups.
$$\text{$G$ has a subgroup $H$ with which it forms a Frobenius pair $(H,G)$.}$$
My ...
- 33
3
votes
0
answers
115
views
Does the "iterated definability" closure always fall short of standard (Boolean) infinitarization?
Given a (set-sized) logic $\mathcal{L}$, let $\mathcal{L}'$ be gotten from $\mathcal{L}$ by adding the ability to quantify over $\mathcal{L}$-definable relations. (I'm being a bit vague here, since e....
- 19.3k
8
votes
1
answer
308
views
Modal logic of "mostly-satisfiability"
For $n\in\omega+1$ let $\mathsf{ZFC}_n$ be $\mathsf{ZC}$ + $\{\Sigma_k$-$\mathsf{Rep}: k<n\}$. Let $\widehat{\mathsf{ZFC}}$ be the strongest consistent theory $\mathsf{ZFC}_n$ (so if $\mathsf{ZFC}$ ...
- 19.3k
3
votes
0
answers
149
views
Systems of elementary embeddings
Recently I've been thinking about elementary embeddings, partition cardinals, etc. as part of my never-ending quest for understanding of consistency strength :p
I came up with this idea, called I* ...
- 704
2
votes
0
answers
75
views
Is "strongly unbounded logics are unbounded" equivalent to "no descending sequence of cardinals"?
This question is motivated by Vaananen's paper Generalized quantifiers in models of set theory. Say that a (set-sized, regular) logic $\mathcal{L}$ is
unbounded if there are $\mathcal{L}$-sentences $\...
- 19.3k
9
votes
2
answers
2k
views
Are the models of infinitesimal analysis (philosophically) circular?
Infinitesimal analysis (by which I mean that originating from topos theory---not the nonstandard analysis of Robinson) seeks to recover the pre-limit notions of calculus (which are sufficiently useful ...
- 341
1
vote
1
answer
194
views
Recursively inaccessible ordinals and non locally countable ordinals
This answer seems to imply that: for an ordinal $\alpha$, to be recursively inaccessible (i.e. $\alpha$ is admissible and limit of admissible) implies to be not locally countable (i.e. $L_\alpha \...
- 531
7
votes
1
answer
205
views
Does $\mathit{Aut}(\mathbb{R};+)$ have a copy in $L(\mathbb{R})$ granting large cardinals?
Throughout, work in $\mathsf{ZFC}$ + large cardinals (let's say a proper class of Woodin limits of Woodins but I'm happy to go higher if that would help).
Let $\mathcal{R}=(\mathbb{R};+)$ be the ...
- 19.3k
8
votes
0
answers
93
views
Is the hypotenuse operation associative in every Tarski plane?
By a Tarski space I understand a mathematical structure $(X,\mathsf B,\equiv)$ consisting of set $X$, a betweenness relation $\mathsf B\subseteq X^3$ and a congruence relation ${\equiv}\subseteq X^2\...
- 40.9k
7
votes
1
answer
246
views
Complexity of infinitary satisfiability, part 2
This question is a follow-up to this one, which was almost entirely answered by Farmer S. Throughout, we work in $\mathsf{ZFC+V=L}$.
Given a "pre-admissible" (= admissible or limit of ...
- 19.3k
5
votes
0
answers
115
views
Is an equilateral triangle constructible in a Tarski plane?
By a Tarski space I understand a mathematical structure $(X,\mathsf B,\equiv)$ consisting of set $X$, a betweenness relation $\mathsf B\subseteq X^3$ and a congruence relation ${\equiv}\subseteq X^2\...
- 40.9k
6
votes
0
answers
146
views
Does every Tarski plane embed into a 3-dimensional Tarski space?
By a Tarski space I understand a mathematical structure $(X,B,\equiv)$ consisting of set $X$, a betweenness relation $B\subseteq X^3$ and a congruence relation ${\equiv}\subseteq X^2\times X^2$ ...
- 40.9k
8
votes
3
answers
509
views
Elementary countable submodels in Gödel's universe
By the downward Lowenheim-Skölem theorem we can find two countable ordinals $\alpha < \beta$ such that $L_\alpha \prec L_{\omega_1}$ and $L_\beta \prec L_{\omega_1}$. That is, $L_\alpha$ and $L_\...
- 531
12
votes
1
answer
457
views
What is the "iterated definability" limit of first-order logic?
Roughly speaking, given a set-sized logic $\mathcal{L}$ let $\mathcal{L}'$ be gotten by adding to $\mathcal{L}$ the ability to quantify over $\mathcal{L}$-definable relations. (The details are a bit ...
- 19.3k
0
votes
1
answer
135
views
Is a right triangle with the given cathetus and the opposite angle constructible in the absolute plane?
Question. Is it possible to construct a right triangle with a given cathetus $a$ and a given opposite angle $\alpha$ using only compass and ruler in the absolute geometry (so without the axiom of ...
- 40.9k
17
votes
3
answers
950
views
Minimum transitive models and V=L
Is there a c.e. theory $T⊢\text{ZFC}$ in the language of set theory such that the minimum transitive model of $T$ exists but does not satisfy $V=L$?
You may assume that ZFC has transitive models. ...
- 6,112
3
votes
1
answer
152
views
If a theory speaks of sets that cannot be forced to be parameter free definable, then does this entail a large cardinal property?
If we say that an effectively generated first order theory $\sf T$ extends $\sf ZF$, such that every countable model of $\sf T$ doesn't have a class forcing extension that is pointwise definable. ...
- 9,276
3
votes
1
answer
180
views
Definable closure in class-sized expansions of o-minimal groups
I am working in NBG set theory with limitation of size (i.e. the class of all sets is in bijection with the class of ordinals).
Let $\mathbf{G}$ be a class-sized o-minimal expansion of an ordered ...
- 2,367
1
vote
1
answer
142
views
Is there a model of each of the following kinds of theories in the first transitive model of ZFC?
The question of whether the minimal transitive model $M$ of $\sf ZFC$ have a model of each consistent extension $\sf T$ of $\sf ZF$, is answered to the negative, basically because $M$ is countable and ...
- 9,276
10
votes
2
answers
769
views
Does every consistent extension of ZF have a model in the minimal transitive model of ZFC?
Suppose there exists a transitive model of $\sf ZFC$. Is it the case that every consistent theory that extends $\sf ZF$ must have a model that is an element of the minimal transitive model of $\sf ZFC$...
- 9,276
1
vote
1
answer
84
views
Are externally pointwise definable models of ZFC subject to the same limitations of the internally pointwise definable ones?
By pointwise definable models, it's meant that every element of those models is definable after a formula in a parameter free manner, but that defining formula is in the language of that model, i.e., ...
- 9,276
5
votes
1
answer
206
views
What does the Ehrenfeucht-Fraïssé game on structures with infinitely many relations tell us?
EF-games are typically presented for structures with finitely many relations, and if you want to extend them to structures with functions, you can relationalize the functions. This seems to be to ...
- 429
6
votes
1
answer
303
views
What are the simplest sentences which might distinguish Zilber’s field from the complex numbers?
Zilber’s field $\mathbb{B}$ is a field of the same size as the complex numbers $\mathbb{C}$, which satisfies the same first-order sentences about $+$ and $\cdot$. If $\mathbb{B}$ also satisfies the ...
user44143
34
votes
2
answers
2k
views
Ur-elemental surprises
For most of my (mathematical) life, I believed that there was really no essential difference between set theory without urelements and set theory with urelements. However, while that may be true in ...
- 19.3k
5
votes
1
answer
138
views
Does visible nonstandardness imply visible ill-foundedness?
For $X\subseteq\mathfrak{M}\models \mathsf{TA}$, say that $X$ is $\mathfrak{M}$-disruptive iff there is some formula $\varphi$ in the language of arithmetic + a new unary predicate symbol $U$ such ...
- 19.3k
21
votes
2
answers
906
views
Seymour's second neighborhood conjecture for infinite graphs
Let $G$ be a directed graph (say simple, so no loops and each pair of vertices has at most one directed edge between them). Suppose $G$ is 'locally finite', in the sense that each vertex has only ...
- 6,608
7
votes
1
answer
571
views
Systems intermediate in strengthen between Robinson arithmetic and PA
One model of Robinson arithmetic which is obviously not our usual integers is $\mathbb{Z}[X]^+$, that is the set containing 0 and also all polynomials with coefficients in $\mathbb{Z}$ with positive ...
- 6,100
4
votes
0
answers
246
views
Is this notion of "concrete bijection" transitive?
This question looks at the same intuition as, but expressed via a different formal notion than, a couple earlier questions of mine (1, 2). Basically, I'm playing around with using model theory to ...
- 19.3k
13
votes
1
answer
654
views
Are there different "levels" of self-referentiality in arithmetic?
Below, all sentences/formulas are first-order and in the language of arithmetic. For simplicity, we conflate numbers and numerals, and conflate sentences/formulas and their Godel numbers.
Given a ...
- 19.3k
8
votes
1
answer
408
views
Automorphisms of projective spaces, and the Axiom of Choice
It is known that upon not accepting the Axiom of Choice (AC), there exist models of ZF in which there are projective spaces (over a division ring) with a trivial automorphism group. (This is a truly ...
- 4,353
5
votes
1
answer
243
views
Highly improper forcings
The following question comes from a typo in an old notebook of mine (I changed what I was calling my forcing notion partway through writing the definition of properness):
Say that a forcing $\mathbb{P}...
- 19.3k
8
votes
1
answer
1k
views
Definable set in ZF that cannot be proved to be Borel
Is there a predicate $P(x)$ such that $\mathrm{ZF} \vdash \exists! x. P(x)$, and $\mathrm{ZF} \vdash \forall x. P(x) \to (x \subseteq \mathbb R)$, but $\mathrm{ZF} \nvdash \forall x. P(x) \to \mathsf{...
- 1,031
3
votes
1
answer
220
views
Adding sort of sets over theory with multiple sorts?
It's relatively standard to add a sort of sets over some base theory and supplement the axioms with comprehension principles as in second order arithmetic.
Is there a nice way to do this if your ...
- 2,633
3
votes
0
answers
134
views
A modal logic with two diamonds, one is interpreted as the complement of the relation corresponding to the other one
Suppose our language has two diamond operators $\Diamond$ and $\overline{\Diamond}$ and, over a Kripke model whose relation is $R$, we have the following semantics:
$w\models\Diamond\varphi$ if there ...
- 131
2
votes
0
answers
191
views
"Very $L$-like" models, part 2: combinatorics
Say that a good logic is a regular logic $\mathcal{L}$ containing $\mathsf{FOL}$ and having the finite use property and the strong downward Lowenheim-Skolem property together with, for each finite ...
- 19.3k
9
votes
0
answers
225
views
Continuum hypothesis analogue for substructures
This question was previously asked and bountied at MSE. Throughout, "theory" means "possibly-incomplete first-order theory in a countable language."
Say that a theory $T$ has CHS (...
- 19.3k