Содержание к диссертации
Введение
Глава 1. Клоны и соответствия Галуа для классов дискретных функций 24
Глава 2. Теоремы о сохранении 31
Глава 3. Квазитривиальные клоны 47
3.1. Некоторые свойства квазитривиальных клонов 47
3.2. Классификация симметричных квазитривиальных клонов 60
Глава 4. Простое свойство Эрроу для симметричных множеств функций выбора 84
Глава 5. Клоны на множествах функций и общее свойство Эрроу для симметричных множеств функций выбора 103
5.1. Клоны на множествах функций 103
5.2. Клоны Шелаха и общее свойство Эрроу 111
Заключение 130
Литература
- Теоремы о сохранении
- Некоторые свойства квазитривиальных клонов
- Классификация симметричных квазитривиальных клонов
- Клоны Шелаха и общее свойство Эрроу
Введение к работе
Актуальность темы исследования. Диссертация посвящена изучению проблемы агрегирования коллективной системы предпочтений с помощью методов теории замкнутых классов дискретных функций. Проблема агрегирования коллективной системы предпочтений по совокупности индивидуальных систем предпочтений есть центральная задача математической теории коллективного выбора. Интерес к этой задаче научная и философская мысль начала проявлять по меньшей мере с конца восемнадцатого века1. Впервые систематическое исследование широкого класса формальных процедур агрегирования предпринял К. Эрроу, лауреат Нобелевской премии по экономике 1972 г. Им установлен известный результат, известный как парадокс Эрроу или теорема Эрроу о невозможности. По существу, результат состоит в следующем.
Пусть дано конечное множества А (альтернатив) и фиксировано натуральное число п (участников или критериев выбора). Пусть Ord(A) есть множество всех линейных порядков на множестве А. Тогда, если множество А содержит по крайней мере три элемента, то не существует правила агрегирования, т.е. функции /: (Ord(A))n —> Ord(A), которое удовлетворяет условиям единогласия и независимости от посторонних альтернатив и при этом не является диктаторским.
Определим эти условия. Правило агрегирования /: (Ord(A))n —> Ord(A)
удовлетворяет условию единогласия, если
(Va, Ъ є A) ((Vi < п) а -<г Ъ) -* а /(тг) Ъ для каждого профиля 7Г = (-<о? -
удовлетворяет условию независимости от посторонних альтернатив,
если
(Va, Ъ Є A) ((Vi < п) а -<{ Ъ <н> а -<'г Ь) -> (а /(тг) Ъ <н> а /(тг') Ь))
ДЛЯ Любых Профилей 7Г = (-<о? -<1, , -
из (Ord(A))n. Правило агрегирования / называется диктаторским, если / есть проекция, т.е.
(Зі < п) (V -<0, - -<п_іЄ Ord(A)) /(^о, -
В современной литературе можно найти простые доказательства классической теоремы Эрроу.
1 см. Granger G.G. La mathematique sociale du Marquis de Condorcet. Paris, 1956.
2 Arrow K. Social Choice and Individual Values. 2 edition. Yale University Press, 1963, см. также раннюю
версию Arrow К. A difficulty in the concept of social welfare // J. of Political Economy. 1950.—8. Vol. 58, no. 4.
Pp. 328-346.)
3 См., напр., Geanakoplos J. Three Brief Proofs of Arrow's Impossibility Theorem // Economic Theory.
2005. Vol. 26, no. 1. Pp. 211-215 (здесь теорема Эрроу доказана доказана в немного более сильной версии).
С момента появления монографии Эрроу теория коллективного выбора переживает период бурного развития. Проблемы, близкие к теореме Эрроу, исследовалась многими учеными как экономистами, так и математиками, среди которых А. Сен (нобелевская премия по экономике 1978 г.), П. Фишборн, П. К. Паттанаик и др. Существенная часть работ посвящена поискам границ применимости принципа невозможности Эрроу. В частности, в работе П. Фиш-борна показано, что теорему Эрроу нельзя распространить на случай бесконечного количества участников; в ряде работ исследованы условия эффективности правила большинства, в случае, когда его действие ограничено некоторым подмножеством множества всех возможных профилей (т.н. случай ограниченной области). В работах А.К. Сена, К. Паттанаика и ряда других авторов предпринят отход от строгого ординалистского принципа, т.е. рассмотрены системы предпочтений, представляющие собой частичные порядки. Еще более общие случаи систем предпочтений, представляющих собой произвольные бинарные отношения и функции выбора рассмотрены М. А. Айзерманом и Ф. Т. Алеске-ровым .
Большую часть доказанных результатов можно найти в двухтомном издании Handbook of Social Choice and Welfare; также заслуживают внимание классические монографии А.К. Сена, П.Фишборна и книга С. Бергерса. Однако, несмотря на обилие теорем, основными методами теории коллективного выбора до недавнего времени оставались элементарные комбинаторные рассуждения. По всей видимости, это служит основным препятствием для широких обобщений теоремы Эрроу и систематического изучения условий эффективности процедур агрегирования. В частности, существует не так много исследований, посвященных нетранзитивным {нерациональным) системам предпочтений; между тем, прояснение общего случая представляется, несомненно,
4 Fishburn P. Arrow's Impossibility Theorem: Concise Proof and Infinite Voters // Journal of Economics
Theory. 1970. Vol. 2. Pp. 103-106.
5 Cm. Sen A. K. A Possibility Theorem on Majority Decisions // Econometrica. 1966. Vol. 3, no. 4. Pp.
491-499; из более современных исследований, напр., Barbera Salvador, Ehlers Lars. Free triples, large indifference
classes and the majority rule // Social Choice and Welfare. 2011. Vol. 37, no. 4. Pp. 559-574.
e Sen A. K. Quasi-Transitivity, Rational Choice and Collective Decisions // Review of Economic Studies. 1969. Vol. 36. Pp. 381-393; Batra R., Pattanaik K. Transitive multi-stage majority decisions with quasi-transitive individual preferences // Econometrica. 1972. Vol. 40. Pp. 1121-1135; Pini M. S., Rossi F., Venable К. В., Walsh T. Aggregating Partially Ordered Preferences // Journal of Logic and Computation. 2009. Vol. 19. Pp. 475-502. и др.
7 Айзерман M. А., Алескеров Ф. Т. Задача Эрроу в теории группового выбора (анализ проблемы) //
Автомат, и телемех. 1983. № 3. С. 127-151; Айзерман М. А., Алескеров Ф. Т. Функциональные локальные
операторы в теории голосований. I-III // Автомат, и телемех. 1984. No 5. С. 79-88, No 6. С. 105-114, No 7. С.
108-120.
8 Handbook of Social Choice and Welfare, Ed. by K. Arrow, A.K. Sen, K. Suzumura. Amsterdam:
Elsevier/North-holland, 2002.-08. Vol. 1; Handbook of Social Choice and Welfare, Ed. by K. Arrow, A.K. Sen, K.
Suzumura. Amsterdam: Elsevier/North-holland, 2010. Vol. 2.
9 Sen Amartya K. Collective choice and social welfare. San Francisco: Holden-Day, 1970.
10 Fishburn P. The Theory of Social Choice. Princeton University Press, 1973.
11 Borgers C. Mathematics of Social Choice. Society for Industrial and Applied Mathematics, 2010.
важным и мотивированным с социально-психологической точки зрения .
Наиболее значительный результат о нерациональных системах предпочтений получен С. Шелахом. В этой работе в качестве систем предпочтений рассматриваются всевозможные функции выбора, определенные на г-элементных подмножествах множества альтернатив А, где г есть некоторое положительное натуральное число. Множество всех таких функций мы обозначаем символом (Г(А). Множество > С Г(А) называется симметричным, если вместе с каждой функцией д оно содержит все функции да, где о" есть перестановка множества А и Ъа(р) = ~ ft>(&(p))) для всех r-элементных подмножеств р множества А.
Правило агрегирования есть функция /: (г(А))п —> Г(А) для некоторого натурального числа п. Мы называем правило агрегирования
вполне локальным, если
(co(g), ci(g),..., cn_i(g)) = (c0(g), c[{q),..., с'п_^)) -+ ->> /(со, ci,..., cn-i)(q) = f(c'0, c[,..., d)^)
для всех Co, Сі,.. . , Cn_i, Cq, СІ,. .. , с'п_г Є r(A) и q Є [A]r;
локально квазитривиальным, если
/(со, сі,..., tn-i){q) Є {co(g), ci(g),..., cn-i(q)} для всех Co, Сі, ..., cn_i Є r(^4) и g є [Л]г.
Эти два условия на правило агрегирования обобщают условия единогласия и независимости от посторонних альтернатив.
Правило агрегирования / сохраняет множество > С (tr(A), если
/(с0,сі,...,сп_і) Є D
для всех функций Со, Сі,... , Сп_1 Є >.
Множество > С (tr(A) обладает (общим) свойством Эрроу, если не существует сохраняющих его вполне локальных и локально квазитривиальных правил агрегирования, кроме проекций.
Теорема Шелаха о свойстве Эрроу утверждает, что существуют такие натуральные числа г\, г\ (можно положить г\ = г\ = 7), что для каждого конечного множества А и натурального числа г, удовлетворяющего неравенствам г\ < г < \А\ — г\, любое симметричное непустое собственное подмножество > множества (tr(A) обладает свойством Эрроу.
12 См. Kalai G. Learnability and rationality of choice // Journal of Economic Theory. 2003. Vol. 113. Pp.
104-117.
13 Cm. Tversky A. Intransitivity of preferences // Psychological Review. 1969. Vol. 76. Pp. 31-48.
14 Shelah S. On the Arrow property // Advances in Applied Mathematics. 2005. no. 34. Pp. 217-251
При всей важности результата С. Шелаха нельзя не отметить, что он не дает исчерпывающей классификации симметричных множеств r-функций выбора, обладающих свойством Эрроу. В частности, в его область действия не попадает в некотором смысле наиболее интересный случай г = 2, и, следовательно, основная теорема работы Шелаха формально не является обобщением теоремы Эрроу о невозможности. Случай г = 2 интересен также тем, что может быть воспринят как задача теории графов. Действительно, в этом случае каждую функцию с Є <Г(А) можно отождествить с полным ориентированным графом (турниром), а каждое симметричное множество > С Г(А) с множеством турниров, замкнутым относительно автоморфизмов.
Намеченный С. Шелахом метод не менее важен, чем сам результат. В общих чертах метод состоит в следующем. Основная теорема частично сводится к своей более слабой версии - аналогичному утверждению для простого свойства Эрроу. Определим это понятие. Правило агрегирования / называется
простым, если
(с0(р), ci{p), , cn_i(p)) = (c0(q), Ci(q),..., cn-i(q)) ->> /(со, ci,..., cn_i)(p) = /(со, ci,..., cn-i)(q)
для всех со, Сі,..., Cn-i Є r(A) и p, q є [A]r.
Множество > С (r(A) обладает простым свойством Эрроу, если не существует сохраняющих его простых вполне локальных и локально квазитривиальных правил агрегирования, кроме проекций.
Дальнейшие рассуждения основаны на том факте, что множество > обладает простым свойством Эрроу тогда и только тогда, когда каждая квазитривиальная (консервативная) функция д: Ап —> А, которая сохраняет множество > С (tr-i(A), совпадает с некоторой проекцией на множестве
Ап<г ^{аєлп: | rana| < г}.
Здесь функция д: Ап —> А называется квазитривиальной (консервативной), если удовлетворяет условию д(э.) Є ran а для всех n-ок а Є Ап, а отношение сохранения функцией д множества функций Н С 44 (для произвольного множества Q) определяется условием
(V/ii, h2,...,hne Н) g(hhh2,..., hn) є Я,
где последовательность символов g(h\,h2,. .. ,hn) обозначает функцию, которая на любом элементе q Є Q принимает значение f(h\(q), h2(q),..., hn(q)).
С учетом этого факта задача классификации множеств > С (Г(А), обладающих простым свойством Эрроу, становится естественной задачей математической теории функциональных систем и может быть решена методами этой теории.
Изложенные обстоятельства подталкивает к совершенствованию предложенного Шелахом метода с целью получения полной классификационной теоремы о симметричных множествах r-функций выбора (при любых конечных значениях г) и иных приложений. Усовершенствованный автором диссертации метод в дальнейшем будет называться методом клонов в теории коллективного выбора. Этот метод представлен автором в качестве специальной главы теории соответствий Галу а для классов дискретных функций Множество всех функций g (любой арности) на множестве А обозначается символом О (А). Пусть даны множества Q,1C V(QA) и7С0(4 Множество всех функций g Є О {А), которые сохраняют каждое множество Н Є Н, мы будем обозначать символом рої Н, а множество всех множеств Н С 44, которые сохраняются каждой функцией g Є J-, мы будем обозначать символом invg Т. Пара (invg,pol) есть соответствие Галуа между булевыми решетками ViVi^A)) и V(0(A)), причем Галуа-замкнутые множества J- С О (А) есть клоны15. Если множество Q конечно, это соответствие погружается в хорошо известное соответствие Галуа (inv,pol), порожденное отношением сохранения функцией g предиката Р.
Легко заметить, что множество {ро1{>}: > С (г(А)и > симметрично} состоит из симметричных клонов, т.е клонов, которые вместе в каждой функцией g (любой арности п) содержат все функции да, где а есть перестановка множества А и ga(a.) = a~l(g(a а)) для всех n-ок а Є Ап . Таким образом, для решения задачи классификации симметричных множеств > С (Г(А), обладающих простым свойством Эрроу, достаточно получить явное описание некоторого фрагмента соответствия (invg,pol) при Q = [А]г, а именно
-
получить описание класса симметричных квазитривиальных клонов,
-
для каждого симметричного квазитривиального клона J- с носителем А получить описание множества invg J-
(далее остается только определить, какие из множеств invg J7, могут содержать непустое симметричное множество > С (tr(A)).
Обе задачи в данном исследовании решены, причем на пути описания множеств invg J- для симметричных квазитривиальных клонов J- получены важные результаты (названные в данном исследовании теоремами о сохранении) об инвариантных множествах трех достаточно широких классов клонов, а именно, о классах клонов, удовлетворяющих определенным ниже условиям А , А^: и А2.
15 О клонах см., напр., Кон П. Универсальная алгебра. Москва: МИР, 1968.
16 См. Poschel R., Kaluznin L. A. Funktionenund Relationenalgebren. Ein Kapitel der Diskreten
Mathematik. Berlin: VEB DEUTSCHER VERLAG DER WISSENSCHAFTEN, 1979.
17 Такие клоны в работе Нгуен В. X. «О семействах замкнутых классов k-значной логики, сохра
няемых всеми автоморфизмами» названы клонами, замкнутыми относительно всех автоморфизмов, см.
Нгуен В. X. О семействах замкнутых классов k-значной логики, сохраняемых всеми автоморфизмами //
Дискретная математика. 1993. Т. 5, № 4. С. 87-108
Определение 2.1. Пусть дан клон Т С О (А) и натуральное число г > 2. Будем говорить, что клон J7
1. удовлетворяет условию А9, если для любой последовательности а Є А%
и элемента а Є ran а существует такая трехместная функция w Є J-, что
if (а) = а и w(xxy) = w(xyx) = w(yxx) = х для всех ж, у Є А]
2. удовлетворяет условию А^, если существует такое натуральное число
і < г, что для любой последовательности а Є А^ и элемента а Є ran a
существует такая r-местная функция w Є J-, что
ш(а) = й и w(x.) = Х{ для всех х = жоЯл %г-і Є A<r (символ Arr обозначает множество {а Є Ar: | rana| = г});
3. удовлетворяет условию А , если для любых последовательностей a, b Є Щ
с различными областями значений и элементов а Є ran а и 6 Є ran b су
ществует такая двухместная функция w Є J-, что
if (а) = a, it>(b) = 6 и w(xx) = х для всех х Є А.
Инвариантные множества клонов (не обязательно симметричных и квазитривиальных), удовлетворяющих этим условиям, допускают несложное описание, которое представляет самостоятельный интерес.
Теория замкнутых классов дискретных функций имеет собственную богатую историю. Первым и наиболее известным результатом в этой области была теорема Э. Л. Поста о классификации всех замкнутых классов булевых функций. Как известно, непосредственное распространение классификационной теоремы Поста на общий случай дискретных функций (функций /с-значной логики) вызывает затруднения из-за результата Ю. И. Янова и А. А. Мучника, из которого следует, что для к > 3 решетка замкнутых классов континуальна и имеет весьма сложную структуру. В разработку методов изучения этой решетки внесли большой вклад отечественные математики С. В. Яблонский, О. Б. Л у панов, В. Б. Кудрявцев, С. С. Марченко в.
18 Post Е. L. Two-valued iterative systems of mathematical logic, Ed. by Phillip A. Griffiths, John N. Mather,
Elias M. Stein. Princeton Univer, 1942. Vol. 5 of Annal of Math, studies,
современное изложение см. Марченков С. С. Замкнутые классы булевых функций. Москва: Физматлит, 2000
19 Янов Ю. И., Мучник А. А. О существовании k-значных замкнутых классов, не имеющих конечного
базиса // ДАН СССР. 1959. Т. 127, № 1. С. 44-46.
20 Подробное изложение основных результатов можно найти в книгах Яблонский СВ. Функциональ
ные построения в к-значной логике // Тр. МИАН СССР им. В. А. Стеклова. 1958. Т. 51. С. 5-142; Яб
лонский С. В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста. Москва: Наука,
1966; Кудрявцев В. Б. Функциональные системы. Москва: Изд-во МГУ, 1982; Марченков С. С. Функцио
нальные системы с операцией суперпозиции. Москва: Физматлит, 2004, а также в зарубежных монографиях
Poschel R., Kaluznin L. A. Funktionenund Relationenalgebren. Ein Kapitel der Diskreten Mathematik. Berlin:
VEB DEUTSCHER VERLAG DER WISSENSCHAFTEN, 1979 и Lau D. Function Algebras on Finite Sets. A
Basic Course on Many-Valued Logic and Clone Theory. Springer-Verlag Berlin Heidelberg, 2006.
Соответствие Галуа (inv, рої) для классов дискретных функций, по всей видимости, впервые было обнаружено Д. Гейгером21 и независимо В. Г. Бод-нарчуком, Л. А. Калужниным и др. Соответствие Галуа успешно применяется для получения классификационных теорем в теории замкнутых классов, в частности, оно иногда позволяет получить простое описание функционально замкнутых систем, удовлетворяющих какому-либо условию, напоминающему условия А , Д^; и А , т.е. содержащих некоторую функцию или множество функций специального вида.
Консервативные клоны изучались в работах Я. Ежека и др. Симметричные (замкнутые относительно всех автоморфизмов) клоны, содержащие все константы, описаны в работе В. X. Нгуена О семействах замкнутых классов k-значной логики, сохраняемых всеми автоморфизмами(непосредственно воспользоваться результатом этой работы в нашем исследовании невозможно, т.к. квазитривиальные клоны с более чем одноэлементным носителем, напротив, не содержат ни одной константы).
Отметим, что известно не так много примеров приложения теории функциональных систем к другим областям математического знания. Неожиданное применение автором диссертации развитой техники теории Галуа для классов дискретных функций к проблемам агрегирования коллективных систем предпочтений представляется новым привлекательным и перспективным направлением теории коллективного выбора.
Цели и задачи работы. Основной целью работы является получить окончательное решение вопроса о свойстве Эрроу для симметричных классов r-функций выбора и развить предложенный С. Шелахом метод клонов в теории коллективного выбора. Поэтапное достижение основной цели ставит перед автором следующие задачи.
Получить характеризацию инвариантных множеств клонов с конечным носителем, удовлетворяющих условиям А , А^: и А .
21 Geiger D. Closed systems of functions and predicate // Pacific journal of mathematics. 1968. Vol. 27,
no. 1. Pp. 95-100.
22 Боднарчук В. Г., Калужнин Л. А., Котов В. Н., Ромов Б. А. Теория Галуа для алгебр Поста І-П//
Кибернетика. 1969. Т. 3. С. 1-Ю и Т. 5. С. 1-9.
23 См., напр., Жук Д. Н. Решётка замкнутых классов самодвойственных функций трёхзначной логики.
Москва: Издательство МГУ, 2011.
24 Примерами таких результатов являются работы Марченков С. С. Клоновая классификация дуально
дискриминаторных алгебр // Математические заметки. 1997. Т. 61, № 3. С. 359-366 (теорема 2.2 настоящего
исследования, по существу, есть усиление основного результата этой работы); Марченков С. С. О замкнутых
классах в k-значной логике, содержащих переключательную однородную функцию // Дискретный анализ
и исследование операций. 1995. Т. 2, № 2. С. 49-61; Парватов Н. Г. Клоны с мажоритарной функцией и их
обобщения // Дискретн. анализ и исслед. опер. 2010. Т. 17, № 3. С. 46-60.
25 Jezek J., Kepka Т. Quasetrivial and nearly quasitrivial distributive goupoids and semigroups // Acta
Universitatis Carolinae. Mathematica et Physica. 1978. Vol. 19, no. 2. Pp. 25-44 и Jezek J., Quackenbush R.
Minimal clones of conservative functions // International J. of Algebra and Computation. 1995. Vol. 5. Pp. 615-630.
26 Нгуен В. X. О семействах замкнутых классов k-значной логики, сохраняемых всеми автоморфизма
ми // Дискретная математика. 1993. Т. 5, № 4. С. 87-108.
Описать основные типы квазитривиальных клонов.
Построить полную классификацию симметричных квазитривиальных клонов с конечным носителем.
Обобщить теоремы Шелаха о простом и общем свойстве Эрроу для симметричных классов r-функций выбора на случай произвольного натурального числа г.
Научная новизна. Результаты являются новыми, получены автором самостоятельно. Метод клонов в теории коллективного выбора впервые последовательно представлен как специальный раздел теории функциональных систем. Основные результаты:
Получена характеризация инвариантных множеств клонов с конечным носителем, удовлетворяющих условиям А , А^. и А2.
Введены понятия г-клона и его распространения, свободной склейки квазитривиальных клонов и 2-монотонной функции. Введено понятие и получено явное описание класса инъективно устойчивых справа и устойчивых слева отношений эквивалентности на множестве А<ш. С помощью этих понятий определены четыре простых типа квазитривиальных клонов.
Построена классификация симметричных квазитривиальных клонов с конечным носителем, представляющая каждый из них в виде пересечения четырех клонов простых типов.
Получена полная классификация симметричных множеств r-функций выбора, обладающих простым и общим свойством Эрроу.
Теоретическая и практическая значимость. Работа имеет теоретический характер. Результаты, изложенные в диссертации, могут быть использованы в теории коллективного выбора для доказательства различных обобщений теоремы Эрроу о невозможности и в теории функциональных систем для построения классификаций замкнутых классов дискретных функций. Также результаты диссертации позволяют исследовать практические задачи агрегирования систем предпочтений и некоторые процедуры принятия коллективных решений.
Методология и методы исследования. В работе использованы методы дискретной математики и универсальной алгебры.
Положения, выносимые на защиту:
1. Построение полной классификации симметричных квазитривиальных клонов с конечным носителем.
2. Построение полной классификации симметричных классов r-функций выбора, обладающих общим свойством Эрроу.
Степень достоверности и апробация результатов. Результаты прошли апробацию на международных и всероссийских научных конференциях, а также на авторитетных научных семинарах.
Конференции.
«Информационные технологии и системы - 2012» 35-я конференция молодых ученых и специалистов, 19 - 25 августа 2012, Петрозаводск, Россия.
ESSLLI Workshop on Logical Models of Group Decision Making, Dusseldorf, 12-16 August 2013
VII международная конференция по математическому моделированию, 30 июня-4 июля 2014, Якутск, Россия.
II научная конференция «Управленческие науки в современном мире», 25-26 ноября 2014, Москва, Россия.
Научная сессия математического факультета МПГУ, 19 - 21 марта 2015,
Международная научная конференция «Дискретная математика, алгебра и их приложения» (DIMA-2015), 14 - 18 сентября 2015, Минск.
Семинары.
Научный семинар «Проблемы современных информационно-вычислительных систем» под руководством д. ф.-м. н., проф. В. А. Васенина, механико-математический факультет МГУ им. М.В. Ломоносова.
Кафедральный семинар «Теория автоматов» кафедры Математической теории интеллектуальных систем механико-математического факультета МГУ им. М.В. Ломоносова под руководством д. ф.-м. н., академика В.Б. Кудрявцева.
Научный семинар «Актуальные проблемы геометрии и механики» имени проф. В. В. Трофимова под руководством проф. Д. В. Георгиевского, проф. М. В. Шамолина и проф. С. А. Агафонова, механико-математический факультет МГУ им. М.В. Ломоносова.
Семинар «Математические модели информационных технологий» департамента анализа данных и искусственного интеллекта и МНУЛ «Интеллектуальные системы и структурный анализ» Высшей школы экономики под руководством СО. Кузнецова.
Семинар по дискретным математическим моделям кафедры математического моделирования НИУ «МЭИ».
Семинар «Экстремальная комбинаторика и случайные структуры» под руководством д.ф.-м.н. Д.А. Шабанова и к.ф.-.м.н. М.Е. Жуковского, механико-математический факультет МГУ им. М.В. Ломоносова.
Объединенный семинар «Логические проблемы информатики» под руководством проф. С.Н. Артёмова, чл.-корр. РАН Л.Д. Беклемишева, доц. В.Н. Крупского, проф. М.Р. Пентуса, доц. Т.Л. Яворской и «Модальная и алгебраическая логика» под руководством проф. М.Р. Пентуса, проф. В.Б. Шехтмана, к.ф.-м.н. И.Б. Шапировского, механико-математический факультет МГУ им. М.В. Ломоносова.
Также в 2012 году в ФГОБУ ВПО «Финансовый университет при правительстве Российской Федерации» был выпущен препринт .
Публикации. Материалы диссертации опубликованы в 7 печатных работах, из них 3 статьи в рецензируемых журналах -] и 4 тезисов докладов -].
Структура и объем диссертации. Диссертация состоит из введения, обзора литературы, 5 глав, заключения и библиографии. Общий объем диссертации 136 страниц, из них 129 страницы текста. Библиография включает 54 наименования на 6 страницах.
Теоремы о сохранении
В этой главе мы зафиксируем основные определения и обозначения, которые будем использовать ниже.
Для любых множеств Q и А множество всех функций h: Q — А обозначается символом 44. Ограничением h \ Р произвольной функции h Є 44 на множествР называется функция НГ\ (Р х А). Продолжением любой функции h Є 44 на множество Р мы будем называть любую функцию g Є Ри44 с условием g \ Q = h. Множество всех продолжений функции h: Q — Л на множество Р мы будем обозначать символом h \ Р. Если Н есть произвольное множество, состоящее из функций (вообще говоря, с различными областями определения), то символом Н \ Р мы будем обозначать множество {h \ Р: h Є Н} всех ограничений функций из Н на множество Р, а символом Н \ Р множество (J h \ Р heH всех продолжений функций из Н на множество Р. Для любой функции h Є 44 и множества Р С Q символ /і(-Р) обозначает множество {/і(р): р Є Р}. Аналогично, для любого множества Н С 44 и элемента q Є Q символ -//(#) обозначает множество {h(p): h Є і/}. Множество и группа перестановок произвольного множества А обозначается символом SA- Тождественная перестановка множества А обозначается символом 1сЦ. Этим же символом мы будем обозначать отношение равенства на множестве А, если символ «=» оказывается неудобным. Циклические перестановки будут обозначаться знакосочетаниями вида ( 2о, Q-i, , ап).
Для каждого натурального числа п и каждого множества А множество всех n-элементных подмножеств множества А обозначается символом [А]п:
[А}п = {ВС А: \В\ =п}. Для любого натурального числа п декартова степень Ап произвольного множества А отождествляется с множеством пА функций а: п — А (здесь п = {0,1,...,п — 1} в соответствии со стандартным определением множества натуральных чисел); поэтому для любой n-ки а Є А и) мы употребляем стандартные обозначения dom а и ran а для ее области определения и области значений соответственно. Будем использовать обозначение А для множества {а Є Ап: гапа = т}. В естественном смысле будем употреблять обозначения Km - U К Km - U Km, Km - U шИ Т П- ПРИ ЯВН0Й 3anH" к т п ш т п ш си последовательностей мы, как правило, будем опускать служебные символы, т.е. использовать знакосочетания вида abc, а\(і2 .. . ап и т-п. Соответственно, конкатенацию последовательностей а = а$а\... ап-\ и b = Ьф\... Ът-\ мы обозначаем пустым символом: ab = а$а\ ... ап-\Ьфі ... Ът-\. Для последовательностей, состоящих из последовательностейао, аі,... , а , мы сохраним обозначение (ао, ai,..., ап), каждый раз особо это оговаривая.
Для обозначения композиции одноместных функций мы будем использовать символ «». Например, для всякой последовательности а = а$а\... ап-\ Є А и функции о": А — А запись а а обозначает последовательность а(а0)а(аі) ...cr(an_i). Для каждой n-ки функций f = /о/і ... fn-i Є (Ч4)п символом f мы обозначаем функцию из множества Q в множество Лп, определенную равенством r(q) = fo(q)fl(q)...fn.l(q) для всех q Є Q. Каждая функция / Є А называется n-местной или n-арной функцией на множестве А, а натуральное число п арностью функции /. Множество всех функций произвольной конечной арности на множестве А, т.е. множество [J А, обозначается символом О (А). Для краткости для любого множества J- С О (А) и натурального числа п вместо J- П А будем писать J-щ. В частности, вместо А будем, как правило, писать (9(A)ui. Функция из множества 0(А)і„], которая ставит в соответствие каждой п-ке а = (іфі... ап-\ Є Ап элемент а{ для некоторого фиксированного номера і п, называется n-местной г-ой проекцией или селекторной функцией и обозначается символом е. Множество всех селекторных функций на множестве А будем обозначать символом (А).
Множество О (А), как правило, рассматривается вместе с частичной операцией композиции. Композиция определена на множестве всех кортежей для всех а Є dom f\. Как правило, вместо выражений вида /о (/1/2 /«,) мы будем использовать более привычную запись /о(/і, /2, , fn) Клоном на множестве А называется любое множество J- С С (А), которое содержит все селекторные функции и замкнуто относительно композиции, см. [29]. Эквивалентно можно определить клон на множестве А как любое функционально (или термально) замкнутое множество J- С О (А), которое содержит все селекторные функции, см. [33]. Если J- есть клон на множестве Л, то множество А называется носителем клона J-.
Клоны J- и Q с носителями А и В соответственно мы будем называть эквивалентными, если существуют такие взаимно однозначные функции а: А — В и (3: J- —/, что для каждого натурального числа п и функции / Є J-щ функция a(f) n-арна и «(/)(b) = /3-/(/3-1-b) для всех b Є Вп. В теории функционально замкнутых классов часто рассматривают соответствие Галуа, порожденное отношением сохранения функцией f предиката Р. Пусть даны множество А, натуральные числа п т, функция / Є (9(A)[nj и предикат Р С Ат. Говорят, что функция / сохраняет предикат Р, а предикат Р сохраняется функцией /, если для любых п кортежей
Для каждого множества J- С О (А) и P С (J V(An) символом inv J- обо-значается множ;ество всех предикатов, которые сохраняются каждой функцией / Є J-, и для каждого множества P С (J V(An) символом роІP обозначает-ся множ;ество всех функций / Є О {А), которые сохраняют каждый предикат Р Є P. Хорошо известно (см. [41, 42]), что пара (inv, рої) есть соответствие Галуа между булевыми решетками подмножеств множеств О (А) и (J V{An), причем Галуа-замкнутые множества J- С О (А) суть в точности клоны.
Иногда удобно говорить о клонах в теоретико-модельных терминах. Для этого каждому клону J- можно сопоставить модель 9JTj- некоторого языка L без предикатных символов, для которой множество J- совпадает с множеством интерпретаций функциональных символов языка L (носитель модели 9JTj-, очевидно, совпадает с носителем клона J-). При необходимости явно обозначить интерпретацию X функциональных символов языка L, мы будем вместо 9JTj-записывать 9JTJ;I. С учетом этих обозначений, эквивалентность клонов J- и Q равносильна изоморфности моделей 9JTJ;I и ZOlg j для некоторых интерпретаций X и J функциональных символов некоторого языка L. Кроме того, для любого клона J- n-местный предикат Р принадлежит множеству inv J- тогда и только тогда, когда Р есть носитель некоторой подмодели модели
Некоторые свойства квазитривиальных клонов
Также, как в доказательстве теоремы 2.2 отбросим тривиальные случаи \Q\ = 1 и \Н\ = 0. Обозначим Ш = {Н Є Є0 U Шг: Н С Я }. Кроме того, положим Q(r) = {(J Є Q: 1 ( )1 т} и i/(r) = (Я Ї Q[r)) \ Q. Очевидно, для доказательства теоремы достаточно доказать включение Н П f] Ш С Н. Докажем теперь леммы, аналогичные леммам 2.3 и 2.4. Лемма 2.8. Пусть даны такие элементы p q Є Q и а Є А, что \H(q)\ г, и множество Н слабо отделяет элемент р от элемента q в точке а. Тогда множество Н сильно отделяет элемент р от элемента q в точке а.
Доказательство. Для произвольного элемента Ь Є H(q) предположим, что множество Н не содержит функции /г, которая на элементе р принимает значение а, а на элементе q значение Ь, и придем к противоречию. Выберем такие функции /іо, /її, /і2 Є Н и различные элементы c,d Є А, что /г0(р) = hi(p) = a, /i0(g) = с, /ii(g) = rf, /i2(g) = Ь. По сделанному предположению, элемент Ь не принадлежит множеству {c,d}. Используя неравенство \H(q)\ г, выберем еще г—3 функций /із, /14, , /ir-i из Я так, чтобы последовательность b = ho(q)hi(q)h2(q)... hr-i(q) была бы инъективной. Последовательность а = ho(p)hi(p)h2(p)... hr-\(p) принадлежит множеству Аг г. По лемме 2.7 существует функция w Є J-, для которой вы полнены равенства «/(а) = ho(p) = а и if (b) = /12(g) = & Рассмотрим функ цию h = w (ho, /її,..., /іГ-і) Є H. Легко проверить, что имеют место равенства h(p) = «/(а) = а и /i(g) = «/(b) = 6; противоречие. Лемма 2.9. Пусть дано множество Р = {p,q} Є Q , Р Q(r)- ТЬгда ew-полнен один из следующих случаев 1. H\P = H0(p,H(p),P)nH0(q,H(q),P), 2. H \ P = Ho(p,H(p),P) П Ho(q,H(q),P) П Hi(p,q,a,P) для некоторой перестановки т Є 5д. Доказательство. Если множество Н не отделяет слабо р и q то выполнен случай случай 2, что доказывается также, как в лемме 2.4. В противном случае покажем, что выполнен случай 1, что докажет лемму. Без ограничения общности будем считать, что \Н(р)\ \H(q)\. Из этого следует, что \H(q)\ г. Покажем, что без ограничения общности можно считать, что множество Н слабо отделяет рот g в некоторой точке а Є Н{р). Действительно, если множество Н не отделяет слабо р от q, то существует сюръективная функция а: Н(р) — H(q), для которой %) = o-(h(p)) для всех h Є Н. Значит, \Н(р)\ = \H(q)\, и элементы р и q при необходимости можно поменять местами. Теперь в силу леммы 2.8, достаточно показать, что множество Н слабо отделяет р от q в каждой точке а Є Н(р) \ {а}. Выберем произвольный элемент а Є Н(р) \ {а}. Используя лемму 2.8, вы берем такие функции /io, h\}..., hr-\ из Н, что ho(p) = a , h\(p) = Ji2(p) = ... = hr-i(p) = а, и последовательность b = ho(q)hi(q)h2(q)... hr-\(q) инъективна. Поскольку последовательность а = ho(p)hi(p)h2(p)... hr-\(p) = а а...а при надлежит множеству Аг г, из леммы 2.7 следует, что клон J- содержит такую функцию w , что «/(а) = а и «/(b) ф ho(q). Тогда значения функций ho и h = w (ho, /її, /і2, , hr-i) совпадают (и равны а ) на элементе р и различны на элементе q. Поскольку функция h принадлежит множеству Н, множество Н слабо отделяет р от q в точке о!. Теперь для доказательства теоремы достаточно для каждого множества Q Q, \Q \ 2, доказать включение (я(г)Пре) \Q CH\Q . Индукция мощности множества Q . Если Q С Qr, включение очевидно. Если Qf ( Qr и \Qf\ = 2, включение следует из леммы 2.9. Пусть теперь \Q \ 3, \Q \ Qr\ 1? и предположение индукции выполнено.
Пусть / есть произвольная функция из множества (Я(г) П Р HJ f Q . Надо доказать, что существует функция h Є Н, для которой /г \ Q = f Выберем такие различные элементы p,q Є Q , что -Н"(#) т. По предположению индукции множество Н содержит функции fp и fq, которые совпадают с функцией / соответственно на множествах Q \ {р\ и Q \ {q}. В частности, fq(p) = f(p) и fP(q) = f(q) Если имеет место равенство fq(q) = f(q), положим h = fq. Пусть теперь fq(q) = /(#) Покажем, что в этом случае множество Ш. не содержит ни одного элемента вида H\(p, q, т, Q). Действительно, если Hi(p,q,a,Q) Є Н, то, во-первых, / Є Hi(p,q,a,Q) \ Q = Hi(p,q,a,Q ), а во-вторых, Н С Hi(p,q,a,Q) и, следовательно, fq Є Hi(p}q}a}Q). Значит, Таким образом, нет таких перестановок а Є 5д, что Н \ {р} q} С Н\(р} q} т, {р, q}). Тогда по лемме 2.9 Н \ {р, q} = Но(р, Н(р),{р, q}) П H0(q, H(q),{p, q}). Используя этот факт, выберем г — 2 функций fr-i из множества Н, для которых J2(p) = h(p) = ... = fr-i(p) = f(p), а последовательность b = fq(q)fp(q)f2(q)h(q) fr-i(q) инъективна. Используя лемму 2.7, выберем функцию w из J-, которая совпадает с селекторной функцией е[) на множестве Ar r и принимает значение fp(q) на последовательности Ь. Покажем, что можно положить h = w(fqJpJ2J ---Jr-i)-Действительно, функция h принадлежит множеству Н. Последовательность а = fq(p)fp(p)f2(p)h(p) fr-l(p) принадлежит множеству Аг г. Кроме того, для всех х Є Q \{p,q} верно равенство fp(x) = fq(x) = f(x), и, значит последовательность fq(x)fp(x)f2(x)f (x) ... fr-i(x) тоже принадлежит множеству Аг г. Поэтому имеют место равенства h(p) = Ца) = fq(p) = f(p), h(q) =w(h) = fp(q) = f(q), h(x) = w(fq(x)fp(x)f2(x)h(x)... fr-i(x)) = f(x) для всех x Є Q \ {p, q\, что окончательно доказывает шаг индукции и теорему. Теорема 2.10. Пусть даны клон Т С О (А), который удовлетворяет условию 2, и множество Н Є invg Т. Тогда существует такое множество iCi0U M\d U Из, что Н = П Ш.
Классификация симметричных квазитривиальных клонов
Поэтому множество V(A) \ А замкнуто относительно композиции. Сформулируем это утверждение более строго. Обозначим для краткости символом V(A)/r\ множество V(A) \ А" . Для каждой функции д Є V(A)/r\ естественным образом определена ее арность. Тогда для каждого натурального числа г 1 и кортежа gogifj2 9п Є (V(A) ) UJ, для которого функция до имеет арность n, а функции (?i, Q2-,.. . і дп имеют одну и ту же арность т, существует единственная функция д{ді-,д2і , #«,) ( -)(г); удовлетворяющая условию 9І9и92, -,9п)(а) = #(#і(а),#2(а),... }д„(а.)) для всех а Є Аг. Этим равенством определяется частичная операция композиции из множества (V(A) ) UJ в множество V(A)(r}, которая каждому кортежу дод\д2 дп функций из множества V(A) подходящих арностей ставит в соответствие функцию g0(gi,g2,..., дп). При этом для любых функций /0, /ь /2 ... fn Є V(A) если
Любое замкнутое относительно композиции подмножество Q множества V(A) \ А ", содержащее все функции из (А) \ А ", мы будем называть г-клоном. Заметим, что это множество вместе с операцией композиции и функциями е А , где є Є (А)і есть абстрактный клон (определение абстрактного клона см. [29]). Для каждого r-клона Q символом Q обозначим множество всех функций / Є V(A), для которых / А" Є Q. В силу сделанных замечаний, множество Q есть клон; мы будем называть его распространением г-клона Q.
Для каждого клона J- С V(A) и натурального числа г 1 множество J- \ А" будем для краткости обозначать символом J-/r\. Очевидно, множество J-/r\ есть г-клон и имеет место включение J- С J7), .
Связанная склейка. Пусть дан клон Р С Тої. Каждое семейство клонов {3 в}Ве[А}21 Для которого носитель каждого клона Тв есть В, и клон Тв эк вивалентен клону Р, будем называть Р-семейством. Пусть дано Р-семейство {3 в}Ве[А}2 и такое семейство {о в}ве[А}2 биекций erg: В — {0,1}, что для каждого клона Тв существует взаимно однозначное отображение (їв Р 3 в, для которого «в(/)(x) = 1(/(ав-x)) для всех / Є Р и x Є Вп, где п есть арность /. Для каждого натурального числа п и функции / Є Р[п] существует единственная функция /+ Є V(A)/3\, для которой /+(x) = r"anx(/( anx-x)) для всех x Є А . Можно проверить, что множество функций Q = {f+: / Є Р} есть 3-клон, причем для каждого В Є [А] выполнено Q \ В ш = Тв- Такой 3-клон Q мы будем называть связанной склейкой Р-семейства {3 в}ве[А]2 (П0 семейству {(7в}ве[А}2) Пусть клон Р состоит только из самодвойственных функций. Тогда, как несложно заметить, связанная склейка / Р-семейства {3 в}ве\А}2 не зависит от семейства {о в}ве[А}2 и следовательно, определяется только клоном Р. В этом случае мы будем обозначать 3-клон Q символом Р(А). Как известно (см. [33]), существует всего четыре постовских класса Р самодвойственных функций, сохраняющих ноль и единицу. Следуя обозначениям Поста, будем обозначать их символами Oi, Di, D2 и L4. Они, соответственно, порождаются функциями х, xyVxzVyz, xyVyzVxz и хфуфг. Следовательно, если \А\ 2, то определены всего четыре 3-клона вида Р( 4), причем, 3-клон Оі(А)есть(А) 3 . Определим очень важный в теории квазитривиальных клонов числовой параметр T(J-) клона J-, который мы будем называть рангом клона J-. Определение 3.4. Для каждого клона Т С О (А) положим
Доказательство. Сначала заметим, что лемма верна для селекторных функций /. Пусть, далее, b = (бо, &і, , &t-i) есть некоторая инъективная последовательность всех различных элементов из ran а. Положим т = b а. Рассмотрим функцию / = / (Ч(0) 4(1) --- 4(п-1)) Є Тщ. Поскольку t г, из условия теоремы следует, что / есть селекторная функция. Тогда имеем 7(/(а)) =a(f(h)) = /V Ь) = /(е (0)(а Ь), е\ф Ь),..., е (п_1}(а Ь)) = =/ ( (&т(о) ) , (&r(i) ) , v (&r(n-i) )) = f(cr Ъ г) = f(a). Без ограничения общности будем считать, что множество А содержит подмножество 2 = {0,1}. Тогда клон J- \ 2 ш есть постовский класс, содержащийся в классе Тої. Обозначим его символом Р.
Рассмотрим функцию а: А — А, для которой т(0) = 1 и т(1) = 0. Тогда из леммы 3.6 следует, что каждая функция g Є Р самодвойственная. Значит, Р Є {Oi, Di, D2, L4}. Кроме того, из той же леммы 3.6 следует, что f\Au 3 = (f\ 2 Т для любой функции / Є J-. Это доказывает пункт 1.
Пусть теперь г 4. Для доказательства пункта 2, заметим, что если Р т Оі, то класс Р содержат неселекторные функции от трех переменных, что, конечно, остается верным и для клона J-. Следовательно, в рассматриваемом случае класс Р состоит только из селекторных функций. Пусть п есть произвольное натуральное число и / есть произвольная функция из Тщ. Пусть і есть такой номер, что / \ 2п = е (здесь символом е обозначена г-ая n-местная проекция из класса Р). Для каждой последовательности а Є Av r выберем функцию а: А — А, для которой ст(а ) = 1 и о (х) = 0 для всех х Є А \ {аї\. По лемме 3.6 имеем а(Да)) = Да-а) = (Я2п)(а-а) = 1, откуда /(а) = а{. Следовательно, / Ї Av r Є (А) , пункт 2 доказан. Следствие 3.7. Для любого клона Т С V(A) выполнено одно из двух условий 1. т{Т) = ш 2. r(T) max{3, \А\}. Для каждого клона J- С V(A) ранга г 3 класс Р из теоремы 3.5 будем обозначать символом Pj
Клоны Шелаха и общее свойство Эрроу
На протяжении данного раздела мы будем считать фиксированными непустые конечные множества A, Q и Н С 44. Мы будем изучать некоторые классы клонов на множестве Н. Нашей основной целью является перенесение теоремы 4.8 на более общую ситуацию, а именно, установление, в каких случаях симметричное множество С Г(А) может быть одноместным предикатом из invJ-, где J- есть клон на множестве (tr(A) с некоторыми дополнительными свойствами. Поэтому промежуточные определения результаты будут группироваться вокруг двух основных задач: во-первых, редукции к случаю Т = Сг \ \ (r(A)) UJ для некоторого клона Q Є V(A), а во-вторых, изучения некоторых ситуаций, в которых такая редукция принципиально невозможна. Мы будем формулировать и доказывать только те теоремы о каких-либо классах клонов на множестве Н, которые соответствуют нашему подходу к решению этих задач.
Легко проверить, что множество всех локально квазитривиальных функций / Є 0{Н) одержит все проекции и замкнуто относительно композиции, т.е. есть клон. Этот клон мы будем обозначать символом CV(H). Каждый клон, состоящий из локально квазитривиальных функций, мы будем называть локально-квазитривиальным.
Определение 5.2. Для любого натурального числа п и множества Е С A UJ функцию f Є 0{Н)щ будем называть простой относительно множества Е, если h0(p)hi(p)... hn-i{p) = h0(q)hi(q)... hn-i{q) Є E - - f{hohi... hn-i){p) = fihohi... hn-i){q) для всех ho, h\,..., hn-i Є H и p}q Є Q. Простую относительно множества А ш функцию f Є (Э{Н)щ будем называть простой. Для каждого натурального числа s простую относительно множества А " функцию f Є (Э{Н)щ будем называть s-простой. Легко проверить, что множество всех простых функций / Є 0{Н) есть клон. Этот клон мы будем обозначать символом S{H). Любой подклон клона S{H) будем называть простым. Кроме того, легко проверить, что для любого натурального числа s множество всех s-простых функций / Є JCV(H) есть клон. Этот клон мы будем обозначать символом CVSa{H). Любой подклон клона CVSa{H) будем называть s-простым клоном.
Предложение 5.3. Если \Q\ = 1, то любой клон Т С О(Н) простой. Любой локально квазитривиальный клон является 2-простым, а если для всех p}q Є Q выполнены условия Н(р) = H(q) - p = qu \Н(р)\ 2, то и простым. 104 Доказательство. Очевидно. Определение 5.4. Для любого натурального числа п функцию f Є (Э{Н)щ будем называть вполне локальной, если h0(q)hi(q)... hn-i(q) = hf0(q)h[(q)... Ып_ ) - - f(h0hi... hn-i)(q) = f(h0h[... Ып_ ) для всех ho, /її,..., hn-i, h Q} h[,..., h!n_x Є H и q Є Q. Легко проверить, что множество всех вполне локальных функций/ Є 0{Н)щ есть клон. Мы будем обозначать его символом JCW(H) И каждый его подклон называть вполне локальным клоном. Очевидно, что для каждой вполне локальной функции / Є 0{Н)щ и каждого элемента q Є Q существует единственная функция fq: (H(q))n — H(q), для которой для всех ho,h\,- , hn-\ Є H и q Є Q. При этом множество функций {fq: f Є J-} есть клон на множестве H{q). Этот клон мы будем обозначать символом J (q) Вполне локальный клон J- является локально квазитривиальным тогда и только тогда, когда каждый из клонов J-q квазитривиальный. Вполне локальный клон является простым (s-простым) тогда и только тогда, когда для всех натуральных чисел п, функций / Є J-\nu элементов p,q Є Q и последовательностей а Є (Н(р) П H{q))n (соответственно, последовательностей ае(Я(р)ПЯМ)у.
Для каждого клона J- С О (А) клон J- (см. определение из раздела 1) есть простой вполне локальный клон на множестве 44; если при этом клон J-квазитривиальныи, то клон локально квазитривиальный. Наоборот, любой простой вполне локальный клон Т С О(Н) можно по существу свести к некоторому клону ТА О (А).
Для каждого вполне локального клона Т на множестве Н положим FA \J{ge 0(А) :(yqeQ)g\ (H(q)) " = /J. Легко проверить, что множество ТА есть клон, причем, если клон Т простой, то TQA \ н ш = т. В частности, это влечет следующее предложение. Предложение 5.5. Для любого простого вполне локального клонаТ С О(Н) и множества Н С Н выполнено Н є invТ н Н є invg ТА Если клон Т локально квазитривиальный, то то же самое верно, если вместо ТА взять клон ТА П V(A). Нам потребуется еще одно обобщение. Пусть n, s есть любые натуральные числа и Т есть клон на множестве Н. Положим Щ а) — {Mi /in-i Є Яп: (VgG Q){/i0(g),/ii(g),...,/in-i(g)} s}; TT U1 s. І І ТТП H«s) - U %» T{{s)) T \ H?s). Если клон T локально квазитривиальный, то множество T((s)) в естественном смысле замкнуто относительно композиции. Для каждого натурального числа s и вполне локального локально квазитривиального клона Т на множестве Н положим