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
2
answers
911
views
Does van der Waerden's Theorem hold for $\omega_1$?
One way to phrase van der Waerden's Theorem is:
For every finite coloring of $\mathbb N$ and every finite $F \subseteq \mathbb N$, there exist $a,b \in \mathbb N$ such that $a + b \cdot F$ is ...
- 18.6k
13
votes
2
answers
2k
views
Peculiar examples with Axiom of Countable Choice ?
I've been going over the extremely interesting discussions about Axiom of Choice.
It looks to me like all the "weird" consequences of AC (Banach-Tarski etc) come from using it on uncountable ...
- 581
13
votes
0
answers
345
views
Can you define a probability measure on the set of countable transitive models of ZFC?
It is well known that the set of hereditarily countable sets $H(\omega_1)$ —or, if you prefer, $H_{\omega_1}$— has cardinality $2^{\aleph_0}$, and I understand that every countable ...
- 1,124
13
votes
1
answer
561
views
Iterating Neeman's forcing
In the paper, "Forcing with sequences of models of two types," (MR3201836), Neeman claims that, using a supercompact and a weakly compact above, one can force with his pure side conditions ...
- 18.6k
13
votes
1
answer
875
views
Ultrafilter theorem and translation invariant measures
The usual Vitali construction of a non-Lebesgue measurable set generalizes to a proof that there are no (non-trivial) translation invariant measures on $\mathcal P\mathbb R$.
On the other hand, there ...
- 1,688
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 ...
- 20.5k
13
votes
3
answers
796
views
How to make countably closed forcing "nice" without choice
When working over a model $V$ of $ZFC$, countably closed forcings are extremely nice:
If $\mathbb{P}$ is countably closed, then $V[G]$ has no new $\omega$-sequences of elements of $V$. In ...
- 20.5k
13
votes
2
answers
1k
views
Can we define an "empirically generic" real number?
Summary: My question, in a nutshell, is how we should intuitively imagine a generic real number (as opposed to a random one), and whether we can construct numbers which empirically behave like generic ...
- 32.5k
12
votes
2
answers
778
views
Why "adding" a single extender cannot give an L-like inner model for say, a strong cardinal?
The constructible universe $L$ is too thin for large cardinals greater than measurable. To build $L$-like inner models for large cardinal, it is natural to think about "adding" the evidences into the ...
- 779
12
votes
2
answers
2k
views
Connections between Complexity Theory & Set Theory
Inspired by Joshua Grochow and Iddo Tzameret's answers in a post on http://cstheory.stackexchange.com , I would like to get more references on possible connections between complexity theory and set ...
12
votes
2
answers
1k
views
Finite support iterations of $\sigma$-centered forcing notions
I am looking for a proof (or better, a reference) of the following fact:
The finite support iteration of $\sigma$-centered forcing notions is again $\sigma$-centered, assuming we iterate less than $(...
- 14k
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
2
answers
490
views
Conflating reals and sets of countable ordinals "nicely"
It is consistent with ZFC that $2^{\aleph_1}=2^{\aleph_0}$. This can be gotten easily via forcing; more interestingly, it is a direct consequence of forcing axioms (which also set this value at $\...
- 20.5k
12
votes
1
answer
448
views
Comparing generic versions of $\mathbb{R}$
This question was previously asked and bountied at MSE, unsuccessfully.
I'm currently interested in the behavior of cardinalities in generic extensions of models of $\mathsf{ZF+\neg AC}$, and ...
- 20.5k
12
votes
1
answer
681
views
Can there be a small complete category in ZF?
It's a ZFC theorem of Freyd, any small complete category is a preorder. Freyd's theorem continues to hold in any Grothendieck topos. But Hyland showed it fails in some elementary toposes.
I don't ...
- 64k
11
votes
2
answers
679
views
Sets that are not $\infty$-Borel
I have seen a few techinques for proving that certain sets of real numbers are $\infty$-Borel (definition) but it just occurred to me that I don't know of any way to prove that a set of real numbers ...
- 5,471
12
votes
0
answers
357
views
Undetermined copy/diagonalize games without CH
This question was the motivation behind an earlier question of mine; having thought about it some more, that question seems nontrivial and the connection is actually pretty tenuous anyways, so I've ...
- 20.5k
12
votes
0
answers
240
views
Does $2^{\aleph_0}\rightarrow [\aleph_1]^2_3$ require that the continuum is weakly inaccessible?
A classic result of Sierpiński shows that $2^{\aleph_0}\nrightarrow [\aleph_1]^2_2$, that is, there is a coloring of pairs of real numbers using two colors such that both colors appear on any ...
- 7,125
12
votes
1
answer
556
views
Building the real from Dedekind finite sets
It is well known that the real numbers can be countable union of countable sets by starting with GCH and taking a finite support permutations while collapsing all of $\aleph_n$ for natural $n$.
The ...
- 1,676
12
votes
2
answers
823
views
monochromatic cycle-free colouring of the complete graph on R?
Hi
So there is an edge-colouring of a complete graph on R (the reals), with countably many colours that as no monochromatic triangle. To find it map R to (0,1) write the numbers in binary and if 2 ...
- 436
12
votes
1
answer
780
views
Does every countable set of Turing degrees have an upper bound, without AC?
It is easy to see that every countable collection of sets $A_n\subseteq\mathbb{N}$ has an upper bound in the Turing degrees, since we can just take a copy of their disjoint sum $\oplus_n A_n=\{\langle ...
- 236k
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 ...
- 20.5k
12
votes
2
answers
429
views
Trading Choice for Comprehension (or Replacement)
This question is basically a request for clarification about a remark made by Sam Sanders in a comment to another question: IIUC what he's saying, there are statements that can be proved either with a ...
- 32.5k
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 ...
- 20.5k
12
votes
2
answers
1k
views
Is there a "large powerset axiom" so extreme that it disproves the existence of strongly inaccessible cardinals?
If $\kappa$ is a strongly compact cardinal, then the singular cardinal hypothesis holds above $\kappa$. Hence the existence of large cardinals at the level of "strongly compact" or above is ...
- 3,793
12
votes
1
answer
1k
views
Can there be only one (uncountable transitive model of ZFC)?
It is an immediate consequence of Cohen's forcing that if there is one countable transitive model of $\sf ZFC$, then there are many of them. Even if all of these models are of the same height, there ...
- 39.8k
12
votes
1
answer
695
views
A new cardinality living in every forcing extension?
I'm broadly interested in notions of "generic presentability" - when a given object exists in every forcing extension of the universe by some fixed forcing, at least up to the appropriate ...
- 20.5k
12
votes
4
answers
2k
views
Axiom of Replacement in Category Theory
Does the usual development of category theory (within Goedel-Bernays set theory, for example) require the axiom of replacement? I would have asserted that this was obviously true, but it seems to be ...
- 6,870
12
votes
1
answer
296
views
Can the cardinal $2^{\aleph_0}$ be order-embedded in ${\cal P}(\omega)/(\text{fin})$?
For $A,B\in{\cal P}(\omega)$ we say $A\subseteq^* B$ if $A\setminus B$ is finite (that is, $A$ is "almost contained" in $B$). We write $A\simeq_{\text{fin}} B$ if $A\subseteq^* B$ and $B\...
- 48.9k
12
votes
1
answer
582
views
Is a locally finite union of $G_\delta$-sets a $G_\delta$-set?
Problem. Let $\mathcal F$ be a locally finite (or even discrete) family of (closed) $G_\delta$-sets in a topological space $X$. Is the union $\cup\mathcal F$ a $G_\delta$-set in $X$?
Remark. The ...
- 41.9k
11
votes
1
answer
441
views
Concerning Silver's result
Jack Silver proved that if $x$ is a real so that every $x$-admissible ordinal is a cardinal in $L$, then $0^{\sharp}$ exists.
I wonder whether various weaker or stronger versions of Silver's result ...
- 4,201
11
votes
1
answer
799
views
Restrictions of null/meager ideal
Let I denote the null (resp. meager) ideal on reals. Is it consistent that for any pair of non null (resp. meager) sets A and B, there is a null (resp. meager) preserving bijection between A and B? In ...
- 9,641
10
votes
0
answers
514
views
Existence of a regular subposet which collapses everything except the top cardinal
Suppose $\delta$ is an inaccessible cardinal, and $\mathbb{P}$ is the Levy Collapse $\text{Col}(\kappa, \delta)$ which adds a surjection from $\kappa \to \delta$ (for some regular $\kappa < \delta$)...
- 2,231
11
votes
3
answers
534
views
Who proved "sets in every generic are already in the ground model?"
Suppose $\mathbb{P}$ is a notion of forcing in the ground model $V$, and $X$ is a set which is in $V[G]$ for every $\mathbb{P}$-generic filter $G$. Then $X\in V$ already, by a fairly simple (if ...
- 20.5k
11
votes
4
answers
2k
views
Very Large Cardinal Axioms and Continuum Hypothesis
Are very large cardinal axioms like $I_0$, $I_1$, $I_2$ consistent with $CH$ and $GCH$?
user45878
11
votes
2
answers
725
views
Is a Borel image of a Polish space analytic?
A topological space $X$ is called analytic if it is a continuous image of a Polish space, i.e., the image of a Polish space $P$ under a continuous surjective map $f:P\to X$.
We say that a topological ...
- 41.9k
11
votes
3
answers
794
views
When are two forcing posets "the same"?
Let $B$ and $C$ be complete Boolean algebras. To avoid triviality I may also want them to be atomless. For $b\in B$ nonzero, denote $B\upharpoonright b=\{p\in B:p\leq b\}$, which can be viewed as a ...
- 877
10
votes
1
answer
350
views
What is the smallest density of a metrizable space without countable separation?
A Tychonoff space $X$ is defined to have countable separation if some (equivalently, any) compactification $bX$ of $X$ contains a countable family $\mathcal U$ of open sets such that for any points $x\...
- 41.9k
11
votes
1
answer
892
views
Are all Grothendieck topologies on Set equivalent?
The category $\textbf{Set}$ can be given a Grothendieck topology where the covering families are jointly surjective families of set inclusions $\{X_i\stackrel{\phi_i}{\hookrightarrow} X\}\in\mathrm{...
- 23.3k
11
votes
2
answers
483
views
The "strong" measure number
Beyond measure zero we have yet another measure-y notion of smallness: strong measure zero. A set $S\subseteq\mathbb{R}$ is strong measure zero if, for any $f:\mathbb{N}\rightarrow\mathbb{R}_{>0}$, ...
- 20.5k
11
votes
2
answers
808
views
What is the depth of the "provability hierarchy"?
I am not a logician or set theorist, so hopefully this makes sense. Let $T$ be a theory which is expressive enough to make statements like "Statement $A$ has a proof in $T$"; for example, $...
- 23k
11
votes
1
answer
792
views
Axiom of choice and algebraic tensor product
The first part of the question was asked on Math-stackexchange.
Let $V$, and $W$ be vector spaces. By the universal property of the tensor product,
there is a canonical map from $V^*\otimes W^*$ ...
- 1,035
11
votes
3
answers
2k
views
Kunen's use of Countable Transitive Models
Hi,
I have a doubt concerning Kunen's exposition of forcing in his classical book (arguably $the$ book on forcing). When dealing with Countable Transitive Models to set up the forcing machinery, ...
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
11
votes
1
answer
418
views
A monotone countably cofinal function from $\omega^\omega$ to $\omega^{\omega_1}$
For a set $X$ we endow the set $\omega^X$ of all functions from $X$ to $\omega$ with the natural partial order $\le$ defined by $f\le g$ iff $f(x)\le g(x)$ for all $x\in X$.
A function $f:\omega^\...
- 41.9k
11
votes
1
answer
812
views
Set-theoretic geology: controlled erosion?
I have to say that after the two last posts by Timothy Chow on Forcing I got so intrigued that I am trying to rethink the little I know about this formidable chapter of mathematics.
I have also to add ...
- 7,853
11
votes
1
answer
708
views
Absoluteness of well-orderability
The property of well-orderability is upward absolute for transitive models of ZF: by Replacement in the smaller class, specifically Mostowski collapse, this is equivalent to the upward absoluteness of ...
- 2,550
11
votes
2
answers
605
views
Example of an uncountable scattered space with some properties
This might be an easy question, maybe the example I'm looking for is common knowledge. As always, recall that a topological space $X$ is scattered if and only if every non-empty subset $Y$ of $X$ ...
- 674
11
votes
1
answer
564
views
Is the inclusion version of Kunen inconsistency theorem true?
The relations $\in$ and $\subsetneq$ seem so similar in some sense. For example they are equal on ordinal numbers. So there is a natural question about their possible similar behaviors on the ...
user36136
11
votes
2
answers
1k
views
What are the reflective subcategories of the category of presentable categories?
I am actually interested in the $\infty$-categorical case, but the same question is meaningful in the $1$-categorical situation as well.
A nice property of presentable $\infty$-categories is that if ...
- 2,310