Not signed in (Sign In)

Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

  • Sign in using OpenID

Discussion Tag Cloud

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

Welcome to nForum
If you want to take part in these discussions either sign in now (if you have an account), apply for one now (if you don't).

nLab > Latest Changes: Nielsen-Schreier theorem

Bottom of Page

1 to 42 of 42

  1.  
    • CommentRowNumber1.
    • CommentAuthorUrs
    • CommentTimeOct 8th 2012
    • (edited Oct 8th 2012)

    I discovered that there was a well-hidden entry Nielsen-Schreier theorem. I have now cross-linked it with free group, subgroup and in particular with free module, where the generalization is stated.

    • CommentRowNumber2.
    • CommentAuthorUrs
    • CommentTimeOct 8th 2012

    I also edited the References at Nielsen-Schreier theorem a bit.

    • CommentRowNumber3.
    • CommentAuthorUrs
    • CommentTimeOct 8th 2012
    • (edited Oct 8th 2012)

    Can we think about the proof of the Nielsen-Schreier theorem for a sec?

    I looked at some of the literature that is currently recommended by the entry. For some of the references I am not sure which chapter I am supposed to look at. In Gilbert-Porter I found the relevant page, but there essentially the same sketch of the proof is given as in the entry, with details omitted, it seems to me.

    I feel like writing out the complete proof simply as follows:

    Proposition Every subgroup H↪F(S)H \hookrightarrow F(S) of a free group F(S)F(S) on a set SS is itself free on some set.

    Proof. Let EF(S)≔F(S)⫽F(S)\mathbf{E} F(S) \coloneqq F(S)\sslash F(S) be the action groupoid of F(S)F(S) acting on itself. This is contractible, EF(S)≃*\mathbf{E}F(S) \simeq *, and comes with a canonical F(S)F(S)-action (from the other side). Hence it comes with an induced HH-action and the quotient H\\EF(S)≃H\\*H \backslash \backslash\mathbf{E}F(S) \simeq H \backslash \backslash * is the conneced groupoid with π 1=H\pi_1 = H. So it is sufficient to show that H\\EF(S)H \backslash \backslash\mathbf{E}F(S) is isomorphic to the free groupoid on a connected graph. But EF(S)\mathbf{E}F(S) itself is the free groupoid on a connected graph, namely on the action graph F(S)⫽SF(S)\sslash S. So

    H\\EF(S)=H\F(F(S)⫽S)=F((H\F(S))⫽S). H \backslash \backslash \mathbf{E}F\left(S\right) = H \backslash F\left( F\left(S\right)\sslash S \right) = F \left(\left(H \backslash F\left(S\right)\right)\sslash S\right) \,.

    QED.

    I went ahead and added that to the entry, replacing the previous “sketch” there. Should there be heavy complaints, we can roll back, of course.

    • CommentRowNumber4.
    • CommentAuthorTodd_Trimble
    • CommentTimeOct 8th 2012
    • (edited Oct 9th 2012)

    Urs, I’d suggest that you include both proofs. The proof that you replaced had a certain intuitive immediacy. It looks as though you are trying to rewrite it in more algebraic language, but there is a certain amount of notation that has to be digested, and I think having the earlier proof sketch as a scaffold would help many readers with that digestion.

    • CommentRowNumber5.
    • CommentAuthorEric
    • CommentTimeOct 9th 2012

    Hi Todd,

    Since you bring this up, I thought I'd express a minor observation lately. I've always struggled to follow what goes on here (I still read every nForum discussion and every nLab revision), but I could always squint and look through the words and at least pretend I could understand what is trying to be said. Lately, I cannot even pretend anymore. Maybe it has to do with a slight change of emphasis to logic and the new notation it entails, but I am personally unable to get much out of some of the recent materials. Since the nLab is essentially a selfish endeavor, and I completely support that, it is not very important that I'm no longer able to follow, but thought I'd bring it up in case it might influence the presentation of new material.

    Cheers!

    • CommentRowNumber6.
    • CommentAuthorTodd_Trimble
    • CommentTimeOct 9th 2012

    Eric,

    In response, I’d say Urs is doing a terrific job with the Geometry of Physics page, and the fact that it’s in three tiers will ensure a kind of symbiosis which will enhance understanding. I think that’s also sort of what I’m suggesting here with the Nielsen-Schreier page, that one have an intuitive topological language in concert with the algebraic. Both proofs concern covering spaces, and IMHO it will be very helpful to have them “play off one another”, as it were.

    A lot of stuff appearing on the nLab these days is “hot off the press”, and it will take time before it all sinks in and gets a good going over from the point of view of exposition. All of us, including (perhaps especially!) myself, need to be patient!

    • CommentRowNumber7.
    • CommentAuthorTim_Porter
    • CommentTimeOct 9th 2012

    I would support including the two versions of the proof. Sometimes I am left confused if a highly nPOV language is used too immediately. A sketch proof as was removed may help one to understand the language in the nPOV proof a skill that is then transferrable to other deeper proofs where the nPOV language can not be avoided. (I think the reason why the sketch proof was very like that in Gilbert and Porter is probably obvious! There was also Ronnie’s influence and a paper by Stallings I believe. ) That proof has sides to it that are not so immediate in the new one, e.g. the contractibility is related to a maximal tree choice, and allows explicit generators to be observed and manipulated. It also leads on conceptually to the analysis of homotopical syzygies.

    • CommentRowNumber8.
    • CommentAuthorUrs
    • CommentTimeOct 9th 2012
    • (edited Oct 9th 2012)

    Okay, I didn’t think of what I wrote as being another proof. I thought I was making explicit precisely the proof that was being hinted at in the entry. In particular the emphasis on groupoids was meant to follow the numerous hints in the entry that “this is really a groupoid proof”.

    I have now added a paragraph to the entry, first paragraph in the proof now, which provides a bit more chat and mentions the word “covering space”, if that was felt to be amiss.

    I think this says all that the previous version of the entry alluded to and says it in detail. But please, if you find aspects missing, add a comment.

    I must say I found the previous version of the entry fell short of being satisfactory. The “sketch of the proof” given there really ended before the key step appeared (namely to see that the quotient of the covering space is still the free groupoid on a directed graph) and I didn’t see that the literature being pointed to says it more explicitly. But it is easy to see this statement directly in one line and I wanted to record that. So I thought of my edit as adding to the entry, not as removing. Sorry if it came across differently.

    • CommentRowNumber9.
    • CommentAuthorTim_Porter
    • CommentTimeOct 9th 2012
    • (edited Oct 9th 2012)

    I used to illustrate the proof with an example of a figure eight and then looked at a Cayley graph of S3S3 as a covering space of that space. This was nice and visual, but it really needs being seen to be done rather than on web page. I found students seemed to react well to that as one could show quite intuitively that the projection was a covering. Somehow the proof in Gilbert and Porter did not capture enough of the intuitions, and they are hard to get ’right’. Perhaps I will be able to add in some material on that example in a separate entry. I seem to have little time (like us all) but I am meant to be ‘retired’! :-)

    • CommentRowNumber10.
    • CommentAuthorUrs
    • CommentTimeOct 9th 2012

    Re #5:

    the way to make more expositions and explanations appear is to ask for them. I think whenever you asked here, you got a reply, and usually a detailed reply, as far as I remember. My students often ask me stuff (usually not on this forum here, though) and whenever they do I add an explanation to an nnLab entry somewhere.

    So: what’s the next question you have? :-)

    • CommentRowNumber11.
    • CommentAuthorjim_stasheff
    • CommentTimeOct 9th 2012
    In re: it really needs being seen to be done rather than on web page

    Did you mean dynamically or a still or a small number of stills?

    Happy to see reference to Stallings who used topology to good effect for this and related results.
    • CommentRowNumber12.
    • CommentAuthorjim_stasheff
    • CommentTimeOct 9th 2012
    In re: Stallings
    His work began with Stallings, John R.; SOME TOPOLOGICAL PROOFS AND EXTENSIONS OF GRUSKO'S THEOREM. Thesis (Ph.D.)–Princeton University. 1959. 65 pp, ProQuest LLC
    and continues with many further uses of TOPOLOGICAL PROOFS in group theory.
    • CommentRowNumber13.
    • CommentAuthorTim_Porter
    • CommentTimeOct 9th 2012

    @Jim. There are some proofs that are perhaps better seen been done because of the movement of the hands (not hand waves), the sequence of drawing of diagrams (rather than just a finished diagram) and so on…. almost a bit of theatre!

    • CommentRowNumber14.
    • CommentAuthorTodd_Trimble
    • CommentTimeOct 9th 2012
    • (edited Oct 9th 2012)

    @Urs: I do agree with you that the earlier proof sort of petered out at the end, which is too bad. I think it could have been carried to its completion in the same vein.

    Okay, I didn’t think of what I wrote as being another proof. I thought I was making explicit precisely the proof that was being hinted at in the entry.

    I also agree with you that it’s not essentially a different proof. It was merely a question of pedagogy and getting the underlying topological pictures across. I think your recent revision, with the chat included, helps the pedagogy along, and at this point I might be happy with only a few small changes.

    But if I were writing the entry, I think I might start with a preamble like this. A free group G=F(S)G = F(S) is a fundamental group of a bouquet of SS many circles, which is in particular a connected 1-dimensional CW-complex XX (in simpler language, a connected graph). By general covering space theory, given a (pointed) connected space XX with π 1(X,x)=G\pi_1(X, x) = G, subgroups H⊆GH \subseteq G are in bijective correspondence with isomorphism classes of connected covering spaces p:(E,e)→(X,x)p: (E, e) \to (X, x), where π 1(E)≅H\pi_1(E) \cong H. Now, a covering space EE of a connected graph XX is also a connected graph. But any connected graph is homotopy equivalent to a bouquet of circles, whose fundamental group is a free group. Thus π 1(E)\pi_1(E) is a free group, and we are done.

    Then I would continue by saying that it is possible, with a little groupoid theory, to recast this topological-looking proof into more algebraic language. This would be essentially exactly the proof you gave, but I think I would mention the general action groupoid construction X//GX//G a little earlier, and maybe also include an explanation intended to invoke the right pictures (X//GX//G has an underlying directed graph whose vertices are points of XX and whose edges are labeled by elements of GG, etc.). (One could just send them to the action groupoid page, but my own experience is that having to chase down definitions by moving other pages breaks up one’s concentration.)

    In conclusion, I think what you’ve done is nice – all I’d want to do is insert a little bit more to get the visuals across. If this seems okay, I’d be happy to work on this when I have some more time later today or tonight. Hope I’m not coming across as too harsh.

    • CommentRowNumber15.
    • CommentAuthorUrs
    • CommentTimeOct 9th 2012

    If this seems okay

    Sure!

    • CommentRowNumber16.
    • CommentAuthorTodd_Trimble
    • CommentTimeOct 10th 2012

    I have done some editing at Nielsen-Schreier theorem. Urs, would you mind looking over it critically? I have a slight concern about the last displayed line in the groupoidal proof, and particularly in the arrangement of parentheses in the term inside FF, namely (H\F(S))⫽S(H\backslash F(S)) \sslash S. Do you want this, or do you want H\(F(S)⫽S)H \backslash (F(S) \sslash S)?

    • CommentRowNumber17.
    • CommentAuthorUrs
    • CommentTimeOct 10th 2012
    • (edited Oct 10th 2012)

    Thanks, Todd, that looks good.

    On the other hand, I find the topological argument still incomplete: the key steps a) that a covering space of a graph is a graph and b) that every connected graph is homotopy equivalent to a bouquet of circles are not indicated.

    My original intention when editing the entry had been to fill these gaps (standard as they may be). I think if I were ignorant of what the entry is about, I would find the “Topological proof” as currently stated less illuminating than the “Groupoidal proof”. But I guess I am strange and different. If you all think this way it is nicer to the reader, I won’t object.

    Concerning the question about the notation for the quotients: to me both these expressions are isomorphic. So F(S)⫽SF(S)\sslash S looks as follows:

    F(S)⫽S={ * g 1↙ ↘ g 2=g 1⋅s * →s *g 1,g 2∈F(S),s∈S↪F(S)} F(S) \sslash S = \left\{ \array{ && * \\ & {}^{\mathllap{g_1}}\swarrow && \searrow^{\mathrlap{g_2 = g_1 \cdot s}} \\ * &&\stackrel{s}{\to}&& * } \;\;\; g_1, g_2 \in F(S), s \in S \hookrightarrow F(S) \right\}

    where on the right we see an edge ss going from vertex g 1g_1 to vertex g 2g_2.

    The remaining left F(S)F(S)-action is that given by composing (in *⫽F(S)*\sslash F(S)) “from the top” in this picture. This manifestly commutes with the weak quotient action “on the bottom” so it does not matter which of the two quotients one takes first.

    • CommentRowNumber18.
    • CommentAuthorTodd_Trimble
    • CommentTimeOct 10th 2012

    still incomplete

    I did call it a proof sketch. On the other hand, I find those two key statements intuitively obvious.

    On the other hand: what are you using to justify, “It is then sufficient to observe that this quotient is still a free groupoid on a directed graph to conclude that H is a free group.”? To me, this is understandable intuitively in terms of the second key statement you identified.

    I’m not sure you answered my question about placement of parentheses, involving particularly the subgroup HH.

    • CommentRowNumber19.
    • CommentAuthorUrs
    • CommentTimeOct 10th 2012

    I’m not sure you answered my question about placement of parentheses, involving particularly the subgroup H.

    Maybe I misunderstand. Let’s see: the difference in the placement of the parentheses is that in one case we first take the quotient on the left by HH and then the weak quotient on the right by SS, or the other way round.

    Right?

    So I suggested that both versions are equally good. But maybe we are talking past each other. Or I am mixed up. I admit of being involved in something else at the moment, so I might not be concentrating enough here. Let me know.

    • CommentRowNumber20.
    • CommentAuthorTodd_Trimble
    • CommentTimeOct 10th 2012

    Right?

    Well, I don’t know! :-)

    Maybe my problem is that I’m still not sure I know what you mean by “the action graph” (this is not defined anywhere in the nLab, and I even have trouble finding a clear explanation anywhere on the Internet). I took a guess that the directed graph F(S)⫽SF(S) \sslash S is the infinite SS-ary tree, but that might be totally wrong. Would you mind giving a formal definition? I gather it’s a directed graph. The picture you drew in your last comment makes me afraid I’d gotten it wrong.

    The expression (H\F(S))⫽S(H \backslash F(S)) \sslash S looks like a set of cosets, modulo a set. Off the bat, I wouldn’t know what that means, so I was guessing what you meant. This illustrates what I was saying in #4 about having to digest certain notation.

    • CommentRowNumber21.
    • CommentAuthorUrs
    • CommentTimeOct 10th 2012
    • (edited Oct 11th 2012)

    The word “action graph” I made up, it is meant to be the immediate restriction of the notion of action groupoid along a graph inside a groupoid.

    In #17 I wrote it out. F(S)⫽SF(S)\sslash S is supposed to denote the graph whose vertices are the elements of F(S)F(S) and which has edges g→sg⋅sg \stackrel{s}{\to} g \cdot s for all g∈F(S)g \in F(S) and s∈S↪F(S)s \in S \hookrightarrow F(S).

    Similarly (H\F(S))⫽S(H \backslash F(S)) \sslash S is supposed to denote the graph whose vertices are the elements [g][g] in the left coset with edges [g]→s[g⋅s][g] \stackrel{s}{\to} [g \cdot s] for all [g]∈H\F(S)[g] \in H \backslash F(S) and s∈S↪F(S)s \in S \hookrightarrow F(S).

    • CommentRowNumber22.
    • CommentAuthorTodd_Trimble
    • CommentTimeOct 11th 2012
    • (edited Oct 11th 2012)

    Urs: #17 confused me because your picture has three unlabeled vertices and three edges labeled g 1g_1, g 2g_2, ss – instead of two vertices labeled by g 1g_1, g 2g_2 and one edge labeled ss. (This isn’t nitpicking – this is honest confusion.)

    Anyway, thanks – I think we’re on the same page now. So F(S)⫽SF(S) \sslash S is the Cayley graph of the canonical presentation of F(S)F(S) by generators SS and no relations. And now that you’ve explained (H\F(S))⫽S(H \backslash F(S)) \sslash S, I think I’m clear on that too. (But all of this notation should be explained somewhere in the Lab.)

    I think all I need now is your response to my question

    On the other hand: what are you using to justify, “It is then sufficient to observe that this quotient is still a free groupoid on a directed graph to conclude that H is a free group.”?

    To me, the idea is that the graph (H\F(S))⫽S(H \backslash F(S)) \sslash S is “homotopy equivalent” to a graph with one vertex and a bunch of loops – but I want to hear your explanation.

    • CommentRowNumber23.
    • CommentAuthorUrs
    • CommentTimeOct 11th 2012
    • (edited Oct 11th 2012)

    17 confused me because your picture has three unlabeled vertices and three edges labeled

    Sorry for the picture being confusing, I had tried to say in words right below how to to read it. The picture is the way it is because that’s how the covering space of *⫽F(S)*\sslash F(S) comes out: this covering space is the path space (*⫽F(S)) I(*\sslash F(S))^{I} restricted to one endpoint of paths held fixed, hence the pullback

    EF(S)=*× (*⫽F(S))(*⫽F(S)) I. \mathbf{E}F(S) = * \times_{(*\sslash F(S)) }(*\sslash F(S))^I \,.

    That pullback has as morphisms the triangles in *⫽F(S)*\sslash F(S) as indicated.

    I want to hear your explanation.

    The text points to the proof of that statements at free groupoid – fundamental group!

    • CommentRowNumber24.
    • CommentAuthorTodd_Trimble
    • CommentTimeOct 11th 2012

    The text points to the proof of that statements at free groupoid – fundamental group!

    Thanks. I see that the text points to a reference (which I haven’t looked at yet) which advertises a proof for the case of countable directed graphs.

    That apparent lacuna needs to be addressed before calling the groupoidal proof a complete proof. Do you agree?

    • CommentRowNumber25.
    • CommentAuthorUrs
    • CommentTimeOct 11th 2012

    I need to think about where the countability assumption enters. How do you circumvent it in the topological proof?

    • CommentRowNumber26.
    • CommentAuthorTodd_Trimble
    • CommentTimeOct 11th 2012

    Well, I don’t think there’s actually any problem here at all; I’d have to look at what Cote wrote to see what the issue is she’s concerned about. (Axiom of choice issues? I think it’s true that the Nielsen-Schreier theorem is equivalent to the axiom of choice.)

    What I might do later is copy out or paraphrase the topological proof of NS from A Concise Course in Algebraic Topology (pp. 34-35), which also has the more refined statement regarding ranks of the free groups, to remove any lingering concerns. If all this gets sorted out, we’ll have two nice proofs! :-)

    • CommentRowNumber27.
    • CommentAuthorTim_Porter
    • CommentTimeOct 11th 2012
    • (edited Oct 11th 2012)

    Should the Schreier index formula go here somewhere? it is a nice result and fits either here or in a separate entry. It is useful when explaining identities among relations.

    • CommentRowNumber28.
    • CommentAuthorTodd_Trimble
    • CommentTimeOct 11th 2012

    I edited in several things. I put in a reference to May’s book where full details of the topological proof are given, and I included a brief description of some key technical ingredients in the proof of the topological version, following May. (Partly as brief response to Urs’s #25.) I also included the statement of the index formula in the theorem-statement, and gave a brief description in the topological proof how that is shown.

    If desired, I can write out more of the details somewhere, but that might be superfluous since May’s book is freely available online and is linked to in the article.

    • CommentRowNumber29.
    • CommentAuthorTim_Porter
    • CommentTimeOct 11th 2012

    Thanks.

    • CommentRowNumber30.
    • CommentAuthorUrs
    • CommentTimeOct 11th 2012

    Thanks. (I fixed the link to May’s book, the “http” was missing. Is this something that some recent update of Firefox introduced, to remove the “http” when copy-and-pasting url-s? Because since recently it happens to me all the time, too.)

    Can somebody point me to the precise page where in Higgin’s text the groupoid proof is given? Currently the entry claims that there is a proof there.

    • CommentRowNumber31.
    • CommentAuthorUlrik
    • CommentTimeOct 12th 2012

    Can somebody point me to the precise page where in Higgin’s text the groupoid proof is given? Currently the entry claims that there is a proof there.

    The Nielsen-Schreier Theorem is Theorem 9, which in Chapter 14, on page number 117 (page 133 of the pdf).

    • CommentRowNumber32.
    • CommentAuthorUrs
    • CommentTimeOct 12th 2012

    Thanks, I have moved that information to the entry.

    (My pdf search on Higgins’ document doesn’t work, for some reason…)

    • CommentRowNumber33.
    • CommentAuthorTim_Porter
    • CommentTimeOct 12th 2012

    I think it is a scanned document and so the pages are images not text.

    • CommentRowNumber34.
    • CommentAuthorTodd_Trimble
    • CommentTimeOct 12th 2012

    Getting back to #25 and #26: I took a quick look at the paper by Cote, and have no idea why she restricted attention to the countable case. Nor am I able to determine where she is or how to contact her to ask.

    I hope it is generally agreed by this point that the proofs are very similar indeed. The place where the groupoidal proof ends corresponds to an explicit construction of a covering space projection E→XE \to X between connected graphs, where EE has fundamental group HH. To show that the free groupoid on a connected directed graph is equivalent to a free group, presumably one does something similar to what is indicated in the topological proof (modding out by a maximal tree in the graph to get a bouquet of circles).

    • CommentRowNumber35.
    • CommentAuthorUrs
    • CommentTimeOct 12th 2012
    • (edited Oct 12th 2012)

    The proofs better be the same, that’s the content of the homotopy hypothesis! :-)

    What I still don’t see is what its buys us to fatten the combinatorial structure to a topological spayes, in the case at hand. It seems superfluous to me. Of course one can do it. Every invariant statement about groupoids is equivalently a statement about topological spaces that are homotopy 1-types.

    Here it seems to me we are naturally talking about combinatorial graphs. Of cours I can say “think of the free groupoid it generates as a topological space”. But I can also not say this. Nothing changes.

    • CommentRowNumber36.
    • CommentAuthorTodd_Trimble
    • CommentTimeOct 12th 2012

    I think I’m done with this. We agree both proofs are about homotopy 1-types. Arguing further about which is ’better’ is not a productive use of time, or not of my time anyway.

    • CommentRowNumber37.
    • CommentAuthorTom Leinster
    • CommentTimeOct 13th 2012
    • (edited Oct 13th 2012)

    @Urs (30): yes, I think that is a recent-ish Firefox “innovation”. But somehow the “http://” is there invisibly. E.g. in the address box I see now, the address starts with “nforum”. But if I copy and paste the address into a text editor, it begins with “http://nforum”. It’s as if the “http://” really is there in the address bar, but in a typeface too tiny to read.

    Although I don’t really like this change, it hasn’t given me any trouble, personally. I copy and paste URLs quite a lot, and the regaining of the http:// seems to work every time for me.

    • CommentRowNumber38.
    • CommentAuthorUrs
    • CommentTimeOct 22nd 2012
    • (edited Oct 22nd 2012)

    I made explicit at Nielsen-Schreier theorem statement and proof of the corollary (“Dedekind’s theorem”, I guess) that every subgroup of a free abelian group is itself free abelian. (The proof is below the two proofs of the main theorem. Of course it’s immediate, but I want to record it nevertheless.)

    • CommentRowNumber39.
    • CommentAuthorTodd_Trimble
    • CommentTimeOct 22nd 2012

    Sorry, I’m not following the proof. Why is it obvious that HH is the abelianization of p −1(H)p^{-1}(H)?

    • CommentRowNumber40.
    • CommentAuthorUrs
    • CommentTimeOct 22nd 2012

    Thanks, Todd. Right, I guess I made a mistake here. Let me think…

    • CommentRowNumber41.
    • CommentAuthorTodd_Trimble
    • CommentTimeOct 22nd 2012

    Actually, in case it saves you trouble, I am currently writing a proof at principal ideal domain that a submodule of a free module over a pid is itself free. This is Theorem 1 in a section on the structure theory of modules over a pid.

    • CommentRowNumber42.
    • CommentAuthorUrs
    • CommentTimeOct 22nd 2012

    Thanks!

1 to 42 of 42

  1.