* Re: Problems with @incollection + strange trouble--> short (not with log)
[not found] ` <4A6995FA.2010306@telefonica.net>
@ 2009-07-24 11:32 ` Xan
0 siblings, 0 replies; 3+ messages in thread
From: Xan @ 2009-07-24 11:32 UTC (permalink / raw)
To: mailing list for ConTeXt users
[-- Attachment #1: Type: text/plain, Size: 3587 bytes --]
En/na Xan ha escrit:
> Taco,
>
> I have strange problems:
>
> 1)
> With \setuppublicationlayout[incollection]{%
> \insertartauthors{}{}{\insertthekey{}{, }{}}%
> \insertarttitle{, \bgroup }{\egroup}{}%
> \inserttitle
> {, in %
> \bgroup\it}%
> {\egroup
> \inserteditors{, edited by }%
> {}%
> {}
> \insertseries
> {\insertvolume{, number }{~in }{ }}%
> {}%
> {}%
> \insertchap{\unskip, }{ }{ }%
> \insertpubyear{(%
> \insertpublisher{}{, }%{}%
> }{)\insertEdition{, }{ ed. }{}}{}%
> \insertpages{\unskip, p.~}{. }{\unskip. }%
> }%
> {In \insertcrossref{}{}{}%
> \insertchap{\unskip, }{ }{ }%
> \insertpages{\unskip, p.~}{. }{\unskip. }%
> }%
> \insertNote{ }{.}{}%
> }
>
> then I get this error
>
> subject : - Eines geomètrics per fer front al problema de la
> paraula
> {vertical mode: \tracingstats}
> {\tracingpages}
> {\tracingoutput}
> {\tracinglostchars}
> {\tracingmacros}
> {\tracingparagraphs}
> {\tracingrestores}
> {\showboxbreadth}
> {\showboxdepth}
> {\tracinggroups}
> {\tracingifs}
> {\tracingscantokens}
> {\tracingnesting}
> {\tracingassigns}
> {into \tracingassigns=2}
> {\errorstopmode}
>
> {\tracingonline}
> {changing \tracingonline=1}
>
> Completed box being shipped out [9.9]
> Memory usage before: 4840&640775; after: 726&638324; still untouched:
> 931790
>
> Completed box being shipped out [10.10]
> Memory usage before: 2101&638568; after: 528&638393; still untouched:
> 931790
> title : - Refer\dochar {232}ncies
> ! Extra \endcsname.
> <argument> ...}{, }\csname @@pb@pubyear\endcsname
> )\insertEdition {, }{
> ed. }{}
>
> \firstoftwoarguments #1#2->#1
> <argument> ... }}{)\insertEdition {, }{ ed.
> }{}}{}
> \insertpages {\unskip
> , p....
>
> \firstoftwoarguments #1#2->#1
> \@@pvdataincollection ...p , p.~}{.
> }{\unskip . }}
> \insertNote {
> }{.}{}\unskip
> \dotypesetapublication ...ve {\getvalue {pbdt-#1}}
> \fi \egroup
> ...
> l.519 \completepublications[criterium=cite]
> %all per tots
> ?
>
>
> and when I commented (as originally):
>
> \setuppublicationlayout[incollection]{%
> \insertartauthors{}{}{\insertthekey{}{, }{}}%
> \insertarttitle{, \bgroup }{\egroup}{}%
> \inserttitle
> {, in %
> \bgroup\it}%
> {\egroup
> \inserteditors{, edited by }%
> {}%
> {}
> \insertseries
> {\insertvolume{, number }{~in }{ }}%
> {}%
> {}%
> \insertchap{\unskip, }{ }{ }%
> \insertpubyear{(%
> \insertpublisher{}%{, }%{}%
> }{)\insertEdition{, }{ ed. }{}}{}%
> \insertpages{\unskip, p.~}{. }{\unskip. }%
> }%
> {In \insertcrossref{}{}{}%
> \insertchap{\unskip, }{ }{ }%
> \insertpages{\unskip, p.~}{. }{\unskip. }%
> }%
> \insertNote{ }{.}{}%
> }
>
> all works.
>
> I did **not** add your example yet.
>
> 2) when I substitute all "subjects" ({sub}*subjects too) for
> "section", then the references are empty.
>
>
> do you have any idea?
> I have MKII.
>
> I attach the files.
[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: memoria.bib --]
[-- Type: text/x-bibtex; name="memoria.bib", Size: 4467 bytes --]
@book{grillet,
author = "Pierre Antoine Grillet",
title = "Abstract Algebra",
edition = "second",
year = "2007",
publishers = "Springer",
series = "Graduate Texts in Mathematics",
address = "New York"
}
@book{robinson,
author = "Derek J. S. Robinson",
title = "A Course in the Theory of Groups",
edition = "second",
year = "1996",
publishers = "Springer",
series = "Graduate Texts in Mathematics",
address = "New York"
}
@book{cgt,
author = "Roger C. Lyndon and Paul E. Schupp",
title = "Combinatorial Group Theory",
series = "Classics in Mathematics",
publishers = "Springer",
address = "Berlin",
year = "2001"
}
@book{magnus,
author = "Wilhelm Magnus and Abraham Karrass and Donald Solitar",
title = "Combinatorial Group Theory: presentations of Groups in Terms of Generators and Relations",
publishers = "Dover",
year = "2004",
address ="New York"
}
@unpublished{millerIII,
title = "Combinatorial Group Theory",
author = "Charles F. {{Miller III}}",
year = "2004"
}
@article{millerIII-article,
title = "Some presentations of the trivial group",
author = "Charles F. {{Miller III}} and Paul E. Schupp",
year = "1999",
journal = "Contemporany Mathematics of the American Mathematical Society",
volume = "250",
pages = "113-115"
}
@book{meier,
title = "Groups, Graphs and Trees. An Introduction to the Geometry of Infinite Groups",
author = "John Meier",
publishers = "Cambride University Press",
series = "London Mathematical Society Student Texts",
volume = "73",
address = "Cambridge",
year= "2008"
}
@book{crm,
title = "The Geometry of The Word Problem for Finitely Generated Groups",
author = "Noel Brady and Tim Riley and Hamish Short",
publishers = "Springer",
year = "2007",
address = "Berlin",
series = "Advanced Courses in Mathematics CRM Barcelona"
}
@article{novikov,
author = "P. S. Novikov",
title = "On the algorithmic unsolvability of the word problem in group theory",
journal = "Proceedings of Steklov Mathematical Institute",
year = "1955",
volume = "44",
pages = "1-145",
note = "Traducció anglesa a l'American Mathematical Society Translations (2) 9 (1958), 1-122"
}
@article{stillwell,
title = "The Word Problem and the isomorphism problem for groups",
author = "John Stillwell",
journal = "Bulletin (New Series) of the American Mathematical Society",
volume = 6,
number = 1,
year = 1982,
month = "Jan"
}
@incollection{millerIIIa2,
author = "Charles F. {{Miller III}}",
title = "Decision problems for groups: survey and reflections",
booktitle = "Algorithms and Classification in Combinatorial Group Theory",
year = "1992",
publisher = "Springer-Verlag",
address = "Berlin",
editor = "Gilbert Baumslag and Charles F. {{Miller III}}",
pages = "1-59",
series = "MSRI Publications",
volume = 23
}
@incollection{bridson-tutorial,
author= "Martin R. Bridson",
title = {{The geometry of the word problem}},
booktitle= "Invitations to Geometry and Topology",
year = "2002",
publisher = "Oxford University Press",
editor = "Martin R. Bridson, Simon M. Salamon",
pages="29-92"
}
@incollection{gersten,
author = "S. M. Gersten",
title = "Isoperimetric and isodiametric functions of finite presentations",
booktitle = "Geometric Group Theory volume 1",
editor = "G. Niblo and M. Roller",
series = "London Mathematical Society Lecture Note Series",
volume = 181,
pages = "79-96",
publisher = "Cambridge University Press",
address = "Cambridge",
year = "1993"
}
@article{bridson,
author = "Martin R. Bridson",
title = "On the geometry of normal forms in discrete groups",
journal = "Proceedings of the London Mathematical Society",
year = "1993",
volume = "67",
pages = "595-616"
}
@article{riley,
author = "Tim R. Riley",
title = "The geometry of groups satisfying weak almost-convexity or weak geodesic-combability conditions",
journal = "Journal of Group Theory",
year = "2002",
volume= 5,
pages = "513-525"
}
@book{epstein,
author = "Epstein, David B. A. and J. W. Cannon and D. F. Holt and S. V. F. Levy and M. S. Paterson and W. P. Thurston",
title = "Word processing in groups",
publishers="Jones and Barlett Publishers",
year= "1992"
}
@book{delaharpe,
author= "de la Harpe, Pierre",
title = "Topics in Geometric Group Theory",
publishers = "University of Chicago Press",
series= "Chicago Lectures in Mathematics",
year = "2000"
}
[-- Attachment #3: memoria.context --]
[-- Type: text/plain, Size: 38015 bytes --]
% 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={\bfd}]
\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[][{\tfxx \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}
\hyphenation{re-so-lu-ble}
% 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
[nota]
[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[mysymbol][mysymbols]
% Start the text
\starttext
\version[concept]
%\title{Introducció}
\title{Preliminars}
En aquests preliminars s'introdueixen les definicions i notacions bà siques que s'empraran al llarg d'aquesta memòria. La primera secció està dedicada a recordar les definicions i teoremes bà sics de la Teoria de Grups i a enunciar en què consisteix el problema de la paraula per a grups. A la segona secció, s'introdueixen els conceptes està ndard de la Teoria Geomètrica de Grups. Entre aquests es mencionen els conceptes de diagrames de van Kampen, grafs de Cayley i funcions de Dehn.
\subject{Conceptes bà sics}
\subsubject{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)$\mysymbol{$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$.
\subsubject{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)$\mysymbol{$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)$\mysymbol{$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$\mysymbol{$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$\mysymbol{$\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)$.
\subsubject{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$\mysymbol{$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$\mysymbol{$\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$. La clausura normal de $X$ està caracteritzada pel resultat següent:
\startdefinition Donat un element $x$ d'un grup $G$, els {\em conjugats de $x$}\index{conjugat d'un element d'un grup} són els elements de $G$ de la forma $a^{-1} x a$, amb $a \in G$.
\stopdefinition
\startproposition[thmi:clausuranormal] Donat un grup $G$ i $X$ un subconjunt de $G$, la clausura normal $\langle \langle X \rangle \rangle$ consisteix en tots els productes de conjugats d'elements de $X \cup X^{-1}$, i.e.,
\startformula
\langle \langle X \rangle \rangle = \{a_1^{-1} x_1^{e_1} a_1 \cdots a_r^{-1} x_r^{e_r} a_r \mid a_i \in G, x_i \in X, e_i = \pm 1, r \geq 0, i \in \{1, \ldots, r\}\}.
\stopformula
\stopproposition
\startdemo Indiquem amb $Y$ el conjunt format pels productes de conjugats d'elements de $X \cup X^{-1}$. Hem de veure que $\langle \langle X \rangle \rangle = Y$. Com que $X \subseteq Y$ i $Y$ és normal (ja que, per a tot $g \in G$, $g^{-1} Y g \subseteq Y$), aleshores, per definició de clausura normal, tenim que $\langle \langle X \rangle \rangle \subseteq Y$. D'altra banda, per a tot $x \in X$, tenim que $x^{-1}$, $a^{-1} x a$, $a^{-1} x^{-1} a \in \langle \langle X \rangle \rangle$, perquè $X \subseteq \langle \langle X \rangle \rangle$ i la normalitat de $\langle \langle X \rangle \rangle$. Per tant, els productes d'aquests elements també hi pertanyen, la qual cosa implica que $Y \subseteq \langle \langle X \rangle \rangle$.
\stopdemo
\startdefinition Una {\em presentació {\cal P} amb generadors $X$ i relacions $R$}\index{presentació}, que indicarem amb ${\cal P} = \langle X \mid R \rangle$\mysymbol{${\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)$\mysymbol{$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)$, respectivament.
\subsubject{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$\mysymbol{$\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[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
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})$, llavors $\pi \colon {(X \cup X^{-1})}^* \to G({\cal P})$ és un morfisme exhaustiu\footnote{Recordem que abusem del llenguatge, identificant $\iota(X)$ i $X$, i que, realment, $\iota(X)$ és el generador de $G({\cal P})$.}.
\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 \mid R\rangle$ una presentació de $G$. El {\em problema de la paraula per a {\cal P}}\index{problema de la paraula+per una presentació} 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
Si $G$ és un grup i ${\cal P}$ i ${\cal P'}$ són presentacions {\em finites} de $G$, aleshores existeix un algorisme que decideixi si una paraula és nul-homotòpica per ${\cal P}$ si, i només si, n'existeix un altre per ${\cal P'}$ \cite[crm]. Per aquest motiu es parla del {\em problema de la paraula de $G$}\index{problema de la paraula+per un grup}, consistent en decidir la resolubilitat del problema de la paraula d'alguna (i de totes) presentació de $G$.
Donarem, tot seguit, un criteri per saber si una paraula és nul-homotòpica per una presentació {\em finita} donada.
\starttheorem Sigui ${\cal P} = \langle X \mid R \rangle$ amb $X = \{ x_1, \ldots, x_n \}$ i $R = \{ r_1 = 1, \ldots, r_k = 1\}$ una presentació finita i $w$ una paraula sobre $X \cup X^{-1}$. Llavors tenim que $w$ és nul-homotòpica per ${\cal P}$ si, i només si, $w$ compleix la igualtat següent dins el grup lliure $F(X)$:
\startformula
w = \prod_{i=1}^N u_i^{-1} r_i^{e_i} u_i,
\stopformula
per a alguns $N \in \naturalnumbers$, $r_i \in R$, $e_i = \pm 1$ i $u_i \in F(X)$, amb $i \in \{1, \ldots, N\}$.
\stoptheorem
\startdemo Sigui $N = \langle \langle r_1, \ldots, r_k \rangle \rangle \subseteq F(X)$. Si $w \in {(X \cup X^{-1})}^*$, aleshores $\pi(w) = 1 \iff w N = 1 \in G({\cal P}) \iff w \in N \subseteq F(X)$. Per la Proposició \in[thmi:clausuranormal], això vol dir que $w$ és producte de conjugats d'elements de $\{r_1, \ldots, r_k\}$ o dels seus inversos (dins el grup lliure $F(X)$).
\stopdemo
Aquest darrer resultat ens dóna una aproximació natural al problema de la paraula per a presentacions finites. Donada una presentació finita ${\cal P} = \langle x_1, \ldots, x_n \mid r_1 = 1, \ldots, r_k = 1\}$, podem enumerar en una llista totes les expressions de la forma
\placeformula[eq:llista-conjugats]
\startformula
u_1^{-1} r_1^{\pm 1} u_1 \cdots u_m^{-1} r_m^{\pm 1} u_m,
\stopformula
amb $u_i \in F(X)$ i $m \geq 0$.
Si una paraula $w$ és tal que $\pi(w) = 1$, aleshores $w$ apareixerà , prest o tard, en aquesta llista. El problema és si $w$ {\em no} satisfà que $\pi(w)=1$: està clar que $w$ no apareixerà en la llista, però no ho podrem saber amb un temps finit. Tècnicament, pareix que el conjunt de paraules nul-homotòpiques per ${\cal P}$ és recursivament enumerable però no recursiu (és a dir, el seu complement no és recursivament enumerable). Això fa que el problema de la paraula per una presentació pareixi indecidible.
Aquest fet és, precisament, el que va establir Novikov el qual va ser el primer en demostrar, l'any 1955, que existeixen grups finitament presentables amb el problema de la paraula no resoluble \cite[novikov]. Des de la dècada de 1960 fins a mitjans dels anys vuitantes (del segle XX), s'introdueixen diverses tècniques noves que permeten simplificar la demostració original, de 143 pà gines. Es pot trobar una demostració curta de la tesi de Novikov a l'article de Stillwell \cite[stillwell]. Hi ha diverses referències sobre el problema de la paraula que es poden consultar per obtenir-ne més informació \cite[magnus,stillwell,millerIIIa2].
Per mor d'aquest resultat negatiu, cal imposar condicions al grup $G$ per a què aquest tengui el problema de la paraula resoluble. Aquest és el cas, per exemple, de la classe de grups {\em residualment finits}, tal com mostra el resultat següent:
\startdefinition Un grup $G$ és {\em residualment finit}\index{grup+residualment finit} si, donat $g \neq 1$ en $G$, existeix un subgrup normal $N$ de $G$ tal que $g \not \in N$ i $G/N$ és finit.
\stopdefinition
\startproposition{\cite[robinson]} Sigui $G$ un grup residualment finit i finitament presentat. Aleshores $G$ té el problema de la paraula resoluble.
\stopproposition
\startdemo He de posar la demostració. I llevar la referència del tÃtol.
\stopdemo
Una altra manera d'aconseguir que un grup $G$ tengui el problema de la paraula resoluble és, donada una presentació ${\cal P}$ de $G$, fitar el nombre de productes de conjugats de les relacions de ${\cal P}$ (i de les seves inverses) que hem de llistar (o sigui, que apareixen a la llista d'elements (\in[eq:llista-conjugats])), per saber que $w$ no és nul-homotòpica. Això s'aconsegueix mitjançant les funcions de Dehn. La Proposició \in[thmi:WP-Dehn-recursiu] mostra la seva importà ncia.
\startdefinition Sigui $G$ un grup i ${\cal P} = \langle X \mid R \rangle$ una presentació finita de $G$.
\startitemize[a]
\item Si $w$ és una paraula nul-homotòpica per ${\cal P}$, llavors l'{\em à rea algebraica de $w$ respecte de ${\cal P}$}\index{\`{a}rea+algebraica d'una paraula}\mysymbol{$\text{\tf area}_{a, {\cal P}}(w)$} és
\startformula
\text{\tf area}_{a, {\cal P}}(w) = \min \{ N \mid w = \prod_{i=1}^N x_i^{-1} r_i x_i \text{ dins } F(A), \text{ amb } x_i \in F(A), r_i \in R^{\pm 1}\}.
\stopformula
\item Una funció $f\colon \naturalnumbers \rightarrow \naturalnumbers$ és una {\em funció isoperimètrica per a ${\cal P}$}\index{funció isoperimètrica} si, per a tota paraula $w$ nul-homotòpica per ${\cal P}$ tal que $l(w) \leq n$, es té $\text{area}_{a, {\cal P}}(w) \leq f(n)$. El mÃnim, punt a punt, d'aquestes funcions és la {\em funció de Dehn de ${\cal P}$}\index{funció de Dehn}\mysymbol{$\delta_{{\cal P}}$}, i.e., la funció $\delta_{\cal P}\colon \naturalnumbers \rightarrow \naturalnumbers$ definida per
\startformula
\delta_{{\cal P}} = \max \{ \text{area}_{a, {\cal P}}(w) \mid \pi(w) = 1, l(w) \leq n\}.
\stopformula
\stopitemize
\stopdefinition
De forma òbvia, si ${\cal P} = \langle X \mid R \rangle$ és una presentació finita de $G$ i $u, v$ són paraules nul-homotòpiques per ${\cal P}$, aleshores la seva concatenació $u \cdot v$ és nul-homotòpica per ${\cal P}$ ($\pi$ és un morfisme) i $\text{area}_{a, {\cal P}}(u v) \leq \text{area}_{a, {\cal P}}(u) + \text{area}_{a, {\cal P}}(v)$.
\startdefinition Siguin $f$, $g \colon \naturalnumbers \to \naturalnumbers$. Sigui $\preceq$ la relació definida com $f \preceq g$\mysymbol{$\preceq$} si, i només si, existeix $k > 0$ tal que
\startformula
f(x) \leq k g(kx + k) + kx + k,
\stopformula
per a tot $x \in \naturalnumbers$. Si $f \preceq g$ i $g \preceq f$, ho indicarem amb $f \simeq g$\mysymbol{$\simeq$}, i direm que són {\em $\simeq$-equivalents}\index{funcions $\simeq$-equivalents}.
\stopdefinition
Si ${\cal P}$ i ${\cal P}'$ són presentacions finites de $G$, $f$ és una funció isoperimètrica per a ${\cal P}$ i $g$ és una funció isoperimètrica per a ${\cal P}$, aleshores $f \simeq g$ \cite[bridson-tutorial]. En particular, si $f$ i $g$ són funcions de Dehn de ${\cal P}$ i ${\cal P}'$, respectivament. És per això que podem parlar, llevat de transformacions lineals, de {\em la} funció de Dehn {\em de $G$}, $\delta_G$, o de les funcions isoperimètriques {\em de $G$}.
\startproposition[thmi:WP-Dehn-recursiu]{\cite[bridson-tutorial,gersten]} Sigui ${\cal P} = \langle X \mid R \rangle$ una presentació finita de $G$. Aleshores són equivalents:
\startitemize[a]
\item $G({\cal P})$ té el problema de la paraula resoluble.
\item La funció de Dehn de ${\cal P}$ és recursiva.
\item ${\cal P}$ admet una funció isoperimètrica recursiva.
\stopitemize
\stopproposition
El problema de la paraula va sorgir de forma natural de la Topologia Algebraica a finals de segle XIX i principis de segle XX associat a problemes sobre grups fonamentals de superfÃcies \cite[stillwell]. Dehn va ser el primer a enunciar aquest problema, l'any 1911 (cita a Dehn de CRM). A part d'aquest problema, Dehn en va enunciar dos més que tracten de decidir sobre propietats locals i globals d'un grup. Les propietats locals d'un grup s'ocupen de determinar si certs elements compleixen o no determinades relacions i les propietats globals tracten d'esbrinar les caracterÃstiques que té el grup sencer com a estructura.
\startitemize[1]
\item Problema dels conjugats.
Donat un grup $G$ i una presentació ${\cal P} = \langle X \mid R \rangle$, deteminar si existeix un algorisme tal que decideixi si dues paraules $u$, $w$ sobre $X \cup X^{-1}$ són tals que $\pi(u)$ és un conjugat de $\pi(w)$.
\item Problema de l'isomorfisme.
Donats dos grups, trobar un algorisme que determini si són isomorfs o no.
\stopitemize
El problema de la paraula i dels conjugats són problemes de decissió sobre propietats locals mentre que el problema de l'isomorfisme és un problema sobre una relació global. Notem que el problema de si, donada una presentació, aquesta correspon o no al grup lliure és un cas particular del problema de l'isomorfisme.
Aquests problemes tenen la seva importà ncia, tant històrica com teòrica. Es poden consultar diverses fonts per obtenir més informació al respecte (cites).
\subject{Eines geomètrics per fer front al problema de la paraula}
%\cite[prova]
\completepublications[criterium=cite] %all per tots
\title{Llista de sÃmbols}
\placemysymbol
\title{Ãndex alfabètic}
\placeindex
\stoptext
[-- Attachment #4: Type: text/plain, Size: 487 bytes --]
___________________________________________________________________________________
If your question is of interest to others as well, please add an entry to the Wiki!
maillist : ntg-context@ntg.nl / http://www.ntg.nl/mailman/listinfo/ntg-context
webpage : http://www.pragma-ade.nl / http://tex.aanhet.net
archive : https://foundry.supelec.fr/projects/contextrev/
wiki : http://contextgarden.net
___________________________________________________________________________________
^ permalink raw reply [flat|nested] 3+ messages in thread