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


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

  • $\begingroup$ And the question is........? $\endgroup$ – Simon Hayward Aug 29 '13 at 9:25
  • $\begingroup$ Is, of course, how to show that, the "Then..." part. $\endgroup$ – Yellow Aug 29 '13 at 9:28
  • $\begingroup$ Ok, try to make that explicit so that people can pick up what you're asking straight off. $\endgroup$ – Simon Hayward Aug 29 '13 at 9:33
  • $\begingroup$ 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)\}$. $\endgroup$ – 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$.)

  • $\begingroup$ Your sets need not be disjoint, nor need there be a bijection between your sets and $A$. $\endgroup$ – walcher Aug 29 '13 at 9:57
  • $\begingroup$ Sir, could you please say how to construct such $f_i$? $\endgroup$ – Yellow Aug 29 '13 at 14:32
  • $\begingroup$ 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. $\endgroup$ – walcher Aug 29 '13 at 19:33
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Aug 29 '13 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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