Adding distinct $n$ elements separates the elements from a multiset Let $K$ be a field or an abelian group. Let $M$ be a multiset of $n$ elements from $K$, or a sequence of $n$ elements $a_1,a_2,...,a_n$ from $K$. Let $S$ be a usual set of $n$ (distinct) elements from $K$. Is it always possible to separate the elments from $M$ by adding some elements from $S$? I.e, exist a sequence of $s_i\in S$ such that $a_i+s_i$ and $a_j+s_j$ are pairwise distinct for all $i\neq j\in \{1,...,n\}$.
Note that the elements $s_i$ that I picked from the set $S$ need not be pairwise distinct. E.g., say the elements in $M$ are pairwise distinct: $a_1,a_2,...,a_n$. Then I can just pick one element $s\in S$ so that $a_1+s,a_2+s,...,a_n+s$ are still pairwise distinct.
I can see this from example on $\mathbb Q$, $\mathbb R$ or $\mathbb C$. Using the total orders on them, we can easily prove this claim. But for an aribitrary field or an abelian group, I could not formulate the proof nicely. Or is there a proof avoid using the total orders on the field.
 A: It is true, if you allow $(s_i)_i$ to be non-injective.
We will prove a slightly stronger statement. Suppose $G$ is an abelian group, $(a_1,\ldots,a_{m})$ is a sequence in $G$, $S\subseteq G$ has $n$ elements, while $F\subseteq G$ has $n-m$ elements.
Then there is a sequence $s_1,\ldots, s_m$ in $S$ such that $s_i+a_i$ are distinct and not in $F$.
Proof by induction with respect to $m$:

*

*The case when $m=0$ is trivial.

*Fix any $m>0$. Then $S$ has more elements than $F$, so by pigeonhole, there is some $s_{m}\in S$ such that $a_{m}+s_{m}\notin F$. Let $F'=F\cup \{a_{m}+s_{m}\}$, and let $M'=(a_1,\ldots, a_{m-1})$. Proceed.

Your conjecture is the special case when $m=n$.

You probably already got it, but here is the argument for an injective $(s_i)_i$ in the case when $G$ admits a compatible linear ordering.
Choose one, then without loss of generality $a_1\leq a_2\leq\ldots,\leq a_n$ and $s_1<s_2<\ldots<s_n$. Then it is easy to check that $a_i+s_i<a_j+s_j$ when $i<j$.

Both proofs work even if $G$ is not abelian. In the case of the first proof, it is even enough for $+$ to be injective in the second argument.
