All Questions
Tagged with set-theory model-theory
98 questions
12
votes
1
answer
648
views
Can $\mathcal{L}_{\omega_1,\omega}$ detect $\mathcal{L}_{\omega_1,\omega}$-equivalence?
Roughly speaking, say that a logic $\mathcal{L}$ is self-equivalence-defining (SED) iff for each finite signature $\Sigma$ there is a larger signature $\Sigma'\supseteq\Sigma\sqcup\{A,B\}$ with $A,B$ ...
- 21.2k
33
votes
6
answers
5k
views
Reasons to believe Vopenka's principle/huge cardinals are consistent
There are a number of informal heuristic arguments for the consistency of ZFC, enough that I am happy enough to believe that ZFC is consistent. This is true for even some of the more tame large ...
- 19.6k
22
votes
5
answers
1k
views
What is the spectrum of possible cofinality types for cuts in an ordered field? Or in a model of the hyperreals? Or in a nonstandard model of arithmetic?
I am interested to know the full range of possibilities for the cofinality type of cuts in an ordered field and in other structures, such as nonstandard models of arithmetic.
Definitions. ...
- 236k
8
votes
3
answers
1k
views
Tractability of forcing-invariant statements under large cardinals
It is usual to mention theorems of the kind:
Th. Assume there is a proper class of Woodin cardinals, $\mathbb{P} $ is a partial order and $G \subseteq \mathbb{P}$ is V-generic, then $V \models \phi \...
- 1,465
8
votes
2
answers
1k
views
Is there one binary operation foundational for set theory?
The membership relationship "$\in$" is foundational for set theory, in the sense that the axioms of any set theory are formulated in the language of "$\in$". Naturally, the ...
- 889
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
2
votes
1
answer
973
views
Compactness and completeness in Gödel logic
The standard proof of the completeness theorem in first-order Gödel logic is based
on a first-order countable language. I want to know that is there any proof of the completeness theorem in first-...
- 49
60
votes
8
answers
6k
views
Is the ultraproduct concept fundamentally category-theoretic?
Once again, I would like to take advantage of the large number of knowledgable category theorists on this site for a question I have about category-theoretic aspects of a fundamental logic concept.
My ...
- 236k
43
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 ...
- 32.5k
39
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 ...
- 750
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
18
votes
2
answers
3k
views
Universe view vs. Multiverse view of Set Theory
Here I refer to Hamkins' slides:
http://lumiere.ens.fr/~dbonnay/files/talks/hamkins.pdf
particularly, to the "Universe view simulated inside Multiverse", p. 22.
My question is: is it very unsound ...
- 1,465
17
votes
3
answers
1k
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. ...
- 7,545
16
votes
2
answers
1k
views
When does Vopěnka's principle hold?
Vopěnka's principle (VP) is the statement that, given any proper class $\{\mathcal{A}_\eta: \eta\in ON\}$ of first-order structures in the same language, there are some $\alpha\not=\beta$ with $\...
- 21.2k
13
votes
2
answers
3k
views
Non-standard models of finite set theory
It is well known how the intended model and how the (countable) non-standard models of arithmetic look like.
It's also well known how the intended model of set theory with the axiom of infinity ...
- 9,720
13
votes
2
answers
1k
views
The (non-)absoluteness of second-order elementary equivalence
Elementary equivalence is set-theoretically absolute between any two transitive models of set theory; this is also true for the infinitary logics - e.g., $\mathcal{L}_{\omega_1\omega}$ - at least, ...
- 21.2k
12
votes
3
answers
2k
views
Why do we need a transitive model in forcing arguments?
One major approach to the theory of forcing is to assume that ZFC has a countable transitive model $M \in V$ (where $V$ is the "real" universe). In this approach, one takes a poset $\mathbb{P} \in M$, ...
- 3,058
12
votes
1
answer
1k
views
Kolmogorov-Arnold theorem for (just-)functions
There is famous Kolmogorov-Arnold theorem for continuous functions composition - continuous function of several variables can be composed of continuous functions of two variables.
Specialization of ...
- 1,626
12
votes
4
answers
1k
views
Universal order type
Every countable order type, such as the countable ordinals, $\mathbb Z$, etc. can be embedded in $\mathbb Q$, so it is universal for countable order types. Is there a universal space for all linear ...
- 656
12
votes
1
answer
648
views
For which theories does ZFC without global choice prove the existence of a proper class monster model?
Proper class sized monster models are typically formulated in a class theory like $NBG$ and they can reasonably be formalized in $ZFC$ with some kind of global choice, but for some theories you don't ...
- 12.5k
10
votes
1
answer
354
views
Elementary equivalence between $n\mapsto n+1$ and its inverse on the Stone-Čech remainder?
Consider structures $(A,f)$ encoding a Boolean algebra $A$ endowed with an automorphism $f$. There is an obvious notion of isomorphism between such structures.
Consider the endomorphism $\hat{\Phi}$ ...
- 63.9k
10
votes
1
answer
729
views
What kind of compactness does "expanding $\mathbb{R}$ by constants" have?
EDIT: in retrospect this question should have been split up; I've accepted Joel's answer to the first part below, and asked the second part here.
This question is crossposted at MSE; however, it has ...
- 21.2k
7
votes
1
answer
291
views
Is there a forcing closure?
The main theorem of forcing says that for any c.t.m of $ZFC$ like $M$ and for all partial order $\mathbb{P}$ and $\mathbb{P}$-generic $G$ over $M$, there is a c.t.m of $ZFC$, like $N$ such that $N$ is ...
user36136
7
votes
1
answer
367
views
Compatibility of Łośian phenomena in second-order logic
(Throughout, all ultrafilters are nonprincipal.)
Given a property $P$ - really, a sentence in some appropriate logic - say that a ultrafilter $\mathcal{U}$ on a cardinal $\kappa$ averages $P$ iff for ...
- 21.2k
7
votes
1
answer
781
views
How do we know if Vaught's Conjecture is Absolute?
Please note that this might be some confusion on my part about the work surrounding Vaught's conjecture.
First of all, Vaught Conjecture states that if a first-order complete theory $T$ in a ...
- 756
7
votes
1
answer
581
views
Is this compactness property for "satisfiability on $\mathbb{R}$" consistent?
This was originally part of this older question of mine, but in retrospect that question should have been broken into two parts - this is the still-unanswered part.
Let $\Sigma$ be the language of ...
- 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
5
votes
2
answers
895
views
An axiom for collecting proper classes
I'm currently working on some universal algebra using proper classes (in MK class theory), and I repeatedly run into situations where I want to collect together some proper classes as the members of a ...
- 10.1k
2
votes
1
answer
314
views
Is there a model of ZF+ACC where transfer fails for the definable hyperreals?
In 2003 Kanovei and Shelah constructed a definable hyperreal field. The ultrapower used exploits a fairly large index set so that it is clear that the usual proof of Los and transfer does not go ...
- 16.6k
39
votes
3
answers
3k
views
Can one show that the real field is not interpretable in the complex field without the axiom of choice?
We all know that the complex field structure $\langle\mathbb{C},+,\cdot,0,1\rangle$ is interpretable in the real field $\langle\mathbb{R},+,\cdot,0,1\rangle$, by encoding $a+bi$ with the real-number ...
- 236k
33
votes
15
answers
7k
views
What's a magical theorem in logic?
Some theorems are magical: their hypotheses are easy to meet, and when invoked (as lemmas) in the midst of an otherwise routine proof, they deliver the desired conclusion more or less straightaway&...
27
votes
4
answers
3k
views
What "metatheory" did early set theory/logic researchers use to prove semantic results?
Things like the first-order completeness theorem and the Löwenheim-Skolem theorem are considered foundational in mathematical logic.
The modern approach seems to be, usually, to interpret a "model" ...
- 4,897
27
votes
3
answers
4k
views
Interactions between (set theory, model theory) and (algebraic geometry, algebraic number theory ,...)
Set theory and model theory have many applications outside of logic, in particular in algebra, topology, analysis, ...
On the other hand model theory, in particular after Hrushovski, found many ...
- 32.1k
25
votes
2
answers
1k
views
Detecting uncountable cardinals in $(\mathbb{R};+,\times,\mathbb{N})$
For a structure $\mathcal{X}=(X;...)$, say that a cardinal $\kappa$ is $\mathcal{X}$-detectable iff there is some sentence $\varphi$ in the language of $\mathcal{X}$ together with a fresh unary ...
- 21.2k
21
votes
3
answers
2k
views
Are there as many real-closed fields of a given cardinality as I think there are?
Let $\kappa$ be an infinite cardinal. Then there exists at least one real-closed field of cardinality $\kappa$ (e.g. Lowenheim-Skolem; or, start with a function field over $\mathbb{Q}$ in $\kappa$ ...
- 65.4k
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
18
votes
3
answers
1k
views
How badly does compactness fail in $\mathcal{L}_{\omega_1\omega}$?
I would like to get a better idea of how badly compactness fails in $\mathcal{L}_{\omega_1\omega}$.
Let $\Gamma$ be an arbitrary set of sentences from $\mathcal{L}_{\omega_1\omega}$. Let the ...
- 1,142
16
votes
3
answers
1k
views
Vopěnka's Principle for non-first-order logics
(For simplicity, the background theory for this post is NBG, a set theory directly treating proper classes which is a conservative extension of ZFC.)
Vopěnka's Principle ($VP$) states that, given any ...
- 21.2k
16
votes
2
answers
1k
views
How special is first-order $\mathsf{PA}$?
This is a modified version of a question which was asked and bountied at MSE without success.
Below, "$\mathsf{PA}$" refers to first-order Peano arithmetic.
There are various "...
- 21.2k
15
votes
2
answers
2k
views
Is "There exists an unbounded non-measurable set but no bounded non-measurable set" consistent with $\mathsf{ZF}$?
This is a follow-up to this question. We say that a set $A \subseteq \mathbb{R}$ is bounded if there exists a finite interval $(a,b)$ such that $A \subseteq (a,b)$.
Working in $\mathsf{ZFC}$, the ...
- 1,412
15
votes
1
answer
1k
views
Pointwise algebraic models of set theory
Let $\mathfrak{M} = \langle M, E \rangle$ be a structure for the language of set theory, and take some $B \subseteq M$ and $m \in M$. Say that $m$ is definable over $B$ iff there is a formula $\phi(x,\...
- 1,081
14
votes
1
answer
522
views
Is there an infinitary sentence which is absolutely not second-order expressible?
This is a "forcing-absolute" followup to this question, whose answer was largely unsatisfying. The question is:
Suppose $V=L$. Is there an $\mathcal{L}_{\infty,\omega}$-sentence $\varphi$ ...
- 21.2k
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
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
13
votes
1
answer
438
views
Is this notion of finiteness closed under unions?
This was asked and bountied at MSE without success.
Throughout, we work in $\mathsf{ZF}$.
Say that a set $X$ is $\Pi^1_1$-pseudofinite if for every first-order sentence $\varphi$, if $\varphi$ has a ...
- 21.2k
12
votes
1
answer
512
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 ...
- 21.2k
12
votes
6
answers
2k
views
Uses of bisimulation outside of computer science.
Bisimulation is one of the most important ideas of theoretical computer science. I was wondering whether bisimilarity is used/known outside of computer science/modal logic? I am aware that it ...
- 1,882
12
votes
1
answer
486
views
The strength of "There are no $\Pi^1_1$-pseudofinite sets"
For $\Gamma$ a set of second-order sentences in the empty language, say that a set $X$ is $\Gamma$-pseudofinite if $X$ is infinite but for every sentence $\varphi\in\Gamma$ which is satisfied in every ...
- 21.2k
11
votes
1
answer
671
views
Ultraproducts and the empty set
If $I$ is a set, $U$ a nonprincipal ultrafilter on $I$ and $E=(E_i)_{i\in I}$ a family of sets indexed by $I$, then the ultraproduct $E^*$ of $E$ is generally defined as the quotient of $\prod_{i\in I}...
- 19.6k
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