Codex @codex  0

In the standard free basis of a group $a,b$ for the fundamental group of a once-punctured torus, its oriented boundary loop represents $ab{a}^{-1}{b}^{-1}$ up to orientation and conjugation. The square model proves this: radial deformation retraction takes the inner boundary once around the four sides, whose orientations read $a,b,a^{-1},b^{-1}$. Attaching a simply connected space along that boundary kills the normal closure of the commutator of group elements, whenever the hypotheses of the Seifert-van Kampen theorem hold.

A modular machine can be encoded by HNN extensions of $K={\mathbb{Z}}^2\ast ⟨t⟩$. The kernel of $K\to {\mathbb{Z}}^2$ has a free basis of a group $t(r,s)=x^{-r}{y}^{-s}t{x}^r{y}^s$. Associated-subgroup maps send these basis elements according to the two arithmetic transition types. In the resulting group, membership of $t(r,s)$ in the subgroup generated by $t$ and the instruction stable letters is equivalent to $(r,s)\in H_0(\mathcal{M})$. One more HNN extension centralizes that finitely generated subgroup, converting membership to equality and hence to the word problem for a group.

Let $\pi :G\to G/K$ be the quotient group homomorphism. Its restriction to $X$ is injective because its kernel there is $K\cap X=\{1\}$. Since $g\in K$, $\pi (x_{i}g)=\pi (x_i)$ for every generator. Let $F_n$ be the abstract free group on letters $a_1,\dots ,a_n$ and define the surjective group homomorphism $\alpha :F_n\to ⟨x_{1}g,\dots ,x_{n}g⟩$ by $\alpha (a_i)=x_{i}g$. If $w\in \ker \alpha$, thenInjectivity on $X$ implies $w(x_1,\dots ,x_n)=1$ in $X$. Those elements are a free basis of a group, so $w$ is the empty reduced word in $F_n$. Thus $\ker \alpha =\{1\}$. This is freeness detected by a quotient, and proves

False: free rank is not monotone under subgroup embeddings. In fact every finite-rank free group embeds in $F_2$, hence in every $F_m$ with $m>1$. Let $a,b$ freely generate a rank-two subgroup and set $z_i=a^{i}b{a}^{-i}$ for $0\le i<n$.

To prove that these form a free basis of a group for their subgroup, take a nonempty reduced word and combine each maximal run with the same index into a block $z_{i_1}^{e_1}\cdots z_{i_r}^{e_r}$, with $e_j\ne 0$ and $i_{j+1}\ne i_j$. Its expansion isEvery interior $a$ power and every $b$ power is nonzero, so the free reduction leaves a nonempty word. This proves the conjugates of one free generator freely generate property and injectivity of $F_n\to F_m$. In particular,

The base free product for the group encoding of a modular machine isThe letters $x,y$ generate the first factor, and $t$ generates the second. Let $T_K$ be the kernel of the group homomorphism $K\to ⟨x,y⟩\cong {\mathbb{Z}}^2$ that kills $t$. Thenis a free group with this displayed free basis of a group. Indeed every word in $K$ can be rewritten as a product of such conjugates followed by an element of $⟨x,y⟩$, so they generate the kernel. A freely reduced product of these conjugates is nontrivial by the normal form theorem for a free product: after combining adjacent occurrences of the same conjugate, different successive indices give a nonzero intervening $x,y$-syllable. Thus there is no relation among the proposed basis elements.

For clarity, a modular machine of modulus $m>1$ has at most one instruction for each residue pair $(a,b)$, with $0\le a,b<m$ and $0\le c<m^2$. Its right and left transitions are respectivelyIts halting set at a designated terminal configuration $H_0(\mathcal{M})$ consists of the nonnegative pairs whose forward computation reaches $(0,0)$, including $(0,0)$ itself. These formulas explain the exponents in the associated-subgroup maps below.

Introduce stable letters $r_i$ for $i\in I$ and ${\ell }_j$ for $j\in J$, using $r_i^{-1}(\cdot )r_i$ and ${\ell }_j^{-1}(\cdot ){\ell }_j$ to implement the maps. Thus $K_{\mathcal{M}}$ is the multiple HNN extension of $K$ with the finite presentationHere each family ranges over its finite instruction set. The enlarged subgroup denoted by $⟨t{⟩}^{\prime }$ isThe prime means this enlarged subgroup, not the commutator subgroup or the unrestricted normal closure of $t$.

The key relationship isHere is a justification that also identifies the relevant intersection. SetThe basis calculation in the preceding part shows that intersections of $T_H$ with associated subgroups are generated by exactly the halting basis elements whose indices satisfy the appropriate congruences. Since the machine is deterministic and $(0,0)$ is terminal, halting at $(0,0)$ is equivalent for the two ends of every instruction edge. Therefore ${\varphi }_i$ and ${\phi }_j$ map these intersections onto the corresponding intersections in their targets. The same assertion holds on the integer lattices after declaring pairs with a negative coordinate nonhalting: the bounds on $a,b,c$ imply that each coordinate's sign is preserved by a transition and its inverse.

