Uncountable family of infinite subsets with pairwise finite intersections

Question

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.

Answer 1

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!

Answer 2

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

Answer 3

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

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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