ELECTRONIC RESEARCH ANNOUNCEMENTS OF THE AMERICAN MATHEMATICAL SOCIETY Volume 3, Pages 28–37 (April 9, 1997) S 1079-6762(97)00020-6

LEFT-DISTRIBUTIVE EMBEDDING ALGEBRAS

RANDALL DOUGHERTY AND THOMAS JECH

(Communicated by Alexander Kechris)

Abstract. We consider algebras with one binary operation · and one generator, satisfying the left distributive law a·(b·c) = (a·b)·(a·c); such algebras have been shown to have surprising connections with set-theoretic large cardinals and with braid groups. One can construct a sequence of finite left-distributive algebras A_{n}, and then take a limit to get an infinite left-distributive algebra A_{∞} on one generator. Results of Laver and Steel assuming a strong large cardinal axiom imply that A_{∞} is free; it is open whether the freeness of A_{∞} can be proved without the large cardinal assumption, or even in Peano arithmetic. The main result of this paper is the equivalence of this problem with the existence of a certain left-distributive algebra of increasing functions on natural numbers, called an embedding algebra, which emulates some properties of functions on the large cardinal. Using this and results of the first author, we conclude that the freeness of A_{∞} is unprovable in primitive recursive arithmetic.

1. Introduction

We consider algebras with one binary operation · and one generator satisfying the left distributive law a · (b · c) = (a · b) · (a · c).

Such algebras became an object of study when they appeared in a set-theoretic context: Laver [10] studied the properties of an algebra of elementary embeddings arising from an extremely large cardinal. He used these properties to prove purely algebraic results about the free left-distributive algebra on one generator; for instance, he showed that the word problem for this algebra is decidable. However, this was under the assumption that a large cardinal exists.

Later Dehornoy [3] proved these algebraic results using a completely different construction based on braid groups and generalizations of them, thus eliminating the large cardinal hypothesis. (Perhaps even more surprising, results about leftdistributive algebras have recently been used to prove theorems about braid groups; see Dehornoy [4].)

But further algebraic results were obtainable from the large cardinal. Laver [11] used restrictions of the original elementary embeddings to produce a sequence of

Received by the editors December 16, 1996. 1991 Mathematics Subject Classification. Primary 20N02; Secondary 03E55, 08B20. Key words and phrases. Left-distributive algebras, elementary embeddings, critical points,

large cardinals, primitive recursive arithmetic.

The first author was supported by NSF grant number DMS-9158092 and by a grant from the Sloan Foundation.

The second author was supported by NSF grant number DMS-9401275.

\begin{matrix}c \\ ◯ \end{matrix}1997 American Mathematical Society

finite left-distributive algebras A_{n}; these algebras can also be constructed directly, without large cardinals. One can then take a limit of these algebras to get an infinite left-distributive algebra A_{∞} on one generator.

In the large cardinal context, it turns out that such a limit yields the original algebra of elementary embeddings, so it is free on one generator. So “A_{∞} is free” is another statement about small (finite or countable) algebras proved from a large cardinal hypothesis. This statement can be rephrased in purely algebraic form, as an assertion that certain equations do not imply certain other equations under the left distributive law.

It is now natural to ask whether the freeness of A_{∞} can be proved without the large cardinal assumption, or even at the level of basic arithmetic (Dehornoy’s proofs can be formalized at that level). The results we present here provide, to some extent, a negative answer to this question; we show that the freeness of A_{∞} cannot be proved at a low level (Primitive Recursive Arithmetic, or PRA, which is often referred to as the formal version of Hilbert’s ‘finitistic reasoning’).

The main result of this paper is the equivalence of “A_{∞} is free” with the existence of a certain algebra of increasing functions on the set ℕ of natural numbers. We introduce embedding algebras, which are algebras (A, ·) of increasing functions a: ℕ → ℕ endowed with a binary operation ·. The axioms for embedding algebras state that the operation · is left-distributive and that, if cr(a) is the least number moved by a (assuming a is not the identity), then cr(a · b) = a(cr(b)). If a nontrivial embedding algebra (one which contains a function other than the identity) exists, then A_{∞} is free; conversely, we construct a nontrivial embedding algebra under the assumption that A_{∞} is free.

