# A consequence from a proof of the Higman Embedding Theorem

#### by Maurice Chiodo

Institution: Mathematics and Statisics, University of Melbourne
Date: Thu 28th May 2009
Time: 4:15 PM
Location: Room 107, Richard Berry Building, Uni of Melb

Abstract: The Higman embedding theorem states that a finitely generated group
can be embedded into a finitely presented group iff it is recursively
presented. Using parts of a proof of this theorem, as well as a
theorem by Rabin, we shall show the following:
There exists a recursive list of (recursively constructible) finite
presentations of groups P_{1}, P_{2}, ... such that, if i= (the
Cantor pairing function of m and n) then P_{i} is isomorphic to the
trivial group iff the turing machine T_{m} halts on input N (ie: n \in
W_{m}).
Only the necessary parts of the Higman embedding theorem will be used,
and these will be stated without full proof.