Questions tagged [independence-results]
This tag is for questions about proving that some statement is independent from a theory, meaning it is neither provable nor refutable from that theory. Common examples are the continuum hypothesis from the axioms of ZFC, and the axiom of choice from the axioms of ZF.
77 questions
297
votes
34
answers
52k
views
What are some reasonable-sounding statements that are independent of ZFC?
Every now and then, somebody will tell me about a question. When I start thinking about it, they say, "actually, it's undecidable in ZFC."
For example, suppose $A$ is an abelian group such ...
54
votes
1
answer
3k
views
In the two-person Killing the Hydra game, what is the winning strategy?
My question is which player has a winning strategy in the
two-player version of the Killing the Hydra game?
In their amazing paper,
Kirby, Laurie; Paris, Jeff, Accessible independence results for ...
- 236k
51
votes
4
answers
7k
views
How undecidable is the spectral gap?
Nature just published a paper by Cubitt, Perez-Garcia and Wolf titled Undecidability of the Spectral Gap, there is an extended version on arxiv which is 146 pages long. Here is from the abstract:"Many ...
- 1,731
44
votes
3
answers
5k
views
"Simpler" statements equivalent to Con(PA) or Con(ZFC)?
Given any reasonable formal system F (e.g., Peano Arithmetic or ZFC), we all know that one can construct a Turing machine that runs forever iff F is consistent, by enumerating the theorems of F and ...
- 9,823
33
votes
1
answer
2k
views
Is it still an open problem whether $\mathbb{R}^\omega$ is normal in the box topology?
On page 205 of his Topology textbook, James Munkres made an interesting remark:
It is not known whether $\mathbb{R}^\omega$ is normal in the box topology. Mary-Ellen Rudin has shown that the answer ...
- 4,587
32
votes
1
answer
2k
views
Should axiomatic set theory be translated into graph theory?
Recently I saw the abstract of a paper by Nash-Williams: ``Should axiomatic set theory be translated into graph theory?''. The abstract, taken from Mathscinet says the following:
The author ...
- 32.1k
32
votes
1
answer
2k
views
Bidi: A new cardinal characteristic of the continuum?
This question assumes familiarity with combinatorial cardinal
characteristics of the continuum.
Identify an infinite set $a\subseteq\mathbb{N}$ with its increasing
enumeration. Thus, for each natural ...
- 3,104
22
votes
3
answers
2k
views
Nice algebraic statements independent from ZF + V=L (constructibility)
Background and motivation
I've always been fascinated about algebraic statements independent from ZFC set theory. One such fascinating example comes from considering $\rm{Ext}^1_\mathbb{Z}(A,\mathbb{Z}...
user1437
18
votes
3
answers
3k
views
What's the earliest result (outside of logic) that cannot be proven constructively?
Although mathematicians usually do not work in constructive mathematics per se, their results often are constructively valid (even if the original proof isn't).
An obvious counter-example is the law ...
- 6,353
18
votes
3
answers
1k
views
Spectra of elements of a Banach algebra and the role played by the Hahn-Banach Theorem.
This problem was posed on Math StackExchange some time ago, but it did not garner any solutions there. I think that it is interesting enough to be posed here on Math Overflow, so here it goes.
Let $ \...
- 816
16
votes
1
answer
2k
views
A contradiction in the Set Theory of von Neumann–Bernays–Gödel?
Thinking on the theory NBG (of von Neumann–Bernays–Gödel) I arrived at the conclusion that it is contradictory using an argument resembling Russell's Paradox. I am sure that I made a mistake in my ...
- 41.8k
16
votes
1
answer
1k
views
Kaplansky's conjecture and Martin's axiom
Recall Kaplansky's conjecture which states that every algebra homomorphism from the Banach algebra C(X) (where X is a compact Hausdorff topological space) into any other Banach algebra, is ...
- 32.1k
15
votes
4
answers
2k
views
Is every p-point ultrafilter Ramsey?
A non-principal ultrafilter $\mathcal{U}$ on $\omega$ is a p-point (or weakly selective) iff for every partition $\omega = \bigsqcup _{n < \omega} Z_n$ into null sets, i.e each $Z_n \not \in \...
- 3,982
14
votes
3
answers
2k
views
Is the Axiom of Union independent of the rest of ZF?
Short version: Is the axiom of union independent of the rest of axioms of ZF?
NO) Tourlakis (2003) says in p. 177 that the axiom of union can be derived from the rest of ZF if an appropriate version ...
- 243
13
votes
0
answers
325
views
$\mathsf{AC}_\mathsf{WO}+\mathsf{AC}^\mathsf{WO}\Rightarrow \mathsf{AC}$?
Let
$\mathsf{AC}_\mathsf{WO}$: Every well-orderable family of non-empty sets has a choice function.
$\mathsf{AC}^\mathsf{WO}$: Every family of non-empty well-orderable sets has a choice function.
My ...
- 2,286
11
votes
5
answers
3k
views
Minimal subset of axioms for ZFC
Hello all, one may look for "minimal system of axioms" for ZFC (or any other
theory) in the following (unusual) sense : say that a subset S of ZFC is
"sufficient" if there is an explicit procedure ...
- 3,595
11
votes
6
answers
1k
views
When can a function defined on $[a, b] \cup [b, c]$ be constructively extended to a function defined on $[a, c]$?
Let $a, b, c \in \mathbb R$ such that $a \le b \le c$. Let $S$ be some set and $f : [a, b] \cup [b, c] \to S$ be a function. When can we find a function $g : [a, c] \to S$ that meets the following ...
- 6,353
11
votes
3
answers
994
views
Why can we assume a ctm of ZFC exists in forcing
Following Kunen's book, it makes clear that countable transitive models (ctm) exist only for a finite list of axioms of ZFC. So, why can we assume a ctm of the whole ZFC axioms exists and use it as ...
- 111
11
votes
1
answer
628
views
A new cardinal characteristic (related to partitions)?
In this post I will discuss some cardinal characteristic of the continuum, related to partitions of $\omega$ and would like to know if it is equal to some known cardinal characteristic.
By a partition ...
- 41.8k
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 ...
- 41.8k
11
votes
0
answers
256
views
Existence of a strong antichain
Call an antichain (set of pairwise incomparable elements) $A$ of a poset $P$ strong if for every $p,q \in P$ with $p \leq q$ there exists an $a\in A$ which is comparable with both $p$ and $q$.
...
- 111
10
votes
3
answers
2k
views
Reference Request: Independence of the ultrafilter lemma from ZF
I'm looking for references for the following facts concerning the ultrafilter lemma (~ "there exist non-principal ultrafilters"):
The ultrafilter lemma is independent of ZF.
ZF + the ultrafilter ...
- 1,347
10
votes
2
answers
3k
views
Independence of the countable axiom of choice
How does one proove that the Countable axiom of choice is not provable in ZF?Is there any brief proof?Does the Independence of the countable axiom of choice implies the independence of the axiom of ...
- 101
9
votes
2
answers
1k
views
Given a cardinal k, what's the biggest dense linear order with a dense subset of size k?
It's not hard to show that for any cardinal $\kappa$, there is no dense linear order without endpoints (DLO) of size greater than $2^{\kappa}$ that has a dense subset of size $\kappa$. But one can ...
- 3,982
9
votes
1
answer
482
views
Relationship between AC, WO, and Zorn's lemma in ZF-Powerset
In regular ZF, AC, WO, and Zorn's Lemma are equivalent, but every proof I know (of the implication AC -> WO and AC -> Zorn) uses the axiom of choice on the powerset of X (where X is the Set which is ...
- 1,799
9
votes
2
answers
1k
views
Relationship between fragments of the axiom of choice and the dependent choice principles
The dependent choice principle ${\rm DC}_\kappa$ states that if $S$ is a nonempty set and $R$ is a binary relation such that for every $s\in S^{\lt\kappa}$, there is $x\in S$ with $sRx$, then there ...
- 2,240
9
votes
1
answer
489
views
Intuition behind Pincus' "injectively bounded statements"
In
David Pincus, Zermelo-Fraenkel Consistency Results by Fraenkel-Mostowski Methods,
The Journal of Symbolic Logic, Vol. 37, No. 4 (Dec., 1972), pp. 721-743
Pincus introduces the notion of ...
- 35.4k
8
votes
3
answers
745
views
Natural statements independent from true $\Pi^0_2$ sentences
I am looking for sentences in the language of first order arithmetic ($0,1,+,\cdot,\leq$) which are independent from $\Pi^0_2$ consequences of true arithmetic $\Pi^0_2\text{-}\mathsf{Th}(\mathbb{N})$. ...
- 5,502
8
votes
1
answer
323
views
A surjection from square onto power: Is limit Hartogs/Lindenbaum number necessary?
I am considering the construction in [Peng—Shen—Wu] in which the authors show the consistency of a set $X$ such that there is a surjection from $X^2$ onto the power set of $X$ (henceforth $\mathscr{P}(...
- 2,171
8
votes
1
answer
490
views
Natural $\Pi_1$ sentence independent of PA
Order invariant graphs and finite incompleteness by Harvey Friedman gives an example of a combinatorial/non-metamathematical $\Pi_1$ sentence that is independent of ZFC. Is there a simpler example of ...
- 2,203
8
votes
0
answers
238
views
Metrically Ramsey ultrafilters
On Thuesday I was in Kyiv and discussed with Igor Protasov the system of MathOverflow and its power in answering mathematical problems. After this discussion Igor Protasov suggested to ask on MO the ...
- 41.8k
7
votes
6
answers
2k
views
Formal proof of Con(ZFC) => Con(ZFC + not CH) in ZFC
Is it possible to prove $Con(ZFC) \rightarrow Con(ZFC + \neg CH)$ purely within ZFC? To prove this (using forcing) one seems to need a countable transitive model of ZFC. The texts I am reading avoid ...
- 365
7
votes
1
answer
457
views
The existence of definable subsets of finite sets in NBG
This question is motivated by my preceding MO-question on (in)consistency of NBG theory of classes.
Let $\varphi(x,Y,C)$ be a formula of NBG with free parameters $x,Y,C$ and all quantifiers running ...
- 41.8k
7
votes
2
answers
844
views
Statements forced by one condition of a poset, but not the whole thing
In order to get the relative consistency of some statement, it suffices to find a notion of forcing, and a condition $p$ in that forcing, such that $p$ forces the desired statement. It seems to be ...
- 3,982
7
votes
3
answers
439
views
Dedekind-"finiteness" for arbitrary limit cardinals
In $\mathbf{ZF}$, it is possible for a set $A$ to be infinite but not to admit a countable set. In other words, for any $\alpha\in\omega$, there is an injection from $\alpha$ into $A$, but there is no ...
- 1,799
7
votes
1
answer
425
views
On Consistency of an Existence
Let $\omega \leq \kappa <2^{\omega}$ , $\omega \leq\lambda \leq \kappa$ and $D(\kappa, \lambda)$ be the statement:
For all $ \mathfrak{B} \subseteq \mathbf{P}(\omega)$ with $|\mathfrak{B}|=\kappa$...
- 2,381
7
votes
0
answers
177
views
Asymptotically discrete ultrafilters
Definition 1. A ultrafilter $\mathcal U$ on $\omega$ is called discrete (resp. nowhere dense) if for any injective map $f:\omega\to \mathbb R$ there is a set $U\in\mathcal U$ whose image $f(U)$ is a ...
- 41.8k
6
votes
3
answers
1k
views
Is there an "undecided" assertion of which a proof that it's not undecidable is known?
Just a curiosity:
Is there an assertion of which a proof (formalizable, say, in ZFC) is not known but a proof that it's not undecidable (in ZFC) is known?
Edit: after the comments, I think the ...
- 23.3k
6
votes
1
answer
603
views
A strong form of the Axiom Schema of Replacement
Let us consider the following stronger version of the Axiom Schema of Replacement (let us call it the Axiom Schema of Replacement for Definable Relations):
Let $\varphi$ be any formula in the language ...
- 41.8k
6
votes
1
answer
626
views
Can $H_{\omega_1}$ and $H_{\omega_2}$ be in bi-interpretation synonymy?
This question concerns the possibility of the bi-interpretation synonymy of the structure
$\langle
H_{\omega_1},\in\rangle$, consisting of the hereditarily countable sets, and the structure $\langle ...
- 236k
6
votes
1
answer
273
views
$\omega_2$-sequence of Suslin trees
Is it possible to have an $\omega_2$-length sequence of ($\omega_1$-)Suslin trees such that if one builds the product of finitely many trees in that sequence, one ends up with a Suslin tree again?
...
- 2,180
6
votes
0
answers
375
views
How bad a proper forcing of size $\aleph_1$ can be?
This question concerns proper forcings of size $\aleph_1$. In the context of
$\rm ZFC+\neg CH$, I couldn't find any counter example to the following property. Suppose $\mathbb P$ is a proper forcing ...
- 2,381
5
votes
1
answer
325
views
Is Axiom of Choice equivalent to its version for families of sets, indexed by ordinals? [duplicate]
Is Axiom of Choice equivalent to the following statement?
Axiom of Ordinal Choice: For any ordinal $\lambda$ and any indexed family of sets $(X_\alpha)_{\alpha\in\lambda}$ there exists a function $...
- 41.8k
5
votes
1
answer
401
views
Variants of reflection principle
This question concerns two definitions of the reflection principle. One of them known to be a consequence of the other one. I would like to understand if the reverse is true.
Let us state the first ...
- 2,381
5
votes
1
answer
197
views
The cardinal characteristic $\mathfrak r_{(X,f)}$ of a dynamical system
I am interested in a "dynamical" modification of the cardinals $\mathfrak r$ and $\mathfrak r_\sigma$, well-known in the theory of cardinal characteristics of the continuum.
For a compact ...
- 41.8k
5
votes
1
answer
207
views
Examples of independent $\Sigma_4^1$ statements
As in the title, I'm looking for examples of $\Sigma^1_4$ (preferably complete) sentences which are independent from ZFC in both ways, namely given a model $V$ we can extend it to $V'$ where such a ...
5
votes
1
answer
524
views
A topologically transitive dynamical system without dense orbits
By a dynamical system I understand a pair $(K,G)$ consisting a compact Hausdorff space and a subgroup $G$ of the homeomorphism group of $K$.
We say that a dynamical system $(K,G)$
$\bullet$ is ...
- 41.8k
5
votes
1
answer
512
views
Smallest size of a non-measurable set of reals
The question is pretty much the title. I'm wondering if anything is known about the smallest size $\kappa$ of a non-measurable subset of the real numbers (regarding the Lebesgue measure). Since we ...
- 1,799
5
votes
0
answers
212
views
Questions about very fat sets
If $\kappa$ is a regular uncountable cardinal, we call a set $S\subseteq\kappa$ fat if for every $\alpha<\kappa$ and every club $C\subseteq\kappa$, there is a closed subset of $S\cap C$ of ...
- 1,799
5
votes
0
answers
175
views
Selecting an almost disjoint family in a given family of sets
A family $\mathcal A$ of infinite subsets of $\omega$ is called almost disjoint if for any distinct sets $A,B\in\mathcal A$ the intersection $A\cap B$ is finite.
Let $\mathfrak a'$ be the largest ...
- 41.8k