Undecidability of Group Theory

Vista senzilla d'ítem
dc.contributor.advisorCasanovas Ruiz-Fornells, Enrique
dc.contributor.authorGarcia Cilleruelo, Azucena
dc.date.accessioned2026-03-23T17:56:08Z
dc.date.available2026-03-23T17:56:08Z
dc.date.issued2026-01-15
dc.descriptionTreballs Finals de Grau de Matemàtiques, Facultat de Matemàtiques, Universitat de Barcelona, Any: 2026, Director: Enrique Casanovas Ruiz-Fornells
dc.description.sponsorship[en] One of the central questions in mathematical logic is whether the truths of a given mathematical theory can be captured by a mechanical procedure. That is, given a fixed collection of axioms, can we decide algorithmically whether any statement follows from them? In this work we focus on the first-order theory of groups, one of the most fundamental algebraic theories, and yet one of the earliest examples of an undecidable theory. Our main objective is to present a modern proof of its undecidability, following the classical result of Tarski, Mostowski, and Robinson. The proof proceeds by analysing the relationship between undecidability, the representability of recursive functions, and interpretability between theories. We first study some weak arithmetical theories and establish that they are essentially undecidable. We then show how undecidability can be transferred along interpretations, introducing intermediate theories that bridge arithmetic and the theory of groups. With the help of some general results, this will lead us to the undecidability of group theory. [es] Una de les preguntes centrals de la lògica matemàtica és si les veritats d’una teoria matemàtica donada es poden obtenir a través d’un procediment mecànic. És a dir, donada una col·lecció d’axiomes, hi ha algun algoritme que decideixi si una afirmació qualsevol es dedueix d’aquests? En aquest treball ens centrem en la teoria de grups de primer ordre, una de les teories algebraiques més fonamentals i, tanmateix, un dels primers exemples de teoria indecidible. L’objectiu principal és presentar una demostració clara i moderna de la seva indecidibilitat, seguint el resultat clàssic de Tarksi, Mostowski i Robinson. En el procés de demostrar-ho analitzarem la relació entre la indecidibilitat, la representació de funcions recursives, i la interpretabilitat entre teories. Primer estudiarem teories aritmètiques dèbils i establirem que són essencialment indecidibles. Llavors provarem que la indecidibilitat es pot transferir mitjançant interpretacions, i introduirem teories intermèdies que connecten l’aritmètica amb la teoria de grups. Amb l’ajuda d’alguns resultats generals, això ens permetrà concloure la indecidibilitat de la teoria de grups.
dc.format.extent47 p.
dc.format.mimetypeapplication/pdf
dc.identifier.urihttps://hdl.handle.net/2445/228433
dc.language.isoeng
dc.rightscc by-nc-nd (c) Azucena Garcia Cilleruelo, 2026
dc.rights.accessRightsinfo:eu-repo/semantics/openAccess
dc.rights.urihttps://creativecommons.org/licenses/by-nc-nd/4.0/deed.ca
dc.sourceTreballs Finals de Grau (TFG) - Matemàtiques
dc.subject.classificationTeoria de grupsca
dc.subject.classificationLògica matemàtica
dc.subject.classificationTeoria de la computacióca
dc.subject.classificationAzucena Garcia Cillerueloca
dc.subject.classificationTreballs de fi de grauca
dc.subject.otherGroup theoryen
dc.subject.otherMathematical logic
dc.subject.otherTheory of computationen
dc.subject.otherBachelor's thesesen
dc.titleUndecidability of Group Theory
dc.typeinfo:eu-repo/semantics/bachelorThesis

Fitxers

Paquet original

Mostrant 1 - 1 de 1
Miniatura
Nom:
TFG_Garcia_Cilleruelo_Azucena.pdf
Mida:
509.63 KB
Format:
Adobe Portable Document Format
Descarregar

Col·leccions

Treballs Finals de Grau (TFG) - Matemàtiques