[proofplan] We exploit the total order on $\mathbb{R}$ to exhibit $|A| + |B| - 1$ distinct elements of $A + B$. The idea is to walk along two sorted sequences: first hold the smallest element of $A$ fixed and increment through $B$, then hold the largest element of $B$ fixed and increment through $A$. The strict ordering guarantees that each successive sum is strictly larger than the previous one, producing a strictly increasing chain of $|A| + |B| - 1$ distinct sums inside $A + B$. [/proofplan] [step:Exhibit $|A| + |B| - 1$ distinct sums by walking along two sorted sequences] Write $A = \{a_1 < a_2 < \cdots < a_n\}$ and $B = \{b_1 < b_2 < \cdots < b_m\}$ where $n = |A|$ and $m = |B|$. Consider the following $n + m - 1$ elements of $A + B$: \begin{align*} a_1 + b_1 < a_1 + b_2 < \cdots < a_1 + b_m < a_2 + b_m < a_3 + b_m < \cdots < a_n + b_m. \end{align*} We verify that every consecutive pair in this list satisfies a strict inequality: - **Within the first block** ($a_1 + b_j$ for $j = 1, \ldots, m$): since $b_j < b_{j+1}$, adding $a_1$ to both sides preserves the strict inequality, giving $a_1 + b_j < a_1 + b_{j+1}$. - **At the transition** (from $a_1 + b_m$ to $a_2 + b_m$): since $a_1 < a_2$, adding $b_m$ to both sides gives $a_1 + b_m < a_2 + b_m$. - **Within the second block** ($a_i + b_m$ for $i = 2, \ldots, n$): since $a_i < a_{i+1}$, adding $b_m$ to both sides gives $a_i + b_m < a_{i+1} + b_m$. Every strict inequality in the chain uses only the fact that $\mathbb{R}$ is an ordered group: addition preserves strict inequalities. Since all $n + m - 1$ elements are strictly increasing, they are pairwise distinct. [guided] The goal is to show $|A + B| \geq |A| + |B| - 1$, so we need to find at least $n + m - 1$ distinct elements inside $A + B$. How should we search for them? The key observation is that in an ordered group, if $a < a'$ and $b$ is any fixed element, then $a + b < a' + b$. This means we can generate strictly increasing sums by incrementing one summand while holding the other fixed. The strategy is to construct a single increasing chain that uses all of $B$ (holding $a_1$ fixed) and then all of $A$ (holding $b_m$ fixed), with the two chains meeting at the element $a_1 + b_m$. Write $A = \{a_1 < a_2 < \cdots < a_n\}$ and $B = \{b_1 < b_2 < \cdots < b_m\}$ where $n = |A|$ and $m = |B|$. Consider the chain: \begin{align*} \underbrace{a_1 + b_1, \; a_1 + b_2, \; \ldots, \; a_1 + b_m}_{m \text{ elements}}, \; \underbrace{a_2 + b_m, \; a_3 + b_m, \; \ldots, \; a_n + b_m}_{n - 1 \text{ elements}}. \end{align*} This is a list of $m + (n - 1) = n + m - 1$ elements, all belonging to $A + B$. We verify the chain is strictly increasing: - **Within the first block** ($a_1 + b_j$ for $j = 1, \ldots, m$): for consecutive indices $j < j+1$, we have $b_j < b_{j+1}$ by the ordering of $B$. Adding $a_1$ to both sides preserves the strict inequality (since addition in $\mathbb{R}$ is order-preserving), giving $a_1 + b_j < a_1 + b_{j+1}$. - **At the transition** (from $a_1 + b_m$ to $a_2 + b_m$): we have $a_1 < a_2$ since $|A| \geq 1$ and $a_1$ is the smallest element of $A$. Adding $b_m$ to both sides gives $a_1 + b_m < a_2 + b_m$. - **Within the second block** ($a_i + b_m$ for $i = 2, \ldots, n$): for consecutive indices $i < i+1$, we have $a_i < a_{i+1}$ by the ordering of $A$. Adding $b_m$ to both sides gives $a_i + b_m < a_{i+1} + b_m$. Since every consecutive pair satisfies a strict inequality, all $n + m - 1$ elements are pairwise distinct. Each of these elements belongs to $A + B$ (being a sum of one element from $A$ and one from $B$), so $|A + B| \geq n + m - 1 = |A| + |B| - 1$. Why does this argument fail in a group without a total order? The entire construction depends on being able to compare sums: we need $a + b < a' + b$ whenever $a < a'$, which requires a compatible total order. In a finite group like $\mathbb{Z}_n$ with $n$ composite, no such order exists, and the conclusion $|A + B| \geq |A| + |B| - 1$ is indeed false in general (for example, $A = B = \{0, 2, 4\}$ in $\mathbb{Z}_6$ gives $A + B = \{0, 2, 4\}$, which has only $3$ elements rather than the predicted $5$). [/guided] [/step] [step:Conclude the lower bound] Since $A + B$ contains at least $n + m - 1 = |A| + |B| - 1$ distinct elements, we have \begin{align*} |A + B| \geq |A| + |B| - 1. \end{align*} [/step]