37
votes
Accepted
How undecidable is the spectral gap?
I haven't read the paper carefully, but this appears to be a standard undecidability result, of the sort of which there are dozens if not hundreds in the literature, of the same ilk as the ...
- 7,055
28
votes
Should axiomatic set theory be translated into graph theory?
Although it may seem on the face of it that this proposal is just a question of terminology — yes, a model of set theory is a certain kind of acyclic digraph — nevertheless, my opinion is ...
- 216k
26
votes
In the two-person Killing the Hydra game, what is the winning strategy?
We can think of this as a game of "omega-nim;" to more precise since the game you are describing is impartial, operating under the normal play convention, and finite we have that the Sprague-Grundy ...
- 831
21
votes
Accepted
A contradiction in the Set Theory of von Neumann–Bernays–Gödel?
The comments to the question, especially those by Emil Jeřábek and Joel Hamkins make it clear that the proposed inconsistency proof breaks down because the recursive construction carried out in the ...
- 16.1k
20
votes
How undecidable is the spectral gap?
I interpret your question to be asking about the transition from
computable undecidability to Gödelian or logical
undecidability, and furthermore about the extent to which this
logical ...
- 216k
19
votes
Accepted
Bidi: A new cardinal characteristic of the continuum?
Using a characterisation of $\min\{\mathfrak{d},\mathfrak{r}\}$ that comes from dualizing a result in Kamburelis' and Węglorz's paper called "Splittings":
A. Kamburelis, B. Węglorz, Splittings, ...
- 763
18
votes
Why can we assume a ctm of ZFC exists in forcing
Expositionally, forcing is (usually) easier to understand with a c.t.m. This does indeed lead to somewhat different results, such as
$(*)\quad$ If there is a countable transitive model of $\mathsf{...
- 18.2k
14
votes
Accepted
The existence of definable subsets of finite sets in NBG
The answer is in the negative. Let $\mathcal{M}$ be an $\omega$-nonstandard model of ZF, and $\mathfrak{X}$ be the collection of parametrically definable subsets of $\mathcal{M}$. Let $I$ be the cut ...
- 16.1k
13
votes
Accepted
Relationship between AC, WO, and Zorn's lemma in ZF-Powerset
This is a classic theorem of Zarach, that it is consistent that ${\sf ZF}^-$ holds with the Axiom of Choice, but not every set can be well-ordered.
Zarach, Andrzej, Unions of ${\sf ZF}^-$models ...
- 37.5k
12
votes
What are some reasonable-sounding statements that are independent of ZFC?
$``$Given any function $f:\Bbb R\times\Bbb R\to\Bbb R$, there exist functions $g_n,h_n:\Bbb R\to \Bbb R\,$ ($n=1,2,...$) such that$$f(x,y)=\sum_{n=1}^\infty g_n(x)h_n(y)\quad(x,y\in\Bbb R)."$$That ...
11
votes
What are some reasonable-sounding statements that are independent of ZFC?
Is there a vector space with three non-isomorphic Hilbert space structures? A negative answer is equivalent to the conjunction CH + SCH.
Pf: An infinite-dimensional Hilbert space with Hilbert ...
10
votes
Is it still an open problem whether $\mathbb{R}^\omega$ is normal in the box topology?
I'm transcribing here some things from the comments section, so that this question can be marked as answered:
The problem is still open.
This survey by Roitman and Williams, from 2015, said that it ...
10
votes
Arithmetic statement which is independent, and whose independence is independent, and so on?
If $p$ is independent of ZFC, and ZFC is sound, then $I(p)$ is independent of ZFC.
Indeed, because ZFC is sound, it can't disprove $I(p)$ because $I(p)$ is true.
However, $I(p)$ implies consistency of ...
- 129k
9
votes
Is Axiom of Choice equivalent to its version for families of sets, indexed by ordinals?
It is strictly weaker than choice. This is explained in Asaf Karagila's answer at MSE: the $L(\mathbb{R})$ of $L$ + $\aleph_1$-many Cohen generics witnesses this.
(There the principle is phrased for ...
- 18.2k
9
votes
Accepted
Arithmetic statement which is independent, and whose independence is independent, and so on?
If we fix things to avoid Will Sawin's observation, then the answer is yes under any reasonable interpretation I can think of.
For example, consider the following: let $J(p)$ be the sentence "If $...
- 18.2k
8
votes
How undecidable is the spectral gap?
Does it represent a new way of proving independence results compared to forcing, etc.? In other words, is it an advance on Gödel sentences and the continuum hypothesis?
No one's quite said it yet, so:...
- 113k
8
votes
Accepted
Can $H_{\omega_1}$ and $H_{\omega_2}$ be in bi-interpretation synonymy?
A theorem of Harrington (Theorem B of his paper "Long projective wellorders") says $\text{MA} + \neg\text{CH}$ is consistent with a projective wellorder of the reals, hence a wellorder of $H_{\omega_1}...
- 6,174
8
votes
Accepted
Variants of reflection principle
The answer is "yes". The principle you call $\text{RP}^*$ is called "reflection to internally club sets" in the literature; as far as I know this terminology first appeared in Foreman-Todorcevic's ``...
- 2,271
7
votes
Examples of independent $\Sigma_4^1$ statements
As a starting point, think about the sentence "There is a nonconstructible real." This is $\Sigma^1_3$ and clearly not downwards-absolute. However, it is upwards-absolute.
To get the desired ...
- 18.2k
7
votes
Accepted
Is $\mathfrak p=\omega_1$ equivalent to the existence of a Hausdorff gap without infinite pseudointersection?
Yes. This is a result due to Nyikos and Vaughan from 1983, appearing the paper
Nyikos, Peter J.; Vaughan, Jerry E., On first countable, countably compact spaces. I: ((\omega_ 1,\omega^*_ 1))-gaps, ...
- 7,337
7
votes
A new cardinal characteristic (related to partitions)?
This is not an answer, but hopefully it's a helpful observation:
(1) If $U$ is an ultrafilter on $\omega$ and $\mathcal{P}$ is a finitary partition of $\omega$, then there is $A\in U$ such that $A\...
- 7,337
7
votes
Accepted
The cardinal characteristic $\mathfrak r_{(X,f)}$ of a dynamical system
Unfortunately, $\mathfrak r_{(2^\omega,f)}\ge\mathfrak r$. Indeed, let $\mathcal R$ be a family of infinite subsets of $\omega$ such that $|\mathcal R|=\mathfrak r_{(2^\omega,f)}$ and for any $x=(x_n)...
- 3,627
7
votes
Accepted
A strong form of the Axiom Schema of Replacement
Your axiom is known as the axiom of collection.
There are a variety of contexts where it is known that replacement does not imply collection over what may seem reasonable theories.
For example, in set ...
- 216k
6
votes
Accepted
A topologically transitive dynamical system without dense orbits
The answer is yes:
there is a topologically transitive dynamical system without dense orbits.
Indeed,
let X be a topological space that is not separable. Let $\ K=X^{\Bbb Z},\ $ and let $\ G\ $ be ...
- 4,590
5
votes
How undecidable is the spectral gap?
I'm no expert, but the short version of the paper
http://arxiv.org/pdf/1502.04135v1.pdf
seems to address these questions in the conclusion:
But what does it mean for a physical property to be ...
- 10.7k
5
votes
Accepted
$\omega_2$-sequence of Suslin trees
The answer is yes, and indeed, one can even have that any countable
number of the Suslin trees join to a Suslin tree.
To see this, simply force with countable support to add $\omega_2$
many Suslin ...
- 216k
5
votes
What are some reasonable-sounding statements that are independent of ZFC?
https://www.scottaaronson.com/blog/?p=2725
Busy Beaver $8000$ is independent of ZFC. I think this is in the same spirit of this question.
5
votes
Accepted
Implications of the existence of a pair of surjective functions, without Axiom of Choice
No, and here is a counterexample.
Suppose that $|\Bbb R|<|[\Bbb R]^\omega|$, that is, there are more countable subsets of reals than reals. This is indeed possible, e.g. if all sets of Lebesgue ...
- 37.5k
5
votes
Dedekind-"finiteness" for arbitrary limit cardinals
Yes, it is possible; one can see this by a variant of a standard proof of the consistency of ZF + $\neg$AC, as witnessed in symmetric submodels of forcing extensions. Start with universe $V=L$. Let $\...
- 6,999
5
votes
Accepted
Dedekind-"finiteness" for arbitrary limit cardinals
Start with your favourite model of $\sf ZFC$, your favourite regular cardinal $\mu$, and your favourite limit cardinal $\lambda>2^\mu$.
Now consider the ${<}\mu$-support product $\prod_{\alpha&...
- 37.5k
Only top scored, non community-wiki answers of a minimum length are eligible