# Relation on countable sets

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$

• And the question is........? – Simon Hayward Aug 29 '13 at 9:25
• Is, of course, how to show that, the "Then..." part. – Yellow Aug 29 '13 at 9:28
• Ok, try to make that explicit so that people can pick up what you're asking straight off. – Simon Hayward Aug 29 '13 at 9:33
• What is the connection between $R$ and the $f_i$? If you are just looking for bijections between $n$ disjoint subsets of $B$ and $A$, then you can enumerate $B=\{b_1,b_2,...\}$ and take $B_i=\{b_k: k\equiv i (\text{mod}\;n)\}$. – walcher Aug 29 '13 at 9:36

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$.)

• Your sets need not be disjoint, nor need there be a bijection between your sets and $A$. – walcher Aug 29 '13 at 9:57
• Sir, could you please say how to construct such $f_i$? – Yellow Aug 29 '13 at 14:32
• Why is there only one element of $A$ that we could reasonably choose to be $f_k(b_i^a)$? What if for some $b$ there are infinitely many $a\in A$ such that $(a,b)\in R$? For example, what if $R=A\times \{b\}$? Then all your $B_i$ are subsets of $\{b\}$ (in fact all but one are empty) and none of them can be in one-one correspondence with $A$. The whole question is weird, because I don't know what the $R$-part has to do with the question, which only mentions two countable sets. – walcher Aug 29 '13 at 19:33
• @walcher: That comment is seriously incomplete and wasn’t even supposed to be posted; I’m not sure how it happened, and I’m going to delete it. In fact the theorem that you’re trying to prove isn’t true as stated, as you you’ve just pointed out; I misread it slightly when I originally answered. There are modifications of it that are true, but I’m going to have to think a bit to see if I can figure out which one was most likely intended. If I can, I’ll modify my answer suitably; if not, I’ll delete it. In the meantime you might double-check the statement of the theorem. – Brian M. Scott Aug 29 '13 at 19:46