Questions tagged [set-theory]
forcing, large cardinals, descriptive set theory, infinite combinatorics, cardinal characteristics, forcing axioms, ultrapowers, measures, reflection, pcf theory, models of set theory, axioms of set theory, independence, axiom of choice, continuum hypothesis, determinacy, Borel equivalence relations, Boolean-valued models, embeddings, orders, relations, transfinite recursion, set theory as a foundation of mathematics, the philosophy of set theory.
1,111 questions
13
votes
4
answers
2k
views
Is it possible for countably closed forcing to collapse $\aleph_2$ to $\aleph_1$ without collapsing the continuum?
Suppose the continuum is larger than $\aleph_2$. Does there exist a countably closed notion of forcing that collapses $\aleph_2$ to $\aleph_1$, but does not collapse the continuum to $\aleph_1$? ...
- 1,174
13
votes
1
answer
650
views
About primitively recursively recognizable ordinals
Preliminary: I believe the notion of primitive recursive functions on ordinals is standard and unproblematic (the main difference with the finite case is that one needs to introduce a $\sup$ or $\...
- 32.5k
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, ...
- 20.5k
13
votes
3
answers
3k
views
What is Gödel's pairing function on ordinals?
I find many references to Gödel's pairing function on ordinals but I have not found a definition. What is it?
- 11.1k
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
11
votes
0
answers
747
views
Some questions about $0^{\sharp}$ and forcing over $L$
1-Let $P\in L$ be a nontrivial set forcing or even a tame class forcing (tameness in the sense of Sy Friedman; see for example his Handbook paper), and let $G$ be $P-$generic over $L$. Then it is well-...
- 32.2k
12
votes
1
answer
744
views
Can we change the Lebesgue measure by forcing?
Suppose $M$ is a model of ZFC, and $\mu^M$ is the Lebesgue measure on $\mathbb R^M$ such that $\mu^M(\mathbb R^M)=1$. It is known that if $r$ is a Cohen real over $M$ and $N=M[r]$ then $\mu^N(\mathbb ...
- 39.8k
12
votes
1
answer
1k
views
Forcing Diamond
It is well known that adding a subset of a regular cardinal $\kappa$ with partial functions of size $< \kappa$ forces $\Diamond_\kappa$. One can also see that if $S \in V$ is a stationary subset ...
- 18.6k
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 ...
- 13k
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
7
answers
15k
views
Easy proof of the uncountability of bijections on natural numbers
Is there an easy proof of the uncountability of bijections on natural numbers?
The proof that I have in mind is as follows -
$\text{Gal }(\overline{\mathbb Q}/\mathbb Q)$ is a proper uncountable ...
- 899
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
2
answers
1k
views
Questions about Prikry forcing and Cohen forcing
I have some questions.
The first one is about the product of Prikry's forcing.
Let $\kappa$ be a measurable cardinal, $U_1, U_2$ be normal measures on $\kappa$ and let $\mathbb{P}_{U_1}, \mathbb{P}...
- 32.2k
11
votes
2
answers
666
views
Non smallness of the set of anafunctors without AC?
Trying to construct a model category constructively is difficult. One often mention the fact that without the axiom of choice one cannot prove that the localization of the category of small categories ...
- 42.4k
10
votes
0
answers
465
views
Does Sageev's result need an inaccessible?
In 1981, building on work by Ellentuck in 1974, Sageev showed ("A model of ZF + there exists an inaccessible, in which the Dedekind cardinals constitute a natural non-standard model of arithmetic," ...
- 20.5k
11
votes
4
answers
2k
views
Earliest diagonal proof of the uncountability of the reals.
I cited the diagonal proof of the uncountability of the reals as an example of a `common false belief' in mathematics, not because there is anything wrong with the proof but because it is commonly ...
- 11.4k
11
votes
1
answer
704
views
Is $\mathfrak j_{2:1}=\mathfrak{j}_{2:2}$ in ZFC?
A function $f:\omega\to\omega$ is called
$\bullet$ 2-to-1 if $|f^{-1}(y)|\le 2$ for any $y\in\omega$;
$\bullet$ almost injective if the set $\{y\in \omega:|f^{-1}(y)|>1\}$ is finite.
Let us ...
- 42k
11
votes
2
answers
2k
views
Can GCH fail everywhere every way?
The following question is about if it is compatible to add to $\sf ZF$ an axiom asserting the existence of a countable transitive model of $\sf ZF$ such that for every strictly increasing function $f$ ...
- 11.3k
11
votes
2
answers
1k
views
Is sigma-additivity of Lebesgue measure deducible from ZF?
Is sigma-additivity (countable additivity) of Lebesgue measure (say on measurable subsets of the real line) deducible from the Zermelo-Fraenkel set theory (without the axiom of choice)?
Note 1. ...
- 16.6k
11
votes
0
answers
556
views
Various definitions of recursion from ordinal machines
Background: I'm trying to get an intuitive understanding of α-recursion and related concepts in higher recursion theory. Once nice book is Peter Hinman's Recursion-Theoretic Hierarchies, available ...
11
votes
2
answers
2k
views
Are grothendieck universes enough for the foundations of category theory?
Grothendieck universes are equivalent to ZFC+a strongly inaccessible cardinal. This is low on the large cardinal axiom list. Is it enough to place category theory on a firm foundational basis, and how ...
- 2,083
11
votes
4
answers
3k
views
the delta system lemma outside set theory
The lemma:
Any uncountable set $S$ of finite sets has an uncountable subset $\Delta \subseteq S$ and an $x$ such that $\forall a,b \in \Delta$, if $a \neq b$ then $a \cap b = x$. $\Delta$ is called a ...
- 543
11
votes
0
answers
374
views
A game of harmonic series(s)
Given a set $A\subseteq\mathbb{R}_{>0}$, consider the following (two-player, perfect-information, length-$\omega$) game $H_A$:
Players $1$ and $2$ alternately play strictly increasing natural ...
- 20.5k
11
votes
3
answers
1k
views
What is the shape of large cardinal tree in implication strength order?
There are two natural orders on large cardinal axioms.
(a) Consistency strength order
$\sigma \leq_C \theta \Longleftrightarrow ZFC\vdash Con(ZFC+\theta)\longrightarrow Con(ZFC+\sigma)$
(b) ...
user45939
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
2
answers
1k
views
Continuum-many independent vectors over Q in R as a Q-vector space
Let's put ourselves in the framework of ZF. Is it true that if we think of the set of real numbers as a rational vector space, there are continuum-many linearly independent vectors? I feel that we ...
- 35.5k
10
votes
1
answer
937
views
Possible inconsistency of weakly Shelah cardinals (I hope not)
A Mathoverflow question by Trevor Wilson defines weakly Shelah cardinals as follows:
A cardinal $\kappa$ is weakly Shelah if for all $f : \kappa \to \kappa$ there is some $\alpha < \kappa$ that is ...
- 1,097
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 ...
- 20.5k
9
votes
3
answers
1k
views
Is it consistent with ZFC (or ZF) that every definable family of sets has at least one definable member?
I consider definability to mean one of either cases:
Definability without parameters (in the language of set theory), or
Definability from ordinals and a real (in the same language).
So my question ...
- 1,416
9
votes
2
answers
3k
views
A question about Second-Order ZFC and the Continuum Hypothesis
Some logicians-such as G. Kreisel-have stated that the Continuum Hypothesis is decided in
ZFC2 ("Second-Order ZFC") although we do not know which way it is decided. This is rather
confusing, since it ...
- 6,215
9
votes
1
answer
509
views
Transcendence degree of the surreals over the subfield generated by the ordinals
Consider the Grothendieck ring $K[\Omega]$ of the semiring $\Omega$ of all ordinals under the operations of natural sum and product. Its quotient field $K(\Omega)$ is naturally a subfield of the ...
- 4,985
9
votes
2
answers
3k
views
Compact Hausdorff spaces without isolated points in ZF
$S$ is uncountable := $\vert\mathbb{N}\vert<\vert S\vert$
$S$ is noncountable := $\vert S\vert \not\leq \vert\mathbb{N}\vert$
$(X,T)$ is a nice space := $(X,T)$ is a compact Hausdorff space ...
user5810
9
votes
1
answer
1k
views
Uncountable disjoint closed coverings of $[0,1]$
It is well known that the unit interval $[0,1]$ cannot be decomposed as a countable union of pairwise disjoint closed (nonempty) subsets. See for instance this math.stackexchange question. The proof ...
- 1,688
9
votes
3
answers
3k
views
What does the axiom of replacement mean and why should I believe it?
Here Professor Blass describes the following cumulative hierarchy of sets:
Begin with some non-set entities called atoms ("some" could be "none" if you want a world consisting exclusively of sets), ...
- 101
9
votes
1
answer
701
views
Case study: what does it take to formulate and prove Quillen's small object argument in ZFC?
I'm getting a bit lost over at Peter Scholze's interesting question about removing the dependence on universes from theorems in category theory. In particular, I'm being forced to admit that I don't ...
- 64k
9
votes
2
answers
1k
views
Martin's cone theorem and recursion theory
Martin's remarkable cone theorem in the theory of determinacy says the following:
Suppose $A\subseteq \omega^\omega$ is Turing invariant and determined. If $\forall x\exists y(x\le_T y\& y\in ...
- 32.5k
8
votes
1
answer
755
views
Forcing mildly over a worldly cardinal.
A cardinal $\theta$ is worldly if $V_{\theta}$ is a model of ZFC. We could force to collapse $\theta$ to a successor cardinal, for example, and destroy the worldliness of $\theta$, but is there a ...
user10290
8
votes
1
answer
1k
views
Does the consistency strength hierarchy coincide with the "arithmetic consequence" hierarchy at ZF + Reinhardt?
In these slides (see especially slide 26), Steel emphasizes the phenomenon that for all known "natural" extensions of ZFC, the ordering by consistency strength agrees with the ordering by containment ...
- 64k
8
votes
1
answer
420
views
Undetermined games of "overdetermined" type
This is motivated by a previous question of mine, but I think it is ultimately more interesting (and hopefully easier to answer in the positive). In that question, a class of games (on $\omega$, of ...
- 20.5k
8
votes
2
answers
577
views
Possible cardinality and weight of an ordered field
Is it true (in ZFC) that for any regular infinite cardinal $\kappa$ there exists an ordered field of weight $\kappa$ and cardinality $2^\kappa$ (or at least $>\kappa$)?
The field of real numbers ...
- 42k
8
votes
1
answer
525
views
Intersection of two generic extensions
It is well known that the intersection of two models of ZFC does not have to be a model of ZFC (or even ZF). Now what if we restrict ourselves to models $M[G]$, $M[H]$ which are generic over $M$ for ...
8
votes
1
answer
580
views
Indeterminacy of long games
Hello, all,
Several months ago I sat in on a seminar on AD+, which was incredibly wonderful even though I could barely follow it at all. AD+ is a technical variant of AD, the axiom of determinacy, ...
- 20.5k
8
votes
4
answers
1k
views
Formalizations of The Matchstick Diagram Representation of Ordinals
The matchstick diagram is a really interesting and intuitive method of representing countable ordinals. However, because of how difficult it is to graphically represent ordinals with it, I started ...
- 1,252
8
votes
1
answer
769
views
Can $V\neq\text{HOD}$ if every $\Sigma_2$-definable set has an ordinal-definable element?
This question arises from an issue arising in user38200's recent question concerning models of set theory in which every definable set has a definable element. In my answer to that question, with ...
- 236k
8
votes
1
answer
736
views
Stationarity and Fodor's lemma for a (nice) poset?
The notion of a stationary set is peculiar in that it applies to subsets of certain very particular posets -- ordinals or powersets. At least to a non-set-theorist, the situation seems to beg for the ...
- 64k
7
votes
2
answers
268
views
Meeting a set of lines in $\mathbb{R}^n$
Fix an integer $n\ge 2$ and suppose that ${\cal L}$ is a set of lines in $\mathbb{R}^n$. Is there a set $M\subseteq \mathbb{R}^n$ with the following properties?
$M$ intersects all the elements of ${\...
- 48.9k
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
1k
views
Set-theoretic tautologies
Let us consider unquantified formulas of a set theory (for example, NBG), more precisely,
the formulas, constructed from variables and the constants $\emptyset, V$ (the empty set
and the class of all ...
- 897
7
votes
1
answer
488
views
Ref. request: Additive probability measure on $\mathcal P({\bf N})$ supplies subset of $\mathbf R$ without Baire property
ZFC proves, among the other things, the existence of a (finitely) additive probability measure $\theta: \mathcal P(\mathbf N) \to \mathbf R$ on the power set of $\mathbf N$ such that $\theta(X) = 0$ ...
- 10.5k
7
votes
1
answer
555
views
Limitations of determinacy hypotheses in ZFC
When considering (set-theoretic) games, we have three parameters we can adjust:
Definability of the payoff set
The set of legal moves
The length of the game
When working in $\textsf{ZFC}$, what are ...
- 1,170