example of uncountable family of subsets of a countable set with finite intersections


We wish to give an answer to the following:

Problem. Assume, that X is a countable set. Is there a family {Xi}iI of subsets of X such that I is an uncountable set, but for any ijI the intersectionMathworldPlanetmath XiXj is finite?

Example. Let x[1,2) be a real number. Express x using digits

x=1.x1x2x3x4=1+i=1xi10-i

where each xi{0,1,2,3,4,5,6,7,8,9}. With x we associate the following natural numbersMathworldPlanetmath

βn(x)=1x1x2x3xn-1xn=10n+1+i=1nxi10n-i+1.

Now define A:[1,2)P() (here P(X) stands for ,,the power setMathworldPlanetmath of X”) by

A(x)={β1(x),β2(x),β3(x),}.

A is injectivePlanetmathPlanetmath. Indeed, note that for any x,y[1,2) if βi(x)=βj(y), then i=j (this is because equal β numbers have equal ,,length” and this is because each β has 1 at the begining, zeros are not the problem). Therefore, if A(x)=A(y) for some x,y, then it follows, that βi(x)=βi(y) for each i, but this implies that corresponding digits of x and y are equal. Thus x=y.

This shows, that {A(x)}x[1,2) is an uncountable family of subsets of . Now in order to prove that A(x)A(y) is finite whenever xy it is enough to show that we can uniquely reconstruct x from any infiniteMathworldPlanetmathPlanetmath sequence of numbers from A(x). This can be proved by using similar techniques as before and we leave it as a simple exercise.

Title example of uncountable family of subsets of a countable set with finite intersections
Canonical name ExampleOfUncountableFamilyOfSubsetsOfACountableSetWithFiniteIntersections
Date of creation 2013-03-22 19:16:29
Last modified on 2013-03-22 19:16:29
Owner joking (16130)
Last modified by joking (16130)
Numerical id 4
Author joking (16130)
Entry type Example
Classification msc 03E10