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 ...
user avatar
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 ...
user avatar
25 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 ...
user avatar
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 ...
user avatar
18 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, ...
user avatar
  • 753
17 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{...
user avatar
16 votes

What are some reasonable-sounding statements that are independent of ZFC?

Laver tables of order $n$ provide a potential answer (although it's not proven to be independent of ZFC, and may not be independent of ZFC). The Laver table of order $n$ is the $2^n \times 2^n$ table ...
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 ...
user avatar
  • 35.4k
13 votes

Independence of the countable axiom of choice

I'm going to play fast and loose with details here, but the outline is correct. To answer your new questions: no, there is no short proof. And this only shows one direction of the indpenedence of AC, ...
user avatar
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 ...
10 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

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 ...
user avatar
  • 116k
9 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 ...
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 ...
user avatar
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 $...
user avatar
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 ``...
user avatar
  • 2,221
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:...
user avatar
7 votes
Accepted

Relationship between fragments of the axiom of choice and the dependent choice principles

The idea is to mimic the permutation models as given in Jech. One can then ask, "Well, in Jech he chooses some set of objects in the full universe, and shows it has a support. But in forcing we ...
user avatar
  • 35.4k
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 ...
user avatar
7 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}...
user avatar
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\...
user avatar
6 votes

Given a cardinal k, what's the biggest dense linear order with a dense subset of size k?

This is very late, but in 2012, Artem Chernikov, Itay Kaplan and Saharon Shelah posted on arXiv a paper titled "On non-forking spectra" ( http://arxiv.org/abs/1205.3101 ). They claim that it is ...
user avatar
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 ...
user avatar
  • 3,439
6 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)...
user avatar
  • 2,717
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 ...
user avatar
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 ...
user avatar
  • 8,968
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

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, ...
user avatar
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 ...
user avatar
  • 35.4k
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 $\...
user avatar
  • 5,044

Only top scored, non community-wiki answers of a minimum length are eligible