How to prove that a family of subsets of $\mathbb N$ such that the intersection of any two distinct $A,B$ in the family $|A\cap B|\leq1$ is countable?

Question

Hello I'm having trouble figuring out how to prove this problem: let $F$ be contained in $\mathcal{P}(\mathbb{N})$ (power set of natural numbers) such that $F$ is maximal and for every $A, B \in F$ with $A \not = B$, we have $|A \cap B| \leq 1$. Prove that $|F|=\aleph_0$.

Thank you for the help in advance!

Answer 1

To show that $F$ must be countable, consider the function $\min:F-\{\varnothing\}\to\mathbb N$ that sends each nonempty member of $F$ to its smallest element. If $F$ were uncountable, then since $\mathbb N$ is countable, min would be constant, say with value $n$, on some uncountable subfamily $F'$ of $F$. Then $\{A-\{n\}:A\in F'\}$ would be an uncountable family of pairwise disjoint subsets of $\mathbb N$, which is impossible.

To complete the proof, we still need that $F$ can't be finite. Suppose it were finite, say with exactly $m$ elements. Then there are at most $m(m-1)/2$ natural numbers that are in two members of $F$. If $k$ is any natural number other than these, then $F\cup\{k\}$ contradicts the maximality of $F$.

Answer 2

Here’s another approach. Let $F_0$ be a maximal pairwise disjoint subfamily of $F$; clearly $F_0$ is countable. For $x\in F_0$ and $n\in x$ let

$$A(x,n)=\big\{y\in F:y\cap x=\{n\}\big\}\;.$$

For each $y\in F$ there are unique $x_y\in F_0$ and $n_y\in x_y$ such that $y\in A(x_y,n_y)$, so it suffices to show that each $A(x,n)$ is countable. This is not hard: if $y,z\in A(x,n)$, and $y\ne z$, then $y\cap z=\{n\}$, so $y\setminus\{n\}$ and $z\setminus\{x\}$ are disjoint, so the sets $y\setminus\{n\}$ for $y\in A(x,n)$ are pairwise disjoint. Thus, there are only countably many sets $y\setminus\{n\}$ with $y\in A(x,n)$, and $A(x,n)$ is therefore countable.