The first author proved [5] that the elementary embeddings from the large cardinal above yield numerical functions which grow faster than any primitive recursive function, and hence cannot be proved to exist in PRA. The properties of embedding algebras allow us to emulate this construction and produce the same fast-growing functions. Therefore, the existence of nontrivial embedding algebras, and hence the freeness of A_{∞}, cannot be proved in PRA.

In Sections 2 to 5 we outline the main results. Full proofs will appear elsewhere [7].

2. Free left-distributive algebras and elementary embeddings

We consider algebras with one binary operation · generated by a single element that we denote by the symbol 1. We shall often write ab instead of a · b, and use the convention that abc = (ab)c.

The left distributive law is the identity

a(bc) = ab(ac). (LD)

Let W = W_{A} be the set of all words built up from 1 using the operation ·. Denote by ≡ (or by ≡_{A}) the equivalence relation on W given by: a ≡ b iff the equation a = b is a consequence of (LD). Then A = W/≡ is the free left-distributive algebra on one generator.

For the rest of this section, let (A, ·) be a left-distributive algebra generated by 1. We will summarize the relevant known results on such algebras.

Definition 2.1. For a, b ∈ A, say that a is a left subterm of b, or a <_{L} b, if, for some c_{1}, …, c_{k} (k > 0), b = ac_{1} ⋯ c_{k}.

Clearly the relation <_{L} is transitive.

Theorem 2.2 (Dehornoy [1]). On the free algebra A, the relation <_{L} is connected: for all a, b ∈ A, either a = b or a <_{L} b or b <_{L} a.

It follows that <_{L} is connected in any monogenic (i.e., generated by one element) left-distributive algebra (A, ·). Therefore, <_{L} is a strict linear ordering of A if and only if it is irreflexive, i.e., a ≮_{L} a for all a.

Lemma 2.3 (Dehornoy [1]). If the relation <_{L} on A is irreflexive, then (A, ·) is free and satisfies left cancellation.

Theorem 2.4 (Dehornoy [3]). There is an algebra (A, ·) on which <_{L} is irreflexive. Consequently, the free algebra is linearly ordered by <_{L} and satisfies left cancellation.

These results were also proved by Laver [10] under a large cardinal assumption (see below).

All of the steps in Dehornoy’s proofs are accomplished by explicit recursions and inductions, and the recursions are in fact primitive recursions. Therefore, these results can be proved in a very basic theory of arithmetic, such as Primitive Recursive Arithmetic (PRA). PRA is formalized in a language containing function symbols for all possible function definitions using the constant 0, the successor function ′, composition, and primitive recursion; it has axioms stating that the function symbols satisfy their definitions, and that 0′ ≠ 0, and a rule of inference allowing induction on quantifier-free formulas. (See Sieg [12] for more details.) This theory is among the weakest of the commonly studied fragments of arithmetic. It is not hard to show that the methods used to prove the above results can be formalized in this theory.

Now consider algebras with two binary operations · and ∘. We use the conventions ab ∘ c = (ab) ∘ c and a ∘ bc = a ∘ (bc). Let W_{P} be the set of all words built up from 1 using both operations, and let P be the free algebra on one generator under the identities:

\begin{matrix}a ∘ (b ∘ c) = (a ∘ b) ∘ c, \\ (a ∘ b)c = a(bc), \\ a(b ∘ c) = ab ∘ ac, \\ a ∘ b = ab ∘ a. \end{matrix} (LL)

Then P = W_{P}/ ≡_{P}, where a ≡_{P} b iff the equation a = b is a consequence of (LL). Note that (LD) is provable from (LL):

a(bc) = (a ∘ b)c = (ab ∘ a)c = ab(ac).

The motivation for axioms (LL) comes from large cardinal theory. Let V_{λ} be the collection of all sets of rank less than λ, where λ is a limit ordinal. If E is the set of all elementary embeddings from V_{λ} to V_{λ}, then one can ‘almost’ define a binary operation · on E by: j · k is the result of applying j to k. This does not quite work, because k is too large to be in the domain of j. Instead, one can break k into pieces which are small enough for j to digest, and recombine the results:

j · k = ⋃_{α<λ} j(k ∩ V_{α}).

Then j · k will also be in E, and it is easy to show that the operation · is leftdistributive and, together with the operation ∘ of composition, satisfies (LL).

