All Questions
Tagged with set-theory model-theory
401 questions
0
votes
0
answers
95
views
How near are a groupoid and its 'preorderification'?
As remarks, a groupoid is a category with only (categorical) isomorphisms as its morphisms and a preorder is a category only having one morphism between each object. If we choose one isomorphism by ...
1
vote
0
answers
99
views
Is this theory synonymous with ZF + Global Choice?
$\textbf{Logic:}$ Mono-sorted first order logic with equality.
$\textbf{Extralogical Primitives: } <, \in$
Define: $x > y \iff y < x \\ x \leq y \iff x < y \lor x=y \\ x \not > y \iff \...
- 11.3k
1
vote
0
answers
89
views
About synonymy relationships around these two theories?
The following question is about patterns of synonymy relationships around two theories, $T^+$ and $\sf PA$.
For purposes of self inclusiveness I'll re-iterate $T$ and its extensions.
$\textbf{Logic:}$ ...
- 11.3k
4
votes
1
answer
144
views
Stably embedded clone
Let $M$ be a first-order structure, considered as an element of the ambient set-theoretic universe $V$.
Clearly, for any $L_{\infty,\infty}$-formula $\varphi(\bar x)$ (with $\bar x$ finite, say) in ...
- 1,338
3
votes
0
answers
117
views
Topologically symmetric models of $\mathsf{ZFA}$
The standard construction of permutation models (i.e. models of $\mathsf{ZFA}$ involves choosing some collection of atoms $A$, a group $G$ of permutations on these atoms, and then a normal filter $\...
- 131
3
votes
0
answers
211
views
Intuitionistic set-theoretic geology
Work in ZF, if there are proper class many supercompact cardinals, then all grounds are uniformly definable. Hence under reasonable assumption, we can have choiceless set-theoretic geology.
But can we ...
- 695
14
votes
2
answers
1k
views
If every definable class admits a group structure, must global choice hold?
It is a remarkable fact, due to Hajnal and Kertész and explained very well in this MathOverflow answer by user Ashutosh, that the axiom of choice is equivalent to the assertion that every nonempty set ...
- 236k
1
vote
1
answer
138
views
Is there inconsistency with having countable models of Z with these internalizing properties?
Is there a clear inconsistency with the following?
There exists a countable transitive model of Zermelo set theory, such that for all external bijections between sets the images and preimages of sets ...
- 11.3k
3
votes
0
answers
99
views
Counting Eilenberg/Schutzenberger-type definitions of pseudovarieties
See Eilenberg/Schutzenberger, On pseudovarieties for background on pseudovarieties. I've phrased things in terms of pairs-of-sets to avoid some annoying language about multisets. Also, I'm aware that ...
- 21.2k
21
votes
1
answer
864
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 ...
- 236k
8
votes
1
answer
222
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,097
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
5
votes
1
answer
220
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,353
3
votes
0
answers
133
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{...
- 21.2k
4
votes
1
answer
176
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 \...
- 11.3k
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,574
5
votes
1
answer
597
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,897
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
9
votes
2
answers
2k
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,230
4
votes
1
answer
515
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
143
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 ...
- 21.2k
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
4
votes
1
answer
205
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
3
votes
1
answer
240
views
Is Morse-Kelley set theory with Class Choice bi-interpretable with itself after removing Extensionality for classes?
Let $\sf MKCC$ stand for Morse-Kelley set theory with Class Choice. And let this theory be precisely $\sf MK$ with a binary primitive symbol $\prec$ added to its language, and the following axioms ...
- 11.3k
24
votes
4
answers
3k
views
A Löwenheim–Skolem–Tarski-like property
I am interested in the following Löwenheim–Skolem–Tarski-like property.
Given a cardinal $\kappa$, what (if any) is a property $\phi(x)$ such that if $\phi(\kappa)$ holds, then we can prove the ...
- 343
6
votes
5
answers
2k
views
Standard models of N and R: An Alice/Bob approach
This is a question about a comment in a recent publication by Roman
Kossak. Kossak wrote:
"Nonstandardness in set theory has a different nature. In
arithmetic, there is one intended object of ...
- 16.6k
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
2
votes
1
answer
271
views
I have a problem about elementary submodels of ZFC
So suppose $\kappa$ inaccessible so that $V_\kappa$ is a model of ZFC, using Skolem and the Mostoswky collapse we have a countable elementary submodel $M$ of $V_\kappa$. This implies that for any ...
- 31
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
10
votes
2
answers
470
views
Is the set of permissible numbers of models of various cardinalities computable?
This question arose in the comments to this question.
Let $X$ be the set of pairs $(m,k)$ such that there is some (consistent complete countable first-order) theory $T$ with exactly $m$ models of size ...
- 21.2k
13
votes
1
answer
571
views
Is there a complete uncountable theory with two countable models?
This is a question originally asked at MSE a few years ago; the original poster hasn't been active in a while, so I'm taking the liberty of asking it here:
Is there a complete first-order theory $T$ ...
- 21.2k
8
votes
2
answers
661
views
Is the existence of substructures satisfying a theory absolute?
Given a first-order structure $\mathfrak{A}$ and a first-order theory $T$ one can ask if
$$
\varphi(\mathfrak{A}, T) := ``\text{there is a substructure } \mathfrak{B} \text{ of } \mathfrak{A} \text{ ...
- 1,328
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
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
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
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
5
votes
1
answer
2k
views
Do bijections from the natural numbers satisfy the Peano axioms? [closed]
While thinking of natural numbers as anything that satisfies the Peano axioms, I was left wondering, what if I take the successor function $S(x)$ to be anything other than $x\to x+1$?
Some examples ...
- 129
3
votes
1
answer
271
views
Ultra*powers* in the category of structures and elementary embeddings
This is based on a few previous questions.
Can one characterize ultrapowers in the category of L-structures (modeling a fixed complete theory, say) and elementary embeddings?
Previous posts showed ...
- 151
13
votes
3
answers
1k
views
Can ultraproducts avoid all "factor structures"?
This came up in the comments to an answer of Joel's. Suppose $\mathcal{M}_i$ ($i\in I$) are elementarily equivalent structures in the same fixed signature and $\mathcal{U}$ is an ultrafilter on $I$. ...
- 21.2k
6
votes
1
answer
570
views
Ultraproducts in the category of structures and elementary embeddings
A previous question on the categorical nature of ultraproducts had great answers, mostly categorically characterizing ultraproducts in the category of $L$-structures and homomorphisms for a fixed ...
- 151
3
votes
2
answers
269
views
Is every countable model of ZFC a subset of some parameter free definable pointwise-definable model of ZFC?
Is it consistent with $\sf ZFC + \text{ countable models of } ZFC \text { exist}$, that every countable model of $\sf ZFC$ is a subset of some parameter free definable pointwise-definable model of $\...
- 11.3k
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
5
votes
1
answer
487
views
How to solve this exercise about large countable ordinals?
In this note (Notes on Higher Type ITTM-recursion, 2021) written by Philip Welch, I'm trying to solve exercise 3.5(i), but I don't know how to solve it.
The problem is: assume that $L_{\gamma_0}<_{...
- 1,490
17
votes
1
answer
434
views
End-extension which Mostowski collapses a fake well ordering
Assume $\alpha$ is admissible, $R\in L_\alpha$ is a linear order that don't have any infinite descending chain in $L_\alpha$. Is there always an end extension $M$ of $L_\alpha$, such that $M\vDash KP$ ...
- 1,490
2
votes
1
answer
207
views
Can Foundation be captured in $\mathcal L(\omega_1,\omega)$?
Working in $\mathcal L_{\omega_1, \omega}$, can Foundation be captured?
My idea is to formalize a theory where all of its models are the well founded pointwise definable models of $\sf ZFC$. I attempt ...
- 11.3k
6
votes
1
answer
571
views
Parameter-free effective cardinals
In the paper "Effective cardinals and determinacy in third order arithmetic" by Juan Aguilera, effective cardinals is defined.
I'm curious about its little variation, parameter-free ...
- 1,490
11
votes
2
answers
379
views
Can singular long models require less than PA?
Say that a long model is an $\mathfrak{A}\models\mathsf{I\Sigma_1}$ such that $\mathfrak{A}$ has strictly greater cardinality than each of its proper initial segments (in the case $\vert\mathfrak{A}\...
- 21.2k
2
votes
1
answer
243
views
Is stable ordinals in non-well-founded model the same as well founded models?
Let $BST$ be the axiom system $KP$ - $\Delta_0$ collection. For an ordinal $\alpha$, we say that $\alpha$ is $\varphi$-$\Sigma_n$-stable, if there is a $\beta>\alpha$ satisfies the formula $φ$ such ...
- 1,490
3
votes
0
answers
179
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-...
- 21.2k