41
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 6
    $\begingroup$ Strong measure zero set... mathoverflow.net/questions/48453/… $\endgroup$
    – Gerald Edgar
    Commented Mar 22, 2011 at 0:24
  • 1
    $\begingroup$ 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. $\endgroup$
    – Zsbán Ambrus
    Commented Mar 22, 2011 at 11:09
  • 2
    $\begingroup$ 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) $\endgroup$
    – mathahada
    Commented Mar 22, 2011 at 13:54
  • $\begingroup$ What about $L\cap\mathcal{P}(\omega)$? Its cardinality is $\omega_1^L$ which is uncountable assuming $V=L$ but countable assuming a measurable cardinal exists (or $0^\text{#}$ exists) $\endgroup$
    – Lucenaposition
    Commented Nov 13 at 0:09

14 Answers 14

Reset to default
23
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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.) $\endgroup$
    – Zsbán Ambrus
    Commented Mar 22, 2011 at 11:14
  • 2
    $\begingroup$ The thumbtack question can be also done in the plane: how many nonintersecting figure-Ts can one draw in the plane? $\endgroup$
    – Ori Gurel-Gurevich
    Commented Mar 22, 2011 at 13:53
20
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • 4
    $\begingroup$ Obvious subset? It is not even known whether it is a subset of algebraic numbers! :) $\endgroup$
    – fedja
    Commented Mar 22, 2011 at 18:49
  • $\begingroup$ Sorry, I just realized my "solution" relied on the fact that the quotient of two integers is an integer. $\endgroup$
    – Charles Staats
    Commented Mar 23, 2011 at 5:10
  • $\begingroup$ 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)... $\endgroup$
    – mathahada
    Commented Mar 23, 2011 at 10:50
  • 2
    $\begingroup$ @fedja: I must be right there with those poor grad students. Can you maybe give a hint? $\endgroup$
    – Laurent Berger
    Commented Mar 23, 2011 at 12:36
  • 2
    $\begingroup$ @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/… $\endgroup$
    – George Lowther
    Commented Mar 23, 2011 at 13:17
18
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • 11
    $\begingroup$ Surely there are uncountably many. Just remove countably many tame knots from $\mathbb{R}^{3}$, there are uncountably many ways to do this. $\endgroup$
    – David Cohen
    Commented Mar 22, 2011 at 0:21
  • 1
    $\begingroup$ 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? $\endgroup$
    – Mariano Suárez-Álvarez
    Commented Mar 22, 2011 at 0:24
  • $\begingroup$ 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. $\endgroup$
    – villemoes
    Commented Mar 22, 2011 at 0:28
  • $\begingroup$ A variant for $d=2$: the number of discrete subgroups of $PSL_2(\mathbb R)$ up to conjugacy. $\endgroup$
    – Kimball
    Commented Mar 22, 2011 at 4:04
  • 5
    $\begingroup$ @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. $\endgroup$
    – Tim O
    Commented Mar 22, 2011 at 5:23
14
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – user3462
    Commented Mar 22, 2011 at 12:57
  • $\begingroup$ So, depending on how many iterates you have, you can go from $\Pi_{1}^{1}\setminus\Delta_{1}^{1}$ to $\Sigma_{2}^{0}$? (Wow!) $\endgroup$
    – user3462
    Commented Mar 22, 2011 at 14:16
  • $\begingroup$ 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. $\endgroup$
    – KConrad
    Commented Mar 22, 2011 at 17:10
  • $\begingroup$ @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). $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Mar 23, 2011 at 11:59
13
$\begingroup$

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.

Improve this answer
$\endgroup$
18
  • 7
    $\begingroup$ 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. $\endgroup$
    – Timothy Chow
    Commented Mar 22, 2011 at 13:03
  • 3
    $\begingroup$ Tim, I realize one of "there is" or "there isn't" is a two-word solution. $\endgroup$
    – KConrad
    Commented Mar 22, 2011 at 17:12
  • 6
    $\begingroup$ @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. $\endgroup$
    – Andrés E. Caicedo
    Commented Mar 22, 2011 at 17:53
  • 9
    $\begingroup$ I believe the answer Tim is looking for is "Dedekind cuts". $\endgroup$
    – Asaf Karagila ♦
    Commented Mar 22, 2011 at 21:25
  • 1
    $\begingroup$ @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). $\endgroup$
    – Asaf Karagila ♦
    Commented Mar 24, 2011 at 18:38
11
$\begingroup$

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

Improve this answer
$\endgroup$
11
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ HAH. $\!\!\!\!\!$ $\endgroup$
    – David Hansen
    Commented Mar 22, 2011 at 18:35
  • 4
    $\begingroup$ And that's Mornington Crescent! $\endgroup$
    – Yemon Choi
    Commented Mar 22, 2011 at 19:25
10
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Very nice. How to prove that $f$ must be a polynomial if $F$ is uncountable? $\endgroup$
    – mathahada
    Commented Mar 22, 2011 at 13:52
  • 1
    $\begingroup$ Start by noticing that for infinitely (in fact, uncountably) many y, f(x, y) has the same degree. Now go hunt for their coefficients. $\endgroup$
    – Ashutosh
    Commented Mar 22, 2011 at 14:50
  • $\begingroup$ 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$. $\endgroup$
    – Syang Chen
    Commented Mar 26, 2011 at 1:55
7
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ and, on the same lines, the set of strict local maximum points, for a function of one real variable. $\endgroup$
    – Pietro Majer
    Commented Mar 22, 2011 at 9:39
5
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ 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). $\endgroup$
    – Julien Melleray
    Commented Mar 22, 2011 at 12:14
  • 1
    $\begingroup$ Better: every countable metric (not just compact) can be embedded in Q, and every countable compact metric is homeomorphic to a countable ordinal $\endgroup$
    – mathahada
    Commented Mar 22, 2011 at 12:22
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ +1: also you should ask about the set of isomorphism classes of all $n$-dimensional Lie algebras over a field (why not?). $\endgroup$
    – Pete L. Clark
    Commented Mar 22, 2011 at 12:37
4
$\begingroup$

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

Improve this answer
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$
2

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .