All Questions
Tagged with set-theory model-theory
96 questions with no upvoted or accepted answers
26
votes
0
answers
1k
views
Where do uncountable models collapse to?
Suppose $T$ is a complete first-order theory (in an finite, or at worst countable, language). Given any model $\mathcal{M}\models T$ of cardinality $\kappa$, we can ask whether $\mathcal{M}$ can be ...
- 21.2k
23
votes
0
answers
682
views
CH and automorphisms of ultrapowers of $\mathbb{Z}$ and $\mathbb{R}$
Notation and motivation. Given an algebraic structure $\mathbb{M}$ of cardinality at most the continuum and with countably many operations, and a nonprincipal ultrafilter $\cal{U}$ on a countably ...
- 17.7k
19
votes
0
answers
563
views
What algebraic properties are preserved by $\mathbb{N}\leadsto\beta\mathbb{N}$?
Given a binary operation $\star$ on $\mathbb{N}$, we can naturally extend $\star$ to a semicontinuous operation $\widehat{\star}$ on the set $\beta\mathbb{N}$ of ultrafilters on $\mathbb{N}$ as ...
- 21.2k
17
votes
0
answers
1k
views
Non-rigid ultrapowers in $\mathsf{ZFC}$?
Originally asked and bountied at MSE:
Question: Can $\mathsf{ZFC}$ prove that for every countably infinite structure $\mathcal{A}$ in a countable language there is an ultrafilter $\mathcal{U}$ on $\...
- 21.2k
14
votes
0
answers
500
views
The Ax-Kochen isomorphism theorem and the continuum hypothesis
Let's recall that:
(1): The Ax-Kochen principle says that if $\mathcal{U}$ is a non-principal ultrafilter over prime numbers, then $\prod_{\mathbb{U}} \mathbb{F}_p((t)) \equiv \prod_{\mathbb{U}} \...
- 32.1k
14
votes
0
answers
404
views
O-minimality and forcing
It is well-known that the structure $(\mathbb{R}, +, \cdot, <, 0, 1)$ is an o-minimal structure and hence the set of integers $\mathbb{Z}$ is not definable in it.
In an ongoing project with Will ...
- 32.1k
13
votes
0
answers
707
views
Applications of Set theory vs. model theory in mathematics
I have a question that has occupied my mind for some time.
Let's first consider applications of set theory and model theory in mathematics.
Major applications of set theory are in topology, Banach ...
- 32.1k
12
votes
0
answers
241
views
Is there a characterization of the class of first-order formulas that are closed in every compact Hausdorff structure?
Fix a relational language $\mathcal{L}$. (I don't think relational really matters that much but I don't want to worry about it.) A topological $\mathcal{L}$-structure is an $\mathcal{L}$-structure $M$ ...
- 12.5k
10
votes
0
answers
381
views
Can one define in ZFC a directed system of embeddings on the class of all linear orders realizing the surreal line as the direct limit?
Consider the surreal line $\langle\newcommand\No{\text{No}}\No,\leq\rangle$, in its order structure only. This is a proper class linear order, which is universal for all set-sized linear orders, as ...
- 236k
10
votes
0
answers
331
views
Extending models of topological set theory
$\mathsf{GPK_\infty^+}$ is an alternative set theory in which we have comprehension for formulas which are positive in a certain sense; see the SEP article for more detail (or this MO post, which ...
- 21.2k
10
votes
0
answers
334
views
Definability up to isomorphism versus definability of an isomorphic copy
Question: Is it provable in ZFC that every structure that is ordinal definable up to isomorphism has an ordinal definable isomorphic copy? If not, what are some counterexamples? All structures are ...
- 7,545
9
votes
0
answers
237
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 (...
- 21.2k
9
votes
0
answers
178
views
Does determinacy imply unravellability for the Borel sets (over a weak base theory)?
As far as I know, the only way we currently know how to prove Borel determinacy in $\mathsf{ZFC}$ is to go through unravelability (a rather technical property whose definition can be found in Martin's ...
- 21.2k
9
votes
0
answers
528
views
How many steps does it take to "Tarski-Vaughtify" second-order logic?
Given a regular logic $\mathcal{L}$, let $\preccurlyeq_\mathcal{L}$ be the usual elementary submodelhood relation for $\mathcal{L}$. There is also a separate submodelhood relation coming from the ...
- 21.2k
9
votes
0
answers
279
views
What logic characterizes relative intrinsic complexity in set recursion?
Short version: Is there an analogue of the Ash-Knight-Manasse-Slaman/Chisholm theorem for $E$-recursion?
Long version: I'm interested in "$E$-recursive structure theory," but it's not ...
- 21.2k
8
votes
0
answers
682
views
Is there any theorem achieving Conway's "Mathematician's Liberation Movement"
John Conway on in the appendix to part zero of ONAG describes a "Mathematician's Liberation Movement". The goal would be to give mathematicians the freedom to create mathematical theories with the ...
- 6,353
8
votes
1
answer
368
views
Model ${\sf ZF}$ that "spreads" members of ${\cal P}(X)$
Is there a model of ${\sf ZF}$ such that there is an infinite set $X$ and a injective map $f:{\cal P}(X)\to {\cal P}(X)$ so that for $a\neq b \in {\cal P}(X)$ we have $|f(a)\cap f(b)| \leq 1$?
Note. ...
- 48.9k
7
votes
0
answers
296
views
A system with distinct infinite cardinalities but no "best" version of $\mathbb{N}$
Let $\mathfrak{S}=(M_z,U_z)_{z\in\mathbb{Z}}$ be a sequence such that for each $z\in\mathbb{Z}$ we have
$M_z\models\mathsf{ZFC}+$ "$U_z$ is a nonprincipal ultrafilter on $\omega$" (so in ...
- 21.2k
7
votes
0
answers
185
views
Interest in the size of ultrapowers in model theory
It seems that in the 60s (at least), there was interest in computing the size of ultrapowers by countably incomplete ultrafilters. For example, given an ultrafilter $U$ on some relatively small set ...
- 18.6k
7
votes
0
answers
269
views
Something like "o-minimal ordinal analysis"
Below, by "nice structure" I mean "o-minimal expansion of $(\mathbb{R};<)$ by countably many continuous functions and open relations."
Suppose $\mathfrak{A}=(\mathbb{R};<,......
- 21.2k
7
votes
0
answers
173
views
"Minimal-ish" Dedekind-finite cardinalities of models
Throughout, we work in $\mathsf{ZF}+$ "There is an infinite Dedekind-finite set."
Say that a Dedekind-finite cardinality $\kappa$ is $\Sigma^1_1$-isolated iff there is some first-order ...
- 21.2k
7
votes
0
answers
314
views
Is there a "nice" inner model for $\mathsf{ZF}$ + a Dedekind-finite infinite set of reals?
Below, given a formula $\varphi$ which $\mathsf{ZF}$ proves defines a set of reals and an inner model $W$, I'll write "$\varphi^W$" and "$L(\varphi^W)$" for "$\{x:W\models\...
- 21.2k
7
votes
0
answers
304
views
Which countable ordinals are "Barwise compact" for $\mathcal{L}_{\infty,\omega_1}$?
Barwise compactness says (as a special case) that whenever $\alpha$ is countable and admissible, $T\subseteq\mathcal{L}_{\infty,\omega}\cap L_\alpha$ is $\alpha$-c.e., and every subset of $T$ which is ...
- 21.2k
7
votes
0
answers
205
views
Which first-order theories admit a compact-like superstructure?
Positive set theory is an approach to rectifying Russel's paradox by restricting the syntactic form of formulas for which we allow comprehension. It can be motivated by the construction of certain ...
- 12.5k
7
votes
0
answers
210
views
Possible cofinalities of cuts of ultraproducts
Suppose $\kappa$ is a regular cardinal, $\bar{\mu}=(\mu_i: i<\kappa)$ is an increasing sequence of regular cardinals ($>\kappa$) and set
$pcut(\bar \mu)=\{ (\lambda_1, \lambda_2):$ for some ...
- 32.1k
7
votes
0
answers
553
views
Recent application of model theory in set theory by Shelah-Malliaris
Recently one of the oldest open problems in set theory about the cardinal invariants of the continuum (i.e the question of whether $\mathfrak{p}=\mathfrak{t}$) was solved by Shelah and Malliaris (see "...
user39869
6
votes
0
answers
251
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 $...
- 21.2k
6
votes
0
answers
287
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}$ ...
- 21.2k
6
votes
0
answers
128
views
Detecting uncountable cardinalities, this time with determinacy
By "small cardinality" I mean a Scott cardinality onto which $\mathbb{R}$ surjects ($0$ isn't interesting here). $\mathcal{R}=(\mathbb{R};+,\times,\mathbb{Z})$ is the field of real numbers ...
- 21.2k
6
votes
0
answers
232
views
The number of countable models with determinacy
Throughout, work in $\mathsf{ZF+DC+AD_\mathbb{R}}$.
Given a theory $T$, let $[T]$ be the set of isomorphism types of models of $T$ with domain $\subseteq\omega$. This question is an outgrowth of this ...
- 21.2k
6
votes
0
answers
356
views
How much "finitary combinatorics" can be emulated by an infinite Dedekind-finite set?
Throughout, we work in $\mathsf{ZF}$. Let $[n]=\{1,...,n\}$. Given a set $X$ and a first-order sentence $\varphi$, let $M_X(\varphi)$ be the set of isomorphism types of models of $\varphi$ with ...
- 21.2k
6
votes
0
answers
207
views
Fragments of infinitary logic with a weak definability property
For a countable admissible ordinal $\alpha$, let $\mathcal{L}_\alpha=\mathcal{L}_{\infty,\omega}\cap L_\alpha$ and let $\equiv_\alpha$ be the corresponding elementary equivalence relation. Say that ...
- 21.2k
6
votes
0
answers
239
views
Existing literature on logics "describing their own equivalence notions"
Say that a regular logic $\mathcal{L}$ is self-equivalence-describing (SED) iff for every finite language $\Sigma$ there is a larger language $\Sigma'$ containing at least $\Sigma$ and two new unary ...
- 21.2k
6
votes
0
answers
189
views
Reference requestion: theorem guaranteeing self-embeddings of expansions of $\mathit{Ord}$
This is an attempt to locate a theorem I vaguely remember but cannot find (which arose in the context of Consistency of non-trivial elementary embedding $j : \mathit{Ord} \to \mathit{Ord}$ and ...
- 21.2k
6
votes
0
answers
153
views
How absolute is NIP in a model?
The following question is motivated by a model theoretic question but doesn't really involve any model theory per se. That said, I don't know the appropriate keywords for the relevant functional ...
- 12.5k
6
votes
0
answers
249
views
Number of models vs. complexity for SOL theories
This was previously asked at MSE without success.
Suppose $T$ is a complete first-order theory with continuum-many countable models up to isomorphism. We define two sets of Turing degrees associated ...
- 21.2k
6
votes
0
answers
137
views
Natural theories for the failure of gap-1 transfer principle
The gap-1 transfer principle says that the transfer principle $(\kappa^+, \kappa) \to (\lambda^+, \lambda)$ holds for all infinite cardinals $\kappa, \lambda.$
It is known that for some sentence $\...
- 32.1k
5
votes
0
answers
192
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}$ ...
- 21.2k
5
votes
0
answers
265
views
How strong is this "modal definability principle"?
Throughout, we work in the class theory $\mathsf{MK}$ (although I'm open to tweaking this), "logic" means "set-sized logic whose semantics is definable over $V$," and "$\...
- 21.2k
5
votes
0
answers
235
views
Surreal numbers and the ultrafilter lemma
In this question, I asked how to interpret a historical claim made by Conway regarding the potential, if not ideal, use of the surreal numbers for nonstandard analysis. In the comments and answers it ...
- 4,897
5
votes
0
answers
317
views
$\Sigma_n$-complete sets in the Levy hierarchy
Recall that a set $A \subseteq \mathbb N$ is (many-one, Turing) $\Sigma_n$-complete if it's $\Sigma_n$ and any other $\Sigma_n$ set (many-one, Turing) reduces to it. This definition actually makes ...
- 1,882
5
votes
0
answers
218
views
Improving a Lindstrom-y fact about $\mathcal{L}_{\omega_1,\omega}$?
See e.g. the last section of Ebbinghaus/Flum/Thomas for the relevant background on abstract model theory. Below, all languages are finite for simplicity. "$HC$" is the set of hereditarily ...
- 21.2k
5
votes
0
answers
242
views
Theorems of ZF through countable transitive models
Let $T$ be a finite collection of axioms of $\mathrm{ZF}$, let $\sigma$ be a sentence in the language of $\mathrm{ZF}$ and consider the statement
$\tau$: “any transitive countable model of $T$ ...
- 791
5
votes
0
answers
472
views
The surreal numbers under a change of universe
Suppose we start with a model $\mathcal{M}$ of $ZFC$ (or $GBC$ or $MK$ if you prefer), and let $N_0^\mathcal{M}$ denote the surreals in $\mathcal{M}$. If we add some large cardinal assumptions $\{\...
- 10.1k
5
votes
0
answers
192
views
The club filter in definable preorders
So this is an embarrassing question. Call a preorder $\mathbb{P}$ good if it has the following properties:
Every countable chain in $\mathbb{P}$ has a least upper bound.
$\mathbb{P}$ is directed (any ...
- 21.2k
4
votes
0
answers
247
views
Cantor-Bernstein phenomena for structures (and a "moderate zigzag" property)
My favorite proof of the Cantor-Bernstein theorem is the one that argues by "histories" - given injections $f:A\rightarrow B$ and $g:B\rightarrow A$, we identify each element of $A$ as ...
- 21.2k
4
votes
0
answers
365
views
Does $e^x$ let the reals build any new ordinal functions?
This question is closely related to this one. Belatedly, it occurred to me that I'd probably picked the wrong test question. I'm leaving that question up because I don't think it's bad per se, but I ...
- 21.2k
4
votes
0
answers
221
views
On natural examples, how much stronger is this than Löwenheim–Skolem?
Given a logic (= regular logic in the sense of Ebbinghaus/Flum/Thomas) $\mathcal{L}$, let a $\downarrow$-sentence be an $\mathcal{L}$-sentence $\varphi$ such that, whenever $\mathfrak{M}\models\varphi$...
- 21.2k
4
votes
0
answers
110
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 ...
- 21.2k
4
votes
0
answers
283
views
Is this "finite-ish combinatorics" reflection principle consistent?
This question is an attempt to chisel away at this earlier question of mine, which in retrospect may be rather intractable. Throughout, we work in $\mathsf{ZF}$.
Briefly (see the linked question for ...
- 21.2k