pattern. Since we are considering a class that meets Kieffer’s condition, we find the redundancy in coding the dictionary given the pattern is $o(n)$. This also carries over to coding the dictionary given the pattern of the multiset, due to the independence between dictionary and order of pattern that we had put forth in Section \[sec:losslessCountable\]. Since both $H(\Delta|\{\Psi_i\}_{i=1}^n)$ and the redundancy in coding the dictionary given the pattern of the multiset are $o(n)$, the total rate requirement for coding the dictionary given the pattern of the multiset is $o(n)$.

Adding together the rate requirements for the two parts yields the following achievability theorem. The rate requirement is universally reduced from $[0,\infty)$ bits per letter for the sequence problem to $1$ bit per letter for the multiset problem.

\[thm:universalAchievability\] Given any i.i.d. source class that is universally encodable as a sequence, the multiset $\{X_i\}_{i=1}^n$ can be encoded with $n + o(n)$ bits.

A representation consists of the concatenation of the type of pattern and the dictionary given the type of pattern. The first part requires $n-1$ bits. The second part requires $o(n)$ bits. The total rate is then $n + o(n)$.

Coding a multiset is equivalent to coding a type 