% interface=en output=pdftex %\environment capcalera.context % Capçalera % Regime \enableregime[utf] % Choose a font \setupbodyfont [cmr,11pt] % cmr, 11pt % Be tolerant with paragraph building \setuptolerance [horizontal,verytolerant,stretch] % Choose a language, and associated hyphenation rules. %\language [ca] \mainlanguage[ca] % Page number \setuppagenumbering [location={footer}] % White space between paragraphs %\setupwhitespace [big] % Paper size \setuppapersize [a4] % Margins %\setuplayout [grid=yes, footer=0.5\footerheight, header=0.5\headerheight] %\setuplayout[footer=2cm, header=2cm] %\showlayout %\showframe %\showsetups % Format de marges %\setuplayout[topspace=1.5cm, % marge d'adalt %margin=1.5cm, %marges dels costats %header=1.0cm,%separació entre adalt i primera línia %footer=1.0cm,%separació entre abaix i darrera línia %width=fit,height=fit,backspace=2cm] % Enable colors and activate hyperlinks \setupcolors [state=start] \definecolor[lightblue][r=0.5, g=0.5, b=1.0] %\setupinteraction [state=start, color=lightBlue] %\setupurl[style=small, space=yes] \setupurl[space=yes] % Enumerate the URLs %\useURL[wiki][http://wiki.contextgarden.net][][\ConTeXt\ wiki] %\useURL[nagorko-pdf][http://www.math.bgu.ac.il/~barakw/probseminar/nagorko/slides.pdf][][http://www.math.bgu.ac.il/\~{}barakw/\quad\quad\quad\quad probseminar/nagorko/slides.pdf] %\useURL[govern-me][http://sgtrelinst.caib.es/llibrestil/00index.html][][http://sgtrelinst.caib.es/llibrestil/00index.html] %\useURL[context-manual-pdf][http://www.pragma-ade.com/general/manuals/cont-eni.pdf][][http://www.pragma-ade.com/general/manuals/ cont-eni.pdf] %\useURL [contextgarden] [{http://www.contextgarden.net}] %\useURL [mccammond][{http://www.math.ucsb.edu/~jon.mccammond/geogrouptheory/}][] [{\tf http://www.math.ucsb.edu/\~{}jon.mccammond/geogrouptheory/}] % Fonts %% Chapters... \setupheads[align=flushleft] \setuphead[chapter][style={\tfd\bf}] \setuphead[section][style={\bfc}, header=nomarking] \setuphead[subsection][style={\bfb}] \setuphead[subsubsection][style={\bfa}] %\setuphead[section][textstyle=bold] % Bibliography options % BIBTEX \usemodule[bib] \usemodule[bibltx] \setupbibtex[database=memoria,sort=author] \setuppublications [alternative=ams,numbering=yes, sorttype=bbl, criterium=cite]% \setupheadtext[ca][pubs=Referències] \setuppublicationlist[authoretallimit=3] \setuppublicationlist[authoretaltext={\it\ et al.}] \setuppublicationlist[authoretaldisplay=1] %Indentation \setupheads[indentnext=yes] \setupindenting[yes,small,first] %\setupformulae[indentnext=yes] % Vertical spaces between paragraphs \setupwhitespace[small] %Itemize \setupitemize[each][indentnext=no,margin=2em] % [identnext=yes,margin=2em] \setupitemize[each][headstyle=bold] %\setupitemize[a][right=),stopper=] % Mathematical packets \usemodule[newmat] \usemodule[math-ams] % Heads and footers %\setupfootertexts[][{\tfx \currentdate}] %\setupfootertexts[\pagenumber/\lastpage] %\setupfooter[text][before=\hrule] %\setupheader[text][after=\hrule] %\setupheadertexts[{\tfx Màster de Matemàtiques}][{\tfx \jobname.\ConTeXt{}.\currentdate}] %\setupheadertexts[][{\tfx \currentdate}] % hyphenating \hyphenation{do-cu-ment} \hyphenation{pro-ble-ma} \hyphenation{es-crip-tu-ra} \hyphenation{ge-ne-ra-lit-za-ció} \hyphenation{cor-res-po-nents} \hyphenation{pa-rells} \hyphenation{ge-ne-rat} % Modules \usemodule[tikz] \usemodule[pgfmath] \usetikzlibrary[mindmap,arrows,calc,decorations.pathmorphing,decorations.markings] %\usetikzlibrary[trees] % AMSTHM equivalent %% Exercici \defineenumeration [exercici] [text={Problema},headstyle=bold,between=\blank,titledistance=0em,textdistance=1em, stopper={.\space},location=serried,left={\bgroup\bf},right={\egroup},width=fit,before={\bgroup\startframedtext[background=screen,frame=off,width=broad]},after={\stopframedtext\egroup}] %% Lema \defineenumeration [lema] [text={Lema}, % Què es mostra before={\blank[big]}, % abans de lema, un bigskip after={\blank[big]}, % després de lema, un bigskip headstyle=bold, % Negreta per la capçaleras %between=\blank, % Entre Lemmes una línia en blanc titledistance=.5em, % espai entre número i parèntesis. textdistance=.5em, % espai entre ) i text stopper={.\space}, % Com acaba. Després de parèntesis un '.' location=serried, width=fit, % que ocupi tot l'espai style=italic, % estil del text title=yes, % si puc posar o no arguments opcionals titlestyle=bf, % estil del títol way=bytext, % enumerar en tot el document conversion=numbers,indenting=yes] % enumera amb arabic %% Proposició, corol·laris, teoremes. %% Comparteix els nombres amb lema %% Si volem que vagin a part, hem de posar 'number=proposition' \defineenumeration [proposition] [lema] [text={Proposició}] \defineenumeration [corollary] [lema] [text={Corol·lari}] \defineenumeration [theorem] [lema] [text={Teorema}] %% Definició \defineenumeration [definition] [lema] [text={Definició},style=tf,titlestyle=bf,indenting=yes] \defineenumeration [notation] [definition] [text={Notació},style=tf,titlestyle=bf,indenting=yes] \defineenumeration [note] [definition] [text={Nota},style=tf,titlestyle=bf,indenting=yes] %% Demostració \defineenumeration[demo][text={Demostració.\space},number=no,location=serried,width=fit,headstyle=italic,indentnext=yes,between=\blank,textdistance=.5em,closesymbol={\mathematics{\Box}},style=normal,indenting=yes] % Table of contents %% dots between... and subsubsubsection are not listed \setupcombinedlist[content][level=4,alternative=c] %% section = bold. % width= 10mm --> less space between num-letter %% line break after section. \setuplist[section][style=bold,width=10mm] \setuplist[section][before=\blank] %% margin = 10 mm. Put the subsection just bottom section. \setuplist[subsection][margin=10mm,width=10mm] \setuplist[subsubsection][margin=20mm,width=10mm] %\setuplist[subsection] %[distance=1em] % section = bold. % % Això ho trec d'un manual: %\setuplist[subsection] % [margin=1em, % numbercommand=\NumCom] %\def\NumCom#1{\hbox to 2em{\hfill #1}} % Set "Índex" like "Índex de continguts" \setupheadtext [ca] [content=Índex] % Definitions/abbreviations \define[1]\dist{d(\sigma_g(#1), \sigma_h(#1))} \define[1]\imp{{\bgroup\startframedtext[background=screen,frame=on,width=broad]#1\stopframedtext\egroup}} %\define[1]\imp{{\bgroup\startframedtext[background=color,backgroundcolor=lightblue,frame=on,width=broad]#1\stopframedtext\egroup}} % SPLIT \def\startsplit {\startalign} % no number by default \def\stopsplit {&\doalignNR[+][]\crcr % for a number on last line \stopalign} % Other \setupunderbar[alternative=b] % Fix underline style % For putting underline with spaces: \underbar{\dorecurse{40}~} % Define new register for the Index of Symbols \defineregister[symbol][symbols] % Start the text \starttext \version[concept] \subsubsubject{Paraules sobre un alfabet} En aquest apartat farem memòria de la definició de paraula (sobre un alfabet) i introduirem certes notacions i operacions estàndards que farem servir posteriorment. Recordem que un {\em alfabet}\index{alfabet} és un conjunt qualsevol de símbols, els quals anomenarem {\em lletres}\index{lletres}. Si $A$ és un alfabet, aleshores una {\em paraula $w$ sobre $A$}\index{paraula} és una successió finita de lletres de $A$, que escriurem com $w = w_1 \ldots w_k$. Indicarem amb $\varepsilon$ la paraula que no té cap lletra, la qual anomenarem {\em paraula buida}\index{paraula+buida}. Quan $w$ consti de dues o més lletres iguals consecutives, per comoditat, podrem agrupar-les usant la notació multiplicativa. Per exemple si $A = \{a,b\}$, aleshores $ab^3a^2b$ denotarà la paraula $abbbaab$. La {\em concatenació}\index{concatenació de paraules} de dues paraules $w_1$, $w_2$ sobre $A$, que indicarem amb $w_1 \cdot w_2$, és la juxtaposició de $w_1$ i $w_2$, és a dir, si $w_1 = a_1 \ldots a_k$ i $w_2 = b_1 \ldots b_s$, aleshores \startformula w_1 \cdot w_2 = a_1 \ldots a_k b_1 \ldots b_s, \stopformula amb la convenció que $w_1 \cdot \varepsilon = \varepsilon \cdot w_1 = w_1$. Sovint ometrem el símbol $\cdot$ i escriurem $u v$ per denotar $u \cdot v$. Si $w$ és una paraula sobre $A$, aleshores $l(w)$\symbol{$l(w)$} denotarà la seva {\em longitud}\index{longitud+d'una paraula}, és a dir, el seu nombre de símbols. De forma clara, $l(u \cdot v) = l(u) + l(v)$, per a qualssevol paraules $u, v$ sobre $A$. D'altra banda, indicarem amb $w(t)$ el {\em prefix de $w$ de longitud $t$}\index{paraula+prefix de longitud $t$,}. Formalment, si $w = \varepsilon$, $w(t) = \varepsilon$ i si $w = w_1 \ldots w_k$, aleshores $w(t) = w_1 \ldots w_t$. Per últim, indicarem amb $A^*$ el {\em monoide lliure sobre $A$}\index{monoide lliure}, és a dir, el conjunt de totes les paraules sobre $A$. \subsubsubject{Grups lliures} En aquesta secció construirem el {\em grup lliure} de base $X$ un conjunt qualsevol i descriurem algunes de les seves propietats a mode de teoremes. Donat $X$ un conjunt qualsevol, agafem un conjunt d'inverses formals de $X$, que indicarem amb $X^{-1}$, format per símbols $x^{-1}$ per a cada $x \in X$. Formalment, $X^{-1}$ és un conjunt del mateix cardinal que $X$ juntament amb una funció bijectiva ${}^{-1} \colon X \to X^{-1}$, de manera que, per a tot $x \in X$, la imatge de $x$ per ${}^{-1}$ s'escriu $x^{-1}$. Amb aquests conjunts podem formar el monoide lliure ${(X \cup X^{-1})}^*$ els elements del qual són llistes finites d'elements de $X$ i de les seves inverses formals. Enfatitzem que els elements de $X^{-1}$ són inverses formals: si $X = \{a, b\}$, aleshores $b$, $aba^{-1}$, $ab$ i $aba^{-1}a$ són elements diferents en el monoide lliure ${(X \cup X^{-1})}^*$. Afegirem dues convencions: abusant del llenguatge, si $a \in X^{-1}$ i $a = x^{-1}$ per a algun $x \in X$, aleshores $a^{-1}$ denotarà $x$, o sigui, de manera informal, el que feim és fer involutiva la funció ${}^{-1}$. D'altra banda, estendrem les inverses formals a les paraules. Per a la paraula buida definim $\varepsilon^{-1} = \varepsilon$, i si \startformula w=x_1 x_2 \ldots x_{k-1}x_k \in {(X \cup X^{-1})}^*, \stopformula aleshores $w^{-1}$ indicarà la paraula \startformula w^{-1} = x_k^{-1}x_{k-1}^{-1}\ldots x_2^{-1} x_1^{-1} \in {(X \cup X^{-1})}^*. \stopformula En poques paraules, amb aquestes convencions, hem aconseguit que ${}^{-1}$ sigui un morfisme en ${(X \cup X^{-1})}^*$ respecte de la concatenació de paraules. Sobre ${(X \cup X^{-1})}^*$ definim la relació $\sim$ definida de la manera següent: dues paraules $u$, $v$ són equivalents, i.e., $u \sim v$, si, i només si, podem passar d'una a l'altra amb un nombre finit de passes del tipus següent: \startitemize[n] \item Reducció: l'eliminació d'una ocurrència de $xx^{-1}$, per a qualque $x \in X\cup X^{-1}$. \item Amplificació: l'afegit d'una ocurrència de $xx^{-1}$, per a qualque $x \in X \cup X^{-1}$. \stopitemize És clar que $\sim$ és una relació d'equivalència. A més, preserva l'estructura de ${(X \cup X^{-1})}^*$: si $u_1 \sim u_2$ i $v_1 \sim v_2$, aleshores $u_1 \cdot v_1 \sim u_2 \cdot v_2$ i $u_1^{-1} \sim u_2^{-1}$. Per tot això, es pot veure fàcilment que ${(X \cup X^{-1})}^*/\sim$ és un grup (l'element neutre és $[\varepsilon]_\sim$ i la inversa de $[w]_\sim$ és $[w^{-1}]_\sim$). Anomenarem a aquest grup el {\em grup lliure de base $X$}\index{grup+lliure}, i l'indicarem amb $F(X)$\symbol{$F(X)$}. Si $X$ té només un sol element, aleshores $F(X) \cong \integers$, el qual és l'únic grup lliure abelià no trivial. Si $X = \emptyset$, aleshores $F(X) \cong \{1\}$. Una paraula sobre $X \cup X^{-1}$ és {\em reduïda}\index{paraula+reduïda} si no conté cap ocurrència de la forma $xx^{-1}$, amb $x \in X \cup X^{-1}$. Qualsevol paraula que només conté una lletra i $aba^{-1}$ són paraules reduïdes. La paraula buida també és reduïda. En canvi $abb^{-1}b$ i $aba^{-1}abb^{-1}a^{-1}$ no són paraules reduïdes. Donada una paraula $w \in {(X \cup X^{-1})}^*$, existeix una paraula reduïda $u$ tal que $w \sim u$, obtinguda aplicant un nombre finit de passes de reducció \cite[extras={, Lema~6.1}][grillet], la qual indicarem amb $red(w)$\symbol{$red(w)$}. A més, aquesta paraula és única, o sigui, no existeix cap altra paraula reduïda dins la classe d'equivalència de $w$ \cite[right={; }, extras={, Lema~6.4}][grillet]\cite[left=,extras={, Teorema~2.1.2}][robinson]. Això fa que el grup lliure $F(X)$ sigui isomorf al grup format pel conjunt de paraules reduïdes sobre $X \cup X^{-1}$ amb l'operació binària consistent en la concatenació de dues paraules reduïdes seguida de la reducció (per exemple, l'aplicació que envia cada paraula reduïda $u$ a la classe d'equivalència $[u]_\sim$ és un isomorfisme entre aquests grups). Estrictament parlant $X$ no està inclòs dins $F(X)$, ara bé, tenim la inclusió natural $\eta$ de $X$ en $F(X)$ tal que $\eta(x) = [x]_\sim$, per a tot $x \in X$. A més, aquesta inclusió es pot estendre per a $X^{-1}$ de la forma $\eta(x^{-1}) = [x^{-1}]_\sim$, per a tot $x \in X$. Per construcció de $F(X)$, això fa que tot element de $F(X)$ es pugui posar com a producte de elements de $\eta(X)$ i els seus inversos, la qual cosa implica el resultat següent: \starttheorem{\cite[right={; }, extras={, Proposició~6.6}][grillet]\cite[left=,extras={, Proposició~1.6}][cgt]}El grup lliure $F(X)$ està generat per $\eta(X)$. \stoptheorem Una propietat molt important que compleix el grup lliure, la qual el caracteritza, és la {\em propietat universal}\index{propietat universal}, que podem enunciar com el resultat següent: \starttheorem{\cite[extras={, Teorema~6.7}][grillet]} Sigui $\eta \colon X \to F(X)$ la inclusió natural. Per a tota funció $f$ de $X$ a un grup qualsevol $G$, existeix un únic morfisme $\nu \colon F(X) \to G$ tal que $\nu \circ \eta = f$. \stoptheorem \startcorollary[thme:gruplliure-imatge]{\cite[grillet, robinson]} Sigui $G$ un grup generat per un conjunt $X$. Aleshores existeix un homomorfisme exhaustiu de $F(X)$ a $G$, o sigui, tot grup és imatge del grup lliure per a qualque homomorfisme. \stopcorollary Altres propietats interessants del grup lliure són les seguents: \starttheorem{\cite[extras={, Teorema~2.1.3}][robinson]} Sigui $G$ un grup i $X$ un subconjunt de $G$. Si tot element $g$ de $G$ es pot escriure de forma única com a $g = x_1^{l_1} \ldots x_r^{l_r}$ amb $r \geq 0$, $x_i \in X$, $l_i \in \integers$ tals que $l_i \neq 0$ i $x_i \neq x_{i+1}$, per a tot $i \in \{0, \ldots, r\}$, aleshores $G$ és lliure de base $X$. \stoptheorem \starttheorem{\cite[extras={, Proposició~1.9}][cgt]} Sigui $X$ un subconjunt de $G$ tal que $X \cap X^{-1} = \emptyset$. Aleshores $X$ és una base d'un subgrup lliure de $G$ si, i només so, no hi ha cap producte de la forma $x_1 \ldots x_r$ que sigui trivial, amb $r \geq 1$, $x_i \in X \cup X^{-1}$ i $x_i \neq x_{i+1}^{-1}$, on $i \in \{0, \ldots, r\}$. \stoptheorem \starttheorem{\cite[robinson,cgt]}Siguin $X$, $Y$ conjunts qualssevol. Aleshores $F(X) \cong F(Y)$ si, i només si, $\lvert X \rvert = \lvert Y \rvert$. \stoptheorem Aquest darrer teorema permet definir el {\em rang d'un grup lliure}\index{grup+lliure+rang,} com el cardinal de qualsevol de les seves bases. En aquest sentit, indicarem amb $F_n$\symbol{$F_n$} el {\em grup lliure de rang $n$}. Per últim, introduirem notació. Si $w$ és una paraula sobre $X \cup X^{-1}$, la {\em longitud reduïda} de $w$\index{longitud+reduïda d'una paraula}, que indicarem amb $\lvert w \rvert$\symbol{$\lvert w \rvert$}, és la longitud de la paraula reduïda de $w$, és a dir, $l(red(w))$. De forma òbvia tenim que, per a totes paraules $u, v$ sobre $X \cup X^{-1}$, $\lvert uv \rvert \leq \lvert u \rvert + \lvert v \rvert$. D'altra banda, si $v, w \in {(X \cup X^{-1})}^*$, aleshores direm que $v$ i $w$ són {\em iguals dins el grup lliure $F(X)$}\index{paraules+iguals dins el grup lliure} si $red(v) = red(w)$ o, equivalentment, si $[v]_\sim = [w]_\sim \in F(X)$. \subsubsubject{Presentacions de grups} Una presentació d'un grup és una generalització del concepte de taula de productes d'un grup. Donat un grup $G$, la seva taula de valors proporciona informació sobre el resultat del producte entre dos elements qualssevol. Però, en aquesta taula, hi ha valors que són obvis (per exemple, sempre $g g^{-1} = 1$, per a tot $g \in G$) o que es poden deduir d'altres productes (per exemple, si $g^3 = 1$, aleshores $g^2 = g^{-1}$ per a tot $g \in G$). Per tant, hi ha certes relacions {\em importants} entre els elements d'un grup que el determinen. Intuïtivament, per exemple, la relació $a^n = 1$ determina el grup $\integers_n$. Ara bé, així com és important especificar les relacions que governen el grup, també ho és especificar el seus elements, ja que el grup $\integers_n \oplus \integers$ amb $a = (1,0)$ i $b = (0,1)$ també compleix que $a^n = 1$. Per tant, informalment, una presentació no serà res més que un conjunt d'elements, que direm {\em generadors}, i un conjunt de {\em relacions} entre ells. Per definir formalment les presentacions de grups ens fa falta recordar què s'entèn per grup quocient. \startdefinition Sigui $G$ un grup i $N$ un subgrup normal de $G$. El {\em grup quocient de $G$ per $N$} (també anomenat {\em grup quocient de $G$ mòdul $N$})\index{grup+quocient}, que indicarem amb $G/N$\symbol{$G/N$}, és el grup format pels cosets de $N$, $\{g N \mid g \in G\}$, i el producte $\cdot$ definit com \startformula a N \cdot b N = ab N. \stopformula A més, l'aplicació $x \mapsto xN = Nx$ és un morfisme exhaustiu entre $G$ i $G/N$ el nucli del qual és $N$. Aquesta aplicació s'anomena {\em projecció canònica dins el grup quocient $G/N$}\index{grup+quocient+projecció canònica,}.%\cite[grillet] \stopdefinition D'ara en endavant, si $G$ és un grup i $X$ és un subconjunt de $G$, indicarem amb $\langle \langle X \rangle \rangle$\symbol{$\langle \langle X \rangle \rangle$} la {\em clausura normal de $X$ en $G$}\index{clausura normal}, és a dir, el subgrup normal més petit que conté $X$. \startdefinition Una {\em presentació {\cal P} amb generadors $X$ i relacions $R$}\index{presentació}, que indicarem amb ${\cal P} = \langle X \mid R \rangle$\symbol{${\cal P} = \langle X \mid R \rangle$}, és un parell ordenat $(X, R)$, on $X$ és un conjunt qualsevol i $R \subseteq F(X) \times F(X)$ és una relació binària sobre el grup lliure $F(X)$. Una presentació defineix el grup quocient $F(X)/\langle \langle R_* \rangle \rangle$, que indicarem amb $G({\cal P})$, on \startformula R_* = \{uv^{-1} \mid (u, v) \in R\} \subseteq F(X). \stopformula Dues presentacions ${\cal P}$ i ${\cal P'}$ són {\em equivalents}\index{presentació+equivalent} si els seus grups $G({\cal P})$ i $G({\cal P^\prime})$ són isomorfs. Freqüentment, per abús de llenguatge, s'identifica la presentació ${\cal P}$ i el seu grup $G({\cal P})$. \stopdefinition Per exemple, si $X = \{a \}$ i $R = \{(a^8,1) \mid a \in X\}$, aleshores $\langle X \mid R \rangle = \integers_8$ (realment el que passa és que el grup que representa aquesta presentació és isomorf a $\integers_8$). Per comoditat, sovint s'abusa de la notació i s'escriuen els parells ordenats de la relació $R$ com una igualtat. Així, l'exemple anterior s'ecriuria com $\langle a \mid a^8 = 1\rangle$. A més, moltes vegades les relacions del tipus $u = v$ són escrites en la forma $uv^{-1} = 1$. Per exemple, $\langle a, b \mid ab = ba \rangle = \langle a, b \mid aba^{-1}b^{-1} = 1\rangle$ i $\langle a \mid a^8 = a^3\rangle = \langle a \mid a^5 = 1\rangle$. \startdefinition Sigui $G$ un grup i ${\cal P} = \langle X \mid R\rangle$ una presentació. Direm que ${\cal P}$ és una {\em presentació de $G$}\index{presentació+d'un grup} si $G({\cal P}) \cong G$. \stopdefinition \startdefinition Una presentació ${\cal P} = \langle X \mid R\rangle$ és {\em finita}\index{presentació+finita} quan $X$ i $R$ són ambdós finits. I un grup $G$ és {\em finitament presentable}\index{grup+finitament presentat} si existeix una presentació finita de $G$. \stopdefinition Notem que, pel Corol·lari \in[thme:gruplliure-imatge], tenim que tot grup és imatge del grup lliure. Per tant, aplicant el Primer Teorema d'Isomorfia, tenim que tot grup és isomorf a un grup d'una presentació. D'altra banda, la definició que hem donat és equivalent a una definició basada en relacions d'equivalència (amb una construcció anàloga del grup lliure): si $X$ és un conjunt qualsevol i $R$ és un subconjunt de ${(X \cup X^{-1})}^*$, es pot definir la relació d'equivalència $\approx$ definida de la manera següent: dues paraules $u, v \in {(X \cup X^{-1})}^*$ són tals que $u \approx v$ si, i només si, es pot passar d'una a l'altra amb un nombre finit de passes del tipus següent: \startitemize[n] \item Reducció: l'eliminació d'una ocurrència de $xx^{-1}$, per a qualque $x \in X\cup X^{-1}$, o d'una ocurrència d'una relació $r \in R$. \item Amplificació: l'afegit d'una ocurrència de $xx^{-1}$, per a qualque $x \in X \cup X^{-1}$, o d'una ocurrència d'una relació $r \in R$. \stopitemize Es pot veure que $\approx$ és d'equivalència i que $F(X)/\approx$ és un grup, que coincideix amb $G({\cal P})$ amb ${\cal P} = \langle X \mid R'\rangle$, on $R' = \{(red(r),1) \mid r \in R\} \subseteq F(X) \times F(X)$ \cite[magnus]. Tot seguit, oferim diverses presentacions dels grups més usuals: \startitemize[n] \item El grup lliure $F(X)$ té presentació $\langle X \mid \emptyset\rangle$. En particular $\integers$ té $\langle a \mid \emptyset \rangle$ com a presentació (recordem que $\integers$ és isomorf al grup lliure $F_1$ de rang $1$). \item El grup $\integers$ (com els altres grups) també té altres presentacions menys {\em naturals}, com, per exemple, $\langle a, b \mid ababa = 1\rangle$ \cite[millerIII]. \item Qualsevol grup finit $G = \{a_1, \ldots, a_n\}$ té una presentació finita: la corresponent a agafar tots els seus elements com a generadors i totes les relacions de la taula de productes de $G$ (aquestes tenen la forma $a_i a_j = a_k$ i n'hi ha $n^2$). \item $\integers_n \cong \langle a \mid a^n = 1 \rangle$. \item $\integers \oplus \integers$ té $\langle a, b \mid ab = ba\rangle$ com a presentació. \item Una presentació de $\integers_n \oplus \integers$ és $\langle a, b \mid a^n = 1\rangle$. \item El grup dièdric $D_n$ d'ordre $2n$ té com a presentació \startformula \langle a, b \mid a^2 = 1, b^n = 1, a^{-1}ba = b^{-1} \rangle. \stopformula \item El grup trivial té com a presentacions \startformula \langle a, b \mid a^{-1} b a = b^2, b^{-1}a b=a^2 \rangle \stopformula i \startformula \langle a, b \mid a^{-1} b^n a = b^{n+1}, a = w \rangle, \stopformula on $w$ és una paraula sobre $\{a, b\}$ tal que la suma dels exponents de $a$ és 0 i $n > 0$ \cite[millerIII, millerIII-article]. Per tant, no és gens senzill saber si una presentació correspon al grup trivial. \item Siguin $m, n \in \integers$. El {\em grup de Baumslag-Solitar}\index{grup+Baumslag-Solitar,}, que indicarem amb $BS(m,n)$\symbol{$BS(m,n)$}, és el subgrup del grup $\text{Homeo}(\reals)$ de les funcions homeomorfes de $\reals$ generat per les funcions lineals $a(x) = nx$ i $b(x) = x + m$ \cite[meier]. Aquest grup té com a presentació $\langle a, b\mid ab^m a^{-1}= b^n \rangle$. \stopitemize Finalment, notem que si ${\cal P} = \langle X \mid R\rangle$ és una presentació, aleshores tenim l'aplicació $\iota \colon X \rightarrow G({\cal P})$ definida com la composició $p \circ \eta$ de la inclusió natural $\eta \colon X \to F(X)$, tal que $\eta(x) = [x]$ per a tot $x \in X \cup X^{-1}$, i la projecció natural $p \colon F(X) \to F(X)/N$, on $N = \langle \langle R_* \rangle \rangle$, tal que $p([w]) = [w]N$, per a tot $[w] \in F(X)$. Aquesta aplicació es pot estendre a ${(X \cup X^{-1})}^*$ com \startformula \iota(w) = \iota(w_1) \cdots \iota(w_r) \in G({\cal P}), \stopformula per a tota paraula $w = w_1 \ldots w_r$ sobre $X \cup X^{-1}$. \starttheorem Per a tota presentació {\cal P} = \langle X \mid R \rangle, $\iota(X)$ genera $G({\cal P})$. \stoptheorem \startdemo Sigui $g \in G({\cal P})$, aleshores $g = [w]N$ per a alguna paraula $w = w_1 \ldots w_r$ sobre $X \cup X^{-1}$. Per tant, \startformula g = [w_1 \ldots w_r]N = ([w_1]\cdots [w_r])N = [w_1]N \cdots [w_r]N. \stopformula Cada $w_i$ és de $X$ o de $X^{-1}$. Si $w_i = x^{-1}$ per a algun $x \in X$, aleshores $[w_i]N = [x^{-1}]N = [x]^{-1}N = \iota(x)^{-1}$. Per tant, $g$ es pot posar com a producte d'elements de $\iota(X)$ i els seus inversos. \stopdemo De forma habitual s'identifica $X$ amb $\iota(X)$, denotant els seus elements amb els mateixos símbols i, per tant, de forma freqüent es diu que $X$ {\em genera} $G({\cal P})$. Per exemple, pel grup $\integers \oplus \integers = \langle a, b \mid ab = ba \rangle$, identifiquem $a$ i $b$ amb $\iota(a)=(1,0)$ i $\iota(b) = (0,1)$. \subsubsubject{El problema de la paraula} Sigui $G$ un grup i $X$ un subconjunt de $G$. Aleshores l'aplicació $\pi \colon {(X \cup X^{-1})}^* \to G$\symbol{$\pi$} consistent a enviar cada lletra $x \in X$ a l'element corresponent $\pi(x) = x \in G$ es pot estendre de manera natural a totes les paraules de $X \cup X^{-1}$ de la forma següent: \startitemize[n] \item $\pi(x^{-1}) = \pi(x)^{-1}$ per a tot $x \in X$. \item Per a tota paraula $w = w_1 \ldots w_r$ sobre $X \cup X^{-1}$, \startformula \pi(w) = \pi(w_1) \cdots \pi(w_r) \in G. \stopformula \stopitemize Per tant, $\pi$ és un morfisme de monoides entre ${(X \cup X^{-1})}^*$ i $G$. De forma òbvia, si $X$ és un conjunt de generadors de $G$, aleshores $\pi$ és exhaustiva. En particular, si ${\cal P} = \langle X \mid R \rangle$ és una presentació, aleshores, com que $X$ és un conjunt de generadors de $G({\cal P})$%\footnote{Recordem que abusem del llenguatge, identificant $\iota(X)$ i $X$, i que, realment, $\iota(X)$ és el generador de $G(\cal{P})$.} , llavors $\pi \colon {(X \cup X^{-1})}^* \to G({\cal P})$ és un morfisme exhaustiu. \startdefinition Sigui $G$ un grup i ${\cal P} = \langle X \mid R\rangle$ és una presentació de $G$. Una paraula $w$ sobre $X \cup X^{-1}$ és {\em nul-homotòpica per ${\cal P}$}\index{paraula+nul-homotòpica per una presentació} si, i només si, $\pi(w) = 1 \in G$. \stopdefinition \startdefinition Sigui $G$ un grup i ${\cal P} = \langle x_1, \ldots, x_n \mid r_1, \ldots, r_k\rangle$ una presentació {\em finita} de $G$. El {\em problema de la paraula per a {\cal P}}\index{problema de la paraula+per una presentació finita} consisteix en trobar un algorisme que, donada una paraula $w \in {(X \cup X^{-1})}^*$, decideixi si $\pi(w) = 1$ o $\pi(w) \neq 1$. \stopdefinition \subsubject{Eines geomètrics per fer front al problema de la paraula} Posar la proposició 2.2 de l'article de Joe. \completepublications[criterium=cite] %all per tots \title{Llista de símbols} \placesymbol \title{Índex alfabètic} \placeindex \stoptext \startitemize[1] \item $\pi(x^{-1}) = \pi(x)^{-1}$ per a tot $x \in X$. \item Per a tota paraula $w = w_1 \ldots w_r$ sobre $X \cup X^{-1}$, \startformula \pi(w) = \pi(w_1) \cdots \pi(w_r) \in G. \stopformula \stopitemize \startdefinition Sigui $X$ un conjunt qualsevol i $R \subseteq F(X) \times F(X)$ una relació binària sobre el grup lliure $F(X)$. Una {\em presentació ${\cal P}$ amb generadors $X$ i relacions $R$}\index{presentació}, que indicarem amb ${\cal P} = \langle X \mid R \rangle$, és el grup quocient $F(X)/\langle \langle R_* \rangle \rangle$, on \startformula R_* = \{uv^{-1} \mid (u, v) \in R\} \subseteq F(X). \stopformula Quan ens convengui diferenciar entre la presentació com a un parell ordenat de símbols i el grup quocient en si, indicarem amb ${\cal P}$ la presentació i $G({\cal P})$ el grup que aquesta representa. \stopdefinition