Talk:Dimension theorem for vector spaces

Could someone write about how to prove the uniqueness of the dimension for infinite cardinals? - Gauge 06:02, 18 December 2005 (UTC)

I know its been a year and a half since anyone replied, but done. jbolden1517^Talk 15:19, 12 May 2007 (UTC)

Cardinality

I think the whole thing with going back and forth between infinite and finite violates the spirit of cardinality. It should be a single case. Actually looking at it the infinite case is false. jbolden1517^Talk 17:48, 12 May 2007 (UTC)

I do not know if there is a nice proof that works for both the finite and infinite case. I do not agree that a case distinction violates the "spirit of cardinality". Finite cardinals behave very differently from infinite one, this is why there are two (often quite separate) fields of mathematics dealing with them, combinatorics and set theory.

You deleted my argument for the case of finite dimensional spaces. But the argument

"Since the set J has smaller cardinality than the set I, the union of finite sets indexed by J still has smaller cardinality than I"

works only if I is infinite.

--Aleph4 00:18, 27 May 2007 (UTC)

I changed your proof a lot. The first line just asserts that as the RAA hypothesis. So its true by given. jbolden1517^Talk 00:38, 27 May 2007 (UTC)

What do you mean by "RAA"? Which first line asserts what?

Please explain why the cardinality of I is bigger than the cardinality of the union of the E_j, j in J.

--Aleph4 14:45, 29 May 2007 (UTC)

I don't really know where to write this, but this proof is wrong, and quite obviously so, too :
just consider the case where b_1 is the sum of the a_i. Then E_1 is I, and there's no i_0 such that ...

This theorem is actually not so easy to prove.
I'm not sure there exist a simple elegant proof, that's what I was looking for here.
The proof I know is no fun.
I also know it can be seen as a consequence of the Jordan-Holder theorem (see Bourbaki), but I ghess that would be overkill —Preceding unsigned comment added by 88.183.30.174 (talk) 15:45, 17 February 2008 (UTC)

I again divided the proof into two cases, one for finite dimension, the other for infinite dimension. As I have pointed out before, the proof from the article that works for infinite dimensions does not work in the finite-dimensional case. --

Aleph4 (talk) 17:44, 17 February 2008 (UTC)

The proof for the infinite case does indeed look wrong ($b_{1}=\sum _{i\in I}a_{i}$, as someone mentioned). Could someone replace it with a correct proof? If not, it should be removed.

Don't know when the above was written, but it seems correct now, the sum is over a finite set for every b. However, the supposition that one of the bases has greater cardinal tan the other depends on the (full) axiom of choice, contrary to what the lead suggests. Marc van Leeuwen (talk) 11:57, 20 March 2011 (UTC)

The case 1 (infinite case) is still wrong when I is countable. Also the proof depends on the axiom of choice (that alepf zero times κ is max of k and aleph zero). I'll try to find time to fix it. I wonder if the theorem remains true sans axiom of choice (assuming bases exist). Hadaso (talk) 07:43, 25 September 2016 (UTC)

AC in Proof?

In the proof it is assumed that there is a relation between the cardinalities of the two bases (that one is greater than the other). It seems to me that this relies on the Well-Ordering Principle. However I'm not familiar with the Ultra-filter Lemma and its applications... is this where it is used? There is a proof here: http://www.dpmms.cam.ac.uk/~tf/cam_only/cleverblass.pdf that relies only on propositional compactness and Hall's Matching Theorem.

You (who?) are right to the extent that trichotomy (any two cardinals are comparable) is equivalent to the axiom of choice, as stated in that article. So indeed the very start of the proof (assume one basis bigger than the other) is in blatant contradiction with the claim in the lead that the theorem only needs the ultrafilter lemma. Marc van Leeuwen (talk) 05:43, 20 March 2011 (UTC)

