Paul R. Halmos bases proof Hi and thanks for reading. For those of you who know the book I am currently going through, Paul R. Halmos'Finite dimensional vector spaces: In the proof that all bases have the same number of elements, why has the author written that $n\geq{m}$, since, if $n=m$, then we would have replaced all of the X's with elements of Y, which is a contradiction to the original assumption, since at each stage of removing an $x_i$ and adding a $y_k$, the set of X's and Y's form a basis for V. But not if we remove all the X's.
For those not familiar with the book: I am having trouble with the following theorem, which states that any two bases of a vector space have the same number of elements.
The proof assumes that a set $X = \{x_1, x_2, ..., x_n\}$ has the property that, via a linear combination of the elements of $X$, we can create any element of the vector space under consideration. It also assumes there is another set $Y = \{y_1, y_2, ..., y_m\}$ of linearly independent vectors.
Since the set $Y$ is linearly independent, no linear combination of the vectors in a set $S\subset{Y}$ can be equal to any of the vectors in $Y\setminus{S}$. If we now take a new set $R$ formed by subtending the elements of $X$ to the last element of $Y$, we obtain the set $R=\{y_m, x_1, x_2, ..., x_n\}$. Since the X's form a basis of the vector space, $R$ is linearly dependent, which via the above, means that there is an $x_i$ that can be written as a linear combination of $y_m, x_1, ..., x_{i-1}$. This means that we can remove this $x_i$ from $R$ and still have a set that forms a basis for the vector space, since we can "add $x_i$" back into $R$ via a linear combination. This initial step has the effect of replacing $x_i$ with an element of $Y$. Since this new set is still a basis then, we can remove another $x_t$ from the set using the same logic, and we append the next element of $Y$ to the set, which gives the set
$\{y_{m-1}, y_m, x_1, ..., x_{i-1}, ..., x_t, x_{t+1}, ..., x_n\}$
Which is again a basis for the vector space. Continuing this way, we know that at each step, the new set is still a basis, since we can reconstruct the original base. It follows then, that we cannot remove all the X's since we would be left with the Y's; which by definition only fulfil one of the conditions of being a basis.
To conclude, the author states that this must imply that the number of X's must be greater than the number of Y's, ie $n\geq{m}$. My problem here is, however, that, by the previous statement, we cannot have $n=m$. We use a similar case where we swap the attributes of X and Y to show that $m\geq{n}$, and deduce that if each set has both conditions, $n=m$.
How is this possible, when $n=m$ contradicts the point of our proof?
Sorry for the long post.
 A: If $V$ is the vector space, the assumptions are that $X$ spans $V$, and $Y$ is linearly independent, where $|X|=n$ and $|Y|=m$. We keep replacing members of $X$ with members of $Y$ in such a way that after each replacement the resulting set still spans $V$. Suppose that $n<m$; then after $n$ replacements we will have a set $X'$ that spans $V$ and is a proper subset of $Y$. But that is impossible: $Y$ is linearly independent, so the vectors in $Y\setminus X'$ are in $V$ but not in the span of $X'$. Thus, it must be the case that $n\ge m$: no linearly independent set can be larger than any spanning set.
In particular, if $n=m$, the process ends when $X$ has been completely replaced by $Y$, and we discover that $Y$ not only is linearly independent, but also spans $V$ and is therefore a basis for $V$. You seem to have ruled out this possibility by misunderstanding the hypothesis: it is not true that $Y$ by definition fulfils only one of the conditions for being a basis. The hypothesis is simply that $Y$ is linearly independent, i.e., that it fulfils at least one of the requirements for being a basis; we are not told (and must not assume) that $Y$ does not span $V$.
A: Since the purpose of the proof is to show that X and Y contain the same number of vectors, how does "m= n contradict the point of the proof"?
