For a positive integer $n>2$, show that there exists infinite sets $A_1, A_2, \ldots, A_n$ such that $A_i \cap A_j = \emptyset$ for $i \neq j$ and $\bigcup_{i=1}^n A_i = \mathbb{N} =\{1,2,3,\ldots\}$ (the $n=2$ case is given by $A_1 = \{1, 3, 5, \ldots \}$ and $A_2 = \{2, 4, 6, \ldots \}$).
This is clearly true and easily shown by taking the set of equivalence classes modulo $n$. However, I thought of another proof using induction, but I'm not certain how to formalize it. The base case is given in the problem itself, and here's my inductive step:
Given $k$ infinite disjoint sets whose union is $\mathbb{N}$, arrange them like this:
\begin{align}
i=1, \; &A_1: \; a_{11} \; a_{12} \; a_{13} \; a_{14} \ldots\\
i=2, \; &A_2: \; a_{21} \; a_{22} \; a_{23} \; a_{24} \ldots\\
i=3, \; &A_3: \; a_{31} \; a_{32} \; a_{33} \; a_{34} \ldots\\
&\vdots \\
i=k, \; &A_k: \; a_{k1} \; a_{k2} \; a_{k3} \; a_{k4} \ldots\\
i=k+1, \; &A_1: \; a_{11} \; a_{12} \; a_{13} \; a_{14} \ldots\\
i=k+2, \; &A_2: \; a_{21} \; a_{22} \; a_{23} \; a_{24} \ldots\\
&\vdots \\
\end{align}
Remove every $ii$-th element from its respective set to form new sets $A_1', A_2', \ldots, A_k'$ and put every removed element in a new set $A_{k+1}'$.
My claim is that this set is disjoint with the others, and that $\bigcup_{i=1}^{k+1} A_i' = \mathbb{N}$. However, I showed this proof to my Analysis professor, and he said it doesn't guarantee that these sets are disjoint, but I'm not sure how can I formalize this since (to me) it is pretty obvious they are disjoint. If this this form is not good enough, what would be a better one, and is my claim correct at all?
Best Answer
I also disagree with your professor, and think that the new collection of sets will still be pairwise disjoint. But this seems like one of those constructions that are pretty easy to understand conceptually, but are absolute hell to come up with a good notation for.
The down side is that I don't think it's a valid argument, if I understand it correctly as some adaptation of the standard diagonal argument. Because at your induction step you only take a finite number of elements to build your new $A'_{k+1}$! I think you gave yourself an invalid mental picture when you wrote your tableau with row $A'_{k+2}$, and then with "..." for an infinite number of rows. At each inductive step you only have $k$ rows.
You could save the argument by "wrapping the diagonal around" the finite number of rows. I.e. when extracting the values for your new row, after $A_{k,k}$ you go back up to the first row and extract $A_{1,k+1}$, then $A_{2,k+2}$, .... Basically, at step $k$ you take $1/k$ of each existing rows' elements to build your new infinite row. Maybe you had this image in your mind when you used the word 'every' in 'every $ii$-th element', but it didn't come through in your description.
Although once you've fixed it this way, you could see that it could be even easier: At each step $k$, build a new row by taking every other element of your current first row. It's a little easier to describe this procedure, although in both constructions it'd still be a pain to write a formula for what the sequences look like.