Although this particular proof does use full AC, it is nevertheless true that the dimension theorem (also known as Löwig's theorem) follows from the ultrafilter lemma. I have checked the primary source on this kind of issues: "Consequences of the axiom of choice" by Howard & Rubin. You can also check it online at http://consequences.emich.edu/file-source/htdocs/conseq.htm .Godelian (talk) 05:09, 11 October 2011 (UTC)

I've put up a somewhat rough proof at ProofWiki. That proof uses Hall's marriage theorem for infinite sets of finite sets, which I prove here from the finite form of the marriage theorem along with the Cowen-Engeler Lemma, an equivalent of the Ultrafilter Lemma. --Dfeuer (talk) 04:04, 24 May 2013 (UTC)

Please put a (more detailed) reference in the article as well. Thanks a lot. Marc van Leeuwen (talk) 08:45, 11 October 2011 (UTC)

Done. Godelian (talk) 23:57, 11 October 2011 (UTC)

Possible error?

I'm probably wrong, but in the alternative proof (the only one I understand): "there is at least one $t\in \{1,\ldots ,r\}$ such that $b_{t}$ can be written as a linear combination of $\{a_{1},b_{1},\dots ,b_{t-1}\}$. Thus, $\operatorname {span} (\{a_{1},b_{1},\dots ,b_{r}\}\setminus \{b_{t}\})=V$."

I agree with the last sentence, however to be technically correct, I believe that "there is at least one $t\in \{1,\ldots ,r\}$ such that $b_{t}$ can be written as a linear combination of $\{a_{1},b_{1},\dots ,b_{t-1}\}\cup \{b_{t+1},\dots ,b_{r}\}$. Thus..."

Am I wrong? If so, please delete this. Spartan S58 (talk) 08:18, 1 October 2011 (UTC)

Your alternative formulation is easier to understand, but the one currently in place is (almost) correct, because if one takes the smallest t such that the family $a_{1},b_{1},\ldots ,b_{t}$ is linearly dependent (and it exists because for $t=r$ one has dependence) then by minimality the final vector $b_{t}$ is a linear combination of the preceding ones. However this somewhat stronger statement does not appear to be used in the proof, so I agree that morally the somewhat longer statement should have been there. Yet the current proof is clumsy, and IMHO should be rewritten anyway. What should be used is what in France we call the fr:Théorème de la base incomplète (don't know if it has an English name), which I like to state in the following form: if F is a free (possibly empty) set of vectors and S a spanning list, then there exist a basis consisting of F together with a subset of S; moreover with the additional requirement the every retained element s of S be linearly independent on F united with the elements of S (strictly) before s, this basis is unique. The proof is by induction on the size of S: if one has selected the unique basis $B_{W}$ of $W=\operatorname {span} (F\cup \{b_{1},\dots ,b_{r-1}\})$ (with the additional requirement), then either already $W=V$, and then the additional condition forbids including $b_{r}$ in the basis so one must take $B_{W}$ as basis for V, or else W is strictly smaller than V, and since together with $b_{r}$ it spans V, W cannot contain $b_{r}$; then our basis for V must include $b_{r}$, and the remainder is forced to be $B_{W}$, and indeed $B_{W}\cup \{b_{r}\}$ is a basis of V satisfying the additional condition.

And to justify my "(almost) correct" above: when the current proof talks about $\operatorname {span} (\{a_{1},b_{1},\dots ,b_{r}\}\setminus \{b_{t}\})$, it forgets that removing $b_{t}$ could also inadvertently remove $a_{1}$ (when $b_{t}=a_{1}$). It should have said $\operatorname {span} (\{a_{1}\}\cup (\{b_{1},\dots ,b_{r}\}\setminus \{b_{t}\}))$. Marc van Leeuwen (talk) 07:24, 10 October 2011 (UTC)

A small correction to what I said above. I realised that as stated the inductive argument is wrong because the assumption is not satisfied when the induction hypothesis is applied: $\{b_{1},\dots ,b_{r-1}\}$ need not generate $\operatorname {span} (F\cup \{b_{1},\dots ,b_{r-1}\})$. The solution is surprisingly simple: for the sake of the inductive proof, weaken the condition in the statement from "S a spanning list" to "S is a list such that $F\cup S$ generates V"; the more general statement remains true, and in fact the inductive proof becomes valid (this is a case of Strengthening the induction hypothesis, for which I would have expected to find a WP article). Also, since I brought up the point that F and S could overlap, I should specify that a "retained element" of S is one that is in the basis but is not in F (without the latter clause, the elements of $F\cap S$ would necessarily be retained, but they cannot satisfy the additional requirement). Marc van Leeuwen (talk) 09:27, 10 October 2011 (UTC)

I must admit your proof loses me. I am a freshman in college, just turned 18, with an Intro to Lin Alg class Spring 2011, my last semester of high school. On the other hand, having reviewed the link, I remember that the proof of the dimension theorem that I saw in the class I took involved either cutting down a spanning but dependent set to a basis, or constructing a basis from an independent set that didn't span; this seems to be about what the French theorem talks about, just that it's a separate theorem from the dimension theorem. Also, having read that, I think part of my confusion with your proof initially comes from your use of the word "free" to mean linearly independent. I've never seen free used in that sense in English, though clearly in the French article. I give your proof another shot. (Also I have no clue what you mean by minimality, regarding my original question.) ((In an unrelated note, mijn Opa (en Oma) are from the Netherlands, but I don't speak Dutch :P)) Spartan S58 (talk) 22:49, 17 October 2011 (UTC)

