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 ...
- 839
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 ...
- 17.1k
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{...
- 19k
17
votes
What's the earliest result (outside of logic) that cannot be proven constructively?
According to Wikipedia, in 5th century BCE, Bryson of Heraclea spoke of a special case of the intermediate value theorem. If we're very generous, that would be an early occurrence of a constructively ...
- 48k
15
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 ...
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 ...
- 17.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 ...
- 38.2k
12
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 ...
- 137k
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 ...
- 19k
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 $...
- 19k
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,281
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}...
- 7,654
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 ...
- 19k
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,345
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,345
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)...
- 4,102
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 ...
- 225k
7
votes
When can a function defined on $[a, b] \cup [b, c]$ be constructively extended to a function defined on $[a, c]$?
The question for what $S$ this extension property holds is one I've looked at in the context of computable analysis. I've formulated the notion as follows:
Let $\mathbb{T}$ be the space of ternary ...
- 4,481
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,686
6
votes
When can a function defined on $[a, b] \cup [b, c]$ be constructively extended to a function defined on $[a, c]$?
I am going to work Bishop-style (in particular I am giving myself countable choice, we can try to get rid of it later).
Observe that the Cauchy completion of $[a,b] \cup [b,c]$ is $[a,c]$. For this to ...
- 48k
6
votes
What's the earliest result (outside of logic) that cannot be proven constructively?
A somewhat different type of example, not as early as the ones in Andrej Bauer's answer, but perhaps a bit more resistant to "moving the goalposts," is an ineffective result in number theory....
- 78.3k
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
$\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 ...
- 225k
5
votes
What are some reasonable-sounding statements that are independent of ZFC?
"There exists a complete metric space $(X,d)$ and a Borel probability measure $\mu$ on $X$ with non-separable support."
This has been discussed elsewhere on MO (I forget where, sorry), but ...
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 ...
- 38.2k
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 $\...
- 8,752
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&...
- 38.2k
5
votes
When can a function defined on $[a, b] \cup [b, c]$ be constructively extended to a function defined on $[a, c]$?
This is not an answer (since that is already well covered by the other answers), but there's a relevant paper that you will probably be interested in: Palmgren, From Intuitionistic to Point-Free ...
- 3,846
Only top scored, non community-wiki answers of a minimum length are eligible