Prove a set is countable using its intersections I have the following question:
Suppose $A$ is a collection of subsets of $\mathbb{N}$ such that the intersection of any $b$ of them is a subset of $\{k \in \mathbb{N} : k < b\}$. Prove that $A$ is countable.
My initial thought was that since $\mathbb{N}$ is countable then any collection of subsets of $\mathbb{N}$ is likewise countable. But that would be incorrect since the power set of $\mathbb{N}$ is not countable by Cantor's Theorem. So instead to prove that $F$ is countable, I'm thinking for this question I need to create a bijection from $\mathbb{N}$ to $F$ but unsure how to do so using the intersection of any $m$ of them is a subset of $\{k \in \mathbb{N} : k < b\}$. I want to say that $\{k \in \mathbb{N} : k < b\}$ is countable since it's a subset of $\mathbb{N}$. But then I'm not sure how to relate that back to $A$.
The other approach I was thinking of was to say something like, let's define $m$ sufficiently large so that it has the same magnitude as $A$ but that assumption fails too because that will assume $A$ to be countable from the beginning.
Any advice or hints about this problem would be much appreciated
 A: So for this problem I am going to assume that $b \gt 1$ as if $b=1$ the problem breaks down as the intersection is a binary set operator. I am also assuming that $\mathbb{N}/0$ and that all elements in sets in $A$ are in $\mathbb{N}$. Hopefully my reasons for doing so are clear.
Hint: Start by proving that no set in A can contain members of the other sets in a other than $1$.
My Solution:
Let $b = 2$ then $\forall r_{1}, r_{2} \in A$ $r_{1} \cap r_{2} = \emptyset$ or $\{1\}$  Therefore any two sets in $A$ must not share any elements other than $\{1\}$. We know that $A$ can vary in elements, but by our condition we can show that one formulation of $A$ is $A_{0} =\{\{x_{n}\}\}$ $\forall x_{n} \in \mathbb{N}$. Now all we have to prove is that this formulation of A is countable and that $\vert A_{0}\vert \ge \vert A\vert$. The first is done by defining the bijection $f:A\to \mathbb{N}$ $st. f(\{x_{n}\}) = x_{n}$ $\forall n \in \mathbb{N}$. The second can be shown by noting that, because two sets in A must not share any elements other than $\{1\}$, and if a set contains one and another element the set with that element excluding $1$ cannot be in $A$. So the formulation of $A$ with each set only containing one element or that element and $1$ must have the greatest possible cardinality, assuming each contain all elements in $\mathbb{N}$. Therefore all formulations of $A$ are countable.
A: I would assume $b$ is a fixed natural number, so we cannot choose it.
Under that assumption, the following works as a proof:
Define $[b] := \{k \in \mathbb{N} \mid k < b\}$.  Now, given any subset $X \subseteq \mathbb{N}$, it holds that either $X \subseteq [b]$ or there is some [likely not at all unique] natural number $n \geq b$ such that $n \in X$.  In particular, this means we may write
$$\mathcal{A} = \{A \in \mathcal{A} \mid A \subseteq [b]\} \cup \bigcup_{n \geq b} \{A \in \mathcal{A} \mid n \in A\}.$$
The set $\{A \in \mathcal{A} \mid A \subseteq [b]\}$ is a subset of the power set of $[b]$, which is finite, and therefore $\{A \in \mathcal{A} \mid A \subseteq [b]\}$ is finite.  Additionally, the union is indexed over natural numbers $n \geq b$, so it is a countable union, so the only question is how large each set in the union can be.
To this end, fix $n \geq b$ and consider $\{A \in \mathcal{A} \mid n \in A\}$.  If this set has at least $b$ elements, we can select $b$ of them $A_1, A_2, \ldots, A_b$, but then $n \in \bigcap_{i=1}^b A_i \subseteq [b]$ is a contradiction as $n \not\in [b]$.  It follows that $\{A \in \mathcal{A} \mid n \in A\}$ has at most $b-1$ elements, so in particular, it's a finite collection of sets.
It follows that $\mathcal{A}$ is a countable union of finite sets, hence it is countable.

The following was my initial proof, which is much less elegant by my judgement.  I'm leaving it here just to highlight another way you might work such a problem.
First, we show that if $\mathcal{A}_0$ is a collection of subsets of $\mathbb{N}$ such that the intersection of any $b$ of them is empty, then $\mathcal{A}_0$ is countable.
To prove this claim, first we reconsider what "the intersection of any $b$ of them is empty" means in terms of the elements of $\mathbb{N}$.  That is, the intersection of any $b$ sets in $\mathcal{A}_0$ will be empty precisely when each element $n \in \mathbb{N}$ lies in at most $b-1$ sets in $\mathcal{A}_0$.  If we think about it, this gives us a way of listing out all the elements of $\mathcal{A}_0$!

*

*Step -1: If $\emptyset \in \mathcal{A}_0$, then put it first.

*Step 0: Choose an order for the at most $b-1$ sets $C \in \mathcal{A}_0$ such that $0 \in C$. Add them to the list in this order.

*Step 1: Choose an order for the at most $b-1$ sets $C \in \mathcal{A}_0$ such that $1 \in C$. Add them to the list in this order.

*...

*Step n: Choose an order for the at most $b-1$ sets $C \in \mathcal{A}_0$ such that $n \in C$.  Add them to the list in this order.

This list represents a surjection $\mathbb{N} \to \mathcal{A}_0$, so $\mathcal{A}_0$ will be countable.

Now we turn to the original problem of whether $\mathcal{A}$ is countable.  For this, we consider the map $$\Psi : \mathcal{A} \to \mathcal{P}(\{b, b+1, b+2, \ldots\})$$
defined by
$$\Psi(C) = C\cap \{b, b+1, b+2, \ldots\}.$$
Then the range of $\Psi$ is a collection $\Psi(\mathcal{A})$ of subsets of $\mathbb{N}$ such that the intersection of any $b$ of them is empty.  By the above argument, $\Psi(\mathcal{A})$ is countable.
Now, $\mathcal{P}(\{0, 1, \ldots, b-1\})$ is the power set of a finite set, hence finite, and since the cartesian product of a finite set and a countable set is countable, we see that $\mathcal{P}(\{0,1,\ldots,b-1\}) \times \Psi(\mathcal{A})$ is countable.  Therefore, the map
$$\Phi : \mathcal{P}(\{0,1,\ldots, b-1\}) \times \Psi(\mathcal{A}) \to \mathcal{P}(\mathbb{N})$$
defined by the union $\Phi(C_1, C_2) = C_1 \cup C_2$ has a countable range!
Why is that a good result?  It's because $$\mathcal{A} \subset \Phi(\mathcal{P}(\{0,1,\ldots, b-1\}) \times \Psi(\mathcal{A})),$$
so we conclude $\mathcal{A}$ is countable since it's a subset of a countable set.
The proof of this last claim, that $\mathcal{A}$ is a subset of that countable set we constructed, is simple if you have been able to follow the arguments up to that point, so I'll leave it to the reader.
