A set for which it is hard to determine whether or not it is countable. - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T11:20:25Z http://mathoverflow.net/feeds/question/59115 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/59115/a-set-for-which-it-is-hard-to-determine-whether-or-not-it-is-countable A set for which it is hard to determine whether or not it is countable. Spencer 2011-03-21T23:23:54Z 2011-03-27T08:24:48Z <p>I got thinking recently, while trying to come up with a problem, that I did not know of any sets which were reasonable to define but for which it was very difficult to determine whether or not they were countable or uncountable.</p> <p>When one first learns these concepts, it can be difficult, but with some experience, a mathematician can look at most sets which he or she meets in day-to-day and say almost immediately 'countable' or 'uncountable'.</p> <blockquote> <p>What examples of sets are there for which determining whether or not they are countable is a difficult problem?</p> </blockquote> <p>I won't define 'difficult' too rigorously but ideally I'm looking for something which any grad student <em>can</em> think about but which most would still be thinking about after 10 minutes. </p> http://mathoverflow.net/questions/59115/a-set-for-which-it-is-hard-to-determine-whether-or-not-it-is-countable/59121#59121 Answer by Matthew Kahle for A set for which it is hard to determine whether or not it is countable. Matthew Kahle 2011-03-21T23:53:01Z 2011-03-21T23:53:01Z <p>How about the set of $d$-dimensional manifolds, up to homeomorphism?</p> <p>I believe it is known for <em>compact</em> manifolds that this is a countable set (reference?), but I think this is not obvious. If we include non-compact manifolds I don't know the answer.</p> http://mathoverflow.net/questions/59115/a-set-for-which-it-is-hard-to-determine-whether-or-not-it-is-countable/59124#59124 Answer by Qiaochu Yuan for A set for which it is hard to determine whether or not it is countable. Qiaochu Yuan 2011-03-22T01:03:51Z 2011-03-22T01:03:51Z <p>Pick some misleadingly specific class of finite CW-complexes (e.g. the spheres) and ask for the cardinality of the set of homotopy classes of continuous maps between them. Whether this is easy or hard depends on whether you're familiar with simplicial approximation... </p> http://mathoverflow.net/questions/59115/a-set-for-which-it-is-hard-to-determine-whether-or-not-it-is-countable/59126#59126 Answer by Bjørn Kjos-Hanssen for A set for which it is hard to determine whether or not it is countable. Bjørn Kjos-Hanssen 2011-03-22T02:14:47Z 2011-03-22T02:14:47Z <p>Here is an example where it is <i>hard in a proof-theoretic sense</i> to determine whether a set is countable. </p> <p>Jan Reimann and Theodore A. Slaman (in the paper <a href="http://www.math.psu.edu/reimann/Publications/continuous_randomness_draft.pdf" rel="nofollow">Randomness for continuous measures</a>) study randomness with respect to continuous measures on $2^\mathbb N$.</p> <p>They show that for every $n$, the set NCR$_n$ of elements of $2^\mathbb N$ that are not $n$-random (Martin-Löf random relative to the $n$th iterate of the halting problem) with respect to any continuous probability measure, is countable. Furthermore, they show that for every $k\in\mathbb N$, there exists $n\in\mathbb N$ such that the statement </p> <blockquote> <p>NCR$_n$ is countable</p> </blockquote> <p>cannot be proven in the theory</p> <blockquote> <p>ZFC$^-$ + "There exists $k$ iterates of the power set of $\mathbb N$", </p> </blockquote> <p>where ZFC$^-$ denotes Zermelo-Fraenkel set theory with choice, minus the power set axiom. </p> <p>In other words, if you don't want to assume that the sets $\mathbb N$, $\mathcal P(\mathbb N)$, $\mathcal P(\mathcal P(\mathbb N))$, ... exist then you cannot prove that <i>all but countably many real numbers look random w.r.t. some probability distribution</i>.</p> http://mathoverflow.net/questions/59115/a-set-for-which-it-is-hard-to-determine-whether-or-not-it-is-countable/59128#59128 Answer by ndkrempel for A set for which it is hard to determine whether or not it is countable. ndkrempel 2011-03-22T03:06:17Z 2011-03-22T03:06:17Z <p>The set of isomorphism classes of n-dimensional simple Lie algebras over some field. </p> <p>The set of isomorphism classes of n-dimensional Hopf algebras over some field.</p> http://mathoverflow.net/questions/59115/a-set-for-which-it-is-hard-to-determine-whether-or-not-it-is-countable/59130#59130 Answer by fedja for A set for which it is hard to determine whether or not it is countable. fedja 2011-03-22T03:19:46Z 2011-03-22T03:19:46Z <p>If it is just to puzzle the graduate students for 10+ minutes, consider the set of reals $a>1$ such that for some $K>0$ the distance from $Ka^n$ to the nearest integer tends to $0$ as $n\to\infty$. The answer is, indeed, next to obvious but I've seen quite a few graduate students that weren't able to do it off hand. Now take a stopwatch and see how soon you'll solve this one yourself :).</p> http://mathoverflow.net/questions/59115/a-set-for-which-it-is-hard-to-determine-whether-or-not-it-is-countable/59132#59132 Answer by Daniel Litt for A set for which it is hard to determine whether or not it is countable. Daniel Litt 2011-03-22T03:30:03Z 2011-03-22T03:30:03Z <p>A <a href="http://books.google.com/books?id=ElSi5V5uS2MC&amp;lpg=PA60&amp;ots=_n8S5U40Mz&amp;dq=figure%2520eights%2520in%2520the%2520plane%2520countable&amp;pg=PA60#v=onepage&amp;q=figure%2520eights%2520in%2520the%2520plane%2520countable&amp;f=false" rel="nofollow">standard problem of this type</a> is, can one draw uncountably many non-intersecting, non-degenerate figure-eights in the plane? The problem is trivially "yes" for circles, rather than figure-eights, so I found this problem surprising when I first saw it. </p> http://mathoverflow.net/questions/59115/a-set-for-which-it-is-hard-to-determine-whether-or-not-it-is-countable/59138#59138 Answer by Syang Chen for A set for which it is hard to determine whether or not it is countable. Syang Chen 2011-03-22T05:17:23Z 2011-03-27T08:24:48Z <p>An elementary example which any grad can think about. Hope it will require 10 mins for most of them to figure out (or recall) the proof:</p> <p>The set of discontinuous points of a non-decreasing function.</p> <p>Or, making it more geometric, (under suitable assumptions) the set of the radius $r$ such that a given Borel measure charges the $r$-sphere.</p> <p>Or, based on the first result, the set of non-differentiable points of a convex function on the real line.</p> http://mathoverflow.net/questions/59115/a-set-for-which-it-is-hard-to-determine-whether-or-not-it-is-countable/59162#59162 Answer by mathahada for A set for which it is hard to determine whether or not it is countable. mathahada 2011-03-22T10:09:27Z 2011-03-22T10:09:27Z <p>The collection of all compact subsets of the real line up to homeomorphism</p> http://mathoverflow.net/questions/59115/a-set-for-which-it-is-hard-to-determine-whether-or-not-it-is-countable/59180#59180 Answer by Pete L. Clark for A set for which it is hard to determine whether or not it is countable. Pete L. Clark 2011-03-22T12:44:25Z 2011-03-22T16:51:17Z <p>This is of the "to puzzle graduate students" variety, but I was taken enough with it to write it up in a <a href="http://math.uga.edu/~pete/coveringnumbersv2.pdf" rel="nofollow">short note</a>:</p> <p>Let $V$ be a vector space over a field $F$, of dimension at least $2$, and consider coverings $\mathcal{C} = (W_i)$ of $V$ by proper subspaces. Does there exist a countable covering $\mathcal{C}$? (It depends on $\dim V$ and <code>$\# F$</code>, but perhaps not exactly as you expect!)</p> http://mathoverflow.net/questions/59115/a-set-for-which-it-is-hard-to-determine-whether-or-not-it-is-countable/59181#59181 Answer by Tony Huynh for A set for which it is hard to determine whether or not it is countable. Tony Huynh 2011-03-22T12:55:27Z 2011-03-22T12:55:27Z <p>Does there exists an uncountable family of subsets of $\mathbb{N}$ such that the intersection of any two sets is finite? Somewhat surprisingly the answer is yes.</p> http://mathoverflow.net/questions/59115/a-set-for-which-it-is-hard-to-determine-whether-or-not-it-is-countable/59184#59184 Answer by Keivan Karai for A set for which it is hard to determine whether or not it is countable. Keivan Karai 2011-03-22T13:40:13Z 2011-03-22T13:40:13Z <p>This example is from the book "A problem Seminar" by D.J. Newman:</p> <p>Let $F$ be an infinite field and let $f: F \times F \to F$ be a function of two variables such that $f(x_0,y)$ is a polynomial in $y$ for every $x_0 \in F$ and $f(x,y_0)$ is a polynomial in $x$ for every $y_0 \in F$. (Of course, being a polynomial for a function $f: F \to F$ means there exists $p(x) \in F[x]$ such that $f(x)=p(x)$ for all $x \in F$.) Now, is $f$ itself necessarily a polynomial?</p> <p>Surprisingly the answer depends on the cardinality of $F$. It is negative when $F$ is countable and positive when $F$ is uncountable. For countable $F$, enumerate the elements as $a_1, a_2, \dots$ and consider $$f(x,y)=\sum_{i=1}^{\infty} (x-a_1)(x-a_2)\cdots (x-a_i)(y-a_1)\cdots (y-a_i)$$</p> <p>It is obvious that $f$ satisfies the condition, and not hard to show that it is not a polynomial. </p> http://mathoverflow.net/questions/59115/a-set-for-which-it-is-hard-to-determine-whether-or-not-it-is-countable/59188#59188 Answer by Ashutosh for A set for which it is hard to determine whether or not it is countable. Ashutosh 2011-03-22T14:51:54Z 2011-03-22T14:51:54Z <p>Another puzzle: The set of x such that $\lim_{n \rightarrow \infty} \sin(n! \pi x) = 0$.</p> http://mathoverflow.net/questions/59115/a-set-for-which-it-is-hard-to-determine-whether-or-not-it-is-countable/59203#59203 Answer by David Speyer for A set for which it is hard to determine whether or not it is countable. David Speyer 2011-03-22T16:53:34Z 2011-03-22T16:53:34Z <p>I'll be the obnoxious one: The set of subsets $S$ of <code>$\{ x+iy \in \mathbb{C}, \ 1/2 &lt; x &lt; 1 \}$</code> such that $\zeta(s)$ restricted to $S$ is zero.</p> http://mathoverflow.net/questions/59115/a-set-for-which-it-is-hard-to-determine-whether-or-not-it-is-countable/59344#59344 Answer by P C for A set for which it is hard to determine whether or not it is countable. P C 2011-03-23T19:21:29Z 2011-03-23T19:21:29Z <p>Maximal set of mutually disjoint $Y$'s in the plane (a $Y$ is the image by a continuous injection of the usual $Y$ made of $3$ segments).</p>