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
11
votes
2
answers
422
views
Are all generalized Scott sets realized as generalized standard systems?
Below, I've focused on PA when lots of other theories would do. If replacing PA with a different theory leads to a more answerable question, feel free to do so.
The standard system of a nonstandard ...
8
votes
0
answers
136
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 $\...
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 . ...
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 ...
13
votes
1
answer
2k
views
Elementary proof of Chevalley's Theorem on constructible sets
I am looking for a proof of the easiest affine version of Chevalley's Theorem on constructible sets :
Theorem (Chevalley). The image of a constructible subset of $\mathbf C^n$ by a polynomial map $P:...
9
votes
1
answer
356
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 ...
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 ...
25
votes
6
answers
3k
views
Is there a metamathematical $V$?
As with many of you, I've been following Peter Scholze's recent question about universes with great interest. In ring theory, we don't often have to deal with proper classes, but they occasionally ...
8
votes
3
answers
2k
views
Russell's paradox as understood by current set theorists
Many mathematicians like to think of the set of natural numbers as existing as a completed object. But it is difficult to make set theory as concrete, because Russell's paradox, in conjunction with ...
2
votes
2
answers
334
views
dp-minimality and stability
What are some of the common popular stable theories that are known to be dp-minimal (or not dp-minimal)?
Some dp-minimal examples I am aware of are strongly minimal theories, superstable theories of ...
4
votes
1
answer
259
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 ...
12
votes
1
answer
444
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 ...
6
votes
1
answer
299
views
When can interpretations be "optimized"?
To make this more readable, I've put some definitions/conventions at the end of this question.
I'm interested in when a given interpretation isn't "missing any information." Specifically, ...
9
votes
3
answers
549
views
Equational theories determined by "identities without variables"
How to characterize equational theories $T$ which have the following property: for any two terms $t(x_1,...,x_n)$ and $t'(x_1,...,x_n)$ in the signature of $T$, if for any closed terms (i. e. terms ...
0
votes
1
answer
255
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 $ω$)...
3
votes
0
answers
127
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 ...
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 $\...
42
votes
1
answer
2k
views
Do the analogies between metamathematics of set theory and arithmetic have some deeper meaning?
By "formal analogies" between the metamathematics of $\mathsf{ZFC}$/set theory and $\mathsf{PA}$(=Peano Arithmetic)/first order arithmetic, I mean facts such as the following:
We are considering a ...
38
votes
7
answers
6k
views
Is V, the Universe of Sets, a fixed object?
When I first read Set Theory by Jech, I came under the impression that the Universe of Sets, $V$ was a fixed, well defined object like $\pi$ or the Klein four group. However as I have read on, I am ...
3
votes
0
answers
114
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....
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\...
8
votes
1
answer
306
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}$ ...
9
votes
1
answer
396
views
On a result by Rubin on elementary equivalence of homeomorphism groups and homeomorphisms of the underlying spaces
In the known paper On the reconstruction of topological spaces from their group of homeomorphisms by Matatyahu Rubin several deep reconstruction theorems of the form "if $X$ and $Y$ are ...
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 ...
5
votes
0
answers
181
views
"Very $L$-like" models, part 1: large cardinals
(The original version of this question was much narrower and less natural; but see the edit history if interested.)
Say that a good logic is a regular logic $\mathcal{L}$ containing $\mathsf{FOL}$ ...
8
votes
0
answers
238
views
First order formula describing connected components
I ask this question here after no answer came up in the original MathSE question.
Let $\mathcal{L}$ be the language $\{+,-,\cdot,0,1,P\}$ where $P$ is some $n$-ary relation symbol. Is there a formula $...
3
votes
0
answers
147
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* ...
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 $\...
6
votes
1
answer
371
views
Poset of automorphism groups of variants of a structure
Say that two structures $\mathfrak{A},\mathfrak{B}$ in possibly different finite languages are parametrically equivalent - and write "$\mathfrak{A}\approx\mathfrak{B}$" - iff they have the ...
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 ...
7
votes
1
answer
204
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 ...
1
vote
1
answer
190
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 \...
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$ ...
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 ...
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 ...
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\...
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\...
8
votes
3
answers
506
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_\...
17
votes
3
answers
946
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. ...
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. ...
10
votes
2
answers
767
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$...
3
votes
1
answer
179
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 ...
1
vote
1
answer
141
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 ...
1
vote
1
answer
83
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., ...
5
votes
1
answer
205
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 ...
3
votes
1
answer
219
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 ...
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). ...
21
votes
2
answers
900
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 ...
19
votes
1
answer
1k
views
Is the theory of a partial order bi-interpretable with the theory of a pre-order?
A partial order relation $\leq$ on a set $A$ is a binary relation that is reflexive, transitive, and antisymmetric.
A preorder relation $\unlhd$ (also sometimes known as a quasi order or pseudo order) ...
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 ...