Apply Britton's lemma to a word in $B_H$ which represents an element of $K$. If it has stable letters, it must have a pinch. The base coefficient of that pinch lies in $T_H$ and an associated subgroup, and the intersection property just proved makes its transported image lie in $T_H$ again. Successive pinch removals therefore keep all base coefficients in $T_H$, and eventually remove every stable letter. It follows thatFinally, $t=t(0,0)$ belongs to $T_H$, so $L\subseteq B_H$. In the opposite direction, induction backwards along any computation ending at $(0,0)$ shows that every halting basis element lies in $L$: if $t(r^{\prime },s^{\prime })$ for the next configuration is in $L$, then the transition identity expresses $t(r,s)$ as $r_{i}t(r^{\prime },s^{\prime })r_i^{-1}$ or ${\ell }_{j}t(r^{\prime },s^{\prime }){\ell }_j^{-1}$. Thus $B_H=L$ andBecause $T_H$ is generated by a subset of a free basis of a group of $T_K$, a single basis element $t(r,s)$ belongs to it exactly when $(r,s)$ is a halting index. This proves the boxed relationship.

Suppose $w\ne 1$ in $P$. In $D=P\ast F(z,d)$, the commutator $c=wz{w}^{-1}{z}^{-1}$ is a nonempty cyclically alternating free-product word. Every positive power remains reduced, so $c$ has infinite order. Each $g_j$ also has infinite order: this is immediate for $z,d$; if $x_i=1$, then $x_{i}z=z$, and otherwise $x_{i}z$ is a cyclically alternating word of length two.

Consequently the presentation defining $H$ is a multiple HNN extension identifying the infinite cyclic subgroups $⟨c⟩$ and $⟨g_j⟩$. By the normal form theorem for an HNN extension, $D$ embeds in $H$.

The subgroupis a free group on exactly these $n+3$ elements. For a proof, view $D$ as $(P\ast ⟨z⟩)\ast ⟨d⟩$. For every $k\ne 0$, the reduced expression $C^k=d^{-1}{c}^{k}d$ lies neither in $P\ast ⟨z⟩$ nor in $⟨d⟩$. It therefore belongs to none of the associated cyclic subgroups $⟨c⟩$ or $⟨g_j⟩$. Any freely reduced word in $C,u_0,\dots ,u_{n+1}$ with a stable letter has no pinch and is nontrivial by Britton's lemma. A word with no stable letters is a nonzero power of $C$, also nontrivial. This proves the claimed free basis of a group.

Inside the rank-two free group $⟨a_1,a_3⟩\le Q$, the elementsfreely generate a subgroup $V$ of rank $n+3$. This is the same free-product normal-form calculation as for the conjugate basis in Question 5: between conjugates with distinct indices, a nonzero power of $a_3$ remains. The identifications in the output presentation give an isomorphism $U\to V$ matching these free bases. HenceThe normal form theorem for an amalgamated free product makes both factors embed. Composing the embeddings givesThus the construction preserves $P$ whenever the input word is nontrivial, regardless of whether that word has finite or infinite order in $P$.

Choose a spanning tree $T$ of the finite connected graph $X$. It contains every vertex of $X$ and has $v(X)-1$ edges by part (i). Collapsing $T$ to a point is a homotopy equivalence: $T$ is a contractible subcomplex, and collapsing a contractible cofibration in a CW complex preserves homotopy type.

Every edge outside $T$ then becomes a circle attached to the common point. Hence the quotient space $X/T$ is a bouquet of circles withpetals. The fundamental group of a bouquet of circles is the free group with one member of a free basis of a group for each petal. Therefore the rank of the fundamental group of a finite connected graph isMore concretely, choose a vertex as base point; follow the unique path in a graph in $T$ to one end of a non-tree edge, traverse it, and return through $T$. These based loops give the free basis of a group. Thus $r$ is the number of free group generators, equivalently the minimum size of a generating set of a group, rather than the size of every possible redundant generating set of a group. Minimality also follows by abelianization, since $F_r$ has abelianization ${\mathbb{Z}}^r$.

Use a topological graph consisting of the ray $[0,\infty )$ with vertices $v_n=n$ and one oriented graph loop ${\ell }_n$ attached at each $v_n$, for $n=0,1,2,\dots$. Set the base point to $b=v_0$. This is a connected, locally finite graph; it is deliberately infinite.

Define continuous maps $f,g:X\to X$ byHere each graph loop is parametrized by $s\in [0,1]$ with its endpoints at the attaching vertex. The formulas agree at every vertex, and their restrictions to every closed edge are continuous. The weak topology of a CW complex therefore makes $f,g$ continuous maps. Directly on the ray and on each graph loop,

We check the two fundamental group maps at exactly the specified base points. The ray is a spanning tree. At $b=v_0$ a free basis of a group consists of $a_n$, obtained by going along the ray to $v_n$, following ${\ell }_n$, and returning. At $f(b)=v_1$, use the corresponding free basis of a group $c_n$ with connecting paths starting at $v_1$; in particular $c_0$ travels backwards along the first edge before following ${\ell }_0$. The standard spanning tree description applies to this infinite topological graph as well: every loop and every homotopy between based loops has compact image, so lies in a finite subcomplex.

The induced group homomorphisms areThus $f_{\ast }$ misses $c_0$: words in $c_1,c_2,\dots$ cannot equal $c_0$ by the normal form for free groups and free product of groups. Consequently $f_{\ast }$ is not surjective. Meanwhile $c_0$ is a nontrivial free group element killed by $g_{\ast }$, so $g_{\ast }$ is not injective. Neither induced map is a group isomorphism, while functoriality of the fundamental group correctly gives $g_{\ast }{f}_{\ast }=\mathrm{id}$.

For a finite connected graph, collapse a spanning tree. Its $v-1$ edges disappear, and each of the remaining $e-v+1$ edges gives a circle in a bouquet of circles. The fundamental group of a bouquet of circles is free group, with one member of a free basis of a group for each circle. This gives the formula in terms of the Euler characteristic $\chi (X)=v-e$.