# A relation on 2 countable sets [duplicate]

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\subset A$: $$|\{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}$.

I need to 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$?

## migrated from mathoverflow.netSep 4 '13 at 5:51

This question came from our site for professional mathematicians.

• The statement that you need to show is trivial and has nothing to do with $R$. Are you missing something? Why do you need to show that? – Ramiro de la Vega Sep 3 '13 at 16:22
• I guess what Daniella thought is the infinite generalization of the marriage theorem: if $\{A_i:i\in I\}$ is a countable family of finite sets, for every finite $I'\subseteq I$, $|\bigcup\{A_i:i\in I'\}|\geq n|I'|$ holds, then there are $B_i\subseteq A_i$, $|B_i|=n$ such that $\{B_i:i\in I\}$ is a disjoint family. In fact, this holds for any $I$. The case $n=1$ is the Hall-Rado version of the marriage theorem, the case $n>1$ easily follows from the restricted case. – Péter Komjáth Sep 4 '13 at 4:41

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$.
Unfortunately, there are counterexamples. Let $A=B=\Bbb N$, and let $f:\Bbb N\to\Bbb N:k\mapsto 0$ be the constant zero function. Then $|R[k]|=1$ for each $k\in\Bbb N$, and $|R[F]|=1\le|F|$ for each non-empty finite $F\subseteq\Bbb N$, so your hypotheses are satisfied with $n=1$. However, there is no bijection from any subset of $B$ onto $A$.
• I don't quite get your last comment. If both $A$ and $B$ are countably infinite, then there are certainly bijections from subsets of $B$ onto $A$. I guess I just haven't seen what the connection between those functions and the relation needs to be yet. – Tobias Kildetoft Sep 4 '13 at 6:43
• You don’t see it because I read more into the question than is there: I was assuming that the functions $f_k$ were supposed to have something to do with $R$, which is not the case. Ignore this answer: I’ll delete it shortly. (I’m having a bad evening.) – Brian M. Scott Sep 4 '13 at 6:47