Theorem ELIS: maybe you want a corollary for basis expansion

[darijgr]

In the proofs of Theorem UTMR and Theorem ME, you are using the following fact:

Theorem ELISB: Suppose $V$ is a finite-dimensional(!) vector space and $S$ is a linearly independent set of vectors from $V$. Then, there exists a basis $T$ of $V$ such that $S \subseteq T$.

You refer to Theorem ELIS for it, but Theorem ELIS only handles extension to a slightly bigger linearly independent set. Deriving Theorem ELISB from Theorem ELIS is not as obvious as it looks like -- it's not just applying Theorem ELIS several times. You have to prove that you will eventually span the whole $V$. Probably the simplest way is to argue that you cannot add more than $\dim V - |S|$ new vectors, since that (by Theorem SSLD) would give a linearly dependent set. Anyway, this is worth stating as a result in its own, rather than factoring its proof into the already rather long proof of Theorem UTMR.

[rbeezer]

Thanks. Outside of one example, it is a universal assumption that every vector space considered is finite-dimensional, so I never make it part of a hypothesis.

I am assuming that the argument for ELISB can be constructed by the reader, though almost never do I make such assumptions. This might make a good exercise as an application of ELIS and surrounding results, which I could refer to at the two uses you mention? I don't really do this much either.

On 06/20/2017 03:37 AM, Darij Grinberg wrote:

In the proofs of Theorem UTMR and Theorem ME, you are using the following fact:

Theorem ELISB: Suppose $V$ is a finite-dimensional(!) vector space and $S$ is a linearly independent set of vectors from $V$. Then, there exists a basis $T$ of $V$ such that $S \subseteq T$.

You refer to Theorem ELIS for it, but Theorem ELIS only handles extension to a slightly bigger linearly independent set. Deriving Theorem ELISB from Theorem ELIS is not as obvious as it looks like -- it's not just applying Theorem ELIS several times. You have to prove that you will eventually span the whole $V$. Probably the simplest way is to argue that you cannot add more than $\dim V - |S|$ new vectors, since that (by Theorem SSLD) would give a linearly dependent set. Anyway, this is worth stating as a result in its own, rather than factoring its proof into the already rather long proof of Theorem UTMR.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/rbeezer/fcla/issues/86, or mute the thread https://github.com/notifications/unsubscribe-auth/ABy2cqvAGnI2BibFoRAgpum42qMM3_O3ks5sF6ECgaJpZM4N_ZVY.

[darijgr]

I am not sure about its usefulness as an exercise -- the subtle need for applying SSLD is too easy to miss, and at this level students (in my limited experience) are rather likely to miss it (thus believing the exercise to be trivial), particularly if they have never reasoned about algorithms before.

[rbeezer]

I'd likely include a complete solution, for exactly this reason.

On 06/20/2017 01:49 PM, Darij Grinberg wrote:

I am not sure about its usefulness as an exercise -- the subtle need for applying SSLD is too easy to miss, and at this level students (in my limited experience) are rather likely to miss it (thus believing the exercise to be trivial), particularly if they have never reasoned about algorithms before.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/rbeezer/fcla/issues/86#issuecomment-309887090, or mute the thread https://github.com/notifications/unsubscribe-auth/ABy2ctD6U-WTbXqr9CJq0DH5NGgfuWKEks5sGDA_gaJpZM4N_ZVY.