Let $A_1,A_2,...$ be a sequence of sets such that for any positive integer $i$, there are only finitely many values of $j$ such that $A_j\subseteq A_i$. Prove that there is a sequence of positive integers $a_1,a_2,...$ such that for any pair $(i,j)$ to have $a_i\mid a_j\iff A_i\subseteq A_j$.
Problem
Source: China Western Mathematical Olympiad 2014 No.3
Tags: induction, combinatorics unsolved, combinatorics
23.08.2014 01:39
First, WLOG we can assume that there are no equal sets in the sequence (or we compose the sequence, maybe finite, of unique representatives, build the corresponding sequence $a_i$, and then propagate it to duplicates in the initial sequence). Next, renumber $A_1, A_2, \dots$ so that $B_i \subset B_j \implies i<j$, where $B_1, B_2, \dots$ are $A_1, A_2, \dots$ in some other order. This can be done in the following way. Take $A_1$ and those $A_i$ that are inside $A_1$ (by the condition, there is only finite number of them). Assign a weight to each of them equal to the number of sets in selected bunch that are entirely contained within the given set. Write out the sets in their weights' ascending order, sets with equal weights are placed arbitrarily. Then take $A_2$ (if it was not taken in the previous step) and those $A_i$ not taken yet that are inside $A_2$, apply the above ordering to them and write after already writen out elements. Take $A_3$, etc. Finally, assign a positive integer $b_i$ to each $B_i$ (and $a_j=b_i$ to corresponding $A_j$) as follows. Let $p_1<p_2<\dots$ be the infinite sequence of prime numbers. Then the sequence $b_1,b_2,\dots$ is built inductively by \[b_i=p_i \prod_{\substack{j<i \colon \\ B_j \subset B_i}} b_j \, .\] Clearly, $B_j \subseteq B_i \implies b_j \mid b_i$. In adition, it can be shown by induction that the prime divisor $p_j$ is present only in those $b_k$ for which $B_j \subseteq B_k$, so $B_j \not \subseteq B_i \implies b_j \nmid b_i$.