finite-dimensional operator, w i t h the operator (I | P~) T (aS-*)(P-z ~ I), whose finite-dimen-

sionality is established from the relations

(I | p~) T (aTe_)(p_~ | ]) =
- - E n (I @Ptt) T (a~)) T (t~-') P-x (~) I) ----~sto T (a(s)) (P-u Q PtL) T (t~s).
Thus, Theorem 4 is completely proved9

LITERATURE CITED
i. I . V . Simonenko, "Multidimensional discrete convolutions," Mat. Issled., ~, No. I, 108-
122 (1968).
2. R . G . Douglas and R. Howe, "On the C*-algebra of Toeplitz operators on the quarter-
plane," Trans. Am. Math. Soc., 158, 203-217 (1971).
3. L . I . Sazonov, "Continuous functions of two isometric operators: Noether property and
invertibility," Mat. Issled., 9, No. 2, 126-138 (1974).
4. I. Ts. Gokhberg and N. Ya. Krupnik, Introduction in the Theory of One-Dimensional
Singular Integral Operators [in Russian], Shtiintsa, Kishinev (1973).
5. Yu. Laiterer [J. Leiterer] and A. S. Markus, "The normal solvability of singular inte-
gral operators in symmetric~spaces," Mat. Issled., ~, No. i, 72-82 (1972).
6. J. Dixmier, Les C*-Alg~bres et Leurs Representations, Gauthier-Villars, Paris (1969).

VARIANTS O F T H E AXIOM OF CHOICE IN THE SIMPLE THEORY OF TYPES

A. M. Yakubovich

Cohen [i] has established the independence Of the axiom of choice from the axioms ZF
of set theory. In the present note we investigate the corresponding problem for another
axiomatic set theory -- the simple theory of types9
The indicated problem for the theory of types needs some refinement. The axiom of
choice in the theory of types cannot be formulated at once for all sets. Therefore, the
axiom of choice is formulated separately for each layer of the theory of types.
It is easily shown that the axiom of choice for the n-th layer is deduced in the theory
of types from the axiom of choice for the (n + l)-th layer. A result of the present note is
the proof of the independence of the axiom of choice for the n-th layer for n = 0, i, 2,
9 . . from the axioms of the theory of types, in which the axiom of choice for the (n -- l)-
th layer has been added. In particular, the axiom of choice on the zeroth layer does not
depend on the axioms of the theory of types. The proof uses the method of forcing in ZF.
The notions and notation to be used here are given in [2].
The language of the theory of types contains the variables x k, yk, zk, . . . for k =
O, i, 2, . ., the predicate symbol ~, the connectives -~, &, V, -+, and ~-+, and the quan-
tifiers V and 3. The elementary formulas of the theory of types have the form x ~ Y k+1
Formulas are constructed from the elementary formulas in the usual manner.
The theory of types has the following axioms.
The axioms of extensionality:
x~--___y~ * & x ~ z ~ + ~ . - ~ y ~ z ~ + ~ , w h c r e n = O , 1,2,...
The axioms of separation:
3y~+~Vx ~ (x ~ ~_ y~+~ ~-~ A),
where A is an arbitrary formula that does not contain yn+~, n = 0, i, 2, . ., freely.
The Axiom of Infinity:
(3y ~ #: 0 ) (Vx ~ ~ yD (3zO ~ x~) ~ U {z~ ~ yD.
M. V. Lomonosov Moscow State University. Translated from Matematicheskie Zametki, V01.
30, NO. 2, pp. 269-276, August, 1981. Original article submitted June 7, 1978.

622 0001-4346/81/3012-0622507.50 9 1982 Plenum Publishing Corporation

 We will call the following formula the axiom of choice for the n-th layer of the theory
of types :

AC~ : Vy~+*((Vz"+* ~ yn+2) (z~+, =/= _Q~) -+

- + =Ix~+4 (Fne x n+4 & dom x '~+4 ---- yn+, & (Vz,~+, ~ y,~+2) (x,,+a (z,~+,) ~_ z,~+,)));
it asserts the existence of a choice function for each family of nonempty sets of the (n +
l)-th layer. Let WOn denote the f o r m u l a that asserts the existence of a set of the (n +
2)-th layer, well-ordering the n-th l a y e r of the theory of types. The deducibility of the
following formulas in the theory of types is easily established:
WO,~ ,--* A Cn+,, WO,~+I~ WOn.
THEOREM I. The formula ACn-->ACn+, is not deducible in the theory of types for n = 0,
i, 2, . . . (under the assumption of consistency of ZF).
Let ~ (X) denote the power set of X. Let us define ~ n ( X ) by induction as follows:
~ ~ (X) ~ X, ~"+* (X) ~ ~ (.~ (X)).
It is easily verified that the assertion of the theorem follows from the fact that the
following statement (A) is consistent with ZF for each positive integer n: ~k(~) can be
well-ordered for k ~ n, but ~n+, (~) cannot be well-ordered.
As proved in [2], to prove the statement (A) it is sufficient to show that for each
transitive model ~ of Z F C there exists a c o m p l e t e Boolean a l g e b r a B whose automorphism group 9
J and the normal filter ff of subgroups o f J are such that for each ~ - g e n e r i c ultrafilter
of G the statement (A) is valid in the corresponding symmetric extension ~ of the model ~.
Let ~ be an arbitrary transitive model of ZFC. Let us define certain relations and
sets in ~ . We set ~ ~_ [~i (~)l (ai is the cardinality of ~ (co)),
P~{p:Fncp&domp~an • ar~&rngp~{O, 4} & I d o m p t<an-1}.
For p, q ~ P we set p ~<q if q ~ p .
It has been shown in [3]! that with respect to each partially ordered set. Q we can con-
struct a unique complete Boolean algebra X a n d _ a . h o m o m o r p h i s m e from Q. into x such that e " Q
is dense in X and p a n d q are consistent in Q if and only if ep and eq are consistent in X.
The complete Boolean algebra constructed with respect to Q is denoted by RO(Q). Let us set
B = RO(P).
Let w be a permutation on a n . Let us set ~ (~, ~ ) = ( ~ % , ~) for %, P < an. For p ~ P
we define wp as the function q~P, such that dora q = w" dora p and q (~%, ~) = p (%, ~). Thus,
each permutation of a n induces a permutation of P and, therefore, of B. W e denote the set
of all permutations of B induced by the p e r m u t a t i o n s of a n b y J. It is obvious that ~ is a
subgroup of the automorphism group of the complete Boolean algebra B. For each a~_an we
set

It is obvious that H a is a subgroup of J.

By definition, we set
~- ~- {H: H is a subgroup of ~Y and (:=la C~ ten) (1 a [ < r & Ha ~-- 1t)}.
It is easily shown that ~ is the normal filter of subgroups of ~.
Let G be an arbitrary ~ - g e n e r i c ultrafilter. Let ~ denote the Boolean-valued uni-
verse o f the model ~, i G denote the interpretation defined by the ultrafilter G, ~ [G] de-
note the generic extension of ~, defined by G, and 9 denote the symmetric extension of ~ ,
defined by G, $, and ~-.
If x ~ ~ [G], then by _x we will denote an arbitrary element of ~ such that iG(X~ -----X
(X is the name of x).
As shown in [2], the following two statements are valid for each formula ~ (x..... ~) :
i. If x, . . ., y are the names of the sets x, .., y ~ $~B, then

(~[GI ~ r ..... Y ) ) ~ I I+(z_ . . . . , Y) l i n G .

623
 2. If ~ is an automorphism of B and x, ..., y ~ ~B then
I1~(~ x ..... ~y) II = ~ ( l l ~ ( x ..... y) II).
In the course of the proof of Theorem i, we state and prove some lemmas. The first of
them is actually a reformulation of Lemma 57 of [2].
LEMMA i. Let Q be a partially ordered set and k be a cardinal in 8. Suppose that for
each decreasing sequence (in ~ ) of elements of Q: p o / I - P i / / - - . - > p ~ >1t . . . . ~ < k, there
exists a p ~ Q such that p < p ~ (for all ~ < k). Let f be a function from ~[G] such that
rngf~=~, and d o m f = k.
Then ]~, and if a is a cardinal in ~ such that = ~ < k , then a is a cardinal in ~ [G]
also.
It is easily seen that P satisfies the conditions of the lemma for each k-~< =n-i-
LF2flffA 2. ~ (~) coincide in ~ and in ~ [G] for k ~< n. Moreover, [~(~) [= ~ in
@~[G] for k < n,
Proof, This lemma is proved by induction over k. The assertion is obvious for k = 0.
For k ~ n - - l , let [~z(~)[~[a]---- at, and ~t(~)~[Gl -~-~f(~)~ for all l~.<k. Let X
~#i(~)m[a] X ~ 0. Then X c:_ ~ ( ~ ) . Therefore there exists a function f~ ~ [G] such that
dom f = ak and rng f = X. By Lemma i, we have f ~ . Therefore X----rngf~. Hence
~+~ (~)~ [~ = ~§ (~)~.
Let k < n-- i. Then [.~+i(~) I = ~+i in ~ By Lemma i, ak+~ is a cardinal in ~ [G].
Therefore [~u+i(~)[~[ol _--=~+i. The lemma is proved.

COROLLARY i. ~u(0)) coincide in $~, ~ , and ~ [G] for k ~< n.

This corollary follows from the inclusions $~ ~ ~ c- ~ [G].
COROLLARY 2. ~ (~) can be well-ordered in 9 for k .~< n.
Indeed, there exists a function ] ~ @~ such that f is one-to-one, dom / : ~ ( ~ ) and
rng/~am. This function realizes a one-to-one mapping of ~u (~) onto ak i n ~ ; but a k is an
ordinal in 9 (the formula ord a is absolute). The first part of the statement (A) is proved.
COROLLARY 3. [~, [ > ~ - i in ~ [G].
Indeed, [~-1(~) [ -- ~_~ in ~ [G]. Therefore
I a. I = I~ (~) t = I~ ( ~ - 1 ( ~ ) ) I > ( ~ - ~ (~) I = am_~.
We show t h a t ~ - + l (r c a n n o t b e w e l l - o r d e r e d i n ill. T h e r e e x i s t s a o n e - t o - o n e f u n c t i o n
f ( i n ill) s u c h t h a t d o m / = ~ = ( ~ ) and r u g f = an, Therefore there exists a function g in
s u c h t h a t dom g = ~n+~ (~) and rng g ---- ~ ( ~ ) . . T h e r e f o r e i t i s s u f f i c i e n t t o p r o v e t h a t ~ (am)
c a n n o t be w e l l - o r d e r e d i n i)l.
For each x~-~, there is a function ~ in ~s, such that dom ~ = ( ~ : y ~ x } and ~(~) = t
for all ~' in dora ~.
For each % < an we consider xA ~ ~B, defined in the following manner: dora x_~ = {g: ~ <
(~n},
_~(~)=~ ( ~ P : ~(~, ~)= ~).
It is clear that x~ i s a f u n c t i o n q~P, such that domq= {(%, #)} and q(%, ~ ) = i.
It can be easily shown that x_~ is the name of the set
z~ = { ~ < ~ : (~P~G) p(A, ~) = I)}= { ~ < a m : (UG)(~, ~) = i}.
Let us define a function A__~ ~ B in the following manner:
dora A _ = (x_~: ~ < a ~ } , A_(X,)----I.

The function A is the name of the set A-----{z~:~<~}.

LEMMA 3. If ~, ~ < u a , are such that ~ = ~, then []x_~= x_p ]I ~- 0.

624
 Proof, Let ][x~=x~I[~=O. Then there exists a P ~ P such that P ll-~s= ~,. Since
I d o m p l<~n, there exists a ~ < ~ n such that (~, ? ) ~ d o m p and (~, ~ d o m p . Let us de-
fine q ~ P in the following manner:
domq=dompU{(%, W, (~, W}, q ( % , W = l , q(~,9 =0.
Then q~.~p. Therefore qll--~=~a.
We show t h a t q[I--~X~. By d e f i n i t i o n ,

The last sum is not less than q, since q occurs in it. (Here we have used the fact that
[[ $ = ~ [[ = 0 , i f x=/=y.) Thus, q l l - - ~ -
We show that q[I--?~" By definition,

It is sufficient to show that q II~@ix.II = O. We have

The last sum is equal to zero, since p and q are inconsistent for each p such that p(~, y) =
i.
Thus, qI[--~ x ~ and qll--~- Therefore qll--ff~=/:=ffw This contradiction proves
the lemma.
Let sym x denote the set of the permutations ~ such that wx = x. The equality
~ = 2 holds for each permutation n ~ and each x ~ 3 ~ .
We show that ~x~ = x~. It is clear that ~x~(~) = ~q, where q~P, d o m q = {(~, V)}, and
q (~, ~) = i. Then
dora ~q = {(~%,, ~)} and~q (~%,, }~) = 1,
whence
~x~ (~) = ~ (~).
It follows from the last equation that H~} _~ sym x~ and sym_x~ ~ ~. Thus, we have shown
that x~ ~ ~. Further, sym A ----~. Therefore A ~ ~.
We show that A cannot be well-ordered in ~. Since A ~__ ~ (an), it follows that ~ (an)
cannot be well-ordered in ~.
Suppose that A can be well-ordered in ~. Then there exists a one-to-one function f in
that establishes an order isomorphism either between A and a n or between A and an initial
segment of an, o r between a n and an initial segment~of A, i.e., either dom f = a n and r n g
/~A, or dora ] ~ a n and rng f = A. Let us consider a----{~ < ~ n : x ~ r n g ] } . It is obvious
that la l = l ~ n l in H [ G ] , and, by Corollary 3, ]a I ~ n - 1 .
Let f be the name of f. There exists a subset I of a n such that ~e I < ~ and H e ~ s y m l .
There exists a p 0 ~ G , such that P0 ~ Fnef. There also exist ordinals ~ an~l, ~ < a n , such
that ](~)-----x~. There exists a p ~ G , such that p ~ p 0 and p ~ I(~) = x_~.
Since I d o m p I < ~ , there exists a v~a such that I. ~ % ; 2. ~ @ e ; and 3. (~, N) ~ d o m
p for any n < ~n-
Let us consider the permutation w of a n defined in the following manner:
a, if a,=~--~, a=2~:~,

k, if a ~---~.
Then ~p 1~ ~ l ( ~ ) = ~1.X~.. But ~f = f, since ~a = a for a~ I. Further, a~----~ and ~xx
x~. Therefore

We show that p and pw are consistent. Indeed, if (a, 6) ~ (dom p) ~, (dora ~p), then a ~=
and a ~ = V. Therefore ~(a, 6)=(a, ~) and ~p(a, ~)-----p(a, ~).

625
 Since p and ~p are consistent, there exists a q~P such that q ~ p and q ~ p . Then
q[~](~) : x ~ & ~ ( ~ ) = x ~ & F n c ~ ; whence ql~:~ The last equality contradicts eemma 3.
Thus, the supposition that A can be w e l l - o r d e r e d i n 9 leads to a contradiction. There-
fore ~+i(~) cannot be well-ordered in ~,whereas ~ { ~ ) can be well-ordered in 9 for k ~ n
by Corollary 2. The proof of Theorem i is complete.
Remark i~ The consistency of the statement (A) has been proved above for n > 0. If
n = 0, then this statement is also consistent with ZF [2, Theorem 53]. Cohen [i] has even
constructed a model of ZF in which ~ (~) cannot be well-ordered.
Remark 2. Let us consider the Yon Neumann hierarchy: Vn = 0, V ~ = [j~<~V~, if ~ is a
limit ordinal, and Va~ = ~ (Va) We can see that the following relations are valid for the
above-constructed symmetric extension 9 of the model ~R : V~+~ = Ve+~ for k ~ n, V~+~1 ~ V~+~+1
and V ~ + ~ cannot be well-ordered in ~.
Analogous arguments show that for each successor ordinal ~ > ~ we can construct a sym-
metric extension ~ for each model ~ and c a c h e - g e n e r i c ultrafilter G such that V~ = V ~
for ~<= and V=+~=/=V=+~and, in addition, Va+~ cannot be well-ordered in ~
The author thanks A. G. Dragalin for the formulation of the problem and for advice
facilitating its solution.

LITERATURE CITED
I. P . J . Cohen, Set Theory and Continuum Hypothesis, W. A. Benjamin, New York (1966).
2. T. Jech, "Lectures in set theory with particular emphasis on the method of forcing,"
Leer. Notes Math., Vol. 217, Springer-Verlag, Berlin--New York (1971).
3. R. Sikorski, Boolean Algebras, 3rd ed., Springer-Verlag, Berlin--New York (1969).

ASYMPTOTIC BEHAVIOR OF THE MAXIMUM OCCUPANCY IN AN EQUIPROBABLE SCHEME

OF ALLOCATION OF PARTICLES BY COMPLEXES

E. R. Khakimullin

i. Formulation of the Problem. Let us c o n s i d e r a n equiprobable scheme of allocation

of particles by complexes (see, e.g., [i]): n complexes with s particles in each complex
are allocated independently to N cells, the particles of one complex are allocated to cells
with one particle to each cell; moreover, all C~ possible allocations of the particles of a
complex are equiprobable. Let ni be the number of particles in the cell with number i, i =
I, . . . , N, after the allocation of n complexes of particles. In this note we study the
asymptotic behavior of the distribution of the maximum occupancy
B(N) = m a x ~i

for n, N , ( ~ / I n N)-~oo and s/N.-~O, w h e r e ~ =ns/N is t h e a v e r a g e number of p a r t i c l e s in a

cell.
The asymptotic behavior of ~(N) for other relations between the parameters is investi-
gated analogously. In this note, we consider the most complicated (in our opinion) case.
This note is devoted to the proof of the following theorem.
THEOREM i. Let n, N (=/In N) -~ oo and ~ N -+ 0. Then

P t q<N)--a--a'~(~-l(InN--2-11nlnN)' sl(N--s)) + -~<z}--~exp (--exp (-- z)),

Moscow Electronic-Machine-Buildinglnstitute. Translated from Matematicheskie Zametki,

Vol. 30, No. 2, pp. 277-289, August, 1981. Original article submitted July 9, 1980.

626 0001-4346/81/3012-0626507.50 9 1982 Plenum Publishing Corporation