35

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 undecidability of Wang tilings, the undecidability of the existence of solutions to Diophantine equations, the word problem for groups, and many others. It's a formal ...


29

For every function $f$ mapping the reals into the set of all countable subsets of the reals, there are real numbers $x$ and $y$ such that $x \notin f(y)$ and $y \notin f(x)$. This innocent and reasonable statement is actually equivalent to the negation of the Continuum Hypothesis. The equivalence was first proved by Sierpiński, and is actually very easy to ...


27

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 that one can indeed get some insight by thinking this way. In particular, the main results of my paper on the embedding phenomenon arose out of an explicitly ...


23

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 Theorem applies. In other words, to every "hydra-ordinal" there is an "omega-nimber." Already this suggests thinking of the plus signs in the hydra as being ...


20

Let me address the part of your question seeking algebraic statements independent of ZFC+V=L. The basic situation is that in set theory our tools are not so flexible for finding statements independent of ZFC+V=L, as opposed to finding statements independent of ZFC. The main reason for this is that one cannot directly use forcing to prove that a statement is ...


20

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 undecidability might depend on which axioms of mathematics we have adopted. The answer is that one may quite generally deduce that there are concrete instance of logical ...


18

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, Archive for Mathematical Logic 35, Issue 4 (1996) 263-277, doi:10.1007/s001530050044, the cardinal invariant $\mathfrak{bidi}$ is equal to that minimum. To ...


13

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 of an operation $\star$ defined recursively by $$ p \star 1 = p+1 \bmod {2^n}\\ p \star (q \star r) = (p \star q) \star (p \star r). $$ They arise naturally in ...


13

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 which are themselves ${\sf ZF}^-$ models, Logic colloquium ’80, Eur. Summer Meet., Prague 1980, Stud. Logic Found. Math. 108, 315-342 (1982). ZBL0524.03039.


12

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, that ZF doesn't prove AC; in the other direction, we need to show that ZF doesn't disprove AC. This is proved by showing that any model of ZF contains a really ...


11

The answer is yes. Recall that if $S$ is a Suslin tree, then PFA($S$) denotes the forcing axiom for the class of all proper posets which preserve $S$. PFA($S$) is consistent with ZFC relative to a supercompact cardinal, like PFA, and shares many of the consequences of PFA, but a model of PFA($S$) naturally does not satisfy MA (since $S$ is Suslin). Claim: ...


10

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 dimension $\kappa$ has vector space dimension $\kappa^{\aleph_0}.$ So we're really asking whether there is $\kappa$ such that $\kappa^{\aleph_0} \ge \kappa^{++}.$ The ...


10

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 well-ordered index sets, but you can always pass from a well-ordered index set to an ordinal index set.) As Taras Banakh comments below, there is a ...


10

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 ZFC, which isn't provable in ZFC by Godel's theorem (using soundness again), so $I(p)$ is not provable. Thus $I(p)$ is independent.


9

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 $\mathsf{ZFC}$ is consistent then $p$ is independent over $\mathsf{ZFC}$." We can indeed prove in $\mathsf{ZFC}$ many instances of $J$ (e.g. that $J$ holds ...


8

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: the answer to both of these questions is no. As far as I can tell, the result is a standard reduction from the halting problem. The paper shows that computing ...


8

I think Hahn-Banach can be eliminated from the usual proof, but being a non-expert in set theory, I cannot guarantee that the proof is completely independent of the axiom of choice. Here is a sketch of a basic calculus proof. A function $U\to B$ from a region $U\subset C$ to a Banach space $B$ is called analytic if every point has a neighborhood where it ...


8

I do not believe that the Hahn-Banach theorem is necessary. At some point I had planned on writing up a blog post verifying this but I lost the motivation... The idea is that you can prove Liouville's theorem in the Banach space setting directly without using Hahn-Banach to reduce to the case of $\mathbb{C}$ (I asked whether this was possible in this math....


8

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 ``A new Lowenheim-Skolem Theorem". See their paper for the definition of internally stationary, internallly club, and internally approachable. The main result ...


7

$``$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 this statement is independent of ZFC was pointed out in a comment by MathOverflow user @GHfromMO on consideration of answers to a question posted on this site. ...


7

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 situation, we "relativize" and consider the sentence There is some real $r$ such that every real $s$ is constructible relative to $r$. (That is, for some $r\in\...


7

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}$ definable over $H_{\omega_1}$. Since $\text{MA}_{\omega_1}$ implies a strong form of almost disjoint coding (i.e., any almost disjoint family $\langle A_\...


7

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\cap P$ contains at most one element for each $P\in\mathcal{P}$. (As if each piece of the partition has cardinality at most $n$, then there is a $k\leq n$ such ...


6

Very likely the fact that you are trying to remember is the interpolation problem solved by Erdős. http://www.renyi.hu/~p_erdos/1964-04.pdf


6

Let me add a nice remark I just became aware of: In Greg Oman. On the axiom of union, Arch. Math. Logic, 49 (3), (2010), 283–289. MR2609983 (2011g:03122), Oman clarifies precisely which unions can be proved to exist in $\mathsf{ZFC}-\mathrm{Union}$: $\bigcup x$ exists iff $\{|y|\colon y\in x\}$ is bounded. In particular, $A\cup B$ exists for any sets $A,...


6

After working out the details, here is a summary of the proofs using symmetric models. I ran out of free time to fully write them in a nice $\LaTeX$ file, but perhaps I'll have some more free time in September and I could finish up these proofs. The idea is to mimic the permutation models as given in Jech. One can then ask, "Well, in Jech he chooses ...


6

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 was still open whether $(\omega+1)^\omega$ is normal in the box topology. $\mathbb R^\omega$ has a closed subspace homeomorphic to $(\omega+1)^\omega$, so if $\...


6

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 the group of homeomorphism of $\ K,\ $ induced by shifts $\ s_n\ (n\in\Bbb Z)\ $ of $\ \Bbb Z:\ $ $$ \forall_{n\in\Bbb Z}\forall_{x\in\Bbb Z}\quad ...


5

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 undecidable? After all, if it is physical, surely we could in principle construct the system in the laboratory, and measure it. A real quantum many-body ...


5

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 consistent that $Ded(\kappa)< Ded(\kappa)^\omega$. In particular, it is consistent that $Ded(\kappa)<2^\kappa$. It is still open whether both inequalities can ...


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