If j is a nontrivial elementary embedding from V_{λ} to V_{λ}, let (A_{j}, ·) and (P_{j}, ·, ∘) be the subalgebras of (E, ·) and (E, ·, ∘) generated by j. Laver [10] shows, among other things, that (A_{j}, ·) and (P_{j}, ·, ∘) are respectively the free monogenic left-distributive algebra and the free monogenic algebra satisfying axioms (LL).

Again, we summarize some known facts about algebras (P, ·, ∘).

Clearly an algebra satisfying (LL) yields an algebra satisfying (LD), simply by dropping the second operation (and taking a subalgebra, if we want the result to be monogenic). But one can move in the other direction as well:

Proposition 2.5 (Laver [10], Dehornoy [2, Prop. 2]). Any algebra (A, ·) satisfying (LD) can be extended and expanded to an algebra (P, ·, ∘) satisfying (LL).

Proposition 2.6. Let (P, ·, ∘) be an algebra satisfying (LL) and generated by 1, and let (A, ·) be the subalgebra of (P, ·) generated by 1. Then (P, ·, ∘) is a free (LL)-algebra if and only if (A, ·) is a free left-distributive algebra.

The proof of Propostion 2.6 can be carried out in PRA.

Now consider the algebras A_{j} and P_{j} of elementary embeddings. For each nontrivial elementary embedding a from V_{λ} to itself, let cr(a) be the critical point of a, i.e., the least ordinal moved by a. Let Γ be the set of all ordinals which are critical points of elements of A_{j}. We note that

cr(ab) = a(cr(b)), cr(a ∘ b) = min(cr(a), cr(b)).

Consequently, the critical point of every a ∈ P_{j} is in Γ, and every a ∈ P_{j} maps Γ into Γ.

Theorem 2.7 (Laver and Steel [11]). The set Γ has order type ω.

Theorem 2.8 (Laver [11]). For every a, b ∈ A_{j}, if a ≠ b, then a(γ) ≠ b(γ) for some γ ∈ Γ.

One can adjoin to P_{j} the identity embedding id. The extended algebra still satisfies axioms (LL), as well as these rules:

id · a = a, a · id = id, a ∘ id = id ∘ a = a.

3. A limit of finite left-distributive algebras

In this section, we describe, for each natural number n, an algebra A_{n} on {0, 1, …, 2^{n} −1} with a binary operation ∗_{n} satisfying the left distributive law. We also describe a second operation ∘_{n} on this set so that the resulting two-operation algebra P_{n} satisfies (LL). We then construct limit algebras (A_{∞}, ·) and (P_{∞}, ·, ∘).

The construction of these finite algebras is due to Laver; Wehrung proved some additional properties of them. The proof of the following theorem has been reconstructed independently by several people, including the authors.

Theorem 3.1 (mostly Laver). There are unique operations ∗_{n} and ∘_{n} on the set A_{n} = P_{n} = {0, 1, …, 2^{n} − 1} such that the axioms (LL) hold and, for all a ∈ P_{n},

a ∗_{n} 1 = a + 1 mod 2^{n}.

The operation ∗_{n} can be defined by an explicit double recursion (which is more naturally performed over {1, 2, …, 2^{n}} rather than {0, 1, …, 2^{n} − 1}); then ∘_{n} can be defined by the formula a ∘_{n} b = (a ∗_{n} (b + 1)) − 1, where the addition and subtraction are performed modulo 2^{n}. The theorem is then proved by multiple inductions. Along the way, one obtains additional results: reduction modulo 2^{n} is a homomorphism from P_{m} onto P_{n} for m ≥ n; and, for each a ∈ A_{n}, the sequence a ∗_{n} 0, a ∗_{n} 1, … is periodic with period 2^{k} for some k ≤ n depending on a.

The element 0 of P_{n} plays the role that the identity embedding played at the end of Section 2:

0 ∗ a = a, a ∗ 0 = 0, a ∘ 0 = 0 ∘ a = a.

The element 1 is the generator of A_{n} and P_{n} (for n > 0).

Recall that W_{A} and W_{P} are the sets of words built up from 1 using · and using ·, ∘, respectively. For m > 0, let w_{m} ∈ W_{A} be the product 1 · 1 · . . . · 1 with m 1’s, associated to the left as usual. (In fact, it is often convenient to just write m for w_{m} when the context makes this clear. Note that w_{m} evaluates to m in A_{n} whenever m < 2^{n}.) Also, let u_{k} ∈ W_{A} be the product 1 · (1 · . . . (1 · 1) …) of (k + 1) 1’s associated to the right.

