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,101
questions
1
vote
1
answer
73
views
Extending a first-order deductive system with satisfaction relation
I'm trying to structure a proof where there are several algebras instantiated over sets, where the properties that you get from the algebraic theories are important, but the properties of the sets ...
1
vote
0
answers
71
views
Lifting Wilkie's theorem from $\mathbb{N}$ to other structures
Let $\models,\models_2,\models_d$ be the satisfaction relations for first-order logic, second-order logic with full semantics, and second-order logic with set quantifiers ranging over definable-with-...
- 19k
1
vote
0
answers
117
views
Which first-order theories have full indiscernible extraction?
Stable theories have the following useful property, which I will state in a sub-optimal way for simplicity's sake:
Fact 1. If $T$ is $\lambda$-stable for some $\lambda \geq |T|^+$, then for any set ...
- 8,036
12
votes
1
answer
328
views
The scope of a "strong Cantor-Bernstein" property
This question is of course related to this earlier MO question, but I don't believe is answered by the posts there.
My favorite proof of the Cantor-Schroeder-Bernstein theorem actually establishes ...
- 19k
3
votes
1
answer
133
views
Forking in the p-adic field with valuation
I understand that the p-adic field with valuation has NTP2 and so forking=dividing. Does anyone have any explicit examples or a way of characterizing non-forking types and formulas in the theory of $...
- 51
15
votes
3
answers
1k
views
Recommendations to learn about the use of toposes in logic?
I'd like to learn about the use of toposes in logic. The "logic" side I know quite well, but of the "topos" side I am totally ignorant.
Which books/articles (formal and/or casual) ...
- 667
17
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 ...
- 667
1
vote
1
answer
100
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 ...
- 113
7
votes
0
answers
96
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,378
2
votes
0
answers
79
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
104
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 ...
- 19k
9
votes
1
answer
311
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 ...
- 26.4k
2
votes
0
answers
144
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 ...
- 514
4
votes
1
answer
206
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 ...
9
votes
0
answers
159
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.4k
7
votes
0
answers
152
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 ...
0
votes
1
answer
148
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
113
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 ...
- 19k
2
votes
0
answers
64
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 $\...
1
vote
0
answers
138
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\...
- 19k
3
votes
1
answer
143
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
111
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....
- 19k
8
votes
1
answer
256
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}$ ...
- 19k
3
votes
0
answers
119
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* ...
- 560
2
votes
0
answers
67
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 $\...
- 19k
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
106
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 \...
- 471
7
votes
1
answer
193
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 ...
- 19k
8
votes
0
answers
87
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\...
- 38.7k
7
votes
1
answer
232
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 ...
- 19k
5
votes
0
answers
100
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\...
- 38.7k
6
votes
0
answers
138
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$ ...
- 38.7k
8
votes
3
answers
455
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_\...
- 471
12
votes
1
answer
376
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 ...
- 19k
0
votes
1
answer
117
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 ...
- 38.7k
17
votes
3
answers
880
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. ...
- 5,507
3
votes
1
answer
144
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. ...
- 7,048
3
votes
1
answer
172
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,272
1
vote
1
answer
132
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 ...
- 7,048
10
votes
2
answers
705
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$...
- 7,048
1
vote
1
answer
77
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., ...
- 7,048
5
votes
1
answer
143
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 ...
- 399
6
votes
1
answer
284
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
33
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 ...
- 19k
5
votes
1
answer
128
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 ...
- 19k
20
votes
2
answers
826
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,528
7
votes
1
answer
428
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 ...
- 4,919
4
votes
0
answers
240
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 ...
- 19k
13
votes
1
answer
625
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 ...
- 19k
8
votes
1
answer
375
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 ...
- 3,871