40

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.

Spencer
  • 1,771
  • 6
    Strong measure zero set...
    http://mathoverflow.net/questions/48453/a-set-that-can-be-covered-by-arbitrarily-small-intervals     – Gerald Edgar Mar 22 '11 at 00:24
  • 1
    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
  • 2
    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

14 Answers14

22

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.

Daniel Litt
  • 22,187
  • 1
    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
  • 2
    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
20

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

fedja
  • 59,730
  • 4
    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 05: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
  • 2
    @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
  • 2
    @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 http://math.stackexchange.com/questions/28543/sequence-that-approaches-integers/28587#28587 – George Lowther Mar 23 '11 at 13:17
  • @George. Yes, this is the quickest way to see it. @mathahada The set is actually pretty exotic even if it is what most people believe it is. If you don't believe me, just try to answer the question whether it is closed. – fedja Mar 24 '11 at 04:01
18

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.

Matthew Kahle
  • 7,755
  • 11
    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 00:21
  • 1
    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-Álvarez Mar 22 '11 at 00: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 00:28
  • A variant for $d=2$: the number of discrete subgroups of $PSL_2(\mathbb R)$ up to conjugacy. – Kimball Mar 22 '11 at 04:04
  • 5
    @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 05:23
  • @Tim: ah yes, I suppose it was easier than I was thinking. Is it less clear if you ask about the number of subgroups of $PSL_2(\mathbb Z)$? – Kimball Mar 24 '11 at 06:35
  • By the way, unlike exotic R^4's, there are at most countably many distinct exotic 4-spheres, according to Wikipedia. – Junyan Xu Oct 07 '11 at 14:42
15

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 Kjos-Hanssen
  • 24,629
  • 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
14

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.

Tony Huynh
  • 31,500
  • 6
    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
  • @Tony: Please give me a hint where I can learn more about this! – Hans-Peter Stricker Mar 22 '11 at 16:28
  • 3
    Tim, I realize one of "there is" or "there isn't" is a two-word solution. – KConrad Mar 22 '11 at 17:12
  • 6
    @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 E. Caicedo Mar 22 '11 at 17:53
  • @Hans: Tony's problem appears in Donald Newman's book A Problem Seminar and was also problem B-4 on the 1989 Putnam exam. @KConrad: "there is" or "there isn't" is a two-word answer but there is a two-word phrase that gives a complete solution to the problem I posed. – Timothy Chow Mar 22 '11 at 18:03
  • Tim: I thought of a solution but perhaps its different from yours because its not a two word phrase. A good way is to enumerate the rationals and for every real number $r$ let $A_r$ be the set of all those $n$ such that $q_n < r$. I thought of two candidate two word phrases: omega-one and "enumerating rationals", but the first doesn't work and the second is very far from a complete solution – mathahada Mar 22 '11 at 21:10
  • 8
    I believe the answer Tim is looking for is "Dedekind cuts". – Asaf Karagila Mar 22 '11 at 21:25
  • Tony's example here appears, interestingly enough, in a book on Banach space theory; in Albiac and Kalton's Topics in Banach Space Theory, it appears on page 45 as Lemma 2.5.3. There it is used to show (Theorem 2.5.4) that there is no continuous linear projection of $\ell_\infty$ onto its closed subspace $c_0$. – Philip Brooker Mar 22 '11 at 23:27
  • @Tim and Philip: Thanks for the references! – Tony Huynh Mar 23 '11 at 00:08
  • @Philip: In fact, this is but one of a family of results in infinitary combinatorics that one encounters with some frequency in the theory of Banach spaces. Recent years have seen a steep increment in the sophistication of the set theory being directly applied in this area. – Andrés E. Caicedo Mar 23 '11 at 03:33
  • @Andres: Indeed, as I progressed through my graduate studies I noticed precisely what you claim above. As someone who hopes to make further contributions to Banach space theory, learning more set theory, combinatorics and descriptive set theory is now high on my priority list. – Philip Brooker Mar 23 '11 at 04:51
  • For me, even more surprising than the existence of such an uncountable family, is the fact that any countable family (of subsets of $\mathbb N$ such that the intersection of any two elements of the family is finite) can still be further extended, i.e. there is another infinite subset of $\mathbb N$ whose intersection with any set from the previous family is still finite. – David Fernandez-Breton Mar 23 '11 at 21:04
  • @David: I think this is false. Let the family consist of all finite subsets of $\mathbb{N}$, together with $\mathbb{N}$ itself. One cannot extend this family while maintaining the finite intersection property. – Tony Huynh Mar 24 '11 at 00:26
  • @Tony: I believe this discussion is only about infinite subsets of $\mathbb{N}$. – Asaf Karagila Mar 24 '11 at 08:18
  • @Asaf: Thanks, I see what David is trying to say now. For a proof of his claim, let $(X_i)$ be an enumeration of the family. For each $i$ choose $x_i \in X_i$ such that $x_i$ is not in the union of the previous $i−1$ sets. We can then extend the family by adding $X:=(x_i)$ to it. – Tony Huynh Mar 24 '11 at 15:46
  • 1
    @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
  • 1
    @Hans for any real number $a$ take a sequence of rationals converging to $a$. Of course this is essentially the same construction as Andrés'. – Fedor Petrov Nov 28 '16 at 14:44
  • @Fedor: Just to let you know: I received your comment. Thanks for it. – Hans-Peter Stricker Nov 28 '16 at 19:46
11

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

Community
  • 1
Pete L. Clark
  • 64,763
11

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.

David E Speyer
  • 150,821
10

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.

Keivan Karai
  • 6,074
  • Very nice. How to prove that $f$ must be a polynomial if $F$ is uncountable? – mathahada Mar 22 '11 at 13:52
  • 1
    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 01:55
8

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.

Syang Chen
  • 981
5

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

mathahada
  • 636
  • 2
    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
  • 1
    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
4

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.

ndkrempel
  • 1,788
  • 3
    +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
4

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

Ashutosh
  • 9,771
2

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

Qiaochu Yuan
  • 114,941
0

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 C
  • 1