Krdytkyu

I can see the idea behind the following proof but I cannot express it in a mathematically elegant way...any help? Thanks in advance!

Let X = {1, 2, 3, . . . , 2k}. Prove that the largest separated subset of X has
cardinality k.

(A set S of integers (that is S ⊆ Z) is separated if for all i ∈ S
we have (i + 1) is not in S).

There is no largest separated set.

{1,3,.. 2k-1} and {2,4,.. 2k} are two separated subsets.

Neither is the largest. They are both maximal.

If you add another number to either of them, the set is no longer separated.

Contrary to your comment, you included no following proof.

Assume A is a separated subset of X with at least k + 1 elements.

Order A by magintude.

The difference between one point and the next is >= 2.

There are k gaps between the k + 1 numbers.

Thus the distance from the least to the last number is >= 2k.

Therefore last - first >= 2k: last => first + 2k.

As the first number in A is >= 1, a contradiction ensues.

The solution I had in mind is probably worth putting on record, because it avoids using the order structure of $X$.

Let $X^+ = X cup {2k + 1}$, so we have a function $sigma colon X to X^+$, $i mapsto i + 1$.

Because $sigma$ is injective, $|sigma(S)| = |S|$. We're given that $S cap sigma(S) = emptyset$, so $|S cup sigma(S)| = |S| + |sigma(S)|$. Therefore,
$$
2|S| = |S| + |sigma(S)| = |S cup sigma(S)| leqslant |X^+| = 2k + 1,
$$
whence $|S| leqslant k$. $square$