Want to take part in these discussions? Sign in if you have an account, or apply for one below
Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.
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.
I also edited the References at Nielsen-Schreier theorem a bit.
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 \hookrightarrow F(S)$ of a free group $F(S)$ on a set $S$ is itself free on some set.
Proof. Let $\mathbf{E} F(S) \coloneqq F(S)\sslash F(S)$ be the action groupoid of $F(S)$ acting on itself. This is contractible, $\mathbf{E}F(S) \simeq *$, and comes with a canonical $F(S)$-action (from the other side). Hence it comes with an induced $H$-action and the quotient $H \backslash \backslash\mathbf{E}F(S) \simeq H \backslash \backslash *$ is the conneced groupoid with $\pi_1 = H$. So it is sufficient to show that $H \backslash \backslash\mathbf{E}F(S)$ is isomorphic to the free groupoid on a connected graph. But $\mathbf{E}F(S)$ itself is the free groupoid on a connected graph, namely on the action graph $F(S)\sslash S$. So
$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.
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.
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!
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!
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.
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.
I used to illustrate the proof with an example of a figure eight and then looked at a Cayley graph of $S3$ 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’! :-)
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 $n$Lab entry somewhere.
So: what’s the next question you have? :-)
@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!
@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)$ is a fundamental group of a bouquet of $S$ many circles, which is in particular a connected 1-dimensional CW-complex $X$ (in simpler language, a connected graph). By general covering space theory, given a (pointed) connected space $X$ with $\pi_1(X, x) = G$, subgroups $H \subseteq G$ are in bijective correspondence with isomorphism classes of connected covering spaces $p: (E, e) \to (X, x)$, where $\pi_1(E) \cong H$. Now, a covering space $E$ of a connected graph $X$ 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 $\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//G$ a little earlier, and maybe also include an explanation intended to invoke the right pictures ($X//G$ has an underlying directed graph whose vertices are points of $X$ and whose edges are labeled by elements of $G$, 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.
If this seems okay
Sure!
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 $F$, namely $(H\backslash F(S)) \sslash S$. Do you want this, or do you want $H \backslash (F(S) \sslash S)$?
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)\sslash S$ looks as follows:
$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 $s$ going from vertex $g_1$ to vertex $g_2$.
The remaining left $F(S)$-action is that given by composing (in $*\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.
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 $H$.
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 $H$ and then the weak quotient on the right by $S$, 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.
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) \sslash S$ is the infinite $S$-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 \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.
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)\sslash S$ is supposed to denote the graph whose vertices are the elements of $F(S)$ and which has edges $g \stackrel{s}{\to} g \cdot s$ for all $g \in F(S)$ and $s \in S \hookrightarrow F(S)$.
Similarly $(H \backslash F(S)) \sslash S$ is supposed to denote the graph whose vertices are the elements $[g]$ in the left coset with edges $[g] \stackrel{s}{\to} [g \cdot s]$ for all $[g] \in H \backslash F(S)$ and $s \in S \hookrightarrow F(S)$.
Urs: #17 confused me because your picture has three unlabeled vertices and three edges labeled $g_1$, $g_2$, $s$ – instead of two vertices labeled by $g_1$, $g_2$ and one edge labeled $s$. (This isn’t nitpicking – this is honest confusion.)
Anyway, thanks – I think we’re on the same page now. So $F(S) \sslash S$ is the Cayley graph of the canonical presentation of $F(S)$ by generators $S$ and no relations. And now that you’ve explained $(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 \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.
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 $*\sslash F(S)$ comes out: this covering space is the path space $(*\sslash F(S))^{I}$ restricted to one endpoint of paths held fixed, hence the pullback
$\mathbf{E}F(S) = * \times_{(*\sslash F(S)) }(*\sslash F(S))^I \,.$That pullback has as morphisms the triangles in $*\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!
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?
I need to think about where the countability assumption enters. How do you circumvent it in the topological proof?
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! :-)
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.
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.
Thanks.
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.
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).
Thanks, I have moved that information to the entry.
(My pdf search on Higgins’ document doesn’t work, for some reason…)
I think it is a scanned document and so the pages are images not text.
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 \to X$ between connected graphs, where $E$ has fundamental group $H$. 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).
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.
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.
@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.
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.)
Sorry, I’m not following the proof. Why is it obvious that $H$ is the abelianization of $p^{-1}(H)$?
Thanks, Todd. Right, I guess I made a mistake here. Let me think…
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.
Thanks!
1 to 42 of 42