Disjoint Refinement

248 Views Asked by At

Prove that for any countable family of infinite sets from $\mathbb{N}$, $A = \{A_n \colon n \in \mathbb{N}\}$, there is a disjoint refinement $B = \{B_n \colon n \in \mathbb{N}\}$ of infinite sets, that is for every $n$, $B_n$ is an infinite subset of $A_n$, and all the $B_n$'s are pairwise disjoint.

Also prove the version for $\mathbb{R}$: for any family (with cardinality not surpassing $\mathbb{R}$'s) of sets from $\mathbb{R}$, $A = \{A_r \colon r \in \mathbb{R}\}$ such that $|A_r| = \mathbb{R}$ for all $r$, there is a disjoint refinement $B = \{B_r \colon r \in \mathbb{N}\}$, that is for every $r$, $B_r$ is a subset of $A_r$, $|B_r| = \mathbb{R}$ for all $r$, and all the $B_r$'s are pairwise disjoint.

Sorry for my complete lack of knowledge in latex.

2

There are 2 best solutions below

3
On BEST ANSWER

Here's an idea for the first one.

  1. put the least element of $A_0$ into $B_0$.
  2. put the least element of $A_0$ not already assigned into $B_0$, and the least element of $A_1$ not already assigned into $B_1$.
  3. put the least element of $A_0$ not already assigned into $B_0$, the least element of $A_1$ not already assigned into $B_1$, and the least element of $A_2$ not already assigned into $B_2$.
  4. etc.

(By "not already assigned" I mean not already put into some $B_i$ in some previous step or in some previous part of the same step.)

Another way to think about this is that if we change the enumeration of the $A_i$'s so that each one is repeated infinitely many times, then we only have to choose a single element from each one. This approach can be generalized to solve the second problem also: enumerate the $A_i$'s in order type $|\mathbb{R}|$ so that each one is repeated $|\mathbb{R}|$ many times, and then from each $A_i$, choose an element that was not already chosen from any of the previous $A_i$'s (using the fact that every proper initial segment of the well-ordering has fewer than $|\mathbb{R}|$ many elements.) I don't know if the Axiom of Choice is really needed here.

0
On

You can find Arnold Miller's solution here.