A proof of Higman’s embedding theorem, using Britton extensions of groups.

using Britton extensions of groups.

by

Stal Aanderaa

Abstract. A new proof is given of Higman's theorem: Let R be a finitely generated group, then (1) G can be embedded in a finitely presented group iff (2) R is recursively presented.

To prove (1) ==> (2) is trivial; and we shall only deal with the problem. of proving (2) ==> (1). In order to prove (2) ==> (1),

1.1e start with a Turing machine ZE , vrhich recognizes the recur-

sive enumerable set E of defining relation for R . From ZE we construct a semigroup TE by Post's construction and then a group GE , by Boone's (and Britton's), method. Then we construct three Britton extensions, starting with the free product GE * R • Finally we delete redundant relation$ and we obtain a finite pre- sentated group in which R is embedded. By using Britton's lemma, we avoid the use of free product with amalgamations.

Higman's proof as well as Shoenfield's proof gives an indirect construction by developing a theory about benign subgroups. Our construction is simple and explicit a!J4l we avoid the notion

"benign subgroup"altogether.

§ 1. Introduction. The aim of this paper is to give a new proof of the following theorem due to Higman. (See Higman 1961 Theorem 1, p.456).

Theorem 1. A finitely generated group can be embedded in a finitely presented group iff it is recursively presented.

Shoenfield 1967 pp.321-326 presents a variant of Higman's

-

proof.

As pointed out by Higman, one-half of theorem 1 is trivial.

Hence~ from now on we shall consentrate on the non-trivial half of the theorem which we shall state as a lemma:

Lemma 1. Every finitely generated and recursively presen- ted group can be embedded in a finitely presented group.

Definition 1.

-

A positive group presentation is a presen- tation (S!D) where each relation in D is of the form w

=

¹

for some positive word over S •

Note that every group presentation (S!D) can be turned into a positive presentation of the same group by replacing

s

by S' = [s 'Is E S 1 US and D by D'

'

^{where D'} is obtained from D by replacing each occurrence of s -1 by s' and by adding the relation ss' = 1 for every s in

s

Definition 2. A group is recursively presented if it has a positive presentation of the form

where E is a recursive enumerable set of positive words on [ u_{1 ,} u2 , ••• , um l •

§ 2. Outline of the ___E.roof.

We shall start by some remarks on Britton extension and Britton's

le~~a in §3. Then in §4, we shall outline the construction of the Turing machine ZE and the corresponding semigroup TE • In § 5 we shall study the Boone-Britton group G • (See Britton 1963 pp.22-23) The final aim is to prove lemma 11 which is the only lemma in § 5 which is used in § 6 • Lemma 11 corresponds to lemma 5.1 p.473 in Higman 1961~ and to lemma 18 p.335 in

Shoenfield 1967. Lemma 11 shows that the group GE so to speak semicomputes or recognizes the enumerable set of words E •

In § 5 we first form the free product of GE and the group R , which we want to embed. Then we construct three Britton ex-

tensions, which by using a finite number of new generators and new defining relations transfer the information given in group GE about E to generate relations which make all but a finite number of defining relations in G

*

R superfluous.

§ 3. Remarks on Britton extension.

We shall assume that the reader is familiar with Britton's lemma, which is the main tool in this paper. (See lemma 4 p.20 of

Britton 63.) We shall not state the lemma here since the reader1

in order to understand the details of §4 , must have

the paper of Britton before him anyhow. We would only like to define some new concepts and to make some remarks.

Definition 3. A presentation (S*ID*) is a Britton exten- sion of (SjD) with stable letters P , if the following two conditions are satisfied:

1.

(S*!D*)

has stable letters P and corresponding basis

(SID) .

2. The isomorphism conditions are satisfied.

All unexplained concepts are as in Britton 1963. We shall not always state explicitly what the basis and the stable letters consist of when it should be obvious from the context.

Moreover, we shall not always define the mapping which is used to verify that the isomorphism condition holds. Note that

the isomorphism condition is satisfied iff for all v E V and all pairs of words w, w' where w is a word on the set

(Ai!i E Jv} and w' is the corresponding word on [Bili E Jv}, then w

=

1 in

(SID)

iff w'

=

1 in

(SID) .

We may also verify the isomorphism conditionsby proving that A(v) and B(v) have equivalent presentations, where

i E J v •

A. l corresponds to _{B. '}

l

We shall sometimes deviate a little from Britton's notations in order to avoid subsubscripts, and sub-to-superscripts. In- stead of denoting the stable letters by pv(v E V) or (pv lv E V}

we shall use the set P • Then p without subscript may be used to denote an arbitrary element of P • We shall often use the same letter to denote the group and its presentation.

G1 ^{= (}

s

₁

!

D1 ) means that G1 may 1)e used both to denote the group defined by the presentation (S 1

lD

_{1 ) •} We shall use

(G 1;s₂

!D

_{2 )} as anabbreviation for (s₁ us₂

jD

₁

,D

_{2 ) if G1} = (s₁

1D

_1).

G2 ⁼ (G 1

;s

_{2 jD2 )} is called an extension of the presentation G1 • Note that in most cases used in this paper G1 is embedded in

(G 1

;s

₂

!D

2 ) , but in some cases this is not true. We shall not explicitly define homomorphism and isomorphism when the reader

should have no difficulty in finding out the mapping we have in mind ·which will fit into the proof. Talking about the homomor- phism (or isomorphism) of the group G1 ⁼ (S 1 jD1 ) into

G2

=

^{(S2!D2) when s}1

n

_{s 2}

I ¢

⁹ we often mean that the mapping s ^·.p s E s1

n s

₂

= {

^{l ...}

cp( s)

1 if s E s1- s2

can be extended to a homomorphism of G1 into G2 •

Definition 4. Let W be a word. We shall say that W is trivially (or freely) reduced if

w

contains no subword of

-1 -1

the form s s or ss _•

Definition 5. Let (S*!D*) be a Britton extension of (S!D) wjth stable letters P • A pinch is a word of one of the following forms:

(l·) p - 1

c

p , w ere ^h

c

is a word on S and C E A( p ), and p E P or

(ii) pCp- 1 , where C is a word on S and C E B(p), and pEP.

Definition 6. Given (S* !D>~-) with basis (SID) and stable letters P then a word on ^s~~- is p-reduced (for a fixed p E P) if W contains no pinches of the forms p -1c p or

C -1

p p as subwords. Moreover, W is p-reduced if W is p-re- duced for all p E P •

Boone 1966 p. 57 defines p- reduction of a word. We shall use p -reduction in a special case.

Definition_l. Let (S*!D*) be a Britton extension of (S!D) with stable letters P •

Let p E P and suppose all relations in D* involving p are of the form p-1_xp

=

^{X • Let W and W'} be words on S* • Then W' is a p-reduction of W iff W contains a pinch

-e₀ e

p p ( e = ±1) and W' is the result of replacing p-e C pe by

c .

Definition 8. A set X is called a free set of generators in G if the subgroup F generated by X is free on X •

Lemma 2. Let G* be a Britton extension of G with stab~

letters P • Let F be a free subgroup of G free on the set X • Let H be a subgroup of G such that F n H

=

[1} • Let P _{1 :::;} P and suppose F 0 A( p)

=

F n B ( p)

= [

^{1 }} for all p E P _{1 •} Let Fo'<- be the subgroup of G* generated by X U P 1 • Then F*

is a free group on the set X U P 1 , and F* n H

=

[1} • Moreover9

suppose H' is a group generated by y

=

[h.p.g. _{J_ J_ J_}

I

1:Si.:Sl} 9

where h. ,g. _{J_ J_} E G

'

^{p. J_ E p 9 p. J_}

I

^{p1 and} Pi

I

Pj if i

I

^j

'

(i

=

^{1,2, ••• ,1; j}

=

^{1,2p •• ,l)}

'

^{then H'} is a free group on ^y and F-1<- n H' ₌ [ 1 }

.

Proof. Let w be a trivially reduced word on P 1 ^lJ X and suppose w ⁼ h in G* for some h E H • We shall prove that this implies w

-

¹

'

which implies that ^F-lf is free on the set X U P₁ and that F* n H = [ ~ I _, 1 • Suppose that w is a word which involves at least one stable letter p E p1 • Since wh-¹

=

¹

in G-X-

'

and since p does not occur in h we have that w contains a pinch of the form _p ^-E:

c

_p ^E:

'

^(E:

⁼

^{±1) where p E p1}

and

c

E A(p) 'IF

=

^{[ 1 ) or}

c =

B(p)

n

F

=

^{[ 1 }} _• ^Hence

c =

¹

and p ^{-e C} p ^e:

=

¹ which contradicts the fact that w is trivi- ally reduced. Hence w involves no letter p E p1

.

^{That is}

w E F since w is a word on _{X •} But F

n

H

=

{ 1 } which shows that w == 1 and h

=

^{1 in G"f} • To prove the last part of the theorem, let w be trivially reduced word on

and 1 e t w

=

u in G

* . /

^{and let}

u be a trivially reduced word on Y ,., /Then in G*

and exactly as before we can prove that w is a word on X and if u contains a pinch of the form p"":" 1 C 1. p. 1. then u contains

-1 -1 -1 . .

a subword of the form gi pi hi hipigi , wh1.ch contrad1.cts the assumption that u is trivially reduced, Moreover, by a similar argument we can prove that u contains no pinch of the form

pi C Pi 1 Hence u ⁼⁼ 1 and w

=

1 in G-J:- • This proves the last part of the lemma.

§4. The Turing machine and the corresponding semigroups (Readers who are not familiar with Turing machines and recursivetheory, may jump to lemma

4.)

We shall use the convention that s₀ is blank.

Definition. T is a Turing machine, its alphabet is the set [s₀ ,s,.,.,sM_ 1 1 of all s-letters occuring in its quadrupms.

If w is a positive word on the non-blank symbols, {s 1 ,s2 , •••

•• ,sM_ 1

1 ,

then T accepts w if there is a computation of T beginning with q1w • (We use ncomputation of T" in the sense of Davis 1958, def. 1,9 p.7.)

Informally, we regard the machine T as being started in state q1 scanning the leftmost symbol in w , then T accepts

w iff it eventually stops. We shall also call w an input to the Turing machine T in the case we are studying the (finite

or infinite) sequence of instantaneous descriptions q1w .... a.2 .... a.3 ... • ¹ We shall say that a set of positive words are recursively enumer- able iff the set of its g~del numbers is recursively enumerable.

Lemma 3. Let E be a recursively enumerable set of po- sitive words on the letters (a 1 ,a2 , ••• ,am} • Then there exists a Turing machine ZE with alphabet S' = [s₀,s 1 ,s 2 ••• ,sM_ 1 } and states Q' = [q1 ,q2 , ••• ,qN_2 } such that

1. (a,a_{2 , •••} ,am} ~ (s 1 ,s^{290 ••} ,sM_ 1 }

2. If w is a positive word on the letters (a1,a2 , ••• ,amJ' then the Tur~ng machine ZE accepts w iff w E E •

Remark. Note that here, and from now on E is a recur- sively enumerable zet of words on (a 1,a2 , ••• ,am} , while in the abstract, and in definition 2, E was a r.e. set of positive words on [u1 ^,u2^,~ •• ,um} •

Proof. Let w be the set of non-negative integers.

Numbers are represented by a sequence of the symbol 1, on its tape. An input is numerical iff it consists of a sequence of 1's, non-negative integers. A subset A of w is recursively enumerable (abbreviated r.e.) iff A=¢ or A= range f for some recursive function f • A basic theorem on r.e. sets says that A is r.e. iff A

=

^domain

w

for some partial recursive function

w .

Since Turing computable is the same as recursive, we have that A is r.e. iff there exists a Turing machine

which accepts the numerical input n iff n E A • Since a Turing maehine can compute the godmnumber of a word w given as input, we obtain lemma 3.

By Post's construction (see Post 1947) or better by Davis modifi- cation of Post's construction we obtain a semigroup T

=

^TE

which corresponds to the r.e. set E. ^T is generated by SUQ, where S

=

S' ^!' [sM1 and Q

=

Q' U [q_₀ ,qN_ 1 ,q_N} We shall write q_ for q_₀ • A word

r

on the letters S U Q is special iff either

r

^s q_₀ ⁵ q_ or

r

^s wqjw' for some j E [0,1,2 •••• N}

and for some positive words w and w' on S = (s₀ ,s_{1 , •••} ,sM}.

Lemma 4. Let E be a recursively enumerable set of words on the letters [a1 ^,a~, ••• ,a} • Then there exists a semigroup

~ m

T

=

TE generated by the set S U Q

where each

r.

:1. and

r.

1. is a special word, such that for each positive word w on the letters [a₁,a_{2 , •••} ,am} we have that (.,'f) hq₁ wh = q_ in T iff w E E •

Moreover

(**)

• -&'

l..l.

w

= q_ in T then

w

- ^q or where

j E [0,1,2, ••• ,N1 and p _and ~~ are positive words

on ( s ^{0 '} s 1 ' ••• ' SM-1 } •

§ 5. Properties of the Boone-Britton Group.

By Britton's modification of Boone's construction we obtain a group G

=

GE such that

Lemma 5. Let E be a r.eo set of positive words on [a₁,a2 , ••• ,am} • Then there exists a finitely presented group G

=

GE such that

2 • [a _{1 ,} a 2 , • o o , am } ^{,S [} s _{1 ,} s 2 , • o • , sM} • 3. If ~ is a special word then

k-¹ r:-¹ t ^L' k

= r-

¹ t I: in GE iff I:

=

q in T E • 4. If w is a positive word on [a₁,a2 , ••• ,am1 then

k-¹(hq₁wh)-¹t(hq₁wh)k = (hq₁wh)-¹t(hq₁wh) iff w ^E E • It turns out that we need to know more about Boone's group.

In order to prove lemma 11 we start with the following lemma.

Lemma 6. The subgroup of G generated by the set S U Q lJ [t} is free on this set.

Proof. The detail of the proof is left to the reader, since by using lemma 2, the proof becomes easy, although some- what lengthy, since many details have to be checked.

We first prove that the group generated by S U Q is free on this set, by repeated application of lemma 2o Then we prove that the group generated by S U [p₀ ,p_{1 , •••} ,pN,z} in H2 is free on this set. (See page 24 of Britton 63, next to the last line o) Hence S ! J Q is a free set of generators in G2 • By application of lemma 2 again we can complete the proof of lemma6.

Lemma 7o The subgroup of G generated by the set S U Q U [k} is free on this set.

Proof. Let

G1

^{= (} G2 ,k^{' -1 1}k xk = x, k rik ^-1

=

ri, Then we have that G = (G 1 ,tlt- 1yt = ^y, t- 1l.t = 1.,

~ ~

t- 1 (qkq- 1 )t =qkq- 1 , (i=1,2, ••• ,P)) • Hence G'

1 is a Britton extension of G2 with stable letter k and G is a Britton extension of G1 with stable letter t Hence lemma

7

can be proved in the same way as lemma

6.

This completes the proof of lemma

7.

By modification of Britton's proof we can prove.

Lemma 8. Let 6 be a word on and let 6 be trivially reduced.

so,s1 '• • • ,sM,q'qo,q1 '• • • ,qN Then k- 16- 1t6k = 6- 1t6 im- plies that 6 is a special word.

Proof. First we shall show that 6 contains exactly one

occ~ce of a symbol from the alphabet (q₀,q 1 , .•• ,qN} • ^Exac~

as in equation (4) on p.25 in Britton 1963 we can prove that ( 4') 6 = N ₀ z ⁱ¹ N 1 z •. ^{~ ~} Nb_ 1 z Nb = Lp z R ^ib

where N₀ ,N1 , •.• ,Nb are words on s0,s 1 , ••• ,sM, p0 ,p 1 , ••• ,pN, and where L is a word on ¹₁ ^,1₂^~ •.• ^,~,y and where R is a word on r 1,r2 , ••• ,rp,x •

Let K be the group generated by Then K

n

A(z) = ¹ and K

n

B(z)=1 proof of lemma 6). Since ^{( 4 I )} implies

(4")

R-1z-1p-1L-1Nozi1N1zi2 we have by Britton's lemma that some C E B(z) we have

( 4" ) 1 i2 ib

R- C N 1 z • • • Nb_ 1 z Nb = 1 •

s _{0 '} s 1 ' •.• , SM' p o ' p 1 ,. • • ,pN •

by lemma 2, (see the

Hence for

But since Kf! A(z) = 1, and K

n

B(z)=1ani since K,A(z) and B(z) are free groups and ~ is freely reduced, we have that b = ¹ and i₁ = ¹

Hence we have that

where ^F and ^G are word on [s_{0 ,} s1 , ••• , sM} •

It remains to prove that F and G are positive words. To

prove that we change lemma 8 on page 26 in Britton 1963 to read as follows:

"Lemma 8' • Let F and G be reduced words on [s₀,s_{1 , •••}

• ,sM} and let ~ ~ FqsG. If v_{1 , •••} ,vn and e_{1 , •••} ,en and words L (in 1i,y), R (in ri,x) exist such that (6) and (7) hold, then ~ is a positive word (and hence a special word), moreover, in the semigroup T , ~ can be transformed into q by a sequence of at most n elementary transformations".

Proof. The proof is by induction on n as before. The first place we have to change the proof is in part (s) on page

27.

Change the second paragraph of part (s) to read as follows:

"The reader is reminded that, in

(8),

F and H. are tri-

l

vi ally reduced words (possibly empty) in the sb

'

and Hi is even a positive word; and ^y is a word in y only. We shall prove that F has the form F ^~ UHV (i.e., the form UH.) 9 for

1 ^l

some reduced word U Now reduced words Yv', F' , Hj_ in the sb certainly exist such that W and H! are positive and such that

l

FE F'W 9 Hi - H~W , and suppose W has maximal length, so it is sufficient to prove that H! s 1 •

l Assume that H'. _l

I

^{1 •}

The rest of part (s) may be left almost unchanged. We shall here quote some basic facts and add some new facts:

Since 6

=

^FqsG

formed into the word

=

^{UH. qg K. V 9 the word} 6 can be trans-

l i l

6 *

=

^{UF i qs. G i V} by one elementary trans-

"") J.. *)

formation, as before. By (6*)'' and {J*) we obtain that 6*

=

F* a G-><-

=

^{UF. q G. V} is a special word, and 6

*

can be trans- 13i J.. si J..

formed into q in at most n-1 steps. Hence U and V are positive words, and since Hi and Ki are positive words, we obtain that UH. q K.V ~ 6

J.. gi J.. is a special word, moreover can be transformed into q in at most n steps. Vfhen e 1

=-

1 only slight changes have to be made as before. This completes the proof of the revised lemma 8'.

Hence our lemma 8 is proved.

Remark. A shorter proof of our lemma 8, may be possible by applying lemma 26, p.74 in Boone 1966, and some other results in his paper.

Lemma 9.

Suppose

Proof. Since the group obtained by adding the relation k = 1 G is isomorphic to G1 , the group obtained by deleting k as generator and deleting all relations containing k we have that k -1 -1 61 t62k

=

63 t64 -1 implies 61 t62 -1

=

63 t64 -1 • Hence

61 ^;;: 63 and 62

=

⁶⁴ since the letters in -1

61 t62 and 63 t64 ^-1 form a free set of generators, by lemma 7. In the same way, by adding the relation t

=

1 to G which is isomorphic to the

*)

(See Britton 1963 p,29)

group

G1

⁹ obtained by deleting t from the generators and deleting all relations in the presentation of G which contain t we obtain that k- 161 1t6 2k

=

63 1t6

4

^{and t}

=

1 implies

-1 -1 -1

k 6₁ 6_2k

=

6₃ 6_{4 •} Hence 6₁

=

⁶2 and Hence

d k -1 -1t k -1

6₂

=

⁶_{3 -} ⁶₄ ^{an 6}1 6₁ = 6₁ t6₁ hence is a special word by lemma 8 • This proves lemma 9.

Lemma 10. Let H1 be the subgroup of G ⁼ GE generated by

(1) S U Q ^IJ (t,k}

Then H has the presentation:

(2)

( s u

Q \ I ( t 'k}

I

k- 1 2:-1 _{t 2:} k cial word and 2:

=

^q in T • )

= L: -1 t I: , where is a spe-

Proof. Let

-·

^{H' 1} be a group having the presentation above.

Let w be a word on the letters (1). Suppose w

=

1 in H1 , then w = 1 in H₁ by lemma 7 on page 23 of Britton 63.

Suppose w = 1 in H₁ and w

I

1 in H1 • We shall prove that this leads to a contradiction. We may choose w to have as few occUITBnces of k as possible. From lemma 6 and 7 follows that w must contain at least two occunrences of t and two occurrences

of k •

Since w

=

1 in H1 we also have w

=

^{1 in G By}

Britton's lemma we have that vr must contain a pinch of the form k-⁸Ck⁸ (e:

=

^{±1 ) ' where}

c

E A(k) = B(k) _• Hence k-e:Ck⁸

= c

in H1 • Suppose k-⁸Ck⁸

= c

is true in H' _{1 •} Then w

=

^{Vl I in}

H' where W'

1 is obtained from w by replacing k-e:Cke: in w by

c

_• Then w'

=

^{1 in} H1 ^{and w'}

= \.' I

1 in H'

1 ^•

Since w' contains a smaller number of occurrences of k than w

'

this contradicts the fact that w is minimal. Hence

k- 1Ck

=

C in H1 but k- 1Ck

I c

in H' 1

Let w"

=

k- 1CkC- 1 Then w"

=

¹ in H1 and w"

I

1 in

H1 ,

moreover w" contains just two occurrences of k • The from;

group G of Britton (see p.28 of Britton 63), is obtained G2^~r Britton extension as follows: G1 ⁼

(i =

1~2,

••• ,P)) G = (G 1;k

I

k- 1rik

-1 ) )

=

^{q tq i}

=

1,2, .•• ,P • Here t

(

_{G2 ; t}

I

t ^-1 1. t = 1. , t ^-1 yt = y,

~ ~

-1 -1( -1 )

= r., k xk = x, k q tq k

~

is first added as stable letter and then k is added as stable letter in the second ex- tension. But we may as well obtain G from G2 by first adding k as stabfhe letter and then t in the next extension;

( I

^{1 -1 -1( -1)..1.. -1}

G2

=

G1 ;t t- lit= li,t yt

=

y, t qkq u = qkq

(i

=

1,2p •• ,P)) Among the words w on the letters S U Q U [t,q} choose a w such that

1 . w = 1 in H1 2. w

I

^{1 in H'} ₁

3. w contains just two occurrences of k

.

4.

w contains as few occurrences of t as possible.

We can now prove that w contains just two occurrences of t by using the fact that G is a Britton extension of G' _{1 •} The proof is analogous to the proof above. Hence w contains no more than two occurrences of k and two occurrences of t • By using Britton's lemma and lemma 9 it is easy to prove that w = 1 in H' , also. Hence we have a contradiction which proves

1

lemma 10.

Lemma 11.

Then the subgroup of G generated by a₁,a_{2 , •••} ,am,t₀ ,k₀ has the presentation:

w positive word on (a1, ••• ,am} and wEE.)

Proof. in T

=

^TE by lemma 4 we obtain lemma 11 from lemma 10, since k- 1w- 1t wk _{0 0 0}

= -

w 1t ow iff

k~

¹

(hq 1 ^wh)-

¹

^t 0 ^(hq 1 ^wh)

⁼ (hq1wh)- 1"t(hq1wh) •

Note that our lemma 1i corresponds to lemma 5.1 p.473 in Higman 1961 and to lemma 18 p.335 in Shoenfield 1967.

§ 6 • Completion of the proof.

be the result of replacing all occurrences of a.

J. in w by u.

J.

for all i

=

1,2, .•• ,m, simultaneously. Moreover wb is def~d

to be a word on the letters [b 1 ,b 2 , ••• ,bm} in the same way, ( Example ( a 1a 2a 3 u -1)

=

u 1u 2u 3 , and -1 ( a 1a 2a 3 b -1)

=

_{b 1b2b3} -1) ^{• Let}

R

= (

u 1 , u 2 , ••• , urn

I

^wu

=

1 , ( w E E))

Let G4 be the free product of G

=

GE end R . i.e.

G4

=

^G

*

R •

We shall now consider a sequence of extensions of G4 and prove that we have a sequence of Britton extensions.

=

u. ~

J

b. a.b. -1 = a.,

l J l J

-1 -1 )

b. k b.

=

k u. , for all i,j

=

1,2, ••• ,m

l 0 l 0 l

G6 = (G ·d 5'

I

^{d- 1k d 0} = _ko' d ^-1 a.b.d ^{l l .} = ai' all i = 1,2, ••• ,m) G7 ⁼ (G6;p

I

P ^-1t oP ^{= t d,} ₀ P ^-1k oP ^{= k} o' ^{P -1 a.p l = a. l}

all i

=

^{1,2, ••• ,m)}

Lemma 12. The subgroups (a_{1 , •••} ,am,k₀

>

₄ and

(a_{1 , •••} ,am,t_{0 )} 4 ^{of G}4 are free on the displayed generating sets,

Remark.

- -

The subscript

4

indicates that the subgroups are computed in G4 , i.e., only the relations of G4 are used.

Proof. Lemma 12 is an immediate consequence of lemma 11.

Lemma

..Jl..

G5 is a Britton extension of G4 •

Proof. By lemma 12 we have

hence the mapping cp.(u.) = u.,cp.(a.)

l J J l J and cp. (k ) _{l 0}

=

^{k u-:- 1} _{0 l}

may be extended to a homomorphism of onto B(bi) • Since B(b.) = A(b.)

l l

cp.(a.) ⁼

l J

phism of

and the map

*. (

l ^u.) J given by ~.(u.) = u.,

l J J

1~ • ( k ) = k u. can be extended to a homomor-

l 0 0 l

into A(bi) , and since the extension of 'Vi is the inverse of the extension cp.

l we have that is an isomor- phism. This shows that the isomorphism condition holds and

lemma 13 is proved.

Lemma 14. G6 is a Britton extension of G5 •

Proof. Let G I = ( G5

I

b. = u. = 1)

5 ^{~ ~} Then G'

5 is isomor- phic to G4 Since (a1 ,a2 , ••• ,am,k0 )4 is a free group on the displayed letters, (a1 ,a2 , •• ., ,am,k0 ) and (a₁ b 1 ,a2b2 , •••

•• ,ambm,k_{0 )} are also free groups on the displayed letters in

G5

and then also in G5 ^~ This makes it easy to prove that the isomorphism condition holds. The rest of the proof of lemma 14 is left to the reader.

Definition. Let G' G' G¹ G' be the result of deleting 4' 5' 6' 7

all the relationsof the form wu = 1 , w E E in the presentations of G4 , G5 , G6 , G7 , respectively.

Lemma 15. Let the presentation of H be an extension of the presentation of' G' _•

6 Let w be a word on the letters [ a1 ' a2' • • • ' am}

.

Then ^w u ⁼ 1 in H iff ^k -1 0 wbk = wb 0 in ^H

Proof. Since b. k b. ^-1 _{~ 0 ~}

=

^k ₀ ^{u. -1} _~ is a defining relation in G' and hence also in

5 ' G'

6 and H , we have that k ^-1 b.k =b.u.

0 ~ 0 ~ ~

Since and Hence if w = 1

u in

commute, vre also have H then k -1 w k

=

wb

0 0 0

ko wbko -1

=

in H

•

; f k- 1 k

... o wb o

=

wb then = 1 • This proves lemma 15.

Lemma 16. Let the presentation of H be an extension of the presentation of G' _{6 •} Let w be a word on the letters

[a1 9a2 , ••• ,am} ^j and suppose

k-¹w-¹t dwk

=

w-¹t dw in H iff

0 0 0

Proof. Since a. and b.

J. J

da.

=

a.b.d in H , we have that

J. J. J.

(8)

w _u

=

¹ in H .

in H •

commute in H , and since

Then

Her·e k₀ commutes with d

-1

and we have supposed that k₀ com- mutes with w t w . Hence

0

k-¹w-¹t dwk

=

w-¹t dw

0 0 0 0

~

-1 ( -1 ) ^-1

k₀ w t₀w wbdk₀

=

^{w t} 0\vvrbd

~

(w- 1t w)k- 1wbk d

=

^{(w- 1t}0w)wbd

0 0 0

~

k- 1w k _{0 b 0}

=

^w

~

^b

\\- w _{= 1 •}

u This proves lemma 16.

(by ( 8))

(by the hypothesis)

(by cancelation)

by lemma 15.

Lemma 17. G7 is a Britton extension of G6 •

Proof. The group A(p) has the presentation

( 9) , w E E )

by lemma 11, since G is embedded in G6 •

In order to prove that the isomorphism condition holds, it is sufficient to prove that the group B(p)

=

<a1 ,a2 , ..• ,am,td,k0 )6

(where td = t₀d) has the presentation

B ' = ( a₁,a_{2 , •••} ,am, td,lt, k

I

^{-1 -1} ₀ w tdwk₀ = w tdw, ^-1 w E E )

Let w E E . Then in by lemma 11

and w

b ^{= 1} in G6 by definition. Since· the presentation of G6 is an extension of the presentation of G'

6

'

we have by lemma 16 that k^{-1 -1} ₀ w tdwk₀

=

w tdw in G6 and hence also in ^-1 B(p) _• Let

w

be a word on the generators of B' _• Suppose

w

^{= 1} in B' _• Then

w =

^{1 in B(p)} since B(p) satisfies the definL~g relation of B' Suppose

w =

^{1 in B(p)} • Let

G"

=

(G 6

I

^ui

=

¹

'

^b.

=

^{1 d}

=

¹

'

^td

=

^{t )}

6 ^{1. 0}

Then G"

6 is a homomorphic image of G" is isomorphic to G • Hence

w =

1 in G"

6 Let Vi' be the result of re- placing td by t₀ in W

a word on the generators of

Then VI' = 1 in G" but

6 ' W' is

G and G is isomorphic to G" •

6

Hence W' = 1 in G and so W'

=

1 in A(p) • But A(p) and B' are isomorphic by definition. Hence W

=

1 in B' • This proves lemma 17 .

Lemma 18.

G7

is isomorphic to

G _{7 ,} G7

is finitely pre- sented and R is embedded in

Proof. Recall that G' 7 relations of the form wu ^{= 1}

'

that all the relations w = 1 u Let w E E

( 1 0)

Hence

• Then

=

w -1 t w

0 0

is the result of deleting all the (w E E ⁾ in G

7 We shall prove

'

^{(w E E)·} can be proved in G' 7 ^•

(12)

=

w t dw ^-1

0 since p commutes with all letters in (10) except and P - 1t oP

=

t d o •

The presentation of G'

7 is an extension of the presentation of

G6

Hence by (10), (12) and lemma 16 we have wu

=

^{1 in G'}

7 ' is ob- as desired. Hence G? and G7 are isomorphic and G'

7

viously finitely presented. Moreover, since G

7

is obtained from G4 by a sequence of Britton extensions, we have that R is embedded in Hence R is embedded in This com- pletes the proof of lemma 18. Since R was an arbitrary recur- sively presented group, this also proves lemma 1.

Acknowledgments. July 1970 I wrote an outline of this paper.

I am very gratefull to professor W.W. Boone, Dr. Miller and D.J. Collins for proposing some simplifications and for encour- aging me to write up my work and get it published. I am especi- ally gratefull to professor W.W. Boone, without his encouragmment this paper would hardly have been written. I would also like to thank professor J.J. Rotman. He has given me an early draft of chapter 12 of the second edition of his book in group theory.

I have benefitted form his exposition in some places.

References

Boone~ W.W. 1959, The word problem. Ann. of Math., 70,207-265.

Boone, W.W. 1966, Word problems and recursively enumerable de~rees

of unsolvability. A sequel on finitely presented groups

Ann.

of Math., 84, 49-84.

Britton~ D.J.L. 1963, The word problem.

Ann.

of Math., 77, 16-32.

Davis, M. 1958, Computability and unsolvability. McGraw-Hill Book Company, New York.

Higman~ E.G. 1961, ~bgroups of finity presented groups. Proc.

Royal Soc. London Series A, 262, 455-475.

Post, E.L. 1947, Recursive unsolvability of a problem of Tbue.

J. Symb. Logic, 12, 1-11.

Rogers~ Hartley Jr. 1967, Theory of Recursive Functions and Effective Computability. McGravv-Hill, New York.

Rotman, I.J.J. 1965, The Theory of Groups~ An Introduction, Alyn and Bacon, 1965. (Second edition to appear.) Shoenfield, Joseph R. 1967, Mathematical Logic. Addison-Wesley.