Cardinality of the sum of two sets the question ist how to prove the following: $|X+Y|\ge |X|+|Y|-1$, where $X$ und $Y$ are two finite subsets in some vector space. I know the proof for the one-dimensional case but it is based on the order properties of numbers which are not available in general. I thought about induction but don't see how to do it yet. In case of $|X|=|Y|=2$ the proof is easy but I cannot yet extract a general idea from it. It would be nice to hear some ideas. Thanks in advance.
 A: All we need is that the vector space is finite dimensional. If not, finite subsets can be projected into a finite dimensional subspace of the full vector space. Once this is done, you an have a total order using a lexicographic ordering.

Let $X+Y = \{x+y | x\in X, y\in Y\}$.
Case 1: If X is a singleton, then $|X+Y| = |Y|\geq |X| + |Y| - 1$
Case 2: If X is not a singleton. We will show this by induction on the elements of $X$.
Base Case: Let $X$ have two elements - $\{x,x'\}$.
Let $A_x(Y) = \{x+y | y\in Y\} \text{ for } x\in X$. We note that $|A_x| = |Y|$. Similarly, let $x' \in X \neq x$. Then $A_{x'}(Y) = \{x'+y | y\in Y\}$. $|A_x| = |A_{x'}|=|Y|$.
Note that if $$x'<_{TO}x\qquad or \qquad x'>_{TO}x$$ then $$(x'+min(Y)) <_{TO} (x+min(Y))\qquad or \qquad (x'+max(Y)) >_{TO} (x+max(Y))$$
Therefore we have atleast one new element in the set.
Here we have used the notation "$<_{TO}$" and "$>_{TO}$" for comparisons using our lexicographic total order. We will just use "$<$" and "$>$" notationally going forward.
Therefore $|A_x \cup A_{x'}| \geq |A_x|+1 =|Y|+1 \geq |X|+|Y|-1$
Induction Hypothesis: Let the elements of $X = \{x_1,\dots,x_m\}$ be ordered in terms of our lexicographic order. Then we will assume for the inductive hypothesis that
$|\bigcup\limits_{i=1}^k A_i| \geq |Y|+k-1$ where $A_i = \{x_i + y|y\in Y\}$
Then we want to show that $\left|\bigcup\limits_{i=1}^{k+1} A_i\right| \geq |Y|+k$. But this is straightforward to see as $x_k + max(Y) > max\left(\bigcup\limits_{i=1}^{k} A_i\right)$. Therefore, there is atleast one new element added over $\bigcup\limits_{i=1}^{k} A_i$ by $\bigcup\limits_{i=1}^{k+1} A_i$. Therefore
\begin{align*}
\left|\bigcup\limits_{i=1}^{k+1} A_i\right| &\geq \left|\bigcup\limits_{i=1}^{k} A_i\right| + 1 \\&= (|Y|+k-1)+1 \\&= |Y|+k
\end{align*}

Now we can extend this to all of $X$ and therefore we have $|X+Y|\geq |X|+|Y|-1$ (for this case)
