Relation on countable sets

Question

Let $R$ be a relation on two countable sets $A$ and $B$, where $R\subset A\times B$, with the following properties:

1. $\forall a\in A$ the set $\{b\in B: (a,b)\in R\}$ is finite.
2. For any finite set $A_0$: $$|\{b\in B : \exists a_0\in A_0, \text{such that} \ \ (a_0,b)\in R \}|\leq n|A_0|$$ where $n\in\mathbb{N}$.

How can I show then, that there exist $n$ disjoint sets, $B_1,B_2,\dots, B_n$, where $B_i\subset B\ \ \ \ \ \ \forall \ \ 1 \leq i\leq n$, and there exists $n$ one to one and onto functions $f_1,f_2,\dots, f_n$ such that $f_i:B_i\to A \ \ \ \ \ \ \ \forall \ \ 1 \leq i\leq n $?

Edited:

$B_i\in B$ replaced with $B_i\subset B$

Answer 1

Completely revised: If $a\in A$, I’ll write $R(a)$ for $\{b\in B:\langle a,b\rangle\in R\}$, and if $A_0\subseteq A$, I’ll write $R[A_0]$ for $$\left\{b\in B:\exists a\in A\Big(\langle a,b\rangle\in R\Big)\right\}=\bigcup_{a\in A_0}R(a)\;.$$

Your conditions are that $R(a)$ is finite for each $a\in A$ and that $|R[A_0]|\le n|A_0|$ for each finite $A_0\subseteq A$. You want to conclude that there are pairwise disjoint sets $B_1,\ldots,B_n\subseteq B$ and bijections $f_k:B_k\to A$ for $k=1,\dots,n$.

Note that the second condition implies the first; in fact, it implies that $|R(a)|\le n$ for each $a\in A$. However, neither condition matters, since the desired conclusion does not depend in any way on $R$; are you sure that you stated the problem correctly?

Since $B$ is countably infinite, there is a bijection $h:N^n\times\{1,\ldots,n\}\to B$. For $k\in\{1,\dots,n\}$ let $$B_k=h\big[\Bbb N\times\{k\}\big]=\big\{h(\langle m,k\rangle):m\in\Bbb N\big\}\;;$$ the sets $B_1,\ldots,B_n$ are pairwise disjoint (and their union is $B$, though that wasn’t required). Since $A$ is also countably infinite, there is a bijection $g:\Bbb N\to A$, and for $k\in\{1,\ldots,n\}$ we can define $f_k:B_k\to A$ as follows:

if $b\in B_k$, there is a unique $m\in\Bbb N$ such that $b=h(\langle m,k\rangle)$, and we define $f_k(b)=g(m)$. I leave it to you to check that $f_k$ is then a bijection.

(To me countable means finite or countably infinite, but I’m assuming that you were using it to mean countably infinite. If not, the result can be false when $B$ is finite. For example, take $A=\Bbb N$ and $B=\{0\}$, and let $R=A\times B$; your hypotheses are satisfied with $n=1$, but there is no function from $B$ onto $A$.)