Case 2 is Circular Logic?

The argument says that "... the matrix has n columns so it's column rank cannot exceed n." Isn't this using that the cardinality of a basis cannot exceed the cardinality of a spanning set, which is basically what the case is trying to prove? The argument also says that "This [the last assertion] means that its m rows cannot be linearly independent." Isn't this using that the cardinality of a linearly independent set cannot exceed the cardinality of a basis, which is basically what the case is trying to prove? This seems circular to me.

I see that the Alternative Proof says that "The [first] proof above uses several non-trivial results. If these results are not carefully established in advance, the [first] proof may give rise to circular reasoning." But how is one supposed to establish the results need for Case 2 in advance without first giving the alternative proof? It seems like Case 2 should just be completely replaced by the Alternative Proof.

— Preceding unsigned comment added by LoonetteTheClown (talk • contribs) 16:56, 10 July 2018 (UTC)

Good point. This proof may probably made correct if one use a definition of the rank of a matrix that is independent of the concept of vector space dimension (for example the number of non-zero rows in the row echelon form of the matrix). But here, rank, although not explicitly linked refers to rank (linear algebra), where it is defined as the dimension of the row space (a vector space) of the matrix. Thus the first proof is clearly circular, and must be removed. D.Lazard (talk) 17:57, 10 July 2018 (UTC)

I'm glad you agree about replacing Case 2. You mentioned that the proof may be made correct "if one uses the definition of the rank of a matrix that is independent of the concept of vector space dimension (for example the number of non-zero rows in the row echelon form of the matrix)." This change will certainly work to deal with my complaint about the assertion "... the matrix has n columns so it's column rank cannot exceed n." But it's not clear to me how changing the definition will deal with my complaint about the assertion "... its m rows cannot be linearly independent." Indeed, matrix rank must be connected to bases in some way if one wants to use matrix rank to prove something about bases. — Preceding unsigned comment added by LoonetteTheClown (talk • contribs) 19:20, 10 July 2018 (UTC)

The fix D.Lazard made looks good. Further to my last comment, it seems there is a way to handle the finite case using linear equations (matrix) theory. See the proof of Theorem 4 of Chapter 2 of Linear Algebra, 2 ed. by Hoffman and Kunze. It's page 44. — Preceding unsigned comment added by LoonetteTheClown (talk • contribs) 02:25, 12 July 2018 (UTC)

It was my guess in my above post. However, it appears that something equivalent with Steinitz exchange Lemma is always needed: the rank of a matrix or of a system of linear equations may be defined as the number of nonzero rows in a row echelon form, but one has to prove that this does not depend on the way of computing this row echelon form. Similarly, if the rank is defined as the maximal size of a square submatrix with nonzero determinant, one has to prove that the determinant is (up to the multiplication by a constant) the unique alternating n-linear form in n variables. It may also be argued that the proof of Steinitz exchange lemma is essentially an abstract description of the Gaussian elimination algorithm for computing a reduced row echelon form. However, explicating this requires some developments that make Steinitz exchange lemma the simplest way for proving the dimension theorem. D.Lazard (talk) 07:40, 12 July 2018 (UTC)