9
$\begingroup$

I am searching for a constructive proof of the following fact: If $X$ is an infinite set, there exists an uncountable family $(X_\alpha)_{\alpha \in A}$ of infinite subsets of $X$ such that $X_\alpha \cap X_\beta$ is finite whenever $\alpha \neq \beta$. The way I know how to prove this statement is as follows.

First, it suffices to prove the case when $X$ is countable. Thus we can choose a bijection between $X$ and $\mathbb{Q} \cap [0,1]$. To save notation we can tacitly assume that $X = \mathbb{Q} \cap [0,1]$.

Let the index set be $A = [0,1] \setminus X$, i.e. all the irrationals in $[0,1]$. For each $\alpha \in A$, choose a sequence $(x_{\alpha 1},x_{\alpha 2},\dots)$ of elements of $X$ such that $x_{\alpha n} \to \alpha$ as $n \to \infty$, and let $X_\alpha = \{ x_{\alpha_n} \mid n \in \mathbb{N} \}$.

Since $\alpha$ is irrational, the sequence $(x_{\alpha n})$ cannot be eventually constant, so $X_\alpha$ is infinite. And if $\alpha \neq \beta$ then the sequences $(x_{\alpha n})$ and $(x_{\beta n})$ can have only finitely many terms in common since they have different limits, so $X_\alpha \cap X_\beta$ is finite.

Is it possible to do this in a more constructive way? I know very little about set theory and logic, so I apologize if this question is too elementary. Also, I wasn't sure about any relevant tags other than set-theory, so please feel free to add appropriate tags.

Edit: to clarify, I didn't have a clear notion of what I meant by "constructive" here. What I didn't like about the proof I gave above was that it required a choice of sequence of rationals converging to each irrational. The answers so far all address this concern adequately.

$\endgroup$
3
  • 2
    $\begingroup$ If you assume that $X$ is countable (or contains a countable set), then your proof is constructive (or can easily be made constructive), as pointed out by Valerio Caprano. However, the "obvious" fact that every infinite set contains a countably infinite subset may be seen as nonconstructive by some. And indeed, the theorem you stated is not provable in set theory without the axiom of choice (say: in ZF). (Hint: amorphous sets.) $\endgroup$
    – Goldstern
    Feb 23, 2012 at 19:40
  • $\begingroup$ Goldstern, thanks for that observation. $\endgroup$
    – MTS
    Feb 23, 2012 at 20:33
  • 3
    $\begingroup$ This was problem B-4 on the 1989 Putnam. The book by Kedlaya, Poonen, and Vakil gives four solutions, including some of the ones listed here, and mentions that it is also Problem 49 in Newman's book A Problem Seminar. $\endgroup$ Feb 23, 2012 at 22:52

7 Answers 7

9
$\begingroup$

This all hinges on what you mean by constructive. An easy way to get such a family is to proceed as follows:

Put your countable set $X$ in bijective correspondence with the collection of finite sequences of 0s and 1s.

For every every subset $A$ of the natural numbers, let $\chi_A:\mathbb{N}\rightarrow\{0,1\}$ be the characteristic function of $A$, and let $S_A$ be the collection of finite sequences of the form $\chi_A|\{0,\dots,n\}$ for $n\in\mathbb{N}$.

Each $S_A$ is infinite, and if $A$ and $B$ are distinct subsets of $\mathbb{N}$, then $S_A\cap S_B$ is finite (once we get past the first difference between $A$ and $B$, the characteristic functions disagree). Now use your bijection to pull things back inside your original set $X$. This gives you a family of size $2^{\aleph_0}$ enjoying the property you want.

I don't know if this is constructive enough or not!

$\endgroup$
1
  • 1
    $\begingroup$ Your answer is constructive after a minor cleanup, see my answer for a transcription into "proper" constructive math. $\endgroup$ Feb 26, 2012 at 23:14
18
$\begingroup$

I think that you feel your construction non constructive because you have no way to establish a priori if a given real number is rational or irrational. The following construction avoids the problem: I suppose directly that $X=\mathbb N$. For any $\frac{1}{10}\leq t< 1$, for instance $t=0,324145...$, define $I_t$ to be the set containing the following natural numbers

$$ 3,32,324,3241,32414,324145,\ldots $$

The family $I_t$ is uncountable and $|I_t\cap I_s|<\infty$, for all $t\neq s$.

$\endgroup$
13
$\begingroup$

Here is a transcription of Todd Eisworth's answer into constructive mathematics. His construction is more or less constructive, he just uneccessarily says things which ruin the constructivity such as:

  • In constructive mathematics only decidable subsets of $\mathbb{N}$ have characteristic functions. But we can avoid the problem by speaking only about the characteristic functions.

  • Not every countable set can be put in bijective correspondence with the natural numbers. This can be avoided, because we don't need such a bijection, just an injection from the natural numbers into the set (which is the definition of "infinite").

  • In constructive mathematics cardinals don't work too well, so it is better not to mention $2^{\aleph_0}$. This can be avoidded by talking explicitly about a set being uncountable (i.e., there is no surjection from $\mathbb{N}$ onto the set).

And here is the proof:

The set $2^\ast$ of finite sequences of $0$'s and $1$'s is in bijective correspondence with $\mathbb{N}$, therefore it clearly suffices to find an uncountable collection of subsets of $2^\ast$ such that any two of them have only a finite intersection. Once such a collection is found, it can be embeded into $X$.

The set $2^\mathbb{N}$ is uncountable by the usual Cantor's diagonal argument (which is constructive!). Given any $f \in 2^\mathbb{N}$, let $S_f \subseteq 2^\ast$ be the set of finite prefixes of $f$. The assignment $f \mapsto S_f$ is injective, therefore the $S_f$'s form an uncountable family. If $f$ and $g$ are distinct, then there is a smallest $n \in \mathbb{N}$ such that $f(n) \neq g(n)$, hence $S_f \cap S_g$ is finite, as it contains precisely the first $n$ prefixes of $f$.

$\endgroup$
4
  • $\begingroup$ Are you saying that countable=recursively enumerable (from a constructive viewpoint)? So we could have a countable set $P$ (say all finite sequences of of characters from some alphabet) and yet have a subset which is not countable (say the sequences which code a valid algorithm outputting a binary sequence.) $\endgroup$ Feb 27, 2012 at 8:09
  • 1
    $\begingroup$ No, I am not saying that from a constructive point of view countable is the same as recursively enumerable. There is one particular model of constructive mathematics, namely Russian constructivism or the effective topos, in which "countable" happens to coincide with "recursively enumerable". But that aside, yes it is consistent to assume that a subset of a countable set is not countable. For a striking example, see "Embedding the Baire space into natural numbers" at math.andrej.com/2011/12/06/… $\endgroup$ Feb 27, 2012 at 17:22
  • $\begingroup$ OK, so (from a constructive point of view) countable means having an enumeration and uncountable means having a proof that there could never be an enumeration. However it does not mean "bigger than countable". $\endgroup$ Feb 27, 2012 at 18:00
  • $\begingroup$ Right, "bigger" does not make as much sense constructively as it does classically, at least not if injections or surjections are used for comparison of size. $\endgroup$ Feb 28, 2012 at 12:46
7
$\begingroup$

I think that this was answered by Andres Caicedo in a comment to an answer to this question.

I quote:

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 ℕ, and any two of these sets have finite intersection.

This is basically the same answer as that of Todd Elsworth, perhaps phrased a bit more snappily.

$\endgroup$
1
  • $\begingroup$ Yep, much more snappily! $\endgroup$ Feb 23, 2012 at 19:14
5
$\begingroup$

A geometrical/number-theoretical proof, if $X$ is the set of all pairs of (say, positive) integers:

For each real number $\alpha>0$, let $A_\alpha$ be the set of all pairs $(k,m)$ which are reasonably close to the line $y=\alpha x$.

Several variants are possible, for example: $A_\alpha:=\{ (k,m) : \bigl|m-\alpha k\bigr|<1\}$.

Just looking at a picture will convince you that these sets are almost disjoint; it is also easy to show that they are all infinite.

$\endgroup$
4
$\begingroup$

If your notion of constructive considers the family of binary sequences as uncountable, then set $a_0=1$ and consider the family of all sets $\{1,a_1,a_2,\cdots\}$ with the property that $a_{i+1}$ is either $2a_i$ or $2a_i+1.$ If you do not allow "lawless" binary sequences then there are not likely to be any uncountable families.

This is essentially the binary version of Valerio Capraro's answer, but it looks like it has less baggage.

Another point of view: label the root of an infinite binary tree 1 next level 2 3 the four nodes below that 4 5 6 7 (left to right) and so on. Each set corresponds to a unique path starting at the root.

$\endgroup$
5
  • $\begingroup$ Aaron, I don't quite understand what you mean. Is the following correct? You are saying that the desired family of countable sets is indexed by binary sequences. For a given binary sequence $(x_i)$, we are taking our countable set to be the set of sequences of nonnegative integers of the form $(0,a_1,a_2, \dots)$ such that for $i \ge 1$ we have $a_{i+1} = 2 a_i$ or $2 a_i +1$ according to whether $x_i = 0$ or $1$? What is the initial 0 needed for? $\endgroup$
    – MTS
    Feb 23, 2012 at 20:46
  • $\begingroup$ Better to start with 1, I fixed it. The sequence 011001... would code the set {1,2,5,11,22,44,89,...}. I start with one as a clumsy way to avoid having another set be {11,22,44,89,...} $\endgroup$ Feb 23, 2012 at 21:49
  • $\begingroup$ The last paragraph is my favourite way to visialise this example. It also gives a good visualisation of a similar construction asking for a family of subsets which are pairwise comparable with respect to inclusion! $\endgroup$ Feb 24, 2012 at 12:08
  • 1
    $\begingroup$ Every notion of constructive and non-constructive mathematics consider the binary sequences to form an uncountable set. This is so because Cantor's diagonal argument is constructive (and in fact expressible in a very weak system of logic). $\endgroup$ Feb 26, 2012 at 22:55
  • $\begingroup$ I admire constructive mathematics and shun excluded middle, but I am no expert (so I hope this makes sense). Sure Cantor's Diagonal Argument (CDA) is constructive but what does it really show (constructively speaking)? Suppose I accept those and only only those binary sequences output by a finite algorithm? Then the set $B$ of binary sequences I accept is no larger than the set $P$ of programs ( finite strings of characters including total nonsense ones). I can easily enumerate $P$ but I can not enumerate $B$ (as show by CDA), it is not (recursively?) enumerable. $\endgroup$ Feb 27, 2012 at 7:57
3
$\begingroup$

There are several constructions, some of which are quite nice and visual, and which you are therefore more likely to consider "constructive". These examples were shown to me by Imre Leader.

  1. Your example: take your infinite set to be $\mathbf{Q}$ and look at approximations to reals.

  2. Take your infinite set to be the nodes of an infinite binary tree, and take your sets to be the paths from the root to infinity. Every two such paths will go separate ways after finitely many steps.

  3. Take your infinite set to be the quarter-lattice $\mathbf{N}^2$, and take your sets, indexed by $\theta\in[0,\pi/2)$, to consist of the lattice points between $y=x \tan(\theta)$ and $y=x\tan(\theta) + 1$. Any two such slivers have finite intersection.

Complementary question: Find an uncountable totally ordered chain of subsets of $\mathbf{N}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.