This question already has an answer here:

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 $?

Thank you for your help.


marked as duplicate by Asaf Karagila, user61527, Tobias Kildetoft, Brian M. Scott, TZakrevskiy Sep 4 '13 at 6:56

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

migrated from mathoverflow.net Sep 4 '13 at 5:51

This question came from our site for professional mathematicians.

  • 1
    $\begingroup$ 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? $\endgroup$ – Ramiro de la Vega Sep 3 '13 at 16:22
  • $\begingroup$ 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. $\endgroup$ – 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$.

  • $\begingroup$ I feel that you should have instead expanded your hint on the original question and voted to close this as the duplicate it is. $\endgroup$ – Asaf Karagila Sep 4 '13 at 6:29
  • $\begingroup$ @Asaf: I thought that I’d deleted the other answer. Now that I’ve found it again, I see that I hadn’t. I’ll transfer this one to it, and perhaps add something about what one can legitimately conclude. I’ve also voted to close this one. $\endgroup$ – Brian M. Scott Sep 4 '13 at 6:41
  • $\begingroup$ 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. $\endgroup$ – Tobias Kildetoft Sep 4 '13 at 6:43
  • $\begingroup$ 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.) $\endgroup$ – Brian M. Scott Sep 4 '13 at 6:47

Not the answer you're looking for? Browse other questions tagged or ask your own question.