The algebras A_{n} have a natural purely algebraic definition: Wehrung [13] (see also Drápal [8]) showed that A_{n} is the free algebra on one generator 1 subject to the left distributive law and the equation w_{2^{n}} · 1 = 1 (i.e., w_{2^{n}+1} = 1). If m is not a power of 2, then the free algebra subject to (LD) and the equation w_{m} · 1 = 1 works out to be A_{n}, where 2^{n} is the largest power of 2 which divides m.

For every word a ∈ W_{P} and every n ≥ 0, let [a]_{n} be the value of a in P_{n}. Consider the equivalence relation ≡_{∞} defined by:

a ≡_{∞} b iff [a]_{n} = [b]_{n} for all n ≥ 0.

Let A_{∞} and P_{∞} be, respectively, the quotients by ≡_{∞} of W_{A} and W_{P}. Then · and ∘ are well defined on the quotients, and (A_{∞}, ·) and (P_{∞}, ·, ∘) are generated by 1; also, they satisfy (LD) and (LL), respectively, because A_{n} and P_{n} do. (In fact, an equivalent definition for A_{∞} and P_{∞} is that they are the subalgebras generated by 1 of the inverse limits of the algebras A_{n} and P_{n}, respectively.) Moreover, A_{∞} ⊆ P_{∞}.

Theorem 3.2. The following are equivalent:

(i) (A_{∞}, ·) is a free left-distributive algebra. (ii) (P_{∞}, ·, ∘) is a free (LL)-algebra. (iii) <_{L} on A_{∞} is irreflexive. (iv) For every a ∈ W_{A}, there is an n such that [a]_{n} ≠ 0.

(v) For every k ≥ 1, there is an n such that [1 · w_{k}]_{n} ≠ 0. (vi) For every k ≥ 0, there is an n such that [u_{k}]_{n} ≠ 0. (vii) For every k ≥ 0, there is an m > 0 such that (LD) together with the equation

w_{m} · 1 = 1 does not imply the equation u_{k} · 1 = 1.

All steps of the proof can be formalized in Primitive Recursive Arithmetic, so Theorem 3.2 is a theorem of PRA.

4. Embedding algebras

In this section, we consider algebras of increasing functions from ℕ to ℕ which imitate the behavior of the algebra of elementary embeddings from Laver [10] on ordinals. The existence of such algebras turns out to be equivalent to the properties in Theorem 3.2. Moreover, this equivalence can be proved (and formulated) in Primitive Recursive Arithmetic.

The algebras have the form (A, ·), where A is a collection of strictly increasing functions from ℕ to ℕ and · is a binary operation on A (which we often denote by juxtaposition). The axioms for the algebra will include the axiom (LD).

Let id be the identity function on ℕ. If f: ℕ → ℕ is strictly increasing and different from id, let cr(f) be the least n such that f(n) > n (the critical point of f). This is analogous to the standard definition for nontrivial elementary embeddings j: V_{λ} → V_{λ}: the critical point of j is the least ordinal moved by j.

Definition 4.1. An embedding algebra is a structure (A, ·), where A is a collection of strictly increasing functions from ℕ to ℕ, · is a left-distributive binary operation on A, and for every a, b ∈ A with b ≠ id, cr(a · b) = a(cr(b)).

The set A need not contain the identity function, but one can extend the operation · to A ∪ {id} in a natural way: a · id = id, id · a = a. An embedding algebra is called nontrivial if it has an element other than id.

We will also need to work with a more abstract and elaborate form of embedding algebra, including much of the machinery Laver constructs for algebras of elementary embeddings.

Definition 4.2. A two-sorted embedding algebra consists of a nonempty set E (the ‘embeddings,’ for which we will use variables a, b, …) and a nonempty set O (the ‘ordinals,’ for which we will use variables α, β, …), together with binary operations · and ∘ on E, a binary relation ≤ on O, a constant id ∈ E, an application operation a, β ↦ a(β) (which will often be written without parentheses) from E × O to O, a function cr: E−{id} → O, and a ternary relation ≡ ⊆ E × O × E, satisfying the following axioms:

• The relation ≤ is a linear ordering of O.

• Embeddings are strictly increasing monotone functions:

β < γ implies aβ < aγ,  and  aβ ≥ β.

• For all a ≠ id, a(cr(a)) > cr(a).

• The operation ∘ represents composition: (a ∘ b)γ = a(bγ).

• The constant id represents the identity:

id(γ) = γ,  a · id = id,  and  id · a = a ∘ id = id ∘ a = a.

• The axioms (LL) hold.

• For each γ, ≡^{γ} is an equivalence relation on E which respects · and ∘; also, if γ ≤ δ and a ≡^{δ} b, then a ≡^{γ} b.

• If a ≡^{γ} b and aδ < γ, then aδ = bδ.

• For any a ≠ id, a ≡^{cr(a)} id.

• Coherence: a ≡^{γ} b implies ca ≡^{cγ} cb.

Again, such an algebra is called nontrivial if there is an embedding other than id. Note that the important ordinals are the critical points, those ordinals of the form cr(a) for some embedding a; if we simply deleted all the other ordinals from O, we would still have a two-sorted embedding algebra.

The results of Laver [10] show that one can make the set of all elementary embeddings from V_{λ} to itself into a two-sorted embedding algebra by letting O be the set of limit ordinals less than λ and defining ≡^{γ} to be Laver’s =^{γ}. Conversely, many of Laver’s arguments about elementary embeddings and their critical points use only the properties of a two-sorted embedding algebra.

If desired, one can restrict E to the embeddings obtained from a single embedding j ≠ id using · and ∘ (along with id), to get a two-sorted embedding algebra generated by a single embedding. From now on, we will call a two-sorted embedding algebra monogenic if its embeddings are generated from a single non-identity embedding via · and ∘.

The main result of this paper is the following theorem.

Theorem 4.3. The following are equivalent:

(i) (A_{∞}, ·) is a free left-distributive algebra. (ii) There exists a nontrivial embedding algebra. (iii) There exists a nontrivial two-sorted embedding algebra in which the ordinals

have order type ω.

In order to prove Theorem 4.3, we need to perform a number of the arguments of Laver [11] in the context of two-sorted embedding algebras. This is straightforward for arguments involving only the operations which are built into these algebras, but some arguments use additional features of elementary embeddings. In particular, a few arguments use ordinals of the form a(<γ), defined to be the least ordinal greater than a(β) for all β < γ. For this purpose, we will define an even more elaborate algebra which includes this operation, and show that such algebras can be constructed from ordinary two-sorted embedding algebras; this will allow us to use this new operation to prove facts about the original algebra.

Definition 4.4. An extended two-sorted embedding algebra is a two-sorted embedding algebra (with embedding set E and ordinal set O), together with two new operations, a cofinality function cf : O → O and a mapping from E × O to O for which we use the notation a, γ ↦ a(<γ), satisfying the following additional axioms:

a(b(<γ)) = ab(<aγ);
a(<b(<γ)) = (a ∘ b)(<γ);
a(<γ) ≤ aγ;
if γ < δ, then aγ < a(<δ);
if a ≡^{γ} b and a(<δ) ≤ γ, then a(<δ) = b(<δ);
cf(cr(a)) = cr(a);
cf(a(<γ)) = cf γ;
cf(aγ) = a(cf γ);
cf γ ≤ γ;
if a(cf γ) = cf γ, then a(<γ) = aγ.

Again it is not hard to verify that the axioms for an extended two-sorted embedding algebra hold in the case where E is the set of elementary embeddings on V_{λ} and O is the collection of limit ordinals less than λ [11].

The following is a crucial technical result:

Theorem 4.5. Suppose that we are given a two-sorted embedding algebra, in which every ordinal is a critical point. Then the algebra can be extended to a new twosorted embedding algebra with the same embedding set, on which the required additional operations can be defined so as to give an extended two-sorted embedding algebra.

Theorem 4.5 can be used to transfer various arguments from the context of elementary embeddings to that of two-sorted embedding algebras. One example is the following result, which is proved by following Laver’s proof of Theorem 2.8.

In a two-sorted embedding algebra, let j ≠ id be some embedding, and let A_{j} be the set of embeddings generated from j by the operation · (so each a ∈ A_{j} is given by a word in W_{A} evaluated at j).

Theorem 4.6. Assume that the set of all critical points of elements of A_{j} has order type ω. If a and b are distinct elements of A_{j}, then there is a critical point γ such that a(γ) ≠ b(γ).

We now outline the proof of Theorem 4.3. First, suppose that A_{∞} is free, and hence all of the statements in Theorem 3.2 hold. We build a two-sorted embedding algebra with embedding set P∪{id} and ordinal set ℕ, as follows. For a ∈ P, define cr(a) to be the least n such that [a]_{n+1} ≠ 0, or, equivalently, the largest n such that [a]_{n} = 0. Let a(n) = cr(a · w_{2^{n}}), and define a ≡^{n} b to mean that [a]_{n} = [b]_{n} (where we put [id]_{n} = 0). Then one can prove from the properties of the finite algebras A_{n} that these definitions meet the requirements of a two-sorted embedding algebra.

Next, suppose we have a nontrivial two-sorted embedding algebra in which the ordinals have order type ω. We may take the subalgebra A_{j} generated by some j ≠ id, and then throw away all ordinals that are not critical points of members of A_{j}. The remaining ordinals still have order type ω, so we can relabel them as the natural numbers. By Theorem 4.6, distinct embeddings yield distinct functions from ℕ to ℕ; the resulting set of functions, with the binary operation · transferred from the set of embeddings, forms an embedding algebra.

On the other hand, if we have a nontrivial embedding algebra, then we can turn it into a two-sorted embedding algebra. The set of ordinals will be the set of critical points of the embeddings (which has order type ω, since it is an infinite subset of ℕ). Proposition 2.5 lets us extend the set of embeddings to admit a composition operation; the result of applying composite embeddings a∘b to ordinals is defined by the obvious formula (a ∘ b)(n) = a(b(n)). With more work, one can define suitable equivalence relations ≡^{n} and show that all the axioms of a two-sorted embedding algebra hold.

Finally, again assuming we have a nontrivial two-sorted embedding algebra in which the ordinals have order type ω, we can imitate the arguments of Laver [11] for constructing the finite algebras in the first place, to show that statement (iv) of Theorem 3.2 is true, and hence A_{∞} is free. The only part of this argument that cannot be carried out in two-sorted embedding algebras is the proof of the Laver-Steel result (Theorem 2.7 here), so we have made this a hypothesis instead. This completes the proof outline.

In the process of proving Theorem 4.3, we also obtain the following uniqueness result for monogenic embedding algebras.

Theorem 4.7. If (A, ·) is a monogenic embedding algebra for which every natural number is a critical point, then (A, ·) is the embedding algebra constructed from the algebras A_{n} as above.

Similarly, any monogenic two-sorted embedding algebra in which the ordinals have order type ω and are all critical points must be isomorphic to the one constructed from the algebras A_{n}.

5. The strength of “A_{∞} is free”

Laver’s proof of the irreflexivity of the free left distributive algebra on one generator assumed the existence of a nontrivial elementary embedding from V_{λ} to itself; this is an extremely strong large cardinal hypothesis. (Actually, Laver had noted that the assumption can be reduced to the existence of an n-huge cardinal for each natural number n.) The possibility that the irreflexivity property was strong enough to require large cardinal assumptions for its proof remained until Dehornoy proved the property without such assumptions (in fact, using only Primitive Recursive Arithmetic).

We now consider the statement “A_{∞} is free” (and its equivalent versions). Laver [11] showed that this statement also follows from the existence of a nontrivial elementary embedding j: V_{λ} → V_{λ}. (In fact, one might consider “A_{∞} is free” to be the algebraic content of the set-theoretic Theorem 2.7.) Laver (personal communication) has noted, and the authors have confirmed, that one can use the method of proof of Theorem 2.7 while working with only an n-huge embedding, to get a correspondingly weaker result; hence, the freeness of A_{∞} follows from the existence of an n-huge cardinal for each natural number n.

However, unlike the irreflexivity of the free algebra, the freeness of A_{∞} cannot be proved without some ‘strong’ hypothesis:

Theorem 5.1. The statement “A_{∞} is free” is not provable in Primitive Recursive Arithmetic.

Of course, we assume throughout that PRA is itself consistent.

It is a well-known result from proof theory (see Sieg [12]) that the only recursive functions that can be proved to be total using only PRA are the primitive recursive functions. Therefore, to prove Theorem 5.1, it will suffice to show that PRA+3.2(vi) proves the totality of a recursive function F which is not primitive recursive.

For each natural number n, let F (n) be the largest m such that [u_{n}]_{m} = 0, where u_{n} is the word 1 · (1 · (… (1 · 1) …)) with n + 1 1’s. It follows from 3.2(vi) that F is a total recursive function.

This function can be characterized in another way in terms of the monogenic embedding algebra or two-sorted embedding algebra constructed from the finite algebras. Let j be the generating embedding, and let Γ be the set of all critical points of embeddings in the algebra. Among these critical points are a special sequence κ_{0} < κ_{1} < κ_{2} < ⋯ called the critical sequence of j: κ_{0} = cr(j) and κ_{n+1} = j(κ_{n}). Then F (n) is the number of members of Γ lying below κ_{n}.

The main result of Dougherty [5] shows that, in the context of elementary embeddings from V_{λ} to V_{λ}, the function F defined as in the preceding paragraph grows faster than the Ackermann function, and hence cannot be primitive recursive. However, the methods used in that proof use only the properties of embeddings that follow immediately from the axioms of an embedding algebra or two-sorted embedding algebra. (In fact, all of the proofs in Dougherty [5] can be carried out in any extended two-sorted embedding algebra.) Therefore, the same growth estimates apply to the embedding algebra constructed from the finite algebras, and this requires only the assumption that A_{∞} is free. Therefore, this assumption is too strong to be proved in PRA.

In a sense, the function F gives a measure of the proof-theoretic strength of the statement “A_{∞} is free.” This can be stated precisely as follows.

Proposition 5.2. Any recursive function which is provably total in PRA+“A_{∞} is free” must grow more slowly than F_{m} for some m, where F_{0} = F and F_{m+1} is the iteration of F_{m} (starting at 1, say; that is, F_{m+1}(n) = F_{m}^{n}(1)).

There remain a number of open problems related to these algebras. The main one, of course, is the exact strength of the statement “A_{∞} is free”; the gap between “more than PRA” and “there is an n-huge cardinal for each n” is rather large. More recent results about the finite algebras A_{n} [6], [8], [9] may be steps toward a proof without large cardinals that A_{∞} is free, but the full situation is not at all clear.

References

1. P. Dehornoy, Sur la structure des gerbes libres, C. R. Acad. Sci. Paris Sér. I Math. 309 (1989), 143–148. MR 90j:20146

2. , The adjoint representation of left distributive structures, Comm. Algebra 20 (1992), 1201–1215. MR 93a:20108

3. , Braid groups and left distributive operations, Trans. Amer. Math. Soc. 345 (1994), 115–150. MR 95a:08003

4. , From large cardinals to braids via distributive algebra, J. Knot Theory Ramifications 4 (1995), 33–79. MR 96g:20056

5. R. Dougherty, Critical points in an algebra of elementary embeddings, Ann. Pure Appl. Logic 65 (1993), 211–241. MR 95i:03117

6. , Critical points in an algebra of elementary embeddings, II, Logic: from Foundations to Applications (W. Hodges et al., eds.), Clarendon, Oxford, 1996, pp. 103–136. CMP 97:06

7. R. Dougherty and T. Jech, Finite left-distributive algebras and embedding algebras, Adv. Math. (to appear).

8. A. Drápal, Homomorphisms of primitive left distributive groupoids, Comm. Algebra 22 (1994), 2579–2592. MR 95c:20107

9. , Persistence of cyclic left distributive algebras, J. Pure Appl. Algebra 105 (1995), 137–165. MR 96m:20113

10. R. Laver, The left distributive law and the freeness of an algebra of elementary embeddings, Adv. Math. 91 (1992), 209–231. MR 93b:08008

11. , On the algebra of elementary embeddings of a rank into itself, Adv. Math. 110 (1995), 334–346. MR 96c:03098

12. W. Sieg, Fragments of arithmetic, Ann. Pure Appl. Logic 28 (1985), 33–71. MR 86g:03099 13. F. Wehrung, Gerbes primitives, C. R. Acad. Sci. Paris Sér. I Math. 313 (1991), 357–362. MR

92i:08004

Department of Mathematics, Ohio State University, Columbus, OH 43210

E-mail address: rld@math.ohio-state.edu

Pennsylvania State University, 215 McAllister Building, University Park, PA 16802

E-mail address: jech@math.psu.edu