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

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.

-
Community wiki? – Gjergji Zaimi Mar 21 '11 at 23:25
Strong measure zero set... mathoverflow.net/questions/48453/… – Gerald Edgar Mar 22 '11 at 0:24
Are you only interested in sets that are obviously infinite? If not, I guess you can give definitions that define sets that are either empty or very large. – Zsbán Ambrus Mar 22 '11 at 11:09
Maybe you should change it to "sets for which it is hard to guess their cardinality"? Then there's room for other nice questions like the cardinality of the set of all continuous real valued functions (this example is not difficult, though, but maybe there are others in this vain) – mathahada Mar 22 '11 at 13:54

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.

-
This does not quite meet answer the original question, but indeed leads to an interesting class of puzzles. Perhaps it would deserve its own threads. A related question is how many thumbtacks you can place in the 3-space so that no two intersect. A thumbtack is a union of a disk and a segment one of whose endpoints is an interior point of the disk but the other endpoint is not in the plane of the disk. (The answer is countably many.) – Zsbán Ambrus Mar 22 '11 at 11:14
The thumbtack question can be also done in the plane: how many nonintersecting figure-Ts can one draw in the plane? – Ori Gurel-Gurevich Mar 22 '11 at 13:53

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

-
Obvious subset? It is not even known whether it is a subset of algebraic numbers! :) – fedja Mar 22 '11 at 18:49
Sorry, I just realized my "solution" relied on the fact that the quotient of two integers is an integer. – Charles Staats Mar 23 '11 at 5:10
I thought I solved this until I've seen fedja's comment. The subset in question is not very exotic, its just described in an obscure way (like writing "the set of all non trivial solutions for x^3+y^3=z^3" for the empty set)... – mathahada Mar 23 '11 at 10:50
@fedja: I must be right there with those poor grad students. Can you maybe give a hint? – Laurent Berger Mar 23 '11 at 12:36
@Laurent: Well, they are all computable numbers. Also someone asked about this on math.stackexchange. I'm not sure whether it is the same as Fedja's "next to obvious" answer, but I posted mine as an answer math.stackexchange.com/questions/28543/… – George Lowther Mar 23 '11 at 13:17

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.

-
Surely there are uncountably many. Just remove countably many tame knots from $\mathbb{R}^{3}$, there are uncountably many ways to do this. – David Cohen Mar 22 '11 at 0:21
Work of Kerekjarto and Richards implies there are at least as many non-compact separable surfaces as there are triples $(X,Y,Z)$ with $Z\subseteq Y\subseteq X$ a chain of of compact, separable, totally disconnected spaces. There are too many of these for surfaces to be countable, no? – Mariano Suárez-Alvarez Mar 22 '11 at 0:24
A quick google search yields deepblue.lib.umich.edu/bitstream/2027.42/32762/1/0000133.pdf , but I don't know what the "canonical" reference is. – villemoes Mar 22 '11 at 0:28
A variant for $d=2$: the number of discrete subgroups of $PSL_2(\mathbb R)$ up to conjugacy. – Kimball Mar 22 '11 at 4:04
@Kimball : That's uncountable. It's even uncountable if you look at cyclic subgroups up to conjugacy, which are classified by the absolute value of the trace of a generator. – Tim O Mar 22 '11 at 5:23

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.

-
Bjørn, does the Borel rank of the NCR$_n$ change depending on how many iterates of the power set of the natural numbers are assumed? – tci Mar 22 '11 at 12:57
So, depending on how many iterates you have, you can go from $\Pi_{1}^{1}\setminus\Delta_{1}^{1}$ to $\Sigma_{2}^{0}$? (Wow!) – tci Mar 22 '11 at 14:16
This example is missing the condition in the statement of the problem that any graduate student can think about it, although I'll grant you that they'd still not have an answer after 10 minutes. – KConrad Mar 22 '11 at 17:10
@Tanmay: apparently they show NCR$_n$ is properly $\mathbf\Pi^1_1$ as soon as there are not enough power sets (and countable hence $\mathbf\Sigma^0_2$ when there are). – Bjørn Kjos-Hanssen Mar 23 '11 at 11:59

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.

-
Along similar lines, is there an uncountable family of subsets of $\mathbb N$ that is totally ordered by inclusion? This can cause quite a bit of head-scratching until you realize that there's a two-word solution. – Timothy Chow Mar 22 '11 at 13:03
Tim, I realize one of "there is" or "there isn't" is a two-word solution. – KConrad Mar 22 '11 at 17:12
@Hans: Given an infinite sequence of 1s and 2s, its initial segments are numbers (written in decimal notation, for example), so any such sequence corresponds to an infinite subset of ${\mathbb N}$, and any two of these sets have finite intersection. – Andrés Caicedo Mar 22 '11 at 17:53
I believe the answer Tim is looking for is "Dedekind cuts". – Asaf Karagila Mar 22 '11 at 21:25
@David: Actually it is not very hard to add one more to a countable family, the surprising part is that it carries over to the uncountable case. For example, every countable ordinal can be embedding into the rationals, but $\omega_1$ cannot be embedded into it (even without preserving the order). – Asaf Karagila Mar 24 '11 at 18:38

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

-

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.

-
HAH. $\!\!\!\!\!$ – David Hansen Mar 22 '11 at 18:35
And that's Mornington Crescent! – Yemon Choi Mar 22 '11 at 19:25

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.

-
Very nice. How to prove that $f$ must be a polynomial if $F$ is uncountable? – mathahada Mar 22 '11 at 13:52
Start by noticing that for infinitely (in fact, uncountably) many y, f(x, y) has the same degree. Now go hunt for their coefficients. – Ashutosh Mar 22 '11 at 14:50
Interesting proof. This reminds me the Hartogs' theorem, which states that if $F(z_1,z_2)$ is analytic (which is next to polynomial) in the complex variables $z_1$ and $z_2$ seperately, then $F(z_1,z_2)$ is analytic jointly in $z_1$ and $z_2$. – Syang Chen Mar 26 '11 at 1:55

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.

-
and, on the same lines, the set of strict local maximum points, for a function of one real variable. – Pietro Majer Mar 22 '11 at 9:39

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.

-
+1: also you should ask about the set of isomorphism classes of all $n$-dimensional Lie algebras over a field (why not?). – Pete L. Clark Mar 22 '11 at 12:37

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

-
You might prove this as follows (it is overkill but I like fact (a)) (a) Any countable metrizable compact space is homeomorphic to a subset of the real line (Hint: Baire category thm). The hypothesis "metrizable" is useless as any countable (Hausdorff) compact space is metrizable but it makes things easier. (b) There are uncountably many countable metrizable compact spaces up to homeomorphism (use e.g Cantor-Bendixson rank). – Julien Melleray Mar 22 '11 at 12:14
Better: every countable metric (not just compact) can be embedded in Q, and every countable compact metric is homeomorphic to a countable ordinal – mathahada Mar 22 '11 at 12:22

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

-

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

-

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

-
For the answer to be well defined (unique) the Y has to include the 3 endpoints? – Yaakov Baruch Mar 23 '11 at 21:57
See this answer (mathoverflow.net/questions/59115/…) and my comment. – Ori Gurel-Gurevich Mar 27 '11 at 16:00