A set for which it is hard to determine whether or not it is countable. - MathOverflow

A set for which it is hard to determine whether or not it is countable.

2011-03-21T23:23:54Z

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.

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'.

What examples of sets are there for which determining whether or not they are countable is a difficult problem?

I won't define 'difficult' too rigorously but ideally I'm looking for something which any grad student can think about but which most would still be thinking about after 10 minutes.

Answer by Matthew Kahle for A set for which it is hard to determine whether or not it is countable.

2011-03-21T23:53:01Z

How about the set of $d$-dimensional manifolds, up to homeomorphism?

I believe it is known for compact 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.

Answer by Qiaochu Yuan for A set for which it is hard to determine whether or not it is countable.

2011-03-22T01:03:51Z

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...

Answer by Bjørn Kjos-Hanssen for A set for which it is hard to determine whether or not it is countable.

2011-03-22T02:14:47Z

Here is an example where it is hard in a proof-theoretic sense to determine whether a set is countable.

Jan Reimann and Theodore A. Slaman (in the paper Randomness for continuous measures) study randomness with respect to continuous measures on $2^\mathbb N$.

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

NCR$_n$ is countable

cannot be proven in the theory

ZFC$^-$ + "There exists $k$ iterates of the power set of $\mathbb N$",

where ZFC$^-$ denotes Zermelo-Fraenkel set theory with choice, minus the power set axiom.

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 all but countably many real numbers look random w.r.t. some probability distribution.

Answer by ndkrempel for A set for which it is hard to determine whether or not it is countable.

2011-03-22T03:06:17Z

The set of isomorphism classes of n-dimensional simple Lie algebras over some field.

The set of isomorphism classes of n-dimensional Hopf algebras over some field.

Answer by fedja for A set for which it is hard to determine whether or not it is countable.

2011-03-22T03:19:46Z

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 :).

Answer by Daniel Litt for A set for which it is hard to determine whether or not it is countable.

2011-03-22T03:30:03Z

A standard problem of this type 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.

Answer by Syang Chen for A set for which it is hard to determine whether or not it is countable.

2011-03-22T05:17:23Z

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:

The set of discontinuous points of a non-decreasing function.

Or, making it more geometric, (under suitable assumptions) the set of the radius $r$ such that a given Borel measure charges the $r$-sphere.

Or, based on the first result, the set of non-differentiable points of a convex function on the real line.

Answer by mathahada for A set for which it is hard to determine whether or not it is countable.

2011-03-22T10:09:27Z

The collection of all compact subsets of the real line up to homeomorphism

Answer by Pete L. Clark for A set for which it is hard to determine whether or not it is countable.

2011-03-22T12:44:25Z

This is of the "to puzzle graduate students" variety, but I was taken enough with it to write it up in a short note:

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 $\# F$ , but perhaps not exactly as you expect!)

Answer by Tony Huynh for A set for which it is hard to determine whether or not it is countable.

2011-03-22T12:55:27Z

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.

Answer by Keivan Karai for A set for which it is hard to determine whether or not it is countable.

2011-03-22T13:40:13Z

This example is from the book "A problem Seminar" by D.J. Newman:

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?

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) $$

It is obvious that $f$ satisfies the condition, and not hard to show that it is not a polynomial.

Answer by Ashutosh for A set for which it is hard to determine whether or not it is countable.

2011-03-22T14:51:54Z

Another puzzle: The set of x such that $\lim_{n \rightarrow \infty} \sin(n! \pi x) = 0 $.

Answer by David Speyer for A set for which it is hard to determine whether or not it is countable.

2011-03-22T16:53:34Z

I'll be the obnoxious one: The set of subsets $S$ of $\{ x+iy \in \mathbb{C}, \ 1/2 < x < 1 \}$ such that $\zeta(s)$ restricted to $S$ is zero.

Answer by P C for A set for which it is hard to determine whether or not it is countable.

2011-03-23T19:21:29Z

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).