MAD families

Please comment your solutions, questions and remarks..

Maximal Almost Disjoint families. This is not so much of a riddle than just a theorem, but the solution is fun, so I would like to place it here. This is like a dual to the earlier problem.

Suppose A is a family of subsets of natural numbers. A is called almost disjoint (AD) if the intersection of any two elements of A is finite. For example a family of subsets in which all elements are pairwise disjoint is AD. The latter can be at most countable. Show that an almost disjoint family of subsets of natural numbers can be

(a) uncountable
(b) of size continuum (i.e. as big as the power set of natural number)


A hint below; after the hint the level becomes 2/5 I guess.

There is a bijection between natural numbers and the set of all finite subsets of natural numbers.

About Vadim Kulikov

For details see this
This entry was posted in Combinatorics, Mathematics, Set Theory, Wednesday